Is det(A) maximal, if det(A+E) is maximal?

125 Views Asked by At

Let A be a binary matrix of size n x n and E be the matrix of the same size with all entries $1$.

Proof or disproof :

If det(A+E) has the maximal possible value, then det(A) also has the maximal possible value.

The converse is not true :

$$\pmatrix{1&1&2&2&1&2\\2&1&1&2&1&1\\1&2&1&2&1&2\\2&2&2&1&1&1\\2&1&1&1&2&2\\1&2&2&2&2&1}$$

has determinant 26 and subtracting 1 from any element yields a matrix with determinant 9, the maximal possible determinant for binary matrices of size 6 x 6. However, there is a $(1,2)$-matrix with size 6 x 6 and determinant 27 :

$$\pmatrix{1&2&2&1&2&1\\1&1&2&2&1&2\\2&1&1&1&2&2\\2&2&1&1&1&2\\2&1&2&2&1&1\\1&2&1&2&2&1}$$

If the conjecture is true, it makes the search for $(1,2)$-matrices with maximal possible determinant easier because it would suffice to calculate the determinant of A+E for every binary matrix A with maximal possible determinant.

I asked a similar question (maximal determinant for matrices with entries $1$ and $n$) and someone claimed that the problem would be equivalent to the problem for $(0,1)$-matrices, but as my counterexample shows, this is not the case.

1

There are 1 best solutions below

2
On BEST ANSWER

Your conjecture appears to be true for $n \leq 6$ and $n = 10$, and is true for any $n$ where the maximal determinants satisfy a certain inequality. However, this inequality does not hold for all $n$.

Denote the vector of all 1's by $\vec{1}$ and the column vectors of a fixed binary matrix $A$ by $\vec{a_i}$. Let $A_i$ be the matrix obtained by replacing the $i$-th column of $A$ by $\vec{1}$. Since the determinant is a multilinear function on the columns of $A$, we have $$\text{det}(A + E) = \text{det}(A) + \sum_{i=1}^n \text{det}(A_i).$$

The full multilinear expansion of $\text{det}\left(\vec{a_1} + \vec{1}, \vec{a_2} + \vec{1}, \ldots, \vec{a_n} + \vec{1}\right)$ has $2^n$ terms, but those terms with 2 or more columns of the vector $\vec{1}$ vanish. Your counterexample shows that the summation on the right hand side is different for different 0-1 matrices of maximal determinant. We can obtain more constraints by applying multilinearity to the complement of $A$.

Let $A^c = E - A$ be the complement matrix obtained by switching 1's and 0's. By multilinearity, $$\det(A^c) = (-1)^n \left[ \det(A) - \sum_{i=1}^n \det(A_i) \right].$$ As long as $\sum_{i=1}^n \det(A_i) \geq \det(A)$, or equivalently $\det(A + E) \geq 2 \det(A)$, we have $(-1)^{n+1} \det(A^c) = |\det(A^c)|$. This appears to be true for the matrices under consideration, those near the maximal determinant, so I will assume this throughout instead of breaking into cases based on the parity of $n$. Combining the equations, we have $$\det(A + E) = 2 \det(A) + |\det(A^c)|.$$

Now your counterexample shows that $\det(A^c)$ can be different for different 0-1 matrices of maximal determinant.

Let $M$ be the maximal determinant for $n \times n$ 1-2 matrices and $m$ be the maximal determinant for the corresponding 0-1 matrices. Suppose $\det(A + E) = M$ and $\det(A) < m$. We claim and later justify that $|\det(A^c)| \leq \det(A)$, which implies $M \leq 3m - 3a$, for some $a > 0$. Whenever $M > 3m - 3$, this produces a contradiction and the conjecture is true. Note that $M > 3m - 3$ ensures $\det(A+E) > 2\det(A)$ so long as $m \geq 3$. We conclude: $$M > 3m - 3 \implies \text{ the conjecture is true.}$$

By OEIS A003432, if your numbers are correct, this means the conjecture is true for $n = 4,5,6, \text{ and } 10$, but it may not be true for $n=7$. For $n = 7$, where $M = 88$ and $m = 32$ there can't be 0-1 matrices with determinant 31 whose complement has determinant 26 nor any 0-1 matrices with determinant 30 whose complement has determinant 28 for the conjecture to hold. (Apparently the complements of the determinant 32 matrices have determinant 24 or less.) More possibilities exist for those $n$ where $3m - M$ is somewhat large. I suspect the conjecture is false.

Finally, we justify the claim that $|\det(A^c)| \leq \det(A)$ whenever $A + E$ is of maximal determinant. As before, we assume that $\det(A+E) \geq 2\det(A)$ whenever $A+E$ has maximal determinant. Let $(A+E)^c$ be the matrix obtained by switching 1's and 2's. This is the matrix $2E - A$. Applying multilinearity and combining with previous equations, we find that $$\det(A+E) - |\det\left((A+E)^c\right)| = \det(A) - |\det(A^c)|.$$

Thus, if $\det(A+E)$ is maximal for 1-2 matrices, then $|\det(A^c)|$ is not larger than $\det(A)$, for otherwise, we have $|\det\left((A+E)^c\right)| > \det(A+E)$, contradicting maximality.