Eigenvalues of Circulant matrices

  • #1
102
12

Main Question or Discussion Point

Hi,
I am studying about circulant matrices, and I have seen that one of the properties of such matrices is the eigenvalues which some combinations of roots of unity.

I am trying to understand why it is like that. In all the places I have searched they just show that it is true, but I would like to know how(obviously it's not a guess...).

Thank you.
 

Answers and Replies

  • #2
StoneTemplePython
Science Advisor
Gold Member
2019 Award
1,153
560
It isn't clear what "how" means in this context but I'll give this a shot.

I assume all matrices are ##n## x## n##

note that any circulant matrix ##\mathbf S## can be written as follows

##\mathbf S = \sum_{k=0}^{n-1} s_k \mathbf P^k##
(you should check this for yourself)

where

##\mathbf P = \begin{bmatrix}
0 & 0 &0 & \cdots &0 & 1\\
1 & 0 &0 &\cdots &0 & 0\\
0 & 1 &0 & \cdots &0 &0 \\
0 & 0 &1& \cdots &0 & 0\\
0 & 0 &0& \ddots &0 & 0\\
0 & 0 &0& \cdots &1 & 0
\end{bmatrix}##

##\mathbf P## can be interpreted as a permutation matrix (that is associated with a connected graph). This means it is unitarily diagonalizable and all of its eigenvalues have magnitude 1.

##\mathbf P## can further be interpreted as a Companion matrix associated with ##p(x) = x^n - 1##, and hence its eigenvalues are nth roots of unity. Hence ##\mathbf P= \mathbf F \mathbf \Lambda \mathbf F^* ##, where ##\mathbf \Lambda## is a diagonal matrix that contains nth roots of unity, and ##\mathbf F## is the unitary version of the Vandermonde matrix, i.e. discrete Fourier transform matrix.

As an aside, it maybe worth pointing out that Companion matrices are a bit 'brittle' and are always defective unless all of their eigenvalues are unique (i.e. algebraic multiplicity of 1 for each eig). But we know that this matrix cannot be defective because it is a permutation matrix (which must be unitarily diagonalizable) hence we know it has n unique roots.

The fact that ##\mathbf P## is a companion matrix associated with ##p(x) = x^n - 1##, and a permutation (read: normal) matrix, and serves as a basis for generating circulant matrices -- those three things lead to the result you're asking about.

Using all of the above we can re-write things as:

##\mathbf S = \sum_{k=0}^{n-1} s_k \mathbf P^k = \sum_{k=0}^{n-1} s_k \big(\mathbf F \mathbf \Lambda \mathbf F^*\big)^k = \sum_{k=0}^{n-1} s_k \mathbf F \mathbf \Lambda^k \mathbf F^* = \sum_{k=0}^{n-1} \mathbf F \big(s_k \mathbf \Lambda^k\big) \mathbf F^* = \mathbf F\big(\sum_{k=0}^{n-1} s_k \mathbf \Lambda^k\big) \mathbf F^*##
 
  • Like
Likes MisterX

Related Threads on Eigenvalues of Circulant matrices

  • Last Post
Replies
3
Views
9K
  • Last Post
Replies
5
Views
720
  • Last Post
Replies
3
Views
5K
  • Last Post
Replies
2
Views
3K
Replies
1
Views
3K
Replies
3
Views
2K
Replies
4
Views
775
  • Last Post
Replies
3
Views
557
  • Last Post
Replies
2
Views
7K
Top