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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.