Does a matrix $A$ of $\pm1$'s of order $11$ exist with $\det A >4000$? 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?
 A: 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$.
A: 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$).
A: 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$.
A: 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. $
