Skip to main content
Springer Nature Link
Log in

Primitivity and Local Primitivity of Digraphs and Nonnegative Matrices

  • Published:
Journal of Applied and Industrial Mathematics Aims and scope Submit manuscript

Abstract

The article surveys the main results on the primitivity and local primitivity of digraphs and matrices from the inception of this research area in 1912 by now. We review the universal and special criteria for primitivity and local primitivity as well as universal and special bounds on the exponents and local exponents of digraphs and matrices. We describe some cryptographic applications of this mathematical apparatus for analyzing the mixing properties of block ciphers and keystream generators. The new promising research directions are formulated in the study of primitivity and local primitivity of digraphs and matrices.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ya. E. Avezova, “On Primitivity of Some Sets of Shift Registers Mixing Digraphs,” Prikl. Diskretn. Mat. Prilozh. No. 10, 60–62 (2017).

    Article  Google Scholar 

  2. Ya. E. Avezova and V. M. Fomichev, “Combinatorial Properties of Rectangular 0, 1-Matrix Systems,” Prikl. Diskretn.Mat. No. 2, 5–11 (2014).

    Google Scholar 

  3. Ya. E. Avezova and V. M. Fomichev, “Conditions of Primitivity and Exponent Bounds for Sets of Digraphs,” Prikl. Diskretn.Mat. No. 35, 89–101 (2017).

    Article  Google Scholar 

  4. Yu. A. Al’pin and V. S. Al’pina, “Combinatorial Properties of Irreducible Semigroups of Nonnegative Matrices,” Zap. Nauchn. Semin. POMI 405, 13–23 (2012) [J.Math. Sci. 191 (1), 4–9 (2013)].

    MATH  Google Scholar 

  5. A. S. Voynov, “Multidimensional Equations of Self-Similarity and Applications,” Doctoral Dissertation in Mathematical Physics (Moskov. Gos. Univ., Moscow, 2016).

    Google Scholar 

  6. A. M. Dorokhova and V. M. Fomichev, “Improvement of Exponent Estimates forMixing Graphs of Bijective Shift Registers over a Set of Binary Vectors,” Prikl. Diskretn.Mat. No. 1, 77–83 (2014).

    Google Scholar 

  7. A. V. Knyazev, “Estimates for Extreme Values of Principal Metric Characteristics of Pseudosymmetrical Graphs,” Doctoral Dissertation inMathematical Physics (Vychisl. Tsentr RAN, Moscow, 2002).

    Google Scholar 

  8. A. M. Koreneva and V. M. Fomichev, “Mixing Properties of Modified Additive Generators,” Diskretn. Anal. Issled. Oper. 24 (2), 32–52 (2017) [J. Appl. Indust. Math. 11 (2), 215–226 (2017)].

    MATH  Google Scholar 

  9. S. N. Kyazhin, “On Adaptation of Digraph Local Primitiveness Conditions and Local Exponent Estimations,” Prikl. Diskretn.Mat. No. 4, 81–98 (2016).

    Article  MathSciNet  Google Scholar 

  10. S. N. Kyazhin and V. M. Fomichev, “Local Primitiveness of Graphs and Nonnegative Matrices,” Prikl. Diskretn.Mat. No. 3, 68–80 (2014).

    Google Scholar 

  11. S. N. Kyazhin and V. M. Fomichev, “On Local Exponents of the Mixing Graphs for the Functions Realized by A5/1 Type Algorithms,” Prikl. Diskretn.Mat. Prilozh. No. 8, 11–13 (2015).

    Article  Google Scholar 

  12. S. N. Kyazhin and V. M. Fomichev, “Mixing Properties of 2-Cascade Generators,” Prikl. Diskretn. Mat. Prilozh. No. 9, 60–62 (2016).

    Article  Google Scholar 

  13. V. N. Sachkov, “Probabilistic Converters and Regular Multigraphs. I,” Trudy Diskretn. Mat. 1, 227–250 (1997).

    MathSciNet  MATH  Google Scholar 

  14. V. N. Sachkov and V. E. Tarakanov, Combinatorics of Nonnegative Matrices (TVP,Moscow, 2000; AMS, Providence, 2002).

    Book  MATH  Google Scholar 

  15. V. M. Fomichev, Methods of Discrete Mathematics in Cryptology (Dialog-MIFI, Moscow, 2010) [in Russian].

    Google Scholar 

  16. V. M. Fomichev, “Properties of Paths in Graphs and Multigraphs,” Prikl. Diskretn. Mat. No. 1, 118–124 (2010).

    Google Scholar 

  17. V. M. Fomichev, “Estimates for Exponents of Primitive Graphs,” Prikl. Diskretn. Mat. No. 2, 101–112 (2011).

    Google Scholar 

  18. V. M. Fomichev, “Estimates for Exponent of Some Graphs by Means of Frobenius’s Numbers of Three Arguments,” Prikl. Diskretn.Mat. No. 2, 88–96 (2014).

    Google Scholar 

  19. V. M. Fomichev, “The New Universal Estimation for Exponents of Graphs,” Prikl. Diskretn. Mat. No. 3, 78–84 (2016).

    Article  Google Scholar 

  20. V. M. Fomichev, “Computational Complexity of theOriginal and Extended Diophantine Frobenius Problem,” Diskretn. Anal. Issled. Oper. 24 (3), 104–124 (2017) [J. Appl. Indust. Math. 11 (3), 334–346 (2017)].

    MATH  Google Scholar 

  21. V. M. Fomichev and S. N. Kyazhin, “Local Primitivity of Matrices and Graphs,” Diskretn. Anal. Issled.Oper. 24 (1), 97–119 (2017) [J. Appl. Indust.Math. 11 (1), 26–39 (2017).

    MathSciNet  MATH  Google Scholar 

  22. V. M. Fomichev and D. A. Melnikov, Cryptographic Methods of Information Security, in 2 Parts (YURAYT, Moscow, 2016) [in Russian].

    Google Scholar 

  23. R. Anderson, “On Fibonacci Keystream Generators,” in Fast Software Encryption (Proceedings of 2nd International Workshop FSE, Leuven, Belgium, December 14–16, 1994) (Springer, Heidelberg, 1995), pp. 346–352.

    Google Scholar 

  24. A. Barghi, “Exponents of Primitive Digraphs,” available at http://math.dartmouth.edu/~pw/M100W11/amir.pdf (accessed April 15, 2018).

    MATH  Google Scholar 

  25. 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).

    Article  MathSciNet  MATH  Google Scholar 

  26. T. P. Berger, M. Minier, and G. Thomas, “Extended Generalized Feistel Networks Using Matrix Representation,” in Selected Areas in Cryptography (Revised Selected Papers of 20th International Conference SAC, Burnaby, Canada, August 14–16, 2013) (Springer, Heidelberg, 2014), pp. 289–305.

    Chapter  Google Scholar 

  27. U. Blöcher and M. Dichtl, “Fish: A Fast Software Stream Cipher,” in Fast Software Encryption (Proceedings of Cambridge Security Workshop, Cambridge, UK, December 9–11, 1993) (Springer, Heidelberg, 1994), pp. 41–44.

    Google Scholar 

  28. V. D. Blondel, R. M. Jungers, and A. Olshevsky, “On Primitivity of Sets ofMatrices,” Automatica 61, 80–88 (2015).

    Article  MATH  Google Scholar 

  29. R. A. Brualdi and B. Liu, “Generalized Exponents of Primitive Directed Graphs,” J. Graph Theory 14, 483–499 (1990).

    Article  MathSciNet  MATH  Google Scholar 

  30. A. L. Dulmage and N. S. Mendelsohn, “The Exponent of a Primitive Matrix,” Can. Math. Bull. 5, 241–244 (1962).

    Article  MathSciNet  MATH  Google Scholar 

  31. A. L. Dulmage and N. S. Mendelsohn, “Gaps in the Exponent Set of PrimitiveMatrices,” Illinois J. Math. 8, 642–656 (1964).

    MathSciNet  MATH  Google Scholar 

  32. A. L. Dulmage and N. S. Mendelsohn, “Graphs and Matrices,” in Graph Theory and Theoretical Physics (Acad. Press, London, 1967), pp. 167–229.

    Google Scholar 

  33. G. Frobenius, “Über Matrizen aus nicht negativen Elementen,” Berl. Ber. 456–477 (1912).

    Google Scholar 

  34. J. C. Holladay and R. S. Varga, “On Powers of Nonnegative Matrices,” Proc. Amer. Math. Soc. 9, 631 (1958).

    Article  MathSciNet  MATH  Google Scholar 

  35. Y. Huang and B. Liu, “Generalized r-Exponents of Primitive Digraphs,” Taiwan. J.Math. 15 (5), 1999–2012 (2011).

    Article  MathSciNet  MATH  Google Scholar 

  36. M. Lewin and Y. Vitek, “A SystemofGaps in the Exponent Set of PrimitiveMatrices,” Illinois J.Math. 25 (1), 87–98 (1981).

    MathSciNet  MATH  Google Scholar 

  37. B. Liu, “Generalized Exponents of BooleanMatrices,” Linear Algebra Appl. 373, 169–182 (2003).

    Article  MathSciNet  Google Scholar 

  38. Z. Miao and K. Zhang, “The Local Exponent Sets of Primitive Digraphs,” Linear Algebra Appl. 307, 15–33 (2000).

    Article  MathSciNet  MATH  Google Scholar 

  39. S. W. Neufeld, “A Diameter Bound on the Exponent of a Primitive Directed Graph,” Linear Algebra Appl. 245, 27–47 (1996).

    Article  MathSciNet  MATH  Google Scholar 

  40. P. Perkins, “A Theorem on Regular Graphs,” Pacific J.Math. 2, 1529–1533 (1961).

    Article  MathSciNet  MATH  Google Scholar 

  41. V. Yu. Protasov and A. S. Voynov, “Sets of NonnegativeMatricesWithout PositiveProducts,” Linear Algebra Appl. 437 (3), 749–765 (2012).

    Article  MathSciNet  MATH  Google Scholar 

  42. J. L. Ramírez Alfonsín, The Diophantine Frobenius Problem (Clarendon Press, Oxford, 2005).

    Book  MATH  Google Scholar 

  43. B. Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C (Wiley, New York, 1996; Triumf, Moscow, 2002).

    MATH  Google Scholar 

  44. J. Shen and S. W. Neufeld, “Local Exponents of Primitive Digraphs,” Linear Algebra Appl. 268, 117–129 (1998).

    Article  MathSciNet  MATH  Google Scholar 

  45. T. Suzaki and K. Minematsu, “Improving the Generalized Feistel,” in Fast Software Encryption (Revised Selected Papers of 17th International Workshop FSE, Seoul, Korea, Feb. 7–10, 2010) (Springer, Heidelberg, 2010), pp. 19–39.

    Google Scholar 

  46. A. S. Voynov, “Shortest Positive Products of Nonnegative Matrices,” Linear Algebra Appl. 439 (6), 1627–1634 (2013).

    Article  MathSciNet  MATH  Google Scholar 

  47. H. Wielandt, “Unzerlegbare, nicht negative Matrizen,” Math. Z. 52, 642–648 (1950).

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Financial University under the Government of the Russian Federation, Leningradskii pr. 49, Moscow, 125993, Russia

    V. M. Fomichev

  2. National Research Nuclear University MEPhI, Kashirskoe sh. 31, Moscow, 115409, Russia

    V. M. Fomichev, Ya. E. Avezova, A. M. Koreneva & S. N. Kyazhin

  3. Institute of Informatics Problems, ul. Vavilova 44, korp. 2, Moscow, 119333, Russia

    V. M. Fomichev

Authors
  1. V. M. Fomichev
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ya. E. Avezova
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. A. M. Koreneva
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. S. N. Kyazhin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to V. M. Fomichev.

Additional information

Original Russian Text © V.M. Fomichev, Ya.E. Avezova, A.M. Koreneva, S.N. Kyazhin, 2018, published in Diskretnyi Analiz i Issledovanie Operatsii, 2018, Vol. 25, No. 3, pp. 95–125.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Fomichev, V.M., Avezova, Y.E., Koreneva, A.M. et al. Primitivity and Local Primitivity of Digraphs and Nonnegative Matrices. J. Appl. Ind. Math. 12, 453–469 (2018). https://doi.org/10.1134/S1990478918030067

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1134/S1990478918030067

Keywords

Search

Navigation