[R] eigenvalues of a circulant matrix
Rolf Turner
rolf at math.unb.ca
Mon May 2 16:07:26 CEST 2005
I just Googled around a bit and found definitions of Toeplitz and
circulant matrices as follows:
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.)
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.
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 a matrix is in fact a unitary matrix (operator), whence its
spectrum is contained in the unit circle; its eigenvalues are indeed
n-th roots of unity.
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 at math.unb.ca
More information about the R-help
mailing list