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  <mika> 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