<s>[INST] 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?
 [/INST] 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$.
</s>