# Determinant of a General Circulant Matrix

## Problem 374

Let \[A=\begin{bmatrix}

a_0 & a_1 & \dots & a_{n-2} &a_{n-1} \\

a_{n-1} & a_0 & \dots & a_{n-3} & a_{n-2} \\

a_{n-2} & a_{n-1} & \dots & a_{n-4} & a_{n-3} \\

\vdots & \vdots & \dots & \vdots & \vdots \\

a_{2} & a_3 & \dots & a_{0} & a_{1}\\

a_{1} & a_2 & \dots & a_{n-1} & a_{0}

\end{bmatrix}\]
be a complex $n \times n$ matrix.

Such a matrix is called **circulant** matrix.

Then prove that the determinant of the circulant matrix $A$ is given by

\[\det(A)=\prod_{k=0}^{n-1}(a_0+a_1\zeta^k+a_2 \zeta^{2k}+\cdots+a_{n-1}\zeta^{k(n-1)}),\]
where $\zeta=e^{2 \pi i/n}$ is a primitive $n$-th root of unity.

Sponsored Links

## Proof.

Let $\omega$ be any $n$-th root of unity.

Consider the vector

\[\mathbf{v}=\begin{bmatrix}

1 \\

\omega \\

\omega^2 \\

\vdots \\

\omega^{n-1}

\end{bmatrix}.\]
We show that the vector $\mathbf{v}$ is an eigenvector of $A$.

We compute

\begin{align*}

A\mathbf{v}=\

\begin{bmatrix}

a_0 & a_1 & \dots & a_{n-2} &a_{n-1} \\

a_{n-1} & a_0 & \dots & a_{n-3} & a_{n-2} \\

a_{n-2} & a_{n-1} & \dots & a_{n-4} & a_{n-3} \\

\vdots & \vdots & \dots & \vdots & \vdots \\

a_{2} & a_3 & \dots & a_{0} & a_{1}\\

a_{1} & a_2 & \dots & a_{n-1} & a_{0}

\end{bmatrix}

\begin{bmatrix}

1 \\

\omega \\

\omega^2 \\

\vdots \\

\omega^{n-1}\\

\end{bmatrix}.

\end{align*}

The first entry of the vector $A\mathbf{v}$ is

\[a_0+a_1\omega+a_2\omega^2+\cdots a_{n-2}\omega^{n-2}+a_{n-1}\omega^{n-1}=:\lambda.\]
We define $\lambda$ to be this number.

The second entry is

\begin{align*}

&a_{n-1}+a_0\omega+\cdots+a_{n-3}\omega^{n-2}+a_{n-2}\omega^{n-1}\\

&=(a_{n-1}\omega^{n-1}+a_0+\cdots+a_{n-3}\omega^{n-3}+a_{n-2}\omega^{n-2})\omega \\

&=(a_0+\cdots+a_{n-3}\omega^{n-3}+a_{n-2}\omega^{n-2}+a_{n-1}\omega^{n-1})\omega \\

&=\lambda \omega

\end{align*}

Similarly the $i$-th entry of the vector $A\mathbf{v}$ is

\begin{align*}

&a_{n-i+1}+a_{n-i+2}\omega +\cdots+ a_{n-i}\omega^{n-1}\\

&= (a_{n-i+1}\omega^{n-i+1}+a_{n-i+2}\omega^{n-i+2} +\cdots+ a_{n-i}\omega^{n-i})\omega^{i-1}\\

&=\lambda \omega^{i-1} .

\end{align*}

Therefore we obtain

\[A\mathbf{v}=\begin{bmatrix}

\lambda \\

\lambda\omega \\

\lambda \omega^2 \\

\vdots \\

\lambda\omega^{n-1}

\end{bmatrix}=\lambda \mathbf{v}.\]

Since $\mathbf{v}$ is a nonzero vector, it follows that $\lambda$ is an eigenvalue of $A$ and $\mathbf{v}$ is an eigenvector corresponding to $\lambda$.

The above argument holds for any $n$-th root of unity $\omega$.

We take $\omega=\zeta^k$, where $k$ runs from $0$ to $n-1$.

It follows that the vector

\[\mathbf{v}_k:=\begin{bmatrix}

1 \\

\zeta^k \\

\zeta^{2k} \\

\vdots \\

\zeta^{k(n-1)}

\end{bmatrix}\]
is eigenvector corresponding to the eigenvalue

\[\lambda_k:=a_0+a_1\zeta^k+a_2\zeta^{2k}+\cdots a_{n-2}\zeta^{k(n-2)}+a_{n-1}\zeta^{k(n-1)}\]
for each $k=0,1, \dots, n-1$.

We claim that the vectors $\mathbf{v}_k$ are linearly independent.

To see this, form a matrix whose column vectors are these vectors. That is, we consider

\[B=\begin{bmatrix}

1& 1 & 1 & \dots & 1 &1 \\

1&\zeta & \zeta^{2} & \dots & \zeta^{n-2} & \zeta^{n-1} \\

1&\zeta^{2} & \zeta^{4} & \dots & \zeta^{2(n-2)} & \zeta^{2(n-1)} \\

1& \zeta^{3} & \zeta^{6} & \dots & \zeta^{3(n-2)} & \zeta^{3(n-1)} \\

\vdots& \vdots & \vdots & \dots & \vdots & \vdots \\

1& \zeta^{n-1} & \zeta^{2(n-1)} & \dots & \zeta^{(n-1)(n-2)} &\zeta^{(n-1)(n-1)}

\end{bmatrix}.\]

This is the Vandermonde matrix and its determinant is

\[\det(B)=\prod_{i < j }(\zeta^j-\zeta^i)\neq 0.\]
Thus, the matrix $B$ is nonsingular, hence its column vectors are linearly independent.
It follows that $\lambda_k$, $k=0, 1, \dots, n$ are all the eigenvalues of $A$.
Since the determinant is the product of all the eigenvalues of $A$, we have
\begin{align*}
\det(A)&=\prod_{k=0}^{n-1}\lambda_k\\
&=\prod_{k=0}^{n-1}(a_0+a_1\zeta^k+a_2 \zeta^{2k}+\cdots+a_{n-1}\zeta^{k(n-1)}),
\end{align*}
as required. This completes the proof.

Add to solve later

Sponsored Links

Kindly clarify why the matrix B is taken as (n-1)X(n-1)? It seems that a column of 1at the beginning and the actual second row is missing.

Dear Parthasarathi Mukhopadhyay,

Thank you for pointing out this. That was a typo and I modified it. Thank you!!

Respected Doctor,

I don’t think the second entry you computed for “Av” vector is right, because when you take ‘w’ common then the a_n_1 term should be multiplied with just w instead of w^n-1

Dear Zubair,

Thank you for the comment. I’m not exactly sure what you suggested.

Do you ask why we have $\omega^{n-1]$ in front of $a_{n-1}$? in the following computation?

====================================================

$\begin{align*}

&a_{n-1}+a_0\omega+\cdots+a_{n-3}\omega^{n-2}+a_{n-2}\omega^{n-1}\\

&=(a_{n-1}\omega^{n-1}+a_0+\cdots+a_{n-3}\omega^{n-3}+a_{n-2}\omega^{n-2})\omega \\

&=(a_0+\cdots+a_{n-3}\omega^{n-3}+a_{n-2}\omega^{n-2}+a_{n-1}\omega^{n-1})\omega \\

&=\lambda \omega

\end{align*}$

====================================================

This is because we have $\omega^n=1$ since $\omega$ is an $n$-th root of unity.

Yes! exactly I was asking this qustion.

Thankyou so much I got your point.

Let $p(x) = \sum_{i=0}^{n-1} a_i x^i,$ and note that $A=p(X),$ where $X$ is (the transpose of) the companion matrix of $t^n-1.$ The result then follows from the fact that if $\lambda$ is an eigenvalue of $M,$ then $q(\lambda)$ is an eigenvalue of $q(M)$ for polynomial (in fact, analytic) functions $q.$