No label defined (Q3974962)

[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.