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.

  • I approved the conjecture for $n\le 5$ with brute force. – Peter Aug 13 '14 at 16:59
  • The maximal determinants for $(1,2)$-matrices with size n x n , $n = 2 , 3 , ...14$ seem to be $3 , 5 , 8 , 14 , 27 , 88 , 160 , 408 , 960 , 4131 , 10449 , 27459 \ and\ 74601$. – Peter Aug 13 '14 at 17:01
up vote 1 down vote accepted

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.

  • I will have to work through this long answer, but it is promising! (+1) – Peter Aug 15 '14 at 12:48
  • Thank you - sorry the answer (a partial one at that!) is long. The short version is that there are formulas for $\det(A+E)$ involving the matrix $A^c$ obtained by switching 1's and 0's. These can be applied to show that the conjecture is true if $M > 3m - 3$, where $M$ and $m$ are the maximal 1-2 and 0-1 determinants, respectively. When that bound doesn't hold, we've seen that $A^c$ can take on different values, so the possibility is there for the conjecture to fail. I thought I should give at least some justification for my claims, though! – Hugh Denoncourt Aug 15 '14 at 18:49

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.