Geodesic
Local primitivity of matrices and graphs
Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 1, pp. 97-119 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We develop a matrix-graph approach to the estimation of the communicative properties of a system of connected objects. In particular, this approach can be applied to analyzing the mixing properties of iterative cryptographic transformations of binary vector spaces, i.e. dependence of the output block bits on the input bits. In some applied problems, the saturation of the connections between the objects corresponds to the required level if the matrix modeling the connections or its certain submatrix is positive (the graph modeling the connections or its certain subgraph is complete). The concepts of local primitivity and local exponents of a nonnegative matrix (graph) are introduced. These concepts generalize and expand the area of application as compared to the familiar concepts of primitivity and exponent. We obtain a universal criterion for the local primitivity of a digraph and both a universal bound for the local exponents and its refinements for various particular cases. The results are applied to analyzing the mixing properties of a cryptographic generator constructed on the basis of two shift registers. Tab. 2, bibliogr. 12.
Mots-clés : primitive matrix
Keywords: primitive graph, exponent, local primitivity of a matrix (graph), local exponent. 
@article{DA_2017_24_1_a5,
     author = {V. M. Fomichev and S. N. Kyazhin},
     title = {Local primitivity of matrices and graphs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {97--119},
     year = {2017},
     volume = {24},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2017_24_1_a5/}
}
TY  - JOUR
AU  - V. M. Fomichev
AU  - S. N. Kyazhin
TI  - Local primitivity of matrices and graphs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2017
SP  - 97
EP  - 119
VL  - 24
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DA_2017_24_1_a5/
LA  - ru
ID  - DA_2017_24_1_a5
ER  - 
%0 Journal Article
%A V. M. Fomichev
%A S. N. Kyazhin
%T Local primitivity of matrices and graphs
%J Diskretnyj analiz i issledovanie operacij
%D 2017
%P 97-119
%V 24
%N 1
%U http://geodesic.mathdoc.fr/item/DA_2017_24_1_a5/
%G ru
%F DA_2017_24_1_a5
V. M. Fomichev; S. N. Kyazhin. Local primitivity of matrices and graphs. Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 1, pp. 97-119. http://geodesic.mathdoc.fr/item/DA_2017_24_1_a5/

[1] K. G. Kogos, V. M. Fomichev, “Positive properties of nonnegative matrices”, Prikl. Diskretn. Mat., 2012, no. 4, 5–13 (Russian)

[2] S. N. Kyazhin, V. M. Fomichev, “On primitive sets of natural numbers”, Prikl. Diskretn. Mat., 2012, no. 2, 5–14 (Russian)

[3] S. N. Kyazhin, V. M. Fomichev, “Local primitiveness of graphs and nonnegative matrices”, Prikl. Diskretn. Mat., 2014, no. 3, 68–80 (Russian)

[4] L. Ya. Okunev, A Brief Course in Number Theory, Uchpedgiz, M., 1956, 239 pp. (Russian)

[5] V. N. Sachkov, V. E. Tarakanov, Combinatorics of nonnegative matrices, Transl. Math. Monogr., 213, AMS, Providence, 2002 | MR | Zbl

[6] Brualdi R. A., Liu B., “Generalized exponents of primitive directed graphs”, J. Graph Theory, 14 (1990), 483–499 | DOI | MR | Zbl

[7] Huang Y., Liu B., “Generalized $r$-exponents of primitive digraphs”, Taiwanese J. Math., 15:5 (2011), 1999–2012 | MR | Zbl

[8] Liu B., “Generalized exponents of Boolean matrices”, Linear Algebra Appl., 373 (2003), 169–182 | DOI | MR | Zbl

[9] Miao Z., Zhang K., “The local exponent sets of primitive digraphs”, Linear Algebra Appl., 307 (2000), 15–33 | DOI | MR | Zbl

[10] Ramírez Alfonsín J. L., The Diophantine Frobenius problem, Oxf. Lect. Ser. Math. Appl., 30, Oxf. Univ. Press, Oxford, 2005, 243 pp. | Zbl

[11] Shao J., Wang J., Li G., “Generalized primitive exponents with the complete characterization of the extremal digraphs”, Chinese J. Contemp. Math., 15:4 (1994), 317–324 | MR

[12] Shen J., Neufeld S., “Local exponents of primitive digraphs”, Linear Algebra Appl., 268 (1998), 117–129 | DOI | MR | Zbl