# [R] eigenvalues of a circulant matrix

Globe Trotter itsme_410 at yahoo.com
Mon May 2 20:33:54 CEST 2005

```By the way, I just noticed that eigen(X) returns eigenvectors, at least two of
which are NaN's.

Best wishes!

--- "Huntsinger, Reid" <reid_huntsinger at merck.com> wrote:

> When the matrix is symmetric and omega is not real, omega and its conjugate
> (= inverse) give the same eigenvalue, so you have a 2-dimensional
> eigenspace. R chooses a real basis of this, which is perfectly fine since
> it's not looking for circulant structure.
>
> For example,
>
> > m
>      [,1] [,2] [,3] [,4] [,5]
> [1,]    1    2    3    3    2
> [2,]    2    1    2    3    3
> [3,]    3    2    1    2    3
> [4,]    3    3    2    1    2
> [5,]    2    3    3    2    1
>
> > eigen(m)
> \$values
> [1] 11.000000 -0.381966 -0.381966 -2.618034 -2.618034
>
> \$vectors
>           [,1]      [,2]       [,3]       [,4]      [,5]
> [1,] 0.4472136  0.000000 -0.6324555  0.6324555  0.000000
> [2,] 0.4472136  0.371748  0.5116673  0.1954395  0.601501
> [3,] 0.4472136 -0.601501 -0.1954395 -0.5116673  0.371748
> [4,] 0.4472136  0.601501 -0.1954395 -0.5116673 -0.371748
> [5,] 0.4472136 -0.371748  0.5116673  0.1954395 -0.601501
>
> and you can match these columns up with the "canonical" eigenvectors
> exp(2*pi*1i*(0:4)*j/5) for j = 0,1,2,3,4. E.g.,
>
> > Im(exp(2*pi*1i*(0:4)*3/5))
> [1]  0.0000000 -0.5877853  0.9510565 -0.9510565  0.5877853
>
> which can be seen to be a scalar multiple of column 2.
>
> Reid Huntsinger
>
> Reid Huntsinger
>
> -----Original Message-----
> From: r-help-bounces at stat.math.ethz.ch
> [mailto:r-help-bounces at stat.math.ethz.ch] On Behalf Of Huntsinger, Reid
> Sent: Monday, May 02, 2005 10:43 AM
> To: 'Globe Trotter'; Rolf Turner
> Cc: r-help at stat.math.ethz.ch
> Subject: RE: [R] eigenvalues of a circulant matrix
>
>
> It's hard to argue against the fact that a real symmetric matrix has real
> eigenvalues. The eigenvalues of the circulant matrix with first row v are
> *polynomials* (not the roots of 1 themselves, unless as Rolf suggested you
> start with a vector with all zeros except one 1) in the roots of 1, with
> coefficients equal to the entries in v. This is the finite Fourier transform
> of v, by the way, and takes real values when the coefficients are real and
> symmetric, ie when the matrix is symmetric.
>
> Reid Huntsinger
>
> -----Original Message-----
> From: r-help-bounces at stat.math.ethz.ch
> [mailto:r-help-bounces at stat.math.ethz.ch] On Behalf Of Globe Trotter
> Sent: Monday, May 02, 2005 10:23 AM
> To: Rolf Turner
> Cc: r-help at stat.math.ethz.ch
> Subject: Re: [R] eigenvalues of a circulant matrix
>
>
>
> --- 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!
>
> ______________________________________________
> R-help at stat.math.ethz.ch mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> http://www.R-project.org/posting-guide.html
>
> ______________________________________________
> R-help at stat.math.ethz.ch mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> http://www.R-project.org/posting-guide.html
>
> ----------------------------------------------------------------------------
> --
> Notice:  This e-mail message, together with any attachments, contains
> information of Merck & Co., Inc. (One Merck Drive, Whitehouse Station, New
> Jersey, USA 08889), and/or its affiliates (which may be known outside the
> United States as Merck Frosst, Merck Sharp & Dohme or MSD and in Japan, as
> Banyu) that may be confidential, proprietary copyrighted and/or legally
> privileged. It is intended solely for the use of the individual or entity
> named on this message.  If you are not the intended recipient, and have
> and then delete it from your system.
> ----------------------------------------------------------------------------
> --
>
>
>
>
>
------------------------------------------------------------------------------
> Notice:  This e-mail message, together with any attachments, contains
> information of Merck & Co., Inc. (One Merck Drive, Whitehouse Station, New
> Jersey, USA 08889), and/or its affiliates (which may be known outside the
> United States as Merck Frosst, Merck Sharp & Dohme or MSD and in Japan, as
> Banyu) that may be confidential, proprietary copyrighted and/or legally
> privileged. It is intended solely for the use of the individual or entity
> named on this message.  If you are not the intended recipient, and have