[R] eigenvalues of a circulant matrix

[Globe Trotter]

--- Rolf Turner <rolf at math.unb.ca> wrote:
> 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.)

Agreed. As may a circulant matrix if a_i = a_{p-i+2}

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

The eigenvalues are 4+1*omega+2*omega^2+3*omega^3.
omega=cos(2*pi*k/4)+isin(2*pi*k/4) as k ranges over 1, 2, 3, 4, so the above
holds.

 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.

No, that is not true: his result can be verified for any circulant matrix,
directly.

> 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

Many thanks and best wishes!