From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math,sci.physics Subject: Re: interesting matrix eigenvalues Date: 25 Oct 1995 19:12:16 GMT In article <46lv7g\$f9n@gap.cco.caltech.edu>, Mika Nystroem wrote: >Who can find the eigenvalues of the matrix > >0 2 1....1 >1 0 2....1 > . 0 ...1 > . . . . >2 1 1 ...0 I assume this is a _circulant_ matrix: a_{i,j}=c(i-j), in your case with c(i)=1 except c(0)=0, c(1)=2. For a circulant matrix it's a snap to write down eigenvectors: let w be any n-th root of 1; then the vector v=( 1, w, w^2, ..., w^(n-1) ) has (A*v)_i = Sum a_ij v_j = Sum c(i-j)*w^(j-1) = w^(i-1) * Sum c(k)*w^k (substituting k=i-j mod n ). Thus each such v is an eigenvector, with eigenvalue Sum c(k)*w^k. There are n distinct n-th roots of 1, and the n such vectors v form a basis of C^n, so this matrix is diagonalizable, and the eigenvalues are as above. In your case, the eigenvalues are 2w + (w^2+...w^(n-1)), which if w <> 1 is = 2w + (w^n - w^2)/(w-1) = (w^2 - 2w + 1)/(w-1) = (w-1) and if w=1 is just n. You can get the characteristic polynomial f(x) easily if you really want it: f(x-1) vanishes for all nth roots of unity except x=1, and also vanishes for x=n+1, so f(x-1)=(x-(n+1))*(x^n-1)/(x-1), i.e. f(x)=(x-n)*[(x+1)^n-1]/x There are all kinds of deeper reasons why this kind of thing is possible of course but I don't see that you need to know them to answer your questions. dave