RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretn. Anal. Issled. Oper., 2018, Volume 25, Number 2, Pages 124–143 (Mi da899)  

Semigroup and metric characteristics of locally primitive matrices and graphs

V. M. Fomichevabc

a Financial University under the Government of the Russian Federation, 49 Leningradsky Ave., 125993 Moscow, Russia
b National Research Nuclear University MEPhI, 31 Kashirskoe Highway, 115409 Moscow, Russia
c Institute of Informatics Problems of FRC CSC RAS, 44-2 Vavilov St., 119333 Moscow, Russia

Abstract: The notion of local primitivity for a quadratic $0,1$-matrix of size $n\times n$ is extended to any part of the matrix which need not be a rectangular submatrix. A similar generalization is carried out for any set $B$ of pairs of initial and final vertices of the paths in an $n$-vertex digraph, $B\subseteq\{(i,j)\colon1\le i,j \le n\}$. We establish the relationship between the local $B$-exponent of a matrix (digraph) and its characteristics such as the cyclic depth and period, the number of nonprimitive matrices, and the number of nonidempotent matrices in the multiplicative semigroup of all quadratic $0,1$-matrices of order $n$, etc. We obtain a criterion of $B$-primitivity and an upper bound for the $B$-exponent. We also introduce some new metric characteristics for a locally primitive digraph $\Gamma$: the $k,r$-exporadius, the $k,r$-expocenter, where $1\le k,r\le n$, and the matex which is defined as the matrix of order $n$ of all local exponents in the digraph $\Gamma$. An example of computation of the matex is given for the $n$-vertex Wielandt digraph. Using the introduced characteristics, we propose an idea for algorithmically constructing realizable $s$-boxes (elements of round functions of block ciphers) with a relatively wide range of sizes. Tab. 2, illustr. 1, bibliogr. 13.

Keywords: mixing matrix, primitive matrix, locally primitive matrix, exponent of a matrix, cyclic matrix semigroup.

Funding Agency Grant Number
Russian Foundation for Basic Research 16-01-00226


DOI: https://doi.org/10.17377/daio.2018.25.584

Full text: PDF file (398 kB)
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2018, 12:2, 243–254

UDC: 519.17
Received: 03.07.2017
Revised: 11.12.2017

Citation: V. M. Fomichev, “Semigroup and metric characteristics of locally primitive matrices and graphs”, Diskretn. Anal. Issled. Oper., 25:2 (2018), 124–143; J. Appl. Industr. Math., 12:2 (2018), 243–254

Citation in format AMSBIB
\Bibitem{Fom18}
\by V.~M.~Fomichev
\paper Semigroup and metric characteristics of locally primitive matrices and graphs
\jour Diskretn. Anal. Issled. Oper.
\yr 2018
\vol 25
\issue 2
\pages 124--143
\mathnet{http://mi.mathnet.ru/da899}
\crossref{https://doi.org/10.17377/daio.2018.25.584}
\elib{http://elibrary.ru/item.asp?id=34875800}
\transl
\jour J. Appl. Industr. Math.
\yr 2018
\vol 12
\issue 2
\pages 243--254
\crossref{https://doi.org/10.1134/S1990478918020059}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85047802977}


Linking options:
  • http://mi.mathnet.ru/eng/da899
  • http://mi.mathnet.ru/eng/da/v25/i2/p124

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретный анализ и исследование операций
    Number of views:
    This page:84
    Full text:7
    References:17
    First page:4

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020