[R] eigenvalues of a circulant matrix

[(Ted Harding)]

On 02-May-05 Rolf Turner wrote:
> I just Googled around a bit and found definitions of Toeplitz and
> circulant matrices as follows:
> [...]
> A circulant matrix is an n x n matrix whose rows are composed of
> cyclically shifted versions of a length-n vector. For example, the
> circulant matrix on the vector (1, 2, 3, 4)  is
> 
>       4 1 2 3
>       3 4 1 2
>       2 3 4 1
>       1 2 3 4
> 
> So circulant matrices are a special case of Toeplitz matrices.
> However a circulant matrix cannot be symmetric.

I suspect the confusion may lie in what's meant by "cyclically
shifted". In Rolf's example above, each row is shifted right by 1
and the one that falls off the end is put at the beginning. This
cannot be symmetric for general values in the fist row.

However, if you shift left instead, then you get

        4 1 2 3
        1 2 3 4
        2 3 4 1
        3 4 1 2

and this *is* symmetric (and indeed will always be so, for
general values in the first row).

All the formal definitions of "circulant" which I have seen
use Rolf's definition ("shift right"). Suppose we call the
left-shifted one "anti-circulant" ("AC").

The vector (which *is* and eigenvector of a circulant matrix):

  c(1, w, w^2, ... , w^(p-1))

where w is *any* complex p-th root of unity (including 1), is
not in general an eigenvector of a pxp AC matrix.

Example:

M<-matrix(c(1,2,3,2,3,1,3,1,2),nrow=3)
M
     [,1] [,2] [,3]
[1,]    1    2    3
[2,]    2    3    1
[3,]    3    1    2

p1 <- 1 ; p2 <- (-1-sqrt(3))/2 ; p3 <- (-1+sqrt(3))/2
e1 <- c(1,p1,p1^2)
e2 <- c(1,p2,p2^2)
e3 <- c(1,p3,p3^2)

v1<-(M%*%e1)[1] ; v1
[1] 6
cbind(round(M%*%e1/v1,15), e1)
       e1
[1,] 1  1
[2,] 1  1
[3,] 1  1

v2<-(M%*%e2)[1] ; v2
[1] -0.2320508
cbind(round(M%*%e2/v2,15), e2)
                                  e2
[1,]  1.0+0.0000000i  1.0+0.0000000i
[2,] -0.5+0.8660254i -0.5-0.8660254i
[3,] -0.5-0.8660254i -0.5+0.8660254i

v3<-(M%*%e3)[1] ; v3
[1] 2.133975
cbind(round(M%*%e3/v3,15), e3)
                                  e3
[1,]  1.0+0.0000000i  1.0+0.0000000i
[2,] -0.5-0.8660254i -0.5+0.8660254i
[3,] -0.5+0.8660254i -0.5-0.8660254i

(I've out in rounding because of nasty little specks of "i"
 that keep dropping out, as in

  p2^3
  [1] 1 - 6.432571e-16i
)

So (except for e1) e2 and e3 are not eigenvectors of M
(note the switching of signs in the imaginary parts of
row 2 and in row 3).

The AC matrix, being symmetric, heas real eigenvalues and
real eigevectors, as can be easily verified using 'eigen'.

Therefore I suspect that "Globe Trotter"'s "circulant matrix"
was in fact an "anti-circulant" ("AC") matrix. However, from
the information he gave I'm not clear how to verify that
this is the case.

Hoping this helps,
Ted.


--------------------------------------------------------------------
E-Mail: (Ted Harding) <Ted.Harding at nessie.mcc.ac.uk>
Fax-to-email: +44 (0)870 094 0861
Date: 02-May-05                                       Time: 16:32:27
------------------------------ XFMail ------------------------------