Re: [R] eigenvalues of a circulant matrix

From: Ted Harding <Ted.Harding_at_nessie.mcc.ac.uk>
Date: Tue 03 May 2005 - 01:37:00 EST


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@nessie.mcc.ac.uk> Fax-to-email: +44 (0)870 094 0861
Date: 02-May-05                                       Time: 16:32:27
------------------------------ XFMail ------------------------------

______________________________________________
R-help@stat.math.ethz.ch mailing list
https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html Received on Tue May 03 02:14:24 2005

This archive was generated by hypermail 2.1.8 : Fri 03 Mar 2006 - 03:31:32 EST