$4 \times 4$ Matrix $\max$ determinant is $3$

Question

I used Hadamard matrix formula with entries $0$ and $1$ and found that a $4 \times 4$ Matrix $\max$ determinant is $3$. what does that matrix look like and how do you figure it out?

Answer 1

Here is a $4\times4$ matrix of zeros and ones with determinant $-3$: $$\begin{bmatrix}0 & 1 & 1 & 1\\ 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 0\end{bmatrix}.$$ Swapping two rows gives a matrix with determinant $3.$ I got this by starting with the $5\times5$ matrix $$\begin{bmatrix}-1 & 1 & 1 & 1 & 1\\ 1 & -1 & 1 & 1 & 1\\ 1 & 1 & -1 & 1 & 1\\ 1 & 1 & 1 & -1 & 1\\ 1 & 1 & 1 & 1 & -1\end{bmatrix},$$ which has the maximum determinant, $48=3\cdot2^4,$ for $\pm1$ matrices of size $5.$ I then added the first row to rows $2$–$5,$ and divided the $4\times4$ block in the lower right by $2.$ See the discussion below for the connection between $\{0,1\}$ matrices and $\{-1,1\}$ matrices and their determinant bounds.

The $5\times5$ matrix comes from the following considerations. Maximum determinant for $\pm1$ matrices is achieved when rows are pairwise orthogonal, that is, when $MM^T=nI.$ Orthogonality of rows is not possible when $n$ is odd. It turns out that when $n\equiv1\mod 4,$ the best thing to do is to have inner product of all pairs of rows equal $1,$ which means $MM^T=(n-1)I+J,$ where $J$ is the all-ones matrix. For this to be achievable, the matrix on the right has to have perfect-square determinant, which only happens for $n$ of the form $a+(a+1)^2.$ Since $5=1+2^2,$ we are in luck. We therefore want every pair of rows to have equal entries in three column positions, and unequal entries in two. This is achieved by the matrix shown above.

Determinant bound for $\{0,1\}$ matrices. Here is the bound I think the OP had in mind. I include this discussion because one of the other answerers questioned whether the bound was tight. For an $n\times n$ matrix $M$ with elements $\pm1,$ Hadamard's determinant bound takes the form $$ \lvert\det M\rvert\le n^{n/2}. $$ If $M$ is normalized, meaning all elements in row and column $1$ equal $1$, one can obtain an $(n-1)\times(n-1)$ matrix with elements $0$ and $1$ whose determinant is related to that of $M$ by a scaling factor that depends on $n$ but not on $M.$ Since any $\{-1,1\}$ matrix can be normalized by multiplying a suitable set of rows and columns by $-1$ (which doesn't affect the magnitude of the determinant), the maximal determinant problem for $\{-1,1\}$ matrices is equivalent to that for $\{0,1\}$ matrices.

This $\{0,1\}$ matrix can be obtained as follows. Subtract row $1$ of $M$ from all subsequent rows, producing a matrix $$ \begin{bmatrix} 1 & j\\ 0 & S \end{bmatrix}, $$ where $j$ is the all-ones vector of length $n-1$, and $S$ is an $(n-1)\times(n-1)$ $\{0,-2\}$ matrix that has the same determinant as $M.$ Dividing $S$ by $-2$ gives a $\{0,1\}$ matrix whose determinant is smaller in magnitude than $\det M$ by the factor $2^{n-1}.$

For an $n\times n$ $\{0,1\}$ matrix $B,$ Hadamard's bound therefore takes the form $$\lvert\det B\rvert \le 2^{-n}(n+1)^{(n+1)/2}.$$ When $n=4$ this bound is not an integer, but the floor of the bound equals $3.$ The determinant bound for $5\times5$ $\pm1$ matrices is therefore $3\cdot2^4=48.$