Volume 25, No 2, 2018, P. 124-143

UDC 519.17
V. M. Fomichev
Semigroup and metric characteristics of locally primitive matrices and graphs

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$) | $1 \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: 10.17377/daio.2018.25.584

Vladimir M. Fomichev ^1,2,3
1. Financial University under the Government of the Russian Federation,
49 Leningradsky Ave., 125993 Moscow, Russia
2. National Research Nuclear University MEPhI,
31 Kashirskoe Highway, 115409 Moscow, Russia
3. Institute of Informatics Problems of FRC CSC RAS,
44-2 Vavilov St., 119333 Moscow, Russia
e-mail: fomichev@nm.ru

Received 3 July 2017
Revised 11 December 2017

References