Semigroup and metric characteristics of locally primitive matrices and graphs

V. M. Fomichev

Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 2, pp. 124-143

Résumé

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.

Détail

Keywords: mixing matrix, locally primitive matrix, exponent of a matrix, cyclic matrix semigroup.
Mots-clés : primitive matrix