Structural indices of combinatorial matrix—the systematization of combinatorial matrix indices

Abstract

The index theory of combinatorial matrix is the central research of combinatorial matrix theory. Combinatorial matrix index theory not only has important theoretical value, but also has a wide range of practical applications in many aspects, e.g., computer science, ergodic theory, communications theory, sociology and economics. In this paper, we summarize a number of classic indices of combinatorial matrix, and adopt a unified view to sum them up as structural indices of combinatorial matrix. This theoretical system opens up a new field for the research of index theory.

Keywords

Combinatorial matrix / nonnegative matrix / (generalized) sign pattern matrix / structural index

References

[1] Akelbek M., Fital, S. , Shen, J. . A bound on the scrambling index of a primitive matrix using Boolean rank. Linear Algebra Appl. 2009; 431(10): 1923–1931

[2] Akelbek M. , Kirkland, S. . Primitive digraphs with the largest scrambling index. Linear Algebra Appl. 2009; 430(4): 1099–1110

[3] Akelbek M. , Kirkland, S. . Coefficients of ergodicity and the scrambling index. Linear Algebra Appl. 2009; 430(4): 1111–1130

[4] Bondy, J.A. and Murty, U.S.R., Graph Theory With Applications, London: Macmillan Press Ltd., 1976

[5] Brualdi R.A. , Liu, B.L. . Generalized exponents of primitive directed graphs. J. Graph Theory 1990; 14(4): 483–499

[6] Brualdi R.A. , Liu, B.L. . Hall exponents of Boolean matrices. Czech. Math. J. 1990; 40(4): 659–670

[7] Brualdi R.A. , Liu, B.L. . Fully indecomposable exponents of primitive matrices. Proc. Amer. Math. Soc. 1991; 112(4): 1193–1201

[8] Brualdi, R.A. and Ryser, H.J., Combinatorial Matrix Theory, Cambridge: Cambridge Univ. Press, 1991

[9] Chao C.Y. . On a conjecture of the semigroup of fully indecomposable relations. Czech. Math. J. 1977; 27(4): 591–597

[10] Chao C.Y. , Zhang, M.C. . On the semigroup of fully indecomposable relations. Czech. Math. J. 1983; 33(2): 314–319

[11] Chen S.X. , Liu, B.L. . The scrambling index of symmetric primitive matrices. Linear Algebra Appl. 2010; 433(6): 1110–1126

[12] Chen X. , Zhang, K.M. . The upper bounds of the generalized maximum density index of irreducible Boolean matrices. Linear Algebra Appl. 1997; 256: 75–93

[13] Cho, H.H. and Kim, H.K., Competition indices of digraphs, In: Proceedings of Workshop in Combinatorics, 2004, 99: 96−107

[14] Cho H.H., Kim, S.R. , Nam, Y. . The m-step competition graph of a digraph. Discrete Appl. Math. 2000; 105(1-3): 115–127

[15] Dalmage, A.L. and Mendelsohn, N.S., Graphs and Matrices, Graph Theory and Theoretical Physics (Harary, F. ed.), New York: Academic Press, 1967, 167−277

[16] Frobenius G. . Über Matrizen aus nicht negativen Elementen. S. B. K. Preuss. Akad. Wiss. 1912; 23: 456–477

[17] Heap B.R. , Lynn, M.S. . The structure of powers of nonnegative matrices I: The index of convergence. SIAM J. Appl. Math. 1966; 14(3): 610–639

[18] Heap B.R. , Lynn, M.S. . The structure of powers of nonnegative matrices II: The index of maximum density. SIAM J. Appl. Math. 1966; 14(4): 762–777

[19] Huang Y.F. , Liu, B.L. . The index of maximum ambiguous density for irreducible non-powerful sign pattern matrices. Euro. J. Combin. 2010; 31(1): 230–240

[20] Huang Y.F. , Liu, B.L. . Generalized scrambling indices of a primitive digraph. Linear Algebra Appl. 2010; 433(11-12): 1798–1808

[21] Huang Y.F. , Liu, B.L. . Generalized r-exponents of primitive digraphs. Taiwanese J. Math. 2011; 15(5): 1999–2012

[22] Huang Y.F., Liu, B.L. , Chen, S.Y. . The generalized τ-bases of primitive non-powerful signed digraphs with d loops. Graphs Combin. 2012; 28(2): 227–242

[23] Kim H.K. . Competition indices of tournaments. Bull. Korean Math. Soc. 2008; 45(2): 385–396

[24] Kim H.K. . Generalized competition index of a primitive digraph. Linear Algebra Appl. 2010; 433(1): 72–79

[25] Lewin M. . On exponent of primitive matrices. Numer. Math. 1971; 18(2): 154–161

[26] Li Q. , Liu, B.L. . Bounds on the kth multi-g base index of nearly reducible sign pattern matrices. Discrete Math. 2008; 308(21): 4846–4860

[27] Li Z.S., Hall, F. , Eschenbach, C. . On the period and base of a sign pattern matrix. Linear Algebra Appl. 1994; 212-213: 101–120

[28] Liang C.H., Liu, B.L. , Huang, Y.F. . The kth lower bases of primitive non-powerful signed digraphs. Linear Algebra Appl. 2010; 432(7): 1680–1690

[29] Liu B.L. . On fully indecomposable exponents for primitive Boolean matrices with symmetric ones. Linear Multi. Algebra 1992; 31(1-4): 131–138

[30] Liu B.L. . k-common consequents in Boolean matrices. Czech. Math. J. 1996; 46(3): 523–536

[31] Liu B.L. . On exponent of indecomposability for primitive Boolean matrices. Linear Algebra Appl. 1999; 298(1-3): 1–8

[32] Liu B.L. . Generalized exponents of Boolean matrices. Linear Algebra Appl. 2003; 373: 169–182

[33] Liu, B.L., Combinatorial Matrix Theory, 2nd ed., Beijing: Science Press, 2005 (in Chinese)

[34] Liu B.L. . The period and base of a reducible sign pattern matrix. Discrete Math. 2007; 307(23): 3031–3039

[35] Liu, B.L. and Huang, Y.F., Structural Indices of Combinatorial Matrices, Beijing: Science Press, 2015 (in Chinese)

[36] Liu, B.L. and Lai, H.J., Matrices in Combinatorics and Graph Theory, Dordrecht: Kluwer Academic Publishers, 2001

[37] Liu B.L. , Li, Q.L. . A conjecture on the strict fully indecomposable exponent of primitive matrices. Sci. China Ser. A 1995; 25(9): 920–926

[38] Liu B.L. , Zhou, B. . On the Hall exponents of Boolean matrices. Linear Multi. Algebra 1999; 46(3): 165–175

[39] Samuelson, P.A., Foundations of Economic Analysis, Cambridge: Harvard University Press, 1947

[40] Schwarz S. . On a sharp estimation in the theory of binary relations on a finite set. Czech. Math. J. 1970; 20(4): 703–714

[41] Schwarz S. . The semigroup of fully indecomposable relations and Hall relations. Czech. Math. J. 1973; 23(1): 151–163

[42] Schwarz S. . Common consequents in directed graphs. Czech. Math. J. 1985; 35(2): 212–247

[43] Shao J.Y. . The index of convergence of reducible Boolean matrices. Acta Math. Sin. 1990; 33(1): 13–28

[44] Shao J.Y. . On the indices of convergence of irreducible and nearly reducible Boolean matrices. Acta Math. Appl. Sin. 1992; 15(3): 333–344

[45] Shao J.Y. , Li, Q. . On the index of convergence of irreducible Boolean matrix. Linear Algebra Appl. 1987; 97: 185–210

[46] Shao J.Y. , Li, Q. . The index set for the class of irreducible Boolean matrices with given period. Linear Multi. Algebra 1988; 22(3): 285–303

[47] Shao J.Y. , Li, Q. . On the index of maximum density for irreducible Boolean matrices. Discrete Appl. Math. 1988; 21(2): 147–156

[48] Shao Y.L., Shen, J. , Gao, Y.B. . The kth upper bases of primitive non-powerful signed digraphs. Discrete Math. 2009; 309(9): 2682–2686

[49] Shao J.Y. , Wu, X.J. . Finiteness conditions for generalized exponents of digraphs. Chin. Ann. Math. Ser. B 1998; 19(4): 453–464

[50] Shen J., Gregory, D. , Neufeld, S. . Exponents of indecomposability. Linear Algebra Appl. 1999; 288: 229–241

[51] Stuart J., Eschenbach, C. , Kirkland, S. . Irreducible sign k-potent sign pattern matrices. Linear Algebra Appl. 1999; 294(1-3): 85–92

[52] Wang L.Q., Miao, Z.K. , Yan, C. . Local bases of primitive non-powerful signed digraphs. Discrete Math. 2009; 309(4): 748–754

[53] Wielandt H. . Unzenglebare, nicht negative Matrizen. Math. Z. 1950; 52(1): 642–648

[54] Wu X.J. , Shao, J.Y. . On the indices of convergence of irreducible Boolean matrices (I): an upper bound of Dulmage-Mendelsohn type. J. Tongji Univ. Nat. Sci. 1991; 19(3): 333–340

[55] You L.H., Liu, B.L. , Shen, J. . r-Indecomposable and r-nearly decomposable matrices. Linear Algebra Appl. 2005; 407: 105–116

[56] You L.H., Liu, M.H. , Liu, B.L. . Bounds on the Lewin number for primitive non-powerful signed digraphs. Acta Math. Appl. Sin. 2012; 35(3): 396–407

[57] You L.H., Shao, J.Y. , Shan, H.Y. . Bounds on the bases of irreducible generalized sign pattern matrices. Linear Algebra Appl. 2007; 427(2-3): 285–300

[58] You L.H. , Shen, J. . A survey on bases of sign pattern matrices. Linear Algebra Appl. 2013; 439(2): 346–357

[59] Yu G.L., Miao, Z.K. , Shu, J.L. . The base of a primitive, nonpowerful sign patterns with exactly d nonzero diagonal entries. Discrete Math. 2011; 311(6): 493–503

[60] Zhang K.M., Wang, H.D. , Hong, J.Z. . On the generalized exponent set of tournament graphs. J. Nanjing Univ. Math. Biq. 1987; 4(2): 9–14

[61] Zhou B. . A note on indecomposability of Boolean matrices. Kragujevac J. Math. 2004; 26: 133–137

[62] Zhou B. , Liu, B.L. . On a conjecture of strict Hall exponents of primitive matrices. Chinese Sci. Bull. 1996; 41(22): 1319–1320

Rights & permissions

Higher Education Press 2026