# Determinant of a specific circulant matrix, $A_n$

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?

-
Have you tried eigenvalues? – Aleks Vlasev Nov 11 '11 at 2:53
– Martin Sleziak Jun 8 '15 at 7:46

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

-
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

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

-
Is there a more elementary proof? I don't know what the spectrum of a matrix is. – nullUser Nov 11 '11 at 3:44
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
@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

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

-
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

The determinant of a general circulant matrix is given by \begin{eqnarray*} \left| \begin{array} {ccccc} x_0 & x_{n-1} & \cdots & x_2 &x_1 \\ x_1 & x_0 &\cdots & x_3 & x_2\\ x_2 & x_1 & \cdots & x_4& x_3 \\ \vdots & \vdots & ~ & \vdots & \vdots \\ x_{n-2} & x_{n-3} &\cdots &x_0 & x_{n-1} \\ x_{n-1} & x_{n-2} &\cdots &x_1 & x_0 \end{array} \right| = \prod_{p=0}^{n-1} \left( x_0 + \omega^p x_1 +\cdots + \omega^{(n-1)p}x_{n-1} \right) \end{eqnarray*} where $\omega = e^{2 \pi i /n}$ is an $n$th root of unity; it satisfies the identity $\sum_{q=1}^{n-1} \omega^{qd} = -1$ for $d \neq 0$. So \begin{eqnarray*} \left| \begin{array} {ccccc} 0 & 1 & \cdots & 1 &1 \\ 1 & 0 &\cdots & 1 & 1\\ 1 & 1 & \cdots & 1& 1 \\ \vdots & \vdots & ~ & \vdots & \vdots \\ 1 & 1 &\cdots & 0 & 1\\ 1 & 1 &\cdots & 1 & 0 \end{array} \right| = (0+1+\cdots +1) \prod_{p=1}^{n-1} \left( \omega^p +\cdots + \omega^{(n-1)p} \right)= (n-1)\prod_{p=1}^{n-1} (-1)= (n-1)(-1)^{n-1} \end{eqnarray*}

-