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

DOI10.1016/J.LAA.2009.06.031zbMATH Open1178.15019arXiv0910.2033OpenAlexW2108514217MaRDI QIDQ732085FDOQ732085

J. Shen, Mahmud Akelbek, Sandra Fital

Publication date: 9 October 2009

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: The scrambling index of an $nimesn$ 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 $nimesn$ all ones matrix. For an $mimesn$ Boolean matrix $M$, its {it Boolean rank} $b(M)$ is the smallest positive integer $b$ such that $M=AB$ for some $mimesb$ Boolean matrix $A$ and $bimesn$ Boolean matrix $B$. In this paper, we give an upper bound on the scrambling index of an $nimesn$ primitive matrix $M$ in terms of its Boolean rank $b(M)$. Furthermore we characterize all primitive matrices that achieve the upper bound.

Full work available at URL: https://arxiv.org/abs/0910.2033

zbMATH Keywords

scrambling indexprimitive matrixBoolean matrixBoolean rank

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Positive matrices and their generalizations; cones of matrices (15B48) Matrices of integers (15B36)

Cites Work

• Combinatorial matrix theory
• Primitive digraphs with the largest scrambling index
• Coefficients of ergodicity and the scrambling index
• Unzerlegbare, nicht negative Matrizen
• On the exponent of a primitive digraph
• A bound on the exponent of a primitive matrix using Boolean rank
• On extremal matrices of second largest exponent by Boolean rank

Cited In (14)

• The scrambling index of primitive digraphs
• Generalized scrambling indices of a primitive digraph
• Title not available (Why is that?)
• Upper bounds on scrambling index for non-primitive digraphs
• The primitive Boolean matrices with the second largest scrambling index by Boolean rank
• A bound on the exponent of a primitive matrix using Boolean rank
• Generalized competition index of primitive digraphs
• Characterization of irreducible Boolean matrices with the largest generalized competition index
• A bound on the generalized competition index of a primitive matrix using Boolean rank
• Bounds on the generalized μ-scrambling indices of primitive digraphs
• Characteristic matrix of covering and its application to Boolean matrix decomposition
• Scrambling index set of primitive digraphs
• Some bounds of the generalized \(\mu \)-scrambling indices of primitive digraphs with \(d\) loops
• Generalized competition index of an irreducible Boolean matrix

This page was built for publication: A bound on the scrambling index of a primitive matrix using Boolean rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q732085)