If $A$ Is invertible $n\times n$ matrix which is made of only 1's and -1's, then $|\det(A)| \geq 2^{n-1}$.

Question

How do I prove what's written in the title (By saying "made of 1's and -1's" I mean that A contains only the numbers 1 and -1)? I tried using gauss elimination but I don't see how it helps me, and I have no other idea. If any of you could help me or at least give me a hint, It will help me a lot. Thanks!

Answer 1

Hint: Gaussian elimination is definitely (one of) the right way(s) to go. Think about what happens when you've gotten your matrix into upper-triangular form. Can you get $n-1$ factors of $2$ to pop out anywhere and still get the determinant of an integer matrix? Here's a (simple) example:

$$\begin{vmatrix} 1 & 1 & 1 \\ 1 & -1 & 1 \\ -1 & 1 & 1 \end{vmatrix}=\begin{vmatrix} 1 & 1 & 1 \\ 0 & -2 & 0 \\ 0 & 2 & 2 \end{vmatrix}=\begin{vmatrix} 1 & 1 & 1 \\ 0 & -2 & 0 \\ 0 & 0 & 2 \end{vmatrix}=2^2\begin{vmatrix} 1 & 1 & 1 \\ 0 & -1 & 0 \\ 0 & 0 & 1 \end{vmatrix}.$$

Answer 2

Let $A$ be a matrix with entries $\pm 1$ of size $n>1$. The case $n=1$ is immediate.
We are going to transform $A$ in two steps, without altering $\,|\!\det A|\,$:

(1) Take the first column and the first row of $A$ to define diagonal matrices
$C=a_{11}\cdot\operatorname{diag}(a_{11},-a_{21},\dots,-a_{n1})\:$ and $\:R=\operatorname{diag}(a_{11},a_{12},\dots,a_{1n})\,$.
Then $|\!\det C|=|\!\det R|=1$, and multiplying $A$ from the left and the right yields $$CAR\;=\;\begin{pmatrix} 1&1&\cdots &1\\ -1\\ \vdots &&B\\ -1 \end{pmatrix}$$ where $B\,$ is a submatrix of size $n-1$ with entries from {$\pm 1\}$.

(2) Now let's add the first row in the $CAR\,$ to all the other rows to obtain $$\begin{vmatrix} 1&1&\cdots &1\\ -1\\ \vdots &&B\\ -1 \end{vmatrix} \quad=\quad \begin{vmatrix} 1&1&\cdots &1\\ 0\\ \vdots &&2\cdot B'\\ 0 \end{vmatrix}$$ and $B'$ has entries in $\{1,0\}$. Furthermore, $B'$ is singular iff $A$ is singular (also true if $n=2$).

Reaping the fruit of the preceding steps one has $$\begin{align}|\!\det A|&\;=\;|\!\det(CAR)|\;=\;2^{n-1}\,|\!\det B'|\\[2ex] &\;\geqslant\;2^{n-1},\end{align}$$ as claimed for non-singular $A$.