# Re: [R] eigenvalues of a circulant matrix

From: Rolf Turner <rolf_at_math.unb.ca>
Date: Tue 03 May 2005 - 00:07:26 EST

A Toeplitz matrix is any n x n matrix with values constant along each (top-left to lower-right) diagonal. matrix has the form

```	a_0 a_1 .   .  .   .  ... a_{n-1}
a_{-1} a_0 a_1        ... a_{n-2}
a_{-2} a_{-1} a_0 a_1 ...    .

.      .    .   .   .     .
.      .    .   .   .     .
.      .    .   .   .     .
a_{-(n-1)} a_{-(n-2)} ... a_1 a_0

```

(A Toeplitz matrix ***may*** be symmetric.)

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

The eigenvalues of the forgoing circulant matrix are 10, 2 + 2i, 2 - 2i, and 2 --- certainly not roots of unity. Bellman may have been talking about the particular (important) case of a circulant matrix where the vector from which it is constructed is a canonical basis vector e_i with a 1 in the i-th slot and zeroes elsewhere.

Such matrices are related to the unilateral shift operator on Hilbert space (which is the ``primordial'' Toeplitz operator). It arises as multiplication by z on H^2 --- the ``analytic'' elements of L^2 of the unit circle.

On (infinite dimensional) Hilbert space the unilateral shift looks like

```	0 0 0 0 0 ...
1 0 0 0 0 ...
0 1 0 0 0 ...
0 0 1 0 0 ...
. . . . . ...
. . . . . ...

```

which maps e_0 to e_1, e_1 to e_2, e_2 to e_3, ... on and on forever. On (say) 4 dimensional space we can have a unilateral shift operator/matrix

```	0 0 0 0
1 0 0 0
0 1 0 0
0 0 1 0

```

but its range is a 3 dimensional subspace (e_4 gets ``killed'').

The ``corresponding'' circulant matrix is

```	0 0 0 1
1 0 0 0
0 1 0 0
0 0 1 0

```

which is an onto mapping --- e_4 gets sent back to e_1.

I hope this clears up some of the confusion.

cheers,

```					Rolf Turner
rolf@math.unb.ca

______________________________________________
```
R-help@stat.math.ethz.ch mailing list