×

Semigroup and metric characteristics of locally primitive matrices and graphs. (Russian, English) Zbl 1413.05228

Diskretn. Anal. Issled. Oper. 25, No. 2, 124-143 (2018); translation in J. Appl. Ind. Math. 12, No. 2, 243-254 (2018).
Summary: 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\leq i,j\leq 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\leq k\), \(r\leq 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.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C20 Directed graphs (digraphs), tournaments

Software:

Lilliput
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. N. Kyazhin and V. M. Fomichev, “Local Primitiveness of Graphs and Nonnegative Matrices,” Prikl. Diskretn. Mat. No. 3, 68-80 (2014). · Zbl 07310262
[2] V. M. Fomichev, “On Characteristics of Local Primitive Matrices and Digraphs,” Prikl. Diskretn. Mat. Prilozh. No. 10, 96-99 (2017). · doi:10.17223/2226308X/10/39
[3] Fomichev, V. M.; Zadorozhnyi, D. I.; Koreneva, A. M.; Lolich, D. M.; Yuzbashev, A. V., On Algorithmic Implementation of s-Boxes (2017)
[4] V. M. Fomichev and S. N. Kyazhin, “Local Primitivity ofMatrices and Graphs,” Diskretn. Anal. Issled.Oper. 24 (1), 97-119 (2017) [J. Appl. Indust.Math. 11 (1), 26-39 (2017)]. · Zbl 1374.05150
[5] V. M. Fomichev and D. A. Melnikov, Cryptographic Methods of Information Security, Part 1: Mathematical Aspects (YURAIT, Moscow, 2016) [in Russian].
[6] T. P. Berger, J. Francq, M. Minier, and G. Thomas, “Extended Generalized Feistel Networks Using Matrix Representation to Propose a New Lightweight Block Cipher: Lilliput,” IEEE Trans. Comput. 65 (7), 2074-2089 (2016). · Zbl 1360.94296 · doi:10.1109/TC.2015.2468218
[7] Berger, T. P.; Minier, M.; Thomas, G., Extended Generalized Feistel Networks UsingMatrix Representation (2014), Heidelberg
[8] R. A. Brualdi and B. Liu, “Generalized Exponents of Primitive Directed Graphs,” J. Graph Theory 14, 483-499 (1990). · Zbl 0714.05028 · doi:10.1002/jgt.3190140413
[9] Y. Huang and B. Liu, “Generalized r-Exponents of Primitive Digraphs,” Taiwan. J.Math. 15 (5), 1999-2012 (2011). · Zbl 1234.05152 · doi:10.11650/twjm/1500406419
[10] B. Liu, “Generalized Exponents of BooleanMatrices,” Linear Algebra Appl. 373, 169-182 (2003). · Zbl 1026.05050 · doi:10.1016/S0024-3795(02)00714-0
[11] Z. Miao and K. Zhang, “The Local Exponent Sets of Primitive Digraphs,” Linear Algebra Appl. 307, 15-33 (2000). · Zbl 0991.05073 · doi:10.1016/S0024-3795(99)00255-4
[12] J. Shen and S. Neufeld, “Local Exponents of Primitive Digraphs,” Linear Algebra Appl. 268, 117-129 (1998). · Zbl 0886.05075 · doi:10.1016/S0024-3795(97)00036-0
[13] Suzaki, T.; Minematsu, K., Improving the Generalized Feistel (2010), Heidelberg
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.