Proving that $\det(A) \ne 0$ if $a_{i,i} = 0$ and $a_{i,j} = \pm 1$ for $i \neq j$

Question

Let $A$ be an $n\times n$ matrix ($n=2k$, $k \in \Bbb N^*$) such that.

$$a_{ij} = \begin{cases} \pm 1, & \text{if $i \ne j$} \\ 0, & \text{if $i=j$} \end{cases}$$

Show that $\det (A) \ne 0$.

P.S. $a_{ij}=\pm 1$ means that it can be $+1$ or $-1$ not necessarily the same for all $a_{ij}$.

My approach:

I've started with the definition of $\det A$ writing like a permutation sum but it became messy. I also tried Laplace's method but also didn't work. I also tried induction but once $\pm 1$ is aleatory it became tough to deal with.

Answer 1

Assume that $n$ is even. Consider your matrix $A$ as being a matrix with integer coefficient, and let $\mathbb{F}_2$ be the field with two elements. Then the projection $\pi:\mathbb{Z}\to \mathbb{F}_2$ induces a projection $\pi$ on the rings of matrices; let $A_2$ be the image of $A$ by this projection. Then $\det(A_2) = \pi(\det(A))$.

Now, let $B$ be the matrix defined in the same way as $A$, except that all non-zero entries are $1$ (instead of $\pm 1$). Then $\pi(B)= A_2$. Now $B$ is a circulant matrix, and we know that its determinant is $(n-1)\cdot(-1)^n$. Hence $\det(A_2)=1$, so $\det(A)$ cannot be zero (in fact, it cannot be an even number).

Note that this also shows that if $n$ is odd, then $\det(A)$ will always be an even number.

---

Added:

After seeing Omnomnomnom's answer, I realized that the matrix $A_2$ above is invertible, and is its own inverse, if $n$ is even. So there's no need to use the circulant matrix $B$ in the proof.

---

And if $n$ is odd:

The result is false if $n$ is odd. A counter-example for $n=3$ is given by the matrix $$ \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & -1 & 0 \end{pmatrix}. $$

If $n$ is any odd integer, then this counter-example generalizes: let $A$ have $1$'s everywhere, except on the diagonal, and also on the last row, where $1$ and $-1$ alternate. Then $A$ has zero determinant, since the vector $(1,1,\ldots,1,n-2)^t$ is in its kernel.

Answer 2

Without finite fields: We wish to show that $\det(A)$ is necessarily odd (which we concluded from the $\Bbb F_2$ approach), which would imply $\det(A) \neq 0$. Fix a matrix $A$ of the described pattern. Let $A^{(i,j)}$ denote the matrix in which we "flip" the sign of the $i,j$ entry. That is, $$ A^{(i,j)}_{pq} = \begin{cases} -A_{ij} & p=i,q=j\\ A_{ij} & \text{otherwise} \end{cases} $$ By applying the Laplace expansion of the determinant along the $i$th row, we see $$ \det(A) - \det(A^{(i,j)}) = 2C_{ij} $$ Where $C_{ij}$ is the cofactor associated with $i,j$. Notably, $C_{ij}$ is an integer.

So, flipping one sign won't change the parity of the derivative. Thus, is sufficient to show that the matrix $A$ whose off-diagonal entries are all $1$ has an odd determinant. But this is easy.

In particular, if $x$ is the column vector whose entries are all $1$, then we want to show that $\det(xx^T - I)$ is odd. We can do so either by considering the eigenvalues of the rank-$1$ matrix $xx^T$ or by Sylvester's determinant identity (or by row-reduction, or by observing that the matrix is circulant). Whichever way you choose, we find $\det(xx^T - I) = 1-n$, which is necessarily odd.

---

Another slick proof using finite fields (which avoids appealing to circulant matrices):

Consider the $n \times n$ matrix $B$ whose entries (from $\Bbb F_2$) are all $1$. Since $n$ is even, we find that $B^2 = nB = 0$. Since $B$ is nilpotent, its only eigenvalue is $0$ (with multiplicity $n$).

The matrix $A$ (taken modulo $2$) is given by $A = B + I$. Since $B$ has eigenvalue $0$ with multiplicity $n$, we may conclude that $A$ has eigenvalue $1$ with multiplicity $n$. Thus, $\det(A) = (1)^n = 1 \neq 0$.

Thus, we conclude that the determinant of an $A$ of the presented form is odd, hence non-zero.

---

Or, more simply: $B^2 = 0$. So, $A = B+I$ is invertible since $$ A^2 = B^2 + 2B + I = 0 + 0 +I = I $$

Answer 3

Thank you @Pierre-Guy, your solution and particularly the matrix $B$ gave me an idea.

If we write $\det A$ using congruence modulo $2$, we get that $\pm 1$ will became $1$ and then we have:

$$\det A \equiv\begin{vmatrix} 0 & 1 & 1 & ...&1 \\ 1 & 0 & 1 & ...&1 \\ \vdots & \vdots & \vdots & ...&1 \\ 1 & 1 & 1 & ...&0 \end{vmatrix}$$

and sum every horizontal line at the first we have:

$$\begin{vmatrix} 2k-1 & 2k-1 & 2k-1 & ...&2k-1 \\ 1 & 0 & 1 & ...&1 \\ \vdots & \vdots & \vdots & ...&1 \\ 1 & 1 & 1 & ...&0 \end{vmatrix}=(2k-1)\begin{vmatrix} 1 & 1 & 1 & ...&1 \\ 1 & 0 & 1 & ...&1 \\ \vdots & \vdots & \vdots & ...&1 \\ 1 & 1 & 1 & ...&0 \end{vmatrix}$$

Now if we subtract every horizontal line from the first line we get:

$$(2k-1)\begin{vmatrix} 1 & 1 & 1 & ...&1 \\ 0 & -1 & 1 & ...&1 \\ \vdots & \vdots & \vdots & ...&1 \\ 0 & 0 & 0 & ...&-1 \end{vmatrix}=(2k-1)(-1)^{(2k-1)}\equiv 1 \mod 2$$

and so the $\det A$ is a odd number and then it can't be $0$.

Answer 4

Here's an approach which connects to your original idea of writing out the definition of $\det A$ as a sum over permutations:

If you to this, you get $n!$ terms, each of which is either $+1$, $-1$ or $0$. The terms which are zero are the ones where you include at least one matrix entry from the diagonal, so they correspond exactly to the permutations $\pi$ which have at least one fixpoint (i.e., $\pi(k)=k$ for some $k$).

So the nonzero terms in the sum correspond to the fixpoint-free permutations, also known as derangements. And the number of derangements of $n$ elements, call it $a_n$, is odd if $n$ is even (and even if $n$ is odd), which is easy to prove from the recursion $$ a_1=0 ,\qquad a_n = n a_{n-1} + (-1)^n . $$ So your determinant is the sum of an odd number of $+1$ and $-1$, hence it is itself an odd number, and can't be zero.