# Finding the eigenvalues of the sum of circulant and diagonal matrices - What am I doing wrong?

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:

$$(\mathbf{C}+\mathbf{D})\mathbf{y}=\psi\mathbf{y}$$

(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):

$$\psi=d_m+\sum_{k=0}^{n-1}c_k\rho^k$$

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?

-

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.