Take the 2-minute tour ×
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.

I am trying to find out the spectrum (the collection of eigenvalues) with their multiplicities of the cycle graph $C_n$. Assuming that $X=\pmatrix{x_1\\x_2\\\vdots\\x_n}$ is the eigenvector, by considering $AX=\lambda X$, where $A$ is the adjacency matrix, I get the system of (non linear) equations:

$x_n+x_2=\lambda x_1\\x_1+x_3=\lambda x_2\\\cdots\\x_{n-1}+x_1=\lambda x_n$.

There seem to be no obvious way to solve this except summing which yields $\lambda=2$, provided $\sum x_i\ne 0$. However I already knew that $2$ is an eigenvalue of multiplicity $1$ as $C_n$ is a connected $2$-regular graph.

How do I go about finding the other eigenvalues?

Also in my book the solution provided magically says let $x_i=\epsilon^i$ where $\epsilon$ is a $n$-th root of unity, and proceeds from this point on. I do not understand the basis of this assumption, and if someone can explain just that I would be most obliged.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Your $C_n$ is a circulant matrix. All $n\times n$ complex circulant matrices share a common set of eigenvectors, and there is an explicit formula for their eigenvalues (see Wikipedia). In your specific case, the eigenvalues are $\omega_j+\omega_j^{n-1}$ for $j=0,1,2,\ldots,n-1$, where $\omega_j=e^{2\pi ij/n}$.

share|improve this answer
    
Thank you. Can you provide a reference to the proof? –  Shahab Mar 18 '13 at 14:40
    
@Shahab You can directly verify the formula by multiplying $C_n$ with the eigenvectors. If you really want a reference that you can cite, the one cited by Wikipedia seems OK (see chapter 3). Some books on numerical linear algebra should contain the relevant formulae and proofs too. Actually this property of circulant matrix is rather well known and I don't think it will be challenged by the referees if you mention it in your academic work. –  user1551 Mar 18 '13 at 14:55
    
You haven't answered the bit about multiplicities. Since $\cos(2\pi(n-j)/n)=\cos(2\pi j/n)$ so all eigenvalues (except 2) occur twice. If $n$ is even, will I get another eigenvalue of multiplicity one for $j=n/2$? Is this correct? –  Shahab Mar 19 '13 at 2:14
    
@Shahab Yes. For your $C_n$, only $j=0$ and $j=n/2$ (if $n$ is even) give eigenvalues of multiplicity one. All other eigenvalues have multiplicity 2. –  user1551 Mar 19 '13 at 7:39

Your Answer

 
discard

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.