The Boolean pivot operation, M-matrices, and reducible matrices

DOI10.1016/0024-3795(93)90210-FMaRDI QIDQ2365720zbMATH OpenOpenAlexFDO

Authors Hannu Väliaho

Publication date 29 June 1993

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

Full work available at URL https://doi.org/10.1016/0024-3795(93)90210-f

zbMATH Keywords

\(M\)-matricesBoolean block matricesBoolean matrixBoolean pivot operationdigraphirreducibilityreducibility

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Directed graphs (digraphs), tournaments (05C20) Boolean algebras (Boolean rings) (06E99) Positive matrices and their generalizations; cones of matrices (15B48) Hermitian, skew-Hermitian, and related matrices (15B57)

Review text

The concept of Boolean pivot operation is introduced and its properties are investigated. Some criteria for irreducibility of Boolean block matrices and necessary condition for reducibility of a Boolean (or real) matrix are derived, with the aid of Boolean pivot operations. A condensed form of Wallshall's algorithm for testing whether a Boolean matrix is irreducible is given. A close connection between Boolean matrices and \(M\)-matrices is established: they have the same zero pattern before and after pivoting. A flexible algorithm for excluding and including vertices in a digraph while retaining the original connection between the vertices of the current digraph is given. Finally, two results by \textit{R. L. Smith} [Linear Algebra Appl. 106, 219-231 (1988; Zbl 0652.15017)] on irreducibility of real block matrices are corrected.

Recommendations

• Transitive reduction of a rectangular Boolean matrix
• scientific article; zbMATH DE number 123953
• Two conjectures on the index of convergence of an irreducible Boolean matrix
• Generalized index of Boolean matrices.
• scientific article; zbMATH DE number 2108319

Cites work

• A combinatorial approach to convex quadratic programming
• A generalization of N-matrices
• A polynomial algorithm for testing the nonnegativity of principal minors of Z-matrices
• A polynomial-time test for M-matrices
• A Theorem on Boolean Matrices
• A unified approach to one-parametric general quadratic programming
• Depth-First Search and Linear Graph Algorithms
• scientific article; zbMATH DE number 3839870 (Why is no real title available?)
• scientific article; zbMATH DE number 4109935 (Why is no real title available?)
• scientific article; zbMATH DE number 3760340 (Why is no real title available?)
• scientific article; zbMATH DE number 3779513 (Why is no real title available?)
• scientific article; zbMATH DE number 3432469 (Why is no real title available?)
• Some notes on Z-matrices
• The general quadratic optimization problem
• Updating the Inverse of a Matrix

Cited in

(1)

• Transitive reduction of a rectangular Boolean matrix

This page was built for publication: The Boolean pivot operation, \(M\)-matrices, and reducible matrices

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