Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Eigenvectors with Identical Eigenvalues Lose orthogonality?

Subject: Eigenvectors with Identical Eigenvalues Lose orthogonality?

From: NIcholas

Date: 6 Aug, 2010 16:22:04

Message: 1 of 13

Shouldn't the command "[V,D] = eig(A);" give an orthogonal basis V?
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?

CODE:
rand('state',0);
[Q,R]=qr(rand(4)); % Q is a random orthogonal basis
A=Q * diag([1 2 3 3]) * Q'; % eigenvalue 3 has multiplicity 2
[V,D]=eig(A);
disp(V'*V)

    1.0000 0.0000 -0.0000 -0.0000
    0.0000 1.0000 0.0000 -0.0000
   -0.0000 0.0000 1.0000 -0.3161
   -0.0000 -0.0000 -0.3161 1.0000

If instead I give A unique eigenvalues I do get an orthogonal basis:
A=Q * diag([1 2 3 4]) * Q';
[V,D]=eig(A);
disp(V'*V)
    1.0000 0.0000 0.0000 0.0000
    0.0000 1.0000 -0.0000 0.0000
    0.0000 -0.0000 1.0000 0.0000
    0.0000 0.0000 0.0000 1.0000

Subject: Eigenvectors with Identical Eigenvalues Lose orthogonality?

From: Matt J

Date: 6 Aug, 2010 16:54:04

Message: 2 of 13

"NIcholas " <dsfadfa@aol.com> wrote in message <i3hcrc$g9o$1@fred.mathworks.com>...
> Shouldn't the command "[V,D] = eig(A);" give an orthogonal basis V?
==============

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.

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.

Subject: Eigenvectors with Identical Eigenvalues Lose orthogonality?

From: Matt J

Date: 6 Aug, 2010 16:59:06

Message: 3 of 13

"NIcholas " <dsfadfa@aol.com> wrote in message <i3hcrc$g9o$1@fred.mathworks.com>...

> If instead I give A unique eigenvalues I do get an orthogonal basis:
==========

Yes, the eigenvectors of a Hermitian matrix belonging to different eigenvalues are always orthogonal to each other.

A repeated eigenvalue with multiplicity M has an M-dimensional space of eigenvectors. You can orthogonalize any basis for this M-dimensional space using Gram-Schmidt, but again eig() has no reason to add this processing, not knowing whether A is Hermitian.

Subject: Eigenvectors with Identical Eigenvalues Lose orthogonality?

From: Matt J

Date: 6 Aug, 2010 17:16:07

Message: 4 of 13

"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <i3hf0q$3vk$1@fred.mathworks.com>...

> A repeated eigenvalue with multiplicity M has an M-dimensional space of eigenvectors. You can orthogonalize any basis for this M-dimensional space using Gram-Schmidt, but again eig() has no reason to add this processing, not knowing whether A is Hermitian.
================

eig() also has no way of detecting whether eigenvalues are repeated. The test

EigenValue1==EigenValue2

is too naive to account for floating point errors in the computation of the eigenvalues.

Subject: Eigenvectors with Identical Eigenvalues Lose orthogonality?

From: Bruno Luong

Date: 6 Aug, 2010 17:37:04

Message: 5 of 13

"NIcholas " <dsfadfa@aol.com> wrote in message <i3hcrc$g9o$1@fred.mathworks.com>...
> Shouldn't the command "[V,D] = eig(A);" give an orthogonal basis V?
> 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?

This is not an "issue": there is no warranty that EIG must return the orthogonal basis for multiple-order eigenspace even for Hermitian matrix. Any basis vectors within the multilple-order eigenspace are still *valid* eigen-vectors.

If you want to reorthonalize, use ORTH after EIG. Or you can call SVD

[V D V] = svd(A)

Bruno

Subject: Eigenvectors with Identical Eigenvalues Lose orthogonality?

From: Bruno Luong

Date: 6 Aug, 2010 17:41:05

Message: 6 of 13

"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <i3hg0n$807$1@fred.mathworks.com>...
> "Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <i3hf0q$3vk$1@fred.mathworks.com>...
>
> > A repeated eigenvalue with multiplicity M has an M-dimensional space of eigenvectors. You can orthogonalize any basis for this M-dimensional space using Gram-Schmidt

Don't, Gram-Schmidt is unstable numerically, and only good for educational purpose. Rather use QR or SVD or ORTH.

Bruno

Subject: Eigenvectors with Identical Eigenvalues Lose orthogonality?

From: Matt J

Date: 6 Aug, 2010 17:55:20

Message: 7 of 13

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <i3hhfh$c2l$1@fred.mathworks.com>...
> "Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <i3hg0n$807$1@fred.mathworks.com>...

> > > A repeated eigenvalue with multiplicity M has an M-dimensional space of eigenvectors. You can orthogonalize any basis for this M-dimensional space using Gram-Schmidt
>
> Don't, Gram-Schmidt is unstable numerically, and only good for educational purpose. Rather use QR or SVD or ORTH.
================
 
Good to know. This link describes a stabilized, modified Gram-Schmidt incidentally

http://en.wikipedia.org/wiki/Gram-Schmidt#Numerical_stability

Subject: Eigenvectors with Identical Eigenvalues Lose orthogonality?

From: NIcholas

Date: 6 Aug, 2010 18:10:23

Message: 8 of 13

> This is not an "issue": there is no warranty that EIG must return the orthogonal basis for multiple-order eigenspace even for Hermitian matrix.

Thanks, I was mostly wondering what would guarantee orthogonality; as you suggested SVD does do that.

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.
disp(A-A')
  1.0e-015 *
         0 0 -0.2220 0
         0 0 0 0
    0.2220 0 0 0
         0 0 0 0

But now, if I make A exactly symmetric (which it should be from the above calculation) and do an eigendecomposition the basis IS orthogonal:

A=(A+A')/2;
[V,D]=eig(A);
disp(V'*V)
    1.0000 0.0000 0.0000 0.0000
    0.0000 1.0000 -0.0000 -0.0000
    0.0000 -0.0000 1.0000 0.0000
    0.0000 -0.0000 0.0000 1.0000

Does MATLAB detect symmetry and use a different algorithm for eig?

Subject: Eigenvectors with Identical Eigenvalues Lose orthogonality?

From: Matt J

Date: 6 Aug, 2010 18:20:10

Message: 9 of 13

"NIcholas " <dsfadfa@aol.com> wrote in message <i3hj6f$225$1@fred.mathworks.com>...

> Does MATLAB detect symmetry and use a different algorithm for eig?
========

I guess it must. If it didn't detect symmetry, it shouldn't be able to return exactly real eigenvalues, as below

>> A=rand(2); A=A+A'; d=eig(A)

d =

    0.7700
    2.2667

Subject: Eigenvectors with Identical Eigenvalues Lose orthogonality?

From: Matt J

Date: 6 Aug, 2010 18:29:06

Message: 10 of 13

"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <i3hjoq$7po$1@fred.mathworks.com>...
> "NIcholas " <dsfadfa@aol.com> wrote in message <i3hj6f$225$1@fred.mathworks.com>...
>
> > Does MATLAB detect symmetry and use a different algorithm for eig?
> ========
>
> I guess it must. If it didn't detect symmetry, it shouldn't be able to return exactly real eigenvalues, as below
=======

Forget it. That wouldn't verify it.

Subject: Eigenvectors with Identical Eigenvalues Lose orthogonality?

From: Bruno Luong

Date: 6 Aug, 2010 18:30:33

Message: 11 of 13

"NIcholas " <dsfadfa@aol.com> wrote in message <i3hj6f$225$1@fred.mathworks.com>...

>
> Does MATLAB detect symmetry and use a different algorithm for eig?

Yes, not only for EIG but many other linear algebra functions.

Bruno

Subject: Eigenvectors with Identical Eigenvalues Lose orthogonality?

From: Roger Stafford

Date: 6 Aug, 2010 18:57:05

Message: 12 of 13

"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <i3hf0q$3vk$1@fred.mathworks.com>...
> A repeated eigenvalue with multiplicity M has an M-dimensional space of eigenvectors. You can orthogonalize any basis for this M-dimensional space using Gram-Schmidt, but again eig() has no reason to add this processing, not knowing whether A is Hermitian.
- - - - - - - - - - -
  The trouble with doing a Gram-Schmidt, 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 non-singular. 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.

  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.

Roger Stafford

Subject: Eigenvectors with Identical Eigenvalues Lose orthogonality?

From: Matt J

Date: 6 Aug, 2010 19:08:04

Message: 13 of 13

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <i3hlu1$p1t$1@fred.mathworks.com>...

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

Then I guess SVD is the way to go...

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us