15
$\begingroup$

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.

$\endgroup$
16
  • $\begingroup$ Have you tried with the cofactor expansion by induction? $\endgroup$ Dec 20, 2016 at 12:47
  • 1
    $\begingroup$ @Euler: Yeap! When I used induction combined with Laplace! $\endgroup$
    – Arnaldo
    Dec 20, 2016 at 12:50
  • $\begingroup$ @ArnaldoNascimento Maybe you could post your solution as Answer (I'd be interested to read it) $\endgroup$
    – Surb
    Dec 20, 2016 at 12:53
  • 1
    $\begingroup$ @Alex: Please, post a proof of that! $\endgroup$
    – Arnaldo
    Dec 20, 2016 at 13:05
  • 1
    $\begingroup$ @Pierre: They can be different. That is the big problem. $\endgroup$
    – Arnaldo
    Dec 20, 2016 at 13:06

4 Answers 4

19
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thank you @Pierre, nice, +1. Your matrix $B$ gave me an idea for another proof, I wrote down it. $\endgroup$
    – Arnaldo
    Dec 20, 2016 at 13:38
  • $\begingroup$ CAUTION: You can not deduce that if it is not true for $n = 3$ it is also not true for all odd $n$. This requires a proof. $\endgroup$
    – Piquito
    Dec 20, 2016 at 14:24
  • $\begingroup$ I understand, however I think the question has been edited asking just for $n$ even after your CORRECT answer which I do not refute. I wanted only to say that it remains the possibility of the statement be true for (at least some maybe) odd $n\ne3$. $\endgroup$
    – Piquito
    Dec 20, 2016 at 14:41
  • $\begingroup$ @Piquito There, I've added a counter-example for all odd $n$ :) $\endgroup$ Dec 20, 2016 at 14:55
  • $\begingroup$ Very good. This completes your proof. $\endgroup$
    – Piquito
    Dec 20, 2016 at 15:03
8
$\begingroup$

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 $$

$\endgroup$
2
  • 2
    $\begingroup$ Come to think of it, $A^2=(B+I)^2 = I$ modulo $2$, so $A$ is invertible... $\endgroup$ Dec 20, 2016 at 13:35
  • 1
    $\begingroup$ @Pierre-GuyPlamondon well spotted! $\endgroup$ Dec 20, 2016 at 13:49
8
$\begingroup$

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$.

$\endgroup$
2
  • 1
    $\begingroup$ You could also compute this determinant by noting that $\det A = \det (\mathbf 1 \mathbf 1^T - I)$ and using the matrix-determinant lemma where $\mathbf 1$ is the vector of all $1$s. $\endgroup$
    – jld
    Apr 11, 2017 at 21:08
  • $\begingroup$ @Chaconne: nice hint! Thanks! $\endgroup$
    – Arnaldo
    Apr 11, 2017 at 21:12
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Nice,+1. Good idea. $\endgroup$
    – Arnaldo
    Dec 20, 2016 at 16:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .