A bound on the scrambling index of a primitive matrix using Boolean rank

作者：Akelbek Mahmud^*; Fital Sandra; Shen Jian

来源：Linear Algebra and Its Applications, 2009, 431(10): 1923-1931.

DOI：10.1016/j.laa.2009.06.031

• Scrambling index
• Primitive matrix
• Boolean rank

The scrambling index of an n x n primitive matrix A is the smallest positive integer k such that A(k)(A(t))(k) = J, where A(t) denotes the transpose of A and J denotes the n x n all ones matrix. For an m x n Boolean matrix M, its Boolean rank b(M) is the smallest positive integer b such that M = AB for some m x b Boolean matrix A and b x n Boolean matrix B. In this paper, we give an upper bound on the scrambling index of an n x n primitive matrix M in terms of its Boolean rank b(M). Furthermore we characterize all primitive matrices that achieve the upper bound. Published by Elsevier Inc.

• 出版日期2009-10-15