Maximum determinants of complementary acyclic matrices of zeros and ones (Q1107536): Difference between revisions

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.