|
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.
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{https://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{https://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
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
|
Number of views: |
This page: | 131 | Full text: | 13 | References: | 17 | First page: | 4 |
|