Does a matrix $A$ of $\pm1$'s of order $11$ exist with $\det A >4000$?

Question

How to prove or disprove that statement: there exists a square matrix of size 11 having all entries $ \pm 1$ and its determinant greater than 4000?

Answer 1

Lets walk backwards. Pick any such matrix with the extra $$A=\begin{pmatrix} 1&1&1&1&1&1&1&1&1&1&1 \\ -1&*&*&*&*&*&*&*&*&*&* \\ -1&*&*&*&*&*&*&*&*&*&* \\ -1&*&*&*&*&*&*&*&*&*&* \\ -1&*&*&*&*&*&*&*&*&*&* \\ -1&*&*&*&*&*&*&*&*&*&* \\ -1&*&*&*&*&*&*&*&*&*&* \\ -1&*&*&*&*&*&*&*&*&*&* \\ -1&*&*&*&*&*&*&*&*&*&* \\ -1&*&*&*&*&*&*&*&*&*&* \\ -1&*&*&*&*&*&*&*&*&*&* \\ \end{pmatrix}$$

Adding the first row to the others, and getting a two from the other rows we get

$$\det(A)=2^{10} \det\begin{pmatrix} 1&1&1&1&1&1&1&1&1&1&1 \\ 0&*&*&*&*&*&*&*&*&*&* \\ 0&*&*&*&*&*&*&*&*&*&* \\ 0&*&*&*&*&*&*&*&*&*&* \\ 0&*&*&*&*&*&*&*&*&*&* \\ 0&*&*&*&*&*&*&*&*&*&* \\ 0&*&*&*&*&*&*&*&*&*&* \\ 0&*&*&*&*&*&*&*&*&*&* \\ 0&*&*&*&*&*&*&*&*&*&* \\ 0&*&*&*&*&*&*&*&*&*&* \\ 0&*&*&*&*&*&*&*&*&*&* \\ \end{pmatrix}=\\2^{10} \det\begin{pmatrix} *&*&*&*&*&*&*&*&*&* \\ *&*&*&*&*&*&*&*&*&* \\ *&*&*&*&*&*&*&*&*&* \\ *&*&*&*&*&*&*&*&*&* \\ *&*&*&*&*&*&*&*&*&* \\ *&*&*&*&*&*&*&*&*&* \\ *&*&*&*&*&*&*&*&*&* \\ *&*&*&*&*&*&*&*&*&* \\ *&*&*&*&*&*&*&*&*&* \\ *&*&*&*&*&*&*&*&*&* \\ \end{pmatrix}$$

where this time every $*$ is $0$ or $1$. Note that starting from this last $0,1$ matrix you can backtrack your row reduction and get a $-1,1$ matrix.

Thus the problem reduced to the following:

Find a $10\times 10$ matrix with all entries $0,1$ so that the determinant is at least $4$, which is easy to solve. An easy way to produce such a matrix is the following:

$$B=\begin{pmatrix} 0&1&1&1&1 \\ 1&0&1&1&1 \\ 1&1&0&1&1 \\ 1&1&1&0&1 \\ 1&1&1&1&0 \\ \end{pmatrix}$$

Then $B$ is invertible, and the determinant is a multiple of $4$ [just add all the rows to the first one.]

Construct now the $0,1$ matrix

$$\begin{pmatrix} B&0 \\ 0&I_5 \\ \end{pmatrix}$$

Backtracking back to, any $1$ in $\begin{pmatrix} B&0 \\ 0&I_5 \\ \end{pmatrix}$ stays a $1$, any $0$ becomes $-1$ and you add the first row and column of $A$.

Answer 2

This is a $12\times12$ Hadamard matrix (from Neil Sloane's page).

+-----------
++-+---+++-+
+++-+---+++-
+-++-+---+++
++-++-+---++
+++-++-+---+
++++-++-+---
+-+++-++-+--
+--+++-++-+-
+---+++-++-+
++---+++-++-
+-+---+++-++

Its rows are pairwise orthogonal, and have squared length $12$, so the determinant of the whole thing is $12^6$. What is the maximum of the determinant of an $11\times11$ minor?

Well, $HH^T=12I_{12}$, so the minors all have absolute value $12^5=248832>4000$ (think cofactors in $H^{-1}=H^T/12$).

Answer 3

I found such matrix, having executed a few times the Maple code $$interface(rtablesize = 15):with(LinearAlgebra):with(Statistics): $$ $$P := Array([-1, 1]):X := RandomVariable(EmpiricalDistribution(P)): $$ $$M := convert(Matrix(11, 11, convert(Sample(X, 121), list)),rational); Determinant(M);$$ which outputed $$ \left[ \begin {array}{ccccccccccc} - 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& 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&- 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& 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&- 1& 1&- 1& 1&- 1& 1& 1&- 1& - 1&- 1\\ 1& 1&- 1& 1& 1&- 1&- 1& - 1& 1&- 1&- 1\end {array} \right] $$ and $4096. $

Answer 4

One can prove the existence as follows. Consider a matrix $A = (a_{ij})\in \mathbb R^{11 \times 11}$ whose entries are independent random variables taking the values $1$ and $-1$ with probability $\frac 1 2$. Then: $$ \mathbb E [(\det A)^2] = \mathbb E \left[ \sum_{\sigma\in S_{11}}\sum_{\tau \in S_{11}} \prod_i \prod_j a_{i \sigma(i)} a_{j\sigma_j} \right]. $$ The terms with $\sigma \neq \tau$ have zero expectation as some of the elements $a_{kl}$ appear in the product single time. The terms with $\sigma=\tau$ are equal to one. It follows that: $$ \mathbb E[ (\det A)^2 ] = \mathbb E\left[\sum_{\sigma \in S_{11}} 1\right] = 11! > 4000^2. $$ It follows that there exists a matrix with $(\det A)^2 > 4000^2$. Hence, there exists a matrix with $\det A > 4000$.