# Article

Full entry | PDF   (0.2 MB)
Keywords:
scrambling index; primitive matrix; Boolean rank
Summary:
The scrambling index of an $n\times n$ primitive Boolean matrix $A$ is the smallest positive integer $k$ such that $A^k(A^{\rm T})^k=J$, where $A^{\rm T}$ denotes the transpose of $A$ and $J$ denotes the $n\times n$ all ones matrix. For an $m\times n$ Boolean matrix $M$, its Boolean rank $b(M)$ is the smallest positive integer $b$ such that $M=AB$ for some $m\times b$ Boolean matrix $A$ and $b\times n$ Boolean matrix $B$. In 2009, M. Akelbek, S. Fital, and J. Shen gave an upper bound on the scrambling index of an $n\times n$ primitive matrix $M$ in terms of its Boolean rank $b(M)$, and they also characterized all primitive matrices that achieve the upper bound. In this paper, we characterize primitive Boolean matrices that achieve the second largest scrambling index in terms of their Boolean rank.
References:
[1] Akelbek, M., Kirkland, S.: Coefficients of ergodicity and the scrambling index. Linear Algebra Appl. 430 (2009), 1111-1130. MR 2489382 | Zbl 1167.05030
[2] Akelbek, M., Fital, S., Shen, J.: A bound on the scrambling index of a primitive matrix using Boolean rank. Linear Algebra Appl. 431 (2009), 1923-1931. MR 2567802 | Zbl 1178.15019
[3] Brualdi, R. A., Ryser, H. J.: Combinatorial Matrix Theory. Encyclopedia of Mathematics and its Applications 39 Cambridge University Press, Cambridge (1991). MR 1130611 | Zbl 0746.05002
[4] Liu, B. L., You, L. H., Yu, G. X.: On extremal matrices of second largest exponent by Boolean rank. Linear Algebra Appl. 422 (2007), 186-197. MR 2299004 | Zbl 1122.15002
[5] Shao, Y., Gao, Y.: On the second largest scrambling index of primitive matrices. Ars Comb. 113 (2014), 457-462. MR 3186489

Partner of