http://www.mathworks.com/matlabcentral/newsreader/view_thread/288717
MATLAB Central Newsreader  Eigenvectors with Identical Eigenvalues Lose orthogonality?
Feed for thread: Eigenvectors with Identical Eigenvalues Lose orthogonality?
enus
©19942014 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://www.mathworks.com/images/membrane_icon.gif

Fri, 06 Aug 2010 16:22:04 +0000
Eigenvectors with Identical Eigenvalues Lose orthogonality?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/288717#769223
NIcholas
Shouldn't the command "[V,D] = eig(A);" give an orthogonal basis V?<br>
If A has unique eigenvalues I find this to be true, but if A has identical eigenvalues (see code below) the eigenvectors with identical eigenvalues seem to lose orthogonality. Is this a numerical issue with the eig command? and is there a way around it?<br>
<br>
CODE:<br>
rand('state',0);<br>
[Q,R]=qr(rand(4)); % Q is a random orthogonal basis<br>
A=Q * diag([1 2 3 3]) * Q'; % eigenvalue 3 has multiplicity 2<br>
[V,D]=eig(A);<br>
disp(V'*V)<br>
<br>
1.0000 0.0000 0.0000 0.0000<br>
0.0000 1.0000 0.0000 0.0000<br>
0.0000 0.0000 1.0000 0.3161<br>
0.0000 0.0000 0.3161 1.0000<br>
<br>
If instead I give A unique eigenvalues I do get an orthogonal basis:<br>
A=Q * diag([1 2 3 4]) * Q';<br>
[V,D]=eig(A);<br>
disp(V'*V)<br>
1.0000 0.0000 0.0000 0.0000<br>
0.0000 1.0000 0.0000 0.0000<br>
0.0000 0.0000 1.0000 0.0000<br>
0.0000 0.0000 0.0000 1.0000

Fri, 06 Aug 2010 16:54:04 +0000
Re: Eigenvectors with Identical Eigenvalues Lose orthogonality?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/288717#769237
Matt J
"NIcholas " <dsfadfa@aol.com> wrote in message <i3hcrc$g9o$1@fred.mathworks.com>...<br>
> Shouldn't the command "[V,D] = eig(A);" give an orthogonal basis V?<br>
==============<br>
<br>
If A is not Hermitian, it might not even have a fulll set of linear independent eigenvectors, making it impossible for eig() to produce an orthogonal basis.<br>
<br>
In your example, A is Hermitian, but since eig doesn't know this in advance, it has no reason to try to orthogonalize the result.

Fri, 06 Aug 2010 16:59:06 +0000
Re: Eigenvectors with Identical Eigenvalues Lose orthogonality?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/288717#769241
Matt J
"NIcholas " <dsfadfa@aol.com> wrote in message <i3hcrc$g9o$1@fred.mathworks.com>...<br>
<br>
> If instead I give A unique eigenvalues I do get an orthogonal basis:<br>
==========<br>
<br>
Yes, the eigenvectors of a Hermitian matrix belonging to different eigenvalues are always orthogonal to each other.<br>
<br>
A repeated eigenvalue with multiplicity M has an Mdimensional space of eigenvectors. You can orthogonalize any basis for this Mdimensional space using GramSchmidt, but again eig() has no reason to add this processing, not knowing whether A is Hermitian.

Fri, 06 Aug 2010 17:16:07 +0000
Re: Eigenvectors with Identical Eigenvalues Lose orthogonality?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/288717#769246
Matt J
"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <i3hf0q$3vk$1@fred.mathworks.com>...<br>
<br>
> A repeated eigenvalue with multiplicity M has an Mdimensional space of eigenvectors. You can orthogonalize any basis for this Mdimensional space using GramSchmidt, but again eig() has no reason to add this processing, not knowing whether A is Hermitian.<br>
================<br>
<br>
eig() also has no way of detecting whether eigenvalues are repeated. The test<br>
<br>
EigenValue1==EigenValue2<br>
<br>
is too naive to account for floating point errors in the computation of the eigenvalues.

Fri, 06 Aug 2010 17:37:04 +0000
Re: Eigenvectors with Identical Eigenvalues Lose orthogonality?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/288717#769252
Bruno Luong
"NIcholas " <dsfadfa@aol.com> wrote in message <i3hcrc$g9o$1@fred.mathworks.com>...<br>
> Shouldn't the command "[V,D] = eig(A);" give an orthogonal basis V?<br>
> If A has unique eigenvalues I find this to be true, but if A has identical eigenvalues (see code below) the eigenvectors with identical eigenvalues seem to lose orthogonality. Is this a numerical issue with the eig command? and is there a way around it?<br>
<br>
This is not an "issue": there is no warranty that EIG must return the orthogonal basis for multipleorder eigenspace even for Hermitian matrix. Any basis vectors within the multilpleorder eigenspace are still *valid* eigenvectors.<br>
<br>
If you want to reorthonalize, use ORTH after EIG. Or you can call SVD<br>
<br>
[V D V] = svd(A)<br>
<br>
Bruno

Fri, 06 Aug 2010 17:41:05 +0000
Re: Eigenvectors with Identical Eigenvalues Lose orthogonality?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/288717#769253
Bruno Luong
"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <i3hg0n$807$1@fred.mathworks.com>...<br>
> "Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <i3hf0q$3vk$1@fred.mathworks.com>...<br>
> <br>
> > A repeated eigenvalue with multiplicity M has an Mdimensional space of eigenvectors. You can orthogonalize any basis for this Mdimensional space using GramSchmidt<br>
<br>
Don't, GramSchmidt is unstable numerically, and only good for educational purpose. Rather use QR or SVD or ORTH.<br>
<br>
Bruno

Fri, 06 Aug 2010 17:55:20 +0000
Re: Eigenvectors with Identical Eigenvalues Lose orthogonality?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/288717#769255
Matt J
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <i3hhfh$c2l$1@fred.mathworks.com>...<br>
> "Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <i3hg0n$807$1@fred.mathworks.com>...<br>
<br>
> > > A repeated eigenvalue with multiplicity M has an Mdimensional space of eigenvectors. You can orthogonalize any basis for this Mdimensional space using GramSchmidt<br>
> <br>
> Don't, GramSchmidt is unstable numerically, and only good for educational purpose. Rather use QR or SVD or ORTH.<br>
================<br>
<br>
Good to know. This link describes a stabilized, modified GramSchmidt incidentally<br>
<br>
<a href="http://en.wikipedia.org/wiki/GramSchmidt#Numerical_stability">http://en.wikipedia.org/wiki/GramSchmidt#Numerical_stability</a>

Fri, 06 Aug 2010 18:10:23 +0000
Re: Eigenvectors with Identical Eigenvalues Lose orthogonality?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/288717#769261
NIcholas
> This is not an "issue": there is no warranty that EIG must return the orthogonal basis for multipleorder eigenspace even for Hermitian matrix. <br>
<br>
Thanks, I was mostly wondering what would guarantee orthogonality; as you suggested SVD does do that.<br>
<br>
Also, In the above example with A=Q * diag([1 2 3 3]) * Q'; (when the last two eigenvectors were not orthogonal) A was not exactly symmetric.<br>
disp(AA')<br>
1.0e015 *<br>
0 0 0.2220 0<br>
0 0 0 0<br>
0.2220 0 0 0<br>
0 0 0 0<br>
<br>
But now, if I make A exactly symmetric (which it should be from the above calculation) and do an eigendecomposition the basis IS orthogonal:<br>
<br>
A=(A+A')/2;<br>
[V,D]=eig(A);<br>
disp(V'*V)<br>
1.0000 0.0000 0.0000 0.0000<br>
0.0000 1.0000 0.0000 0.0000<br>
0.0000 0.0000 1.0000 0.0000<br>
0.0000 0.0000 0.0000 1.0000<br>
<br>
Does MATLAB detect symmetry and use a different algorithm for eig?

Fri, 06 Aug 2010 18:20:10 +0000
Re: Eigenvectors with Identical Eigenvalues Lose orthogonality?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/288717#769265
Matt J
"NIcholas " <dsfadfa@aol.com> wrote in message <i3hj6f$225$1@fred.mathworks.com>...<br>
<br>
> Does MATLAB detect symmetry and use a different algorithm for eig?<br>
========<br>
<br>
I guess it must. If it didn't detect symmetry, it shouldn't be able to return exactly real eigenvalues, as below<br>
<br>
>> A=rand(2); A=A+A'; d=eig(A)<br>
<br>
d =<br>
<br>
0.7700<br>
2.2667

Fri, 06 Aug 2010 18:29:06 +0000
Re: Eigenvectors with Identical Eigenvalues Lose orthogonality?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/288717#769272
Matt J
"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <i3hjoq$7po$1@fred.mathworks.com>...<br>
> "NIcholas " <dsfadfa@aol.com> wrote in message <i3hj6f$225$1@fred.mathworks.com>...<br>
> <br>
> > Does MATLAB detect symmetry and use a different algorithm for eig?<br>
> ========<br>
> <br>
> I guess it must. If it didn't detect symmetry, it shouldn't be able to return exactly real eigenvalues, as below<br>
=======<br>
<br>
Forget it. That wouldn't verify it.

Fri, 06 Aug 2010 18:30:33 +0000
Re: Eigenvectors with Identical Eigenvalues Lose orthogonality?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/288717#769273
Bruno Luong
"NIcholas " <dsfadfa@aol.com> wrote in message <i3hj6f$225$1@fred.mathworks.com>...<br>
<br>
> <br>
> Does MATLAB detect symmetry and use a different algorithm for eig?<br>
<br>
Yes, not only for EIG but many other linear algebra functions.<br>
<br>
Bruno

Fri, 06 Aug 2010 18:57:05 +0000
Re: Eigenvectors with Identical Eigenvalues Lose orthogonality?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/288717#769282
Roger Stafford
"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <i3hf0q$3vk$1@fred.mathworks.com>...<br>
> A repeated eigenvalue with multiplicity M has an Mdimensional space of eigenvectors. You can orthogonalize any basis for this Mdimensional space using GramSchmidt, but again eig() has no reason to add this processing, not knowing whether A is Hermitian.<br>
          <br>
The trouble with doing a GramSchmidt, or for that matter any other orthogonalization scheme, on the results from matlab's 'eig' as it stands is that it is quite possible for 'eig' to produce eigenvectors for two equal eigenvalues that are nearly parallel, even though the original matrix was Hermitian and very nonsingular. I have seen this happen. This means that the eigenvector space corresponding to the repeated eigenvalue would not have been thoroughly explored in a sense. One could encounter excessive numerical errors in establishing a valid orthogonal basis of eigenvectors in such a case.<br>
<br>
This would be all the more true in such cases if more than one multiplicity of eigenvalue were present. One would then have no way of accurately separating the "unexplored" eigenvector spaces for the differing multiple eigenvalues without referring back to the original matrix. The point is that 'eig' for repeated eigenvalues is in certain cases not passing on enough information in its eigenvector set to allow for an accurate orthogonalization of it. Whether this is so or not seems to be determined by the vagaries of the particular algorithm used in 'eig'. I see no inherent mathematical reason why this should be so.<br>
<br>
Roger Stafford

Fri, 06 Aug 2010 19:08:04 +0000
Re: Eigenvectors with Identical Eigenvalues Lose orthogonality?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/288717#769286
Matt J
"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <i3hlu1$p1t$1@fred.mathworks.com>...<br>
<br>
Whether this is so or not seems to be determined by the vagaries of the particular algorithm used in 'eig'. I see no inherent mathematical reason why this should be so.<br>
===============<br>
<br>
Then I guess SVD is the way to go...