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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Saw this question about the eigenvalues of the sum of circulant and diagonal matrices on MO and, since I recall my prof mentioned circulant matrices and Robert Gray's book, I thought I'd give it a stab, just for fun. However, my first attempt is clearly incorrect. So, I would like to learn where I went wrong.

The question asks what happens to the eigenvalues of circulant matrix $\mathbf{C}$ when one adds diagonal matrix $\mathbf{D}$ containing positive entries. In the question $\mathbf{C}$ is also symmetric and positive-definite, in addition to being circulant.

Eigenvalues of $\mathbf{A}$ are given by the solution to $\mathbf{A}\mathbf{y}=\psi\mathbf{y}$. So, I just plug $\mathbf{C}+\mathbf{D}$ into (3.2) of page 32 of aforementioned Robert Gray's book instead of $\mathbf{C}$ and get the following:


(3.4) on the same page of that volume than becomes:

$$d_my_m+\sum_{k=0}^{n-1-m}c_ky_{k+m}+\sum_{k=n-m}^{n-1}c_ky_{k-(n-m)}=\psi y_m$$

The only change is the appearance of $d_my_m$.

Now, substituting $y_k=\rho^k$ just like in the book, and canceling $\rho^m$, I get this version of (3.5):


Choosing $\rho_m=e^{-2\pi i m/n}$, the $m$-th eigenvalue then is:

$$\psi_m=d_m+\sum_{k=0}^{n-1}c_ke^{-2\pi i mk/n}$$

However, this is a wrong answer, as evidenced by plugging an example of a symmetric positive-definite circulant matrix into Mathematica:

In[19]:= c = ToeplitzMatrix[{12, 7, -1, -1, 7}]
Out[19]= {{12, 7, -1, -1, 7}, {7, 12, 7, -1, -1}, {-1, 7, 12,   7, -1}, {-1, -1, 7, 12, 7}, {7, -1, -1, 7, 12}}
In[21]:= PositiveDefiniteMatrixQ[c]
Out[21]= True
In[22]:= Eigenvalues[c]
Out[22]= {24, 9 + 4 Sqrt[5], 9 + 4 Sqrt[5], 1/(9 + 4 Sqrt[5]), 1/( 9 + 4 Sqrt[5])}
In[26]:= N[Eigenvalues[c]]
Out[26]= {24., 17.9443, 17.9443, 0.0557281, 0.0557281}
In[23]:= d = DiagonalMatrix[{2, 3, 5, 7, 11}]
Out[23]= {{2, 0, 0, 0, 0}, {0, 3, 0, 0, 0}, {0, 0, 5, 0, 0}, {0, 0, 0,   7, 0}, {0, 0, 0, 0, 11}}
In[25]:= N[Eigenvalues[c + d]]
Out[25]= {30.9203, 24.397, 22.0476, 7.06038, 3.57478}

What did I do wrong?

share|cite|improve this question
up vote 0 down vote accepted

The equation $\psi = d_m + \sum c_k \rho^k$ can't hold because $\psi$ is a constant but $d_m$ depends on $m$ and the equality needs to hold for all $m$ in order for $\psi$ to be an eigenvalue. The eigenvectors do not take the exponential form if the $d_m$ are not all equal.

This is a good illustration of the danger of writing down equations without being explicit about the quantifiers that come with them.

share|cite|improve this answer
I see. So, is there any way to "fix" this? Is there a solution to the equation preceding my mistake? Though, if there is, you should answer the original poster on MO. – GoHokies May 31 '12 at 5:54

Your Answer


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.