# 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
```> 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.

```

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

```

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) ; v1
 6

cbind(round(M%*%e1/v1,15), e1)

e1
[1,] 1 1
[2,] 1 1
[3,] 1 1

v2<-(M%*%e2) ; v2
 -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) ; v3
 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 - 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