Maximum determinants of complementary acyclic matrices of zeros and ones

DOI10.1016/0012-365X(86)90023-3MaRDI QIDQ1107536zbMATH OpenOpenAlexFDO

Authors Richard A. Brualdi, Ernie S. Solheid

Publication date 1986

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(86)90023-3

zbMATH Keywords

(0,1)-matrixcomplementary acyclic matrixgraph

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20)

Review text

Let \(A=\{a_{ij}\}\) be an \(n\times n\) (0,1)-matrix. There are defined two bipartite graphs \(G_ 0(A)\) and \(G_ 1(A)\) whose edges correspond respectively to the 0's and 1's of A. The matrix A is acyclic if the graph \(G_ 1(A)\) has no cycles. The matrix A is called complementary acyclic if the graph \(G_ 0(A)\) has no cycles. In this paper it is shown that for \(n\geq 5\) the largest absolute value of the determinant of an \(n\times n\) complementary acyclic (0,1)-matrix is \(\lfloor (n-1)/2\rfloor \lceil (n-1)/2\rceil.\) The determinant of an acyclic (0,1)-matrix is 0,1 or -1.

Recommendations

• Maximal determinants of combinatorial matrices
• Maximum permanents of matrices of zeros and ones
• The maximum determinant of \(\pm 1\) matrices
• Maximum determinant and permanent of sparse 0-1 matrices
• On the Spectral Radius of Complementary Acyclic Matrices of Zeros and Ones
• Computation of maximal determinants of binary circulant matrices
• scientific article; zbMATH DE number 1496419
• Maximum determinant of (0,1) matrices with certain constant row and column sums
• The acyclic matrices with a P-set of maximum size
• The maximal determinant of cocyclic (-1,1)-matrices over \(D_{2t}\)

Cites work

• Determinantenabschätzung für binäre Matrizen mit \(n\equiv 3\bmod 4\)
• Determinantenabschätzungen für binäre Matrizen. (Estimation of determinants for binary matrices)
• Determinants Whose Elements Are 0 and 1
• scientific article; zbMATH DE number 3182201 (Why is no real title available?)
• scientific article; zbMATH DE number 3747338 (Why is no real title available?)
• Maximal Determinants In Combinatorial Investigations
• On maximizing det (A\(^T\)A)
• The Hadamard Maximum Determinant Problem

Cited in

(6)

• Matrices of zeros and ones with the maximum jump number
• Determinants of certain classes of zero-one matrices with equal line sums
• Maximal determinants of combinatorial matrices
• Largest j-simplices in d-cubes: Some relatives of the Hadamard maximum determinant problem
• Maximum determinant and permanent of sparse 0-1 matrices
• On the Spectral Radius of Complementary Acyclic Matrices of Zeros and Ones

This page was built for publication: Maximum determinants of complementary acyclic matrices of zeros and ones

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