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

 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
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}