2
$\begingroup$

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?

1 Answers 1

1

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.

  • 0
    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.2012-05-31