eigenvalues of a circulant matrix
The example that I submitted earlier in the day. Would you like me to send again? Thanks!
--- "Huntsinger, Reid" <reid_huntsinger at merck.com> wrote:
For which X? Reid Huntsinger -----Original Message----- From: Globe Trotter [mailto:itsme_410 at yahoo.com] Sent: Monday, May 02, 2005 2:34 PM To: Huntsinger, Reid; Rolf Turner Cc: r-help at stat.math.ethz.ch Subject: RE: [R] eigenvalues of a circulant matrix 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 PLEASE do read the posting guide! 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 PLEASE do read the posting guide! 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 received this message in error, please notify us immediately by reply
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 received this message in error, please notify us immediately by reply
and then delete it from your system.
---------------------------------------------------------------------------- --
__________________________________________________ Do You Yahoo!?
------------------------------------------------------------------------------
Notice: This e-mail message, together with any attachment...{{dropped}}