On the generalized indices of boolean matrices

DOI10.1080/03081080108818689MaRDI QIDQ2756160zbMATH OpenOpenAlexFDO

Authors Bo Zhou

Publication date 18 August 2002

Published in Linear and Multilinear Algebra (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10338.dmlcz/127759

zbMATH Keywords

Boolean matrixdirected graphgeneralized indexindex of convergenceirreducible Boolean matrix

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Matrices over special rings (quaternions, finite fields, etc.) (15B33)

Review text

Let \(A\) be an \(n\times n\) Boolean matrix and let \(i\) be an integer with \(1\leq i\leq n\). The \(i\)-th generalized index \(k(A,i)\) of \(A\) is the smallest nonnegative integer \(k\) such that \(i\) rows of \(A^k\) and \(A^{k+t}\) are equal for some \(t\geq 1\). \textit{R. A. Brualdi} and \textit{B. Liu} [J. Graph Theory 14, No. 4, 483-99 (1990; Zbl 0714.05028)] proved that \(k(A,i)\leq (n-1)(n-2)+i\) for any irreducible \(n\times n\) Boolean matrix \(A\) and \(k(A,i) \leq(n-2)(n-3)+i\) for reducible \(A\), and that these bounds are best possible. In this paper, the author characterizes completely those matrices \(A\) with the largest generalized indices. For an irreducible Boolean matrix \(A\) with period \(p\), the author obtains a new upper bound \(k(A,i)\leq (n-p)(n-2p)/p+p+i-1\). The author also generalizes the upper and lower multiexponents of Brualdi and Liu [loc. cit.] from primitive matrices to general Boolean matrices.

Recommendations

• Generalized indices of Boolean matrices
• Generalized index of Boolean matrices.
• The upper bounds of the generalized maximum density index of irreducible Boolean matrices
• The extremal matrices of generalized indices of convergence of Boolean matrices with given number of non-zero diagonal entries
• scientific article; zbMATH DE number 123953

Cites work

• Generalized exponents of primitive directed graphs
• On the set of indices of convergence for reducible matrices
• The Exponents of Strongly Connected Graphs
• The Structure of Powers of Nonnegative Matrices I. The Index of Convergence

Cited in

(17)

• The upper bounds of the generalized maximum density index of irreducible Boolean matrices
• Generalized exponents of Boolean matrices
• Generalized competition index of an irreducible Boolean matrix
• Generalized index of Boolean matrices.
• The generalized maximum density index sets of nearly decomposable matrices
• The competition index of a nearly reducible Boolean matrix
• Transitive index of digraph with \( g\) zero-strong components
• scientific article; zbMATH DE number 123953 (Why is no real title available?)
• scientific article; zbMATH DE number 509923 (Why is no real title available?)
• scientific article; zbMATH DE number 1559167 (Why is no real title available?)
• Computing indexes and periods of all Boolean matrices up to dimension n=8
• Power indices of trace zero symmetric Boolean matrices
• scientific article; zbMATH DE number 6962138 (Why is no real title available?)
• Characterization of irreducible Boolean matrices with the largest generalized competition index
• Generalized indices of Boolean matrices
• scientific article; zbMATH DE number 2188326 (Why is no real title available?)
• A bound on the generalized competition index of a primitive matrix using Boolean rank

This page was built for publication: On the generalized indices of boolean matrices

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