Eigenvectors
Ofer Corshid
Hello,
A is a syymetric non-negative matrix - the affinity matrix.
I want that V will hold the eigenvectors of A (in the rows of V - the
elements of vector vi are in row i) and that D will b a cannonicl matrix
holding the eigenvalues in it's diagonal - the eigenvalue in entry (i,i)
bleongs to the eigenvector in row i of V.
I do this:
[V, D] = eig(A)
First - is this the right way to do it?
Second - and this is the reason for asking the first question - matlab
returns V as a matrix with eigenvectors which are not non-negative - but
an eigenvector of a non-negative symmetric matrix must be non-negative.
What is going on?
Thank You
John D'Errico
Ofer Corshid <ofe...@cs.huji.ac.il> wrote:
> Hello,
>
> A is a syymetric non-negative matrix - the affinity matrix.
> I want that V will hold the eigenvectors of A (in the rows of V - the
> elements of vector vi are in row i) and that D will b a cannonicl matrix
> holding the eigenvalues in it's diagonal - the eigenvalue in entry (i,i)
> bleongs to the eigenvector in row i of V.
> I do this:
> [V, D] = eig(A)
> First - is this the right way to do it?
Except that I think I remember eig returns V with the
eigenvectors as columns of V. If you really want them
as rows,
[V, D] = eig(A);
V=V';
> Second - and this is the reason for asking the first question - matlab
> returns V as a matrix with eigenvectors which are not non-negative - but
> an eigenvector of a non-negative symmetric matrix must be non-negative.
Not exactly.
If x is an eigenvector of the matrix A, then so is -x.
The eigenvector corresponding to the largest eigenvalue of
your non-negative matrix will should be all non-negative,
but after that ...
Remember that the second eigenvector (and all other eigenvectors)
will be orthogonal to the first. If the first eigenvector was
all strictly positive, then the other vectors must have at least
some negative elements to be orthogonal to the first one.
Hope this helps,
John D'Errico
Lars Gregersen
wrote:
>In article <Pine.SUN.3.96.990616...@pita.cs.huji.ac.il>,
>Ofer Corshid <ofe...@cs.huji.ac.il> wrote:
>
>> Hello,
>>
>> A is a syymetric non-negative matrix - the affinity matrix.
>> I want that V will hold the eigenvectors of A (in the rows of V - the
>> elements of vector vi are in row i) and that D will b a cannonicl matrix
>> holding the eigenvalues in it's diagonal - the eigenvalue in entry (i,i)
>> bleongs to the eigenvector in row i of V.
>> I do this:
>> [V, D] = eig(A)
>> First - is this the right way to do it?
It all depends. Where does A come from? How big is it? Is it sparse?
Do you need all the eigenvalues and eigenvectors?
>> Second - and this is the reason for asking the first question - matlab
>> returns V as a matrix with eigenvectors which are not non-negative - but
>> an eigenvector of a non-negative symmetric matrix must be non-negative.
>
>Not exactly.
>
>If x is an eigenvector of the matrix A, then so is -x.
Indeed
>The eigenvector corresponding to the largest eigenvalue of
>your non-negative matrix will should be all non-negative,
>but after that ...
Now, this is in total contradiction with what what you just wrote.
Don't rely on the signs of the eigenvectors. Even if the current
algorithm that Matlab uses gives what you say it could change in the
future.
>Remember that the second eigenvector (and all other eigenvectors)
>will be orthogonal to the first. If the first eigenvector was
>all strictly positive, then the other vectors must have at least
>some negative elements to be orthogonal to the first one.
This is true. What you will normally see is that the eigenvectors
corresponding to the largest eigenvalues will have few sign changes
and the eigenvectors corresponding to the smallest eigenvalues will
have many sign changes.
Now back to the question from Ofer. It is not the eigenvectors of a
possitive definite matrix that must be positive. It is the
eigenvalues.
Also note that the eigenvalues are not sorted when they come out of
'eig'. You have to do this yourself. Remember to reorder the
eigenvectors accordingly.
I hope this helps!
Lars
------------------------------
Lars Gregersen (l...@kt.dtu.dk)
http://www.gbar.dtu.dk/~matlg
jh...@my-deja.com
l...@kt.dtu.dk (Lars Gregersen) wrote:
> On Wed, 16 Jun 1999 13:59:45 -0400, der...@kodak.com (John D'Errico)
> wrote:
>
>
> This is true. What you will normally see is that the eigenvectors
> corresponding to the largest eigenvalues will have few sign changes
> and the eigenvectors corresponding to the smallest eigenvalues will
> have many sign changes.
>
> Now back to the question from Ofer. It is not the eigenvectors of a
> possitive definite matrix that must be positive. It is the
> eigenvalues.
>
It is indeed the eigenvalues, not the eigenvectors, which have anything
to do with the positive-negative definite of the matrix. I am not
so sure about what you said on the eigenvectors corresponding to the
largest/smallest eigenvalues. In many time, there are several
eigenvectors corresponding to one e-value. I believe you have no
conclusions whatsoever on the positiveness of the elements of a
eigenvector.
RT
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
Johan Kullstam
> Hello,
>
> A is a syymetric non-negative matrix - the affinity matrix.
> I want that V will hold the eigenvectors of A (in the rows of V - the
> elements of vector vi are in row i) and that D will b a cannonicl matrix
> holding the eigenvalues in it's diagonal - the eigenvalue in entry (i,i)
> bleongs to the eigenvector in row i of V.
> I do this:
> [V, D] = eig(A)
> First - is this the right way to do it?
for positive semi-definite (PSD) matrix[1], use svd instead of eig.
it's faster and more accurate.
[u,s,v] = svd(A)
note that u and v are the same.
if is gotten by squaring data as in A = X' * X you can apply svd
directly on X.
[u1,s1,v1] = svd(X)
[u2,s2,v2] = svd(A)
note that v1 = u2 = v2 and s1 * s1 = s2. this can save precision.
> Second - and this is the reason for asking the first question - matlab
> returns V as a matrix with eigenvectors which are not non-negative - but
> an eigenvector of a non-negative symmetric matrix must be
> non-negative.
vectors do not have a notion of sign. the _eigenvalues_[2] should be
positive.
> What is going on?
>
> Thank You
[1] PSD over complex based vectorspace implies hermetian symmetry.
[2] for PSD eigenvalues are the same as the singular values.
--
J o h a n K u l l s t a m
[kull...@ne.mediaone.net]
Don't Fear the Penguin!
John D'Errico
You've misquoted me here. I never said any of the above.
Please get your quotes right.
Thank you,
John D'Errico
David Goodmanson
>
> In article <7kbmic$u3j$1...@nnrp1.deja.com>, jh...@my-deja.com wrote:
> > In article <3768b5c2...@news.dtu.dk>,
> > l...@kt.dtu.dk (Lars Gregersen) wrote:
> > > On Wed, 16 Jun 1999 13:59:45 -0400, der...@kodak.com (John D'Errico)
> > > wrote:
> > > Now back to the question from Ofer. ...
> > It is indeed the eigenvalues, ...
>
>
> You've misquoted me here. I never said any of the above.
>
> Please get your quotes right.
>
> Thank you,
> John D'Errico
Hi John--
It's no fun to be misquoted, but one thing you *did* say in your
previous message is:
----------------
" The eigenvector corresponding to the largest eigenvalue of
your non-negative matrix will should be all non-negative,
but after that ...
Remember that the second eigenvector (and all other eigenvectors)
will be orthogonal to the first. If the first eigenvector was
all strictly positive, then the other vectors must have at least
some negative elements to be orthogonal to the first one. "
----------------
According to the first paragraph, the eigenvector corresponding to the
largest eigenvalue has all nonnegative components (or equivalently all
nonpositive components, allowing for a factor of -1). But that is *not*
true in general. Consider the symmetric nonnegative (in fact positive)
matrix
m = 1 -1 1
-1 2 -1
1 -1 3
» [a b] = eig(m) % svd will give the same result
a = 0.8877 0.2332 0.3971
0.4271 -0.7392 -0.5207
-0.1721 -0.6318 0.7558
b = 0.3249 0 0
0 1.4608 0
0 0 4.2143
All three eigenvectors have both positive and negative components.
--Dave
*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
David Goodmanson dgood...@worldnet.att.net
909 4th Ave. N, Apt. D
Seattle, WA 98109 USA
He had bought a large map representing the sea,
Without the least vestige of land:
And the crew were much pleased when they found it to be
A map they could all understand.
--Lewis Carroll
Ulrich Elsner
But your matrix is obviously NOT positive. (it contains -1). It looks like
you confuse "nonnegative" and "nonnegative definite".
A nonnegative matrix has no nonnegative elements.
A nonnegative definite matrix has the property that x^T A x >= 0 for all
real x.
Nonnegative matrices have an eigenvector where all components have the
same sign corresponding to the largest eigenvalue (which equals the
spectral radius). This is a slight generalization of the Perron-Frobenius
Theorem.
For nonnegative definite matrices, we know is that the eigenvalues are
nonnegative.Unless the matrix is symmetric (which the matrix in the
original question was), we don't even know anything (relevant) about the
eigenvectors. They might even all have the same sign. Take, e.g.,:
A= [ 0 1 0; ...
-4 7 -2; ...
-5 7 -1]
Btw, one has to differentiate between positive and nonnegative. For
example, even for symmetric matrices, the argument about different signs
because of the orthogonality does not hold for nonnegative matrices.
A counterexample is the identity matrix.
Regards,
Ulrich
--
Ulrich Elsner, Fak. fuer Mathematik, TU Chemnitz, D-09107 Chemnitz, Germany
Lars Gregersen
>In article <3768b5c2...@news.dtu.dk>,
> l...@kt.dtu.dk (Lars Gregersen) wrote:
>> On Wed, 16 Jun 1999 13:59:45 -0400, der...@kodak.com (John D'Errico)
>> wrote:
>>
>>
>> This is true. What you will normally see is that the eigenvectors
>> corresponding to the largest eigenvalues will have few sign changes
>> and the eigenvectors corresponding to the smallest eigenvalues will
>> have many sign changes.
>>
>> Now back to the question from Ofer. It is not the eigenvectors of a
>> possitive definite matrix that must be positive. It is the
>> eigenvalues.
>>
>
>It is indeed the eigenvalues, not the eigenvectors, which have anything
>to do with the positive-negative definite of the matrix. I am not
>so sure about what you said on the eigenvectors corresponding to the
Then we must make you somewhat sure of this
>largest/smallest eigenvalues. In many time, there are several
>eigenvectors corresponding to one e-value. I believe you have no
In the case of multiple eigenvalues the corresponding eigenvectors are
not uniquely determined as they will span a plane. I haven't looked at
what happens with the signs of the elements of the eigenvectors when
you rotate the eigenvectors (in the plane), which you are free to do,
but my guess(!) is that you will gain much from looking at the sign
changes under rotation.
>conclusions whatsoever on the positiveness of the elements of a
>eigenvector.
I don't have a proof of my statement. See "Rank-Deficient and Discrete
Ill-Posed Problems: Numerical Aspects of Linear Inversion", by Per
Christian Hansen <http://www.imm.dtu.dk/~pch/Book/mm04.html> or
alternatively the manual for his regtool toolbox page 11 at
<http://www.imm.dtu.dk/~pch/Regutools/regutools.html>, where he
mentions that it is an often observed fact that sign changes seem to
be more frequent for the smallest eigenvalues.
Anyway, I don't have any good use of this observation.
John D'Errico
dgood...@worldnet.att.net wrote:
> true in general. Consider the symmetric nonnegative (in fact positive)
> matrix
>
> m = 1 -1 1
> -1 2 -1
> 1 -1 3
>
Dave,
As has been stated by another, this is not a positive matrix.
It is positive definite. There is a difference, as I'm sure
you know. Some people tend to use the two terms as synonyms.
I was not doing so, because the poster apparently was not.
In this case, I looked at the original poster's wording.
They talk about vectors being non-negative, and then about
a matrix being also non-negative. Since The first reference
implies something about the signs of the individual elements,
I would assume that this person also means the same when they
discussed a non-negative matrix. (Perhaps I should have made
this distinction in my original post, but I felt it would
have just confused the issue. Maybe I was just being lazy.
Most likely the difference between positive and positive
definite is what was confusing the original poster, so I
should have cleared it up.)
(Sigh)
John
David Goodmanson
Ulrich--
Mea culpa. I was confused, and it wasn't my intent to stir up even more
entropy on the newsgroup. Thanks for clarifying things.
b...@eigenvector.com
In article <Pine.SUN.3.96.990616...@pita.cs.huji.ac.il>,
Ofer Corshid <ofe...@cs.huji.ac.il> wrote:
>
> Hello,
>
> A is a syymetric non-negative matrix - the affinity matrix.
> I want that V will hold the eigenvectors of A (in the rows of V - the
> elements of vector vi are in row i) and that D will b a cannonicl matrix
> holding the eigenvalues in it's diagonal - the eigenvalue in entry (i,i)
> bleongs to the eigenvector in row i of V.
> I do this:
> [V, D] = eig(A)
> First - is this the right way to do it?
Looks right to me.
> Second - and this is the reason for asking the first question - matlab
> returns V as a matrix with eigenvectors which are not non-negative - but
> an eigenvector of a non-negative symmetric matrix must be non-negative.
You mean all the elements of the eigenvector have to be positive?
Or that the eigenvalues have to be positive? Certainly the former
is not true, in fact you can show that pretty easily because any
eigenvector times -1 is also an eigenvector. If you mean that
all the eigenvalues have to be positive, well, hmm. I know that
covariance matrices are always positive semi-definite, i.e. all
the eigenvalues are >= 0. In your case, if you matrix is symmetric,
I suspect it can be factored as A = W'W, and if it can, then it
has to be positive semi-definite.
Best regards....
BMW
Eigenvector Research, Inc.
jh...@my-deja.com
<woodchips-170...@66.albany-06-07rs.ny.dial-access.att.net>,
wood...@worldnet.att.net (John D'Errico) wrote:
> You've misquoted me here. I never said any of the above.
>
> Please get your quotes right.
>
> Thank you,
> John D'Errico
>
Sorry, John. I hope I quoted right this time. :-)
I know now what going on. The confusion is clearly
from the interpretaion of "positive" for a matrix.
This word to me means "positive definite" all the
time. Anyway, I have learned something from the
discussions.
Happy posting/reading,
RT