Do the matrices with maximum determinant always have integral values?

Question

Consider all $n$ by $n$ matrices whose elements are real values in $[0,1]$. Now for a given $n$, consider all those matrices with maximum determinant.

Are all the elements of these matrices always either exactly $0$ or $1$?

From numerical experiments this seems to be the case but I don't see how to prove it.

---

A very nice counterexample was given to my question as I didn't phrase it correctly. It should have been:

Can the maximum determinant always be reached by a matrix with only $1$ and $0$ entries?

Answer 1

Well, the answer is negative, at least in the $2\times2$ case. Counterexample: $A=\pmatrix{1& x\\ 0&1}$ for any $0<x<1$.

Answer 2

$\det A$ is a function of $a_{ij}$; $$\frac{dA}{da_{ij}}=\pm M_{ij}$$ ($M$ is a minor) (it follows from Laplace expansion of determinant). If all minor's are $0$, then $\det A = 0$. But it's not maximum obviously. Hence, maximum is on boundary, and $a_{ij} = 0$ or $1$.

Answer 3

Since every term in the determinant formula is a product of distinct elements of the matrix $A$, its Laplacian, (when the determinant is viewed as a function of $\mathbb{R}^{n \times n}$) is $0$. i.e. It is harmonic. By the maximum principle, its maximum occurs on the boundary, or it is a constant function (whereas the maximum would still be on the boundary).

The boundary of the $[0,1]^{n^2}$ hypercube are those matrices that have at least one $0$ or $1$. So you can apply this argument inductively. The determinant function restricted to each subdimensional face is still harmonic. So, the max/min occurs on the boundary of each subdimensional face's boundary, etc. All the way down to the corner points.

Alternatively, this can be viewed as a standard linear optimization problem. The optimization function is linear and the constraints are given by standard inequalities. For such a problem, the max/min always occur at vertices of the constrained region. This is relied on by the simplex method.

Answer 4

Partial result:

Suppose that a matrix $A$ has some element $a_{ij}$ not equal to $0$ or $1$.

If we find the Laplace expansion of the determinant along the $i$th row, we find $$ \det(A) = C_1 a_{i1} + \cdots + C_j a_{ij} + \cdots + C_j a_{in} $$ If $C_j > 0$, we can increase the determinant by setting $a_{ij} = 1$. If $C_j < 0$, we can increase the determinant by setting $a_{ij} = 0$.

So, your statement is false if and only if there exists a matrix with entries in $[0,1]$ and maximal determinant that has an $(n-1) \times (n-1)$ submatrix that fails to be invertible.

Answer 5

I should have asked, can the maximum always be achieved by a matrix with only 1 and 0 entries?

Yet another way to see that the answer to this question is "yes" is to note that the determinant is a multilinear function of the columns (or, equivalently, the rows) of the matrix. In particular, this implies that the determinant is also a multilinear function of the individual matrix elements — i.e. that, if we hold all the other elements constant and vary only one element $a_{ij}$ of the matrix, the determinant changes linearly as a function of that element.

Thus, if our matrix has any element strictly between 0 and 1, we can always set that element to either 0 or 1 without decreasing the determinant. By repeating this process for each element of the matrix, we obtain, for any initial matrix $A \in [0,1]^{n \times n}$, another matrix $A' \in \{0,1\}^{n \times n}$ such that $|A| \le |A'|$. In particular, if the determinant of $A$ is maximal, so is that of $A'$.