scientific article; zbMATH DE number 17634

Authors Richard A. Brualdi, Bryan L. Shader

Publication date 26 June 1992

(0,1)-matrix algorithm convertible matrix determinant digraphs incidence matrix maximal convertible matrices permanents sign- nonsingular (0,1,-1)-matrix zero-one matrices

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Determinants, permanents, traces, other special matrix functions (15A15) Hermitian, skew-Hermitian, and related matrices (15B57)

Review text

[For the entire collection see Zbl 0726.00015.] An \(n\times n\) (0,1)-matrix \(E\) is said to be convertible if it can be converted, by changing some of the 1's to -1's, into a matrix \(\hat E\), called a conversion of \(E\), such that \(\hbox{per }E=|\text{det}\hat E|\). It is the same to say that \(E\) can be obtained from a sign- nonsingular (0,1,-1)-matrix \(\hat E\) by changing the -1's into 1's. The convertible matrix \(E\) is said to be maximal if it is fully indecomposable (that is, not convertible to direct sum form by permuting rows and columns) and if no matrix obtained from \(E\) by replacing a 0 with a 1 is convertible. The authors first describe an algorithm, that avoids backtracking, for deciding when a given (0,1)-matrix \(E\) is convertible. A sequence of matrices \(A_ 0,A_ 1,\dots,A_ m\), starting with the unit matrix \(I_ n=A_ 0\) and ending with the given matrix \(E=A_ m\), is constructed according to certain rules. The success of the algorithm rests on the fact that, if \(A_ i\) and \(A_{i+1}\) are convertible, then any conversion \(\hat A_ i\) of \(A_ i\) can be extended to a conversion \(\hat A_{i+1}\) of \(A_{i+1}\). The authors also discuss in some detail the maximal convertible matrices, giving several methods for constructing them. They show (for example) that, if \(n\geq 4\), there are at least \(3n\) 1's in a maximal convertible \(n\times n\) matrix and than, if \(n\geq 5\) and equality holds, then there are exactly three 1's in each row and column. Amongst several conjectures put forward is the interesting one that the only maximal convertible matrix of order \(n\geq 5\) is the incidence matrix of the 7-point projective plane.

Recommendations

Cited in

(35)

This page was built for publication:

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