Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let

$$A_2 = \left[ \begin{array}{cc} 0 & 1\\ 1 & 0 \end{array}\right]$$

$$A_3 = \left[ \begin{array}{ccc} 0 & 1 & 1\\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{array}\right]$$

$$A_4 = \left[ \begin{array}{cccc} 0 & 1 & 1 & 1\\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0\end{array}\right]$$

and so on for $A_n$.

I was asked to calculate the determinant for $A_1, A_2, A_3, A_4$ and then guess about the determinant for $A_n$ in general. Of course the pattern is clear that

$$ \det A_n = (n-1)(-1)^{n-1} $$

but I was wondering as to what the proof of this is. I tried to be clever with cofactor expansions but I couldn't get anywhere.

Could someone explain it to me please?

share|improve this question
    
Have you tried eigenvalues? –  Aleks Vlasev Nov 11 '11 at 2:53
add comment

3 Answers

up vote 8 down vote accepted

Here is an elementary way to compute the determinant of $A_n$: Add row 2 to row 1, add row 3 to row 1, ..., and add row $n$ to row 1, we get $$\det(A_n)=\begin{vmatrix} n-1 & n-1 & n-1 & \cdots & n-1 \\ 1 & 0 & 1 &\cdots & 1 \\ 1 & 1 & 0 &\cdots & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & \ldots & 0 \\ \end{vmatrix}.$$ Next subtract column 2 by column 1, subtract column 3 by column 1, ..., subtract column $n$ by column 1, we get $$\det(A_n)=\begin{vmatrix} n-1 & 0 & 0 & \cdots & 0 \\ 1 & -1 & 0 &\cdots & 0 \\ 1 & 0 & -1 &\cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 0 & 0 & \ldots & -1 \\ \end{vmatrix}=(-1)^{n-1}(n-1).$$

share|improve this answer
    
Column operations, I forgot that those don't change the determinant! Yes this is exactly what I was looking for, excellent proof. –  nullUser Nov 11 '11 at 4:24
add comment

Observe that $A_n = E_n - I_n$ where $E_n$ is the matrix with all its entries equal to $1$ and $I_n$ is the identity matrix. So the spectrum of $A_n$ will be the same as the spectrum of $E_n$ translated by $-1$. But the spectrum of $E_n$ is one eigenvalue equal to $n$ and $n-1$ eigenvalues equal to zero. Translate this by $-1$ and you have one eigenvalue equal to $n-1$ and $n-1$ eigenvalues equal to $-1$.

share|improve this answer
1  
Is there a more elementary proof? I don't know what the spectrum of a matrix is. –  nullUser Nov 11 '11 at 3:44
2  
Why not just look up the word spectrum? Then you'll understand the answer, assuming you know the other terminology in the answer. And if not, well, it is not a bad idea to learn what the other terminology means too. The content of this answer involves basic ideas in linear algebra. –  KCd Nov 11 '11 at 3:47
1  
@Kb100 don't be intimidated by the terminology: the spectrum of a matrix is just the set of its eigenvalues. The other fact you need to understand the proof is that if $\lambda$ is an eigenvalue of a matrix $A$, then $A+\alpha I$ will have a corresponding eigenvalue equal to $\lambda+\alpha$. Prove this. Other than that, the proof is very elementary. –  Manos Nov 11 '11 at 3:51
add comment

There is a combinatorial way to view this problem, too.

An $n \times n$ $0$-$1$ matrix $M$ can be viewed as describing allowed mappings from $\{1, 2, \ldots, n\}$ to itself, where $$M_{ij} = \begin{cases} 1, & \text{ if } i \text{ can be mapped to }j; \\ 0, & \text{ otherwise.}\end{cases}$$ The permanent of $M$ gives the number of permutations of $\{1, 2, \ldots, n\}$ under the allowed mappings, and the determinant of $M$ gives the number of even permutations minus the number of odd permutations, again under the allowed mappings.

The allowed permutations $\sigma$ under the $A_n$ matrices are those for which $\sigma(i) \neq i$ for any $i$. In other words, the allowed permutations are the derangements $D_n$. Thus $$\text{perm } A_n = D_n,$$ and $$\det A_n = E_n - O_n,$$ where $E_n$ is the number of even derangements on $n$ elements, and $O_n$ is the number of odd derangements on $n$ elements.

It's a bit long to include here, but there is a combinatorial proof that $E_n - O_n = (-1)^{n-1}(n-1)$ by pairing up even and odd derangements and observing that there are $n-1$ derangements left over. See, for example, the paper "Recounting the odds of an even derangement," by Benjamin, Bennett, and Newberger (Mathematics Magazine 78(5) 2005, pp. 387-390).

share|improve this answer
    
This solution is not as nice as those already given, but I thought some people might enjoy seeing the combinatorial interpretation. –  Mike Spivey Dec 1 '11 at 6:16
    
+1 for making me aware that there are objects named Permanent and Immanant (apart from Determinant) for a matrix –  user17762 Dec 1 '11 at 6:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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