Peter Denton, Stephen Parke, Xining Zhang, and I have just uploaded to the arXiv the short unpublished note “Eigenvectors from eigenvalues“. This note gives two proofs of a general eigenvector identity observed recently by Denton, Parke and Zhang in the course of some quantum mechanical calculations. The identity is as follows:
Theorem 1 Let
be an
Hermitian matrix, with eigenvalues
. Let
be a unit eigenvector corresponding to the eigenvalue
, and let
be the
component of
. Then
where
is the
Hermitian matrix formed by deleting the
row and column from
.
For instance, if we have
for some real number ,
-dimensional vector
, and
Hermitian matrix
, then we have
assuming that the denominator is non-zero.
Once one is aware of the identity, it is not so difficult to prove it; we give two proofs, each about half a page long, one of which is based on a variant of the Cauchy-Binet formula, and the other based on properties of the adjugate matrix. But perhaps it is surprising that such a formula exists at all; one does not normally expect to learn much information about eigenvectors purely from knowledge of eigenvalues. In the random matrix theory literature, for instance in this paper of Erdos, Schlein, and Yau, or this later paper of Van Vu and myself, a related identity has been used, namely
but it is not immediately obvious that one can derive the former identity from the latter. (I do so below the fold; we ended up not putting this proof in the note as it was longer than the two other proofs we found. I also give two other proofs below the fold, one from a more geometric perspective and one proceeding via Cramer’s rule.) It was certainly something of a surprise to me that there is no explicit appearance of the components of
in the formula (1) (though they do indirectly appear through their effect on the eigenvalues
; for instance from taking traces one sees that
).
One can get some feeling of the identity (1) by considering some special cases. Suppose for instance that is a diagonal matrix with all distinct entries. The upper left entry
of
is one of the eigenvalues of
. If it is equal to
, then the eigenvalues of
are the other
eigenvalues of
, and now the left and right-hand sides of (1) are equal to
. At the other extreme, if
is equal to a different eigenvalue of
, then
now appears as an eigenvalue of
, and both sides of (1) now vanish. More generally, if we order the eigenvalues
and
, then the Cauchy interlacing inequalities tell us that
for , and
for , so that the right-hand side of (1) lies between
and
, which is of course consistent with (1) as
is a unit vector. Thus the identity relates the coefficient sizes of an eigenvector with the extent to which the Cauchy interlacing inequalities are sharp.
— 1. Relating the two identities —
We now show how (1) can be deduced from (2). By a limiting argument, it suffices to prove (1) in the case when is not an eigenvalue of
. Without loss of generality we may take
. By subtracting the matrix
from
(and
from
, thus shifting all the eigenvalues down by
, we may also assume without loss of generality that
. So now we wish to show that
The right-hand side is just . If one differentiates the characteristic polynomial
at , one sees that
Finally, (2) can be rewritten as
so our task is now to show that
By Schur complement, we have
Since is an eigenvalue of
, but not of
(by hypothesis), the factor
vanishes when
. If we then differentiate (4) in
and set
we obtain (3) as desired.
— 2. A geometric proof —
Here is a more geometric way to think about the identity. One can view as a linear operator on
(mapping
to
for any vector
); it then also acts on all the exterior powers
by mapping
to
for all vectors
. In particular, if one evaluates
on the basis
of
induced by the orthogonal eigenbasis
, we see that the action of
on
is rank one, with
for any , where
is the inner product on
induced by the standard inner product on
. If we now apply this to the
-form
, we have
, while
is equal to
plus some terms orthogonal to
. Since
, Theorem 1 follows.
— 3. A proof using Cramer’s rule —
By a limiting argument we can assume that all the eigenvalues of are simple. From the spectral theorem we can compute the resolvent
for
as
Extracting the component of both sides and using Cramer’s rule, we conclude that
or in terms of eigenvalues
Both sides are rational functions with a simple pole at the eigenvalues . Extracting the residue at
we conclude that
and Theorem 1 follows. (Note that this approach also gives a formula for for
, although the formula becomes messier when
because the relevant minor of
is no longer a scalar multiple of the identity
.)
119 comments
Comments feed for this article
13 August, 2019 at 7:44 am
omarleoblog
What kind of mathematics is this?
13 August, 2019 at 8:16 am
Anon
Linear Algebra
1 September, 2019 at 7:27 am
That Kitty
At the research level, these results are sometimes called things like “matrix analysis,” especially when dealing with finite-dimensional normed spaces. Maybe because mathematicians often consider linear algebra “solved” or because so much (especially applied) work can be called “linear algebra” that finer descriptors are needed?
[Insert any variation on the old joke about how all of maths is an attempt to reduce problems to (some generalization) of linear algebra]
14 August, 2019 at 7:31 am
cimmerianhydra
I never visited your blog before, mr. Tao, and the first article I read is about such an interesting equality!
The last proof is especially elegant. About the second one: would you say that geometric intuition is always a valuable perspective from which to understand one’s results? Are there situations where geometry “gets in the way” of seeing things clearly?
14 August, 2019 at 7:35 am
cimmerianhydra
For some reason this was posted as a reply to a comment. I’m sorry, I have no idea how this happened.
13 August, 2019 at 9:21 am
Andrew Krause
Are there any analogues to the identities for any interesting infinite-dimensional cases? I’m wondering specifically if one can relate the eigenfunctions of a differential operator to spectral properties of that operator. Of course Kac’s famous paper on the “shape of the drum” and the solutions in that case suggest that there is no simple relationship, but perhaps there is an analogue of the spectrum of these sub-matrices which helps clarify this.
13 August, 2019 at 1:46 pm
Terence Tao
The first part of the Cramer rule proof, based on the spectral theorem, will hold in some infinite-dimensional settings: for instance, if
is the (positive semi-definite) Laplacian on a smooth compact Riemannian manifold
and
is an
-normalised eigenfunction corresponding to the eigenvalue
, then it is still true that
is the residue at
of the integral kernel of the resolvent
evaluated at
. However it is not obvious how to evaluate this resolvent further; possibly there is still some remnant of Cramer’s rule involving Fredholm determinants, but I’m not sure how useful it would be. Certainly computing residues or other asymptotic expansions of resolvents is quite a common pastime in the spectral theory or microlocal analysis literature though.
14 November, 2019 at 4:51 pm
Ken Krechmer
The solution (eigenvectors to eigenvalues) appears to also be a general solution of the Born Rule in quantum mechanics. A narrower solution to the Born Rule was presented in https://www.sciencedirect.com/science/article/pii/S0263224117306887 in 2018
13 August, 2019 at 1:22 pm
Anonymous
It seems that the LHS product is the discriminant of the characteristic polynomial of the matrix
(i.e. the resultant of the characteristic polynomial and its derivative), while the RHS product is the resultant of the chracteristic polynomials of the matrices
.
Since these resultants representing the two products can be computed via determinants of their corresponding Sylvester matrices, it seems closely related to the proof using Cramer’s rule.
13 August, 2019 at 11:11 pm
Watts
If
is Toeplitz, say the Laplacian
, then the right hand side is constant for any
. Then the formula can only recover the first eigenvector. Right?
13 August, 2019 at 11:36 pm
Watts
This is incorrect, it is not constant for any
. Ignore this comment.
13 August, 2019 at 11:25 pm
Part III: A Physicist Completes a Linear Algebra Result - Nevin Manimala's Blog
[…] a bit. We put the paper online last weekend and it finally appeared on the arXiv, along with a new Terry blog post! I’m so excited you guys don’t even […]
14 August, 2019 at 2:16 am
Raphael
Cool thing!
There is a chemical example which is immediately intuitive. A closed ring of n atoms has an adjacency matrix that is a constant on a 1-band-diagonal (at the n,n+1 and n+1,n elements) and at element (n,1) and (1,n). The eigenvalues of this matrix (Hückel matrix) correspond to the energy levels of the molecule (at some crude approximation). The adjacency matrix of the open chain you get when you remove one atom from the ring is the above described “1-band-diagonal” with dimension (n-1),(n-1). Now the energies (eigenvalues) of the open chain system with n-1 atoms are exactly matching the eigenvalues of the n+1 ring (they both are the real part of the roots of unity in the ring case of order n and in the open chain with n atoms case of order n+1). So removing one atom from the ring to get a chain is one example for making M out of A. In this example the eigenvalues of M without the first, and those of A are identical. From chemical intuition it is immediately clear that both v_1 eigenvectors are (1,…,1). An interesting question would be how or if to get information on the phases of the coefficients. In case of symmetric systems they would correspond to the characters of irreducible representations.
14 August, 2019 at 2:30 am
Raphael
Oh sorry there is a mistake it is even a bit more interesting: The “ground state” eigenvectors
of both systems (A and M) are different, the ring has obviously
while the open chain one is
(up to normalization).
19 November, 2019 at 7:26 am
Terence Tao
In fact we have recently learned that this identity was indeed introduced to study chemical graphs by Mukherjee and Datta in 1989.
19 November, 2019 at 9:00 am
Raphael
Thank you very much! Its amazing to see how this work grows also due to the contribution and knowledge of others. I find it very positive that much of the old literature in this way can be reviewed. Very good results still can gain in weight and meaning if they are set properly in the context of what has already been done and what is known. I imagine there is a lot of stuff out there in the ever growing body of scientific literature that has bee discovered several times or equally that has been forgotten or is invisible for those who search for solutions.
14 August, 2019 at 7:19 am
Anonymous
In the last formula, this should be
on the RHS.
[Corrected, thanks – T.]
14 August, 2019 at 10:00 am
John Mangual
what are these used for?
14 August, 2019 at 11:09 am
Anonymous
These are used for developing a new way to write neutrino oscillation probabilities in matter, both exactly and with simpler approximate expressions.
14 August, 2019 at 7:28 pm
Anonymous
There seems to be something strange about the left hand side of equation (1) in the arXiv paper. The product
is not well defined if
is an
matrix and
. It’s certainly not a squared matrix, so how is that determinant calculated?
15 August, 2019 at 4:49 am
Anonymous
It’s not multiplication, it’s concatenation: stick the column vector after the last column of B to “complete the square”.
18 August, 2019 at 1:22 am
Karl Svozil
In which way is this result different from the one mentioned, for instance, in Par. 79, p. 157 of Halmos’ “Finite-dimensional vector spaces”: Let
be a self-adjoint operator in finite dimensional Hilbert space, and a polynomial
Then the respective orthogonal projectors are
.
18 August, 2019 at 9:27 am
Terence Tao
This identity is related to the ones discussed here, but not quite the same; it involves polynomials of the matrix
, rather than eigenvalues of the minor
. In the notation of this post, Halmos’s identity (assuming simple eigenvalues) would read
It can be proven easily from the spectral theorem. Extracting the
component of this identity, we see that to derive Theorem 1 from this identity (or vice versa) one would have to establish the identity
where
denotes the
component of a matrix
. This identity has to be true (by combining Halmos’s identity with Theorem 1, and using a limiting argument to remove the hypothesis that the eigenvalues are simple), but actually I don’t see any direct way to prove (*) that doesn’t basically proceed via this route. (The right-hand side is
, which suggests some sort of invocation of Cramer’s rule, but if one pursues this idea, one is basically repeating the Cramer’s rule proof given in the blog post, followed by the spectral theory proof of Halmos’s identity. The left-hand side is definitely reminiscent of the Cayley-Hamilton theorem, but I have thus far been unable to use that theorem to give a more tractable expression for the left-hand side of (*), other than by the route of combining Halmos’s identity with Theorem 1.)
It is interesting that there seem to be a number of rather different looking expressions for the same quantity, with the equality between any of the two being a slightly non-trivial theorem. If one writes (assuming simple eigenvalues and
for sake of discussion)
then Theorem 1 asserts that
, the identity from Erdos-Schlein-Yau (and my paper with Van Vu) asserts that
, and Halmos’s identity asserts that
. The Cramer rule proof of Theorem 1 basically proceeds by showing that
and
. In the first proof in the blog post an independent proof is given that
. However I don’t know of a direct way to establish that
or
without going through
or
.
[UPDATE: I can now adapt the adjugate proof of Theorem 1 in the arXiv article to show (*) (or equivalently,
) directly. One can check that
by testing against each of the eigenvectors
separately (or, if one wishes, first checking the identity when
is a diagonal matrix, and using the spectral theorem to extend to general Hermitian
). [Amusingly, if one multiplies both sides of the above identity by
, one also recovers the Cayley-Hamilton theorem.] Extracting the
coefficient, one obtains (*). In other words, one can show
by equating both quantities with
It is also rather easy to show that
, so this proof is arguably “going through”
in some sense.
]
18 August, 2019 at 11:42 pm
Vassilis Papanicolaou
The RHS of (1) makes sense for arbitrary matrices, not only for Hernmitian. One, then, suspects that the formula extends to any square matrix. The guess is that, in the general case, the LHS is the product of the j-th component of the i-th eigenvector with the conjugate of the j-th component of the eigenvector of the Hermitian adjoint of the matrix coresponding to the conjugate eigenvalue.
19 August, 2019 at 9:24 am
Terence Tao
Yes, this seems to indeed be the case; for instance, the Cramer rule based proof looks like it will extend to the non-Hermitian case in the manner indicated.
19 August, 2019 at 2:40 am
Bo B
Maybe it is worthwhile to write the identity in coordinate free notation: We may assume
; otherwise replace
by
. For any vector
, let
be the determinant of the quadratic form
restricted to the orthogonal complement of
. Let
be the (a) vector with
. Then the identity says that

and
have norm 1.
if
One advantage with this is that we may assume that
, instead of
, is an element of an ON basis, which helps (a little) in the proof.
and
is of trace class, it should hold for Fredholm determinants, since they are limits of finite dimensional determinants. It might also hold for determinants defined by zeta-functions (?).
It also suggests that the formula might hold in the case of infinite dimension, for a suitable notion of determinants. For instance, when
19 August, 2019 at 9:26 am
Terence Tao
Nice! This fits well with the geometric proof. The quantity
clearly equals
when
, and also clearly vanishes when
(because the null vector
to the quadratic form now lies in the orthogonal complement of
), while on rewriting
(where
represents the action of
on the exterior power
, and
is the Hodge dual of
) we see that
is a quadratic form in
, at which point the identity
is forced upon us.
In less coordinate-free notation, the identity can also be written as
, with basically the same proof; this is then more or less the adjugate matrix proof in the arXiv posting.
23 September, 2019 at 10:50 am
Theorists discover the “Rosetta Stone” for neutrino physics | News
[…] Experts fully expected the identity to exist somewhere in the literature for centuries but couldn’t find any evidence for it online or in textbooks. The three of us were eventually directed to a similar result by UCLA mathematics professor Terence Tao, who has a Fields Medal and Breakthrough Prize to his name. When we presented Tao with our result, he cheerfully declared that it was, in fact, the discovery of a new identity, and he provided several mathematical proofs, which have now been published online. Tao also discussed the new identity in his math blog. […]
24 September, 2019 at 12:26 pm
Jonathan
I have observed that, due to this version of Cramer’s Rule (I find no separate name for it) :
where
is an eigenvalue of
, then taken column-by-column, each column of
is a candidate eigenvector for eigenvalue
.
Applied to
In the case that the eigenspace of eigenvalue
is 1-dimensional, then all the columns of
will be multiples of each other; the matrix itself is an outer product, just as is the case in eq. (7) of the note on arxiv. Would this be useful to generalize your result to the non-hermitian case?
25 September, 2019 at 3:18 am
Anonymous
Somehow this identity looks like it is a manifestation of a more abstract algebraic principle not restricted to setting of linear spaces over complex numbers. For example, what has the triangle inequality to do with it, or the fact that complex numbers form an algebraically closed field? (Of course there is a bilinear form involved.) Relaxing the precise formulation and letting this thing run loose, what would turn out to be its “natural habitat”?
25 September, 2019 at 5:52 am
Ricardo Marino
What are the implications of this identity for the spectrum of d-regular graphs, Dr. Tao? Let
be the adjacency matrix of a
d-regular graph with
vertices. Taking the trivial eigenvalue and eigenvector, as
and
in the identity, does this mean that the product of all the non-zero L-eigenvalues of
is equivalent to the
, where
are the eigenvalues of any 1-minor. This creates a series of identities between the eigenvalues of all minors of the adjacency matrix, or am I mistaken? Was this well-known before and I am out of the loop?
25 September, 2019 at 11:33 am
Raphael
My thoughts were along similar lines. I thought about Hückel bonding matrices and the eigenfunctions/eigenvalues emerging from that. That is pretty close to spectral graph theory. I see a major problem in that the information on the signs ist lost. That namely makes out a large bit of the unknowns. The absolut values of the components I think are not all too thrilling after all. But as I said also, group representation theory could help here out possibly.
25 September, 2019 at 7:56 am
Researchers Uncover 'Rosetta Stone' For Neutrino Oscillations in Matter - PJ Digital Marketing
[…] The basic nature of the invention made researchers suppose that the id will need to have already been confirmed however couldn’t discover any proof indicating in any other case, Stephen Parke co-author of analysis recalled. The researchers introduced their findings to Fields Medal Awardee, Terence Tao who confirmed that the id is certainly, a brand new elementary id. The researchers together with Tao revealed that findings on arXiv.org merely titled Eigenvectors from Eigenvalues. Tao additionally defined the invention on his math weblog. […]
26 September, 2019 at 6:28 am
Theorists discover the ‘Rosetta Stone’ for neutrino physics – News
[…] Experts fully expected the identity to exist somewhere in the literature for centuries but couldn't find any evidence for it online or in textbooks. The three of us were eventually directed to a similar result by UCLA mathematics professor Terence Tao, who has a Fields Medal and Breakthrough Prize to his name. When we presented Tao with our result, he cheerfully declared that it was, in fact, the discovery of a new identity, and he provided several mathematical proofs, which have now been published online. Tao also discussed the new identity in his math blog. […]
30 September, 2019 at 5:19 am
Lucas Morin
I have been toying with the formula in the context of statistics, but without much results. I was wondering :
after centering and reducing the statistical variables.
, notably in the context of step wise regression, where you recursively add or remove a variable. Removing the k th variable would mean replacing
by it’s minor
in the formula above.
where
is the residual from a regression of
on all the other covariate. I thought about this formula as the regression of
would involve
with kth line and column removed.
1) If it has any practical implication on correlation matrices, which can be put in the form
2) If it could give hindsight into linear regression coefficients that are traditionally given by :
3) If it can add to the general linear regression anatomy formula where the regression coefficient for the kth variable is given by :
1 November, 2019 at 5:37 pm
Anonymous
In case in equation (1), the denominator is zero (.i.e the i-th eigenvalue has a multiplicity bigger than 1), It seems in such case the formula does not allow to derive eigenvectors.
12 November, 2019 at 5:47 pm
Terence Tao
Yes, but this would be expected in any case, since when an eigenvalue occurs with multiplicity then the eigenvectors are not determined uniquely, even after allowing for rotation by a phase and normalising the eigenvector to be of unit length.
13 November, 2019 at 2:18 pm
Michael Nielsen
I wonder if there’s a modification of the result giving an expression for the projector onto the eigenspace in this case?
13 November, 2019 at 2:24 pm
Michael Nielsen
Incidentally, on Twitter Manjari Narayan just pointed out to me that Lemma 2 seems to appear in a 2014 paper of Van Mieghem: https://twitter.com/NeuroStats/status/1194741145177223169
13 November, 2019 at 4:34 pm
Terence Tao
Thanks for this link! Yes, this does seem to be the same identity (and the author here specifically states that it has been discovered a couple times in the past but never successfully publicised to a wider audience). As far as I can tell this particular preprint was never published either – it seems for some reason that this particular identity just has a tough time trying to become known in the literature. (It’s at times like this that I wish we had a good semantic search engine for mathematics – I am not sure how I would have discovered this preprint other than by publishing our own preprint and waiting for someone to notice the connection.)
13 November, 2019 at 5:16 pm
Anonymous
Actually, it is possible you would not have discovered this preprint by publishing your own preprint without the Quanta article. :-)
13 November, 2019 at 5:42 pm
Michael Nielsen
I’m glad it’s getting this publicity. I’ve always had the vague sense there should be some geometric sense to the components of eigenvectors, but didn’t know what it was. Now I do!
14 November, 2019 at 10:35 am
Anonymous
Eigenvectors and eigenvalues. May be useful ?https://www.youtube.com/watch?v=PFDu9oVAE-g
13 November, 2019 at 4:30 pm
Terence Tao
One can write down a formula, but it is messy; it involves the determinants of off-diagonal minors of
, which cannot be computed purely from the eigenvalues of the minors of
as off-diagonal minors of
are no longer multiples of the identity matrix.
13 November, 2019 at 6:02 pm
Manjari Narayan
I stumbled into Mieghem’s results and other similar ones while trying to create a custom measure of network centrality using entries of the eigenvector. There is a similar interest in properties of eigenvector entries in the systems and control theory literature and the statistics literature on leverage scores and variable importance measures.
3 December, 2019 at 11:18 pm
Guoqiang Wan
My name is Guoqiang Wan.I am from China. I’ve heard a lot about your good reputation. You have good character and advanced knowledge. I’ve also heard that you are especially good at cooperating with people. Because my English level is limited, My paper can’t be published. But I think my method is correct. You’re a master of mathematics, I think you will understand my proof. My email is 408073346@qq.com.I hope to receive your reply as soon as possible in order to deliver my paper.
13 November, 2019 at 1:52 pm
Anonymous
Why do you say that eigenvectors are determined by eigenvalues? For example, for symmetric matrices you still do not know n-squared plus or minus signs of the coordinates. Isn’t finding the signs almost as hard to finding eigenvectors themselves?
13 November, 2019 at 4:32 pm
Terence Tao
The title is indeed an oversimplification (it seemed to convey the essence of the result more succinctly than “norm square of coefficients of eigenvectors from eigenvalues”). The second sentence of the abstract is intended to clarify the sense in which we relate eigenvectors and eigenvalues.
15 November, 2019 at 4:11 am
s1291
For a semantic search engine, try to use: https://zbmath.org/formulae/
15 November, 2019 at 1:46 pm
Terence Tao
The problem is that a single identity will appear in very different equivalent forms in the literature, due to a combination of variation in notation and different ways to algebraically rearrange the identity, and so no single regular expression (or other similar device in modern search engines) can currently capture an equivalence class of a given identity, or even to guess when two identities are close to each other. For instance, the forms of the current identity that I am aware of in the literature are described in radically different ways:
* [Denton-Parke-T.-Zhang 2019]
* [Forrester-Zhang 2019]
* [van Mieghem 2014]
* [Cvetkovic-Rowlinson-Simic 2007]
* [Hagos 2002]
* [Baryshnikov 2001]
* [Mukherjee-Datta 1989]
* [Thompson-McEnteggert 1968]
It is not too difficult to mathematically derive any of these identities from the others, after one unpacks all the notation and performs some standard linear algebraic manipulations, but I don’t see how this could be done automatically by a search engine.
15 November, 2019 at 9:54 am
lostinio (@lostinio)
Hello! I implemented your formula in numpy and found the results are exact up to 6-th position. That’s great. Is there any algorithmically simple way to recover the sign, after we found the norm of each component. Thank you.
15 November, 2019 at 1:19 pm
Terence Tao
This may not be the most optimal way to do things, but if one conjugates the original matrix
by some orthogonal matrix
, then the eigenvectors of the conjugation
are then the vectors
formed by applying the orthogonal matrix to the original eigenvectors
. So if one uses the identity twice, once for
and once for
, then one gets the magnitudes of the components of both
and
, and for various choices of
one could use this to determine the signs of the components of
. For instance if
is even one could make
a block-diagonal matrix with
copies of the rotation matrix
. This would give the magnitudes of
for even
, which when combined with the magnitudes of
would be enough information to determine the signs. Hopefully this only increases the numerical cost of this approach by a factor of 2 or so.
14 November, 2019 at 6:40 am
La física de los neutrinos inspira cómo calcular los autovectores de matrices hermíticas - La Ciencia de la Mula Francis
[…] las tres demostraciones en el blog de Terence Tao, “Eigenvectors from eigenvalues,” What’s new, 13 Aug 2019; cuando lo leí entonces no le presté mayor atención pues no tienen interés desde el punto de […]
14 November, 2019 at 8:20 pm
Michael Nielsen
On Twitter, Aram Harrow shares a nice proof related to your Cramer’s rule proof:
Let
and consider the special case of a zero eigenvalue. Then
. Cramer’s rule says the jj’th entry of the LHS is
. The result follows by taking the limit
.
The result for a general eigenvalue may be done similarly, or can be recovered by considering
.
I really like this way of thinking, since it’s all pretty much automatic once one thinks about
.
Ref: https://twitter.com/quantum_aram/status/1195185551667847170
15 November, 2019 at 12:43 am
Jon
We were deriving eigenvectors from eigenvalues in universsity math class back in the 90’s. How come this is now something new and revolutional?
15 November, 2019 at 2:11 am
Shay
It will take me a while to fully understand the math here, but I was wondering from an applied algorithmic complexity perspective if this approach can yield faster eigenvalue/eigenvector algorithms?
Additionally, does this result make the Inverse Iteration algorithm redundant?
https://en.wikipedia.org/wiki/Inverse_iteration
15 November, 2019 at 2:29 am
Cheng Wang
I found this corollary interesting and nonintuitive: If lambda is a repeated eigenvalue, then each minor matrix M_j of A would have lambda as an eigenvalue. There must be some elegant geometry explanation to this
15 November, 2019 at 2:45 am
Cheng Wang
This might be a potential way to reduce the multiplicity of eigenvalue by using the minor matrix in some cases.
15 November, 2019 at 9:30 am
Terence Tao
If
is a repeated eigenvalue of
, then the
-eigenspace of
is at least two dimensional, and in particular contains an eigenvector whose
component vanishes (since the hyperplane of vectors with vanishing
component has codimension one). Removing this zero component, we obtain an eigenvector of
with the same eigenvalue. The corollary is also a special case of the Cauchy interlacing inequalities.
18 November, 2019 at 10:53 am
Craig
How can one get a similar “eigenvectors from eigenvalues” formula in the paper when there are repeated eigenvalues?
18 November, 2019 at 11:53 am
Terence Tao
There is a variant identity in this case that we found in a 2002 paper of Hagos. If there is eigenvalue multiplicity
with some multiplicity
, then
where
is the characteristic polynomial of
, and
is the characteristic polynomial of
. In the multiplicity one case
one can recover the previous identity from this one by using L’Hopital’s rule. This generalized identity can also be easily obtained from a modification of the Cramer’s rule proof in this blog post.
15 November, 2019 at 3:45 am
Anonymous
could you write 3 examples for 3 lemma?
it’s hard for me to understand it.
Thanks~!
[Some examples are discussed in the final paragraph before Section 1 of the blog post. -T]
15 November, 2019 at 4:08 am
Eigenvectors from eigenvalues – GeekWay
[…] Peter Denton, Stephen Parke, Xining Zhang, and I have just uploaded to the arXiv the short unpublished note “Eigenvectors from eigenvalues”. This note gives two proofs of a general eige…Read More […]
15 November, 2019 at 4:21 am
Anonymous
vi,j can be positive or negative,
How can I make sure whether it is positive or negtive?
Thanks.
15 November, 2019 at 9:26 am
Terence Tao
A (real) unit eigenvector
is only determined up to sign: if
is an eigenvector, then so is
. So the sign
is ambiguous to begin with. The relative sign
between two different components
of
is not ambiguous in this fashion; there is a formula linking this to various determinants involving (off-diagonal) minors, but now the formula does not seem to be neatly expressible in terms of eigenvalues. (See the end of Section 3 of the blog post.)
15 November, 2019 at 4:34 am
Yiteng Hu
This result is very interesting. It reminds me of another observation in inverse spectral theory for Sturm-Liouville operators. We can find it in Levitan’s book
Inverse Sturm—Liouville Problems in 1987 at pages 64-67. Consider the Sturm-Liouville problems on finite interval [0,1] with two different separated boundary conditions, denote them by L_1 and L_2, then, the norming constants of one operator can read from the spectrum of L_1 and L_2, the formula is highly similar. I don’t know whether there is a similar result for inverse problems of Jacobi operators.
15 November, 2019 at 5:44 am
Yiteng Hu
I think the result from the inverse spectral theory are just the generalization of this n x n matrix to infinite dimension. For two sequences tends to infinity to be the spectrum of Sturm-Liouville problems, they must satisfy two conditions: interlacing property, asymptotics. For the n x n matrix, the eigenvalues of A and M_j also satisfy interlacing property.
15 November, 2019 at 6:08 am
Yiteng Hu
After writing this, I begin to wonder whether there is an inverse spectral theory for this n x n matrix situation: by the spectrum of A and one of M_j, to reconstruct this matrix. Since for the inverse Sturm—Liouville problems, by two spectrum or one spectrum and the corresponding norming constants, there is so called Gelfand-Levitan equation to recover the potential. Perhaps, there are already some results about this argument, I’m not sure.
15 November, 2019 at 5:33 am
Zhiyue Lu
I wonder what can we say about the non-hermitian matrix such as the transition probability rate matrix? Can we get nice ways to get its eigenvectors there as well?
[Yes: see the previous remark of Vassilis Papanicolaou in this comment thread -T.]
15 November, 2019 at 5:52 pm
Anonymous
It looks like they have just reinvented the wheel.
15 November, 2019 at 5:59 pm
yc
This can be related to evaluating the transition probability between two states in quantum mechanics. If we define
then
will oscillate at angular frequencies given by eigenvalues of
. Here
are used to label basis vectors in which
is not necessarily diagonal. Let us use
to label eigenvectors and eigenvalues of
.
If we carry out Laplace transform, we obtain
If we take the residue of
at any eigenvalue
, this will extract the projection of
and
onto the
eigenvector. More specifically,
15 November, 2019 at 6:07 pm
Anonymous
I think the equation (1) in linked paper is missing a symbol after B?
15 November, 2019 at 6:41 pm
Anonymous
https://www.sciencedirect.com/science/article/pii/0024379568900050
16 November, 2019 at 12:36 am
Sean O'Connor
There are problems with neural network research too.
The dot product as a linear associative memory in the context of the central limit theorem.
ReLU as a literal switch, meaning networks are switched systems of linear projections. Each switch decision is determined by looking at a simple equivalent dot product of the input vector.
The failure to incorporate efficient dot product algorithms such as the FFT or WHT where that can usefully be done.
https://github.com/S6Regen/Fixed-Filter-Bank-Neural-Networks
16 November, 2019 at 1:11 am
Anon313
Maybe this is too simplistic, but I think one way to understand why this is possible is to say that the diagonal eigenvalue matrix is one instance of a matrix with those eigenvalues, and its eigenvectors are simply the unit matrix. Then the question is how the complete set (equivalence class?) of matrices that have the same eigenvalues looks like. Then one has vector permutation and basis rotation as transposition operations that do not change the eigenvalues (maybe thats all?). Then these identyties are expressing projection relations between M and A in these rotated and permuted matrices .
16 November, 2019 at 3:25 am
J. M.
Let me add a little note, which may or may not be ultimately useful in relation to these results. In Beresford Parlett’s now classical book The Symmetric Eigenvalue Problem, there is a result he ascribes to Paige relating the square of the magnitude of an eigenvector component with the characteristic polynomials of submatrices for a symmetric tridiagonal matrix, evaluated at the corresponding eigenvalue. The possible relevance of this is that it is well-known that any Hermitian matrix is (unitarily) similar to a symmetric tridiagonal matrix. I presume there is a way to relate these results to the results in the arXiv preprint.
16 November, 2019 at 5:29 am
Greg Coxson
I would like to see a short paper extending the result to the non-Hermitian case.
16 November, 2019 at 7:34 am
Yanda Jiang
So, this method could calculate eigenvectors given eigenvalues are known. And the value of it is we don’t need all information of original matrix and still be able to get what we want. However, how could we get eigenvalues without original matrix? Plz correct me where I am wrong.
16 November, 2019 at 9:09 am
H Zhao
Dear Terence, have you a practical way to apply the new equation for eigenvectors to eigenvalues of infinite square matrix? Dr. H Zhao (univ of St. Andrews)
16 November, 2019 at 12:31 pm
FranklyWrong
Reblogged this on Yourong Frank WANG and commented:
… Something whose importance only reblogging can be commensurate
16 November, 2019 at 12:43 pm
Alan Edelman
The result can essentially be found in our beta ensembles paper [https://arxiv.org/abs/math-ph/0206043] from 2002.Like J.M. (see the note earlier today), I also found the key formula in Beresford Parlett’s book (Theorem 7.2.1) that may be traced to Chris Paige’s thesis [https://pdfs.semanticscholar.org/48ed/e1ea2ad4a079c3d7386e97b6635c58544170.pdf] (8.12) on page 107. Our formulation of Paige’s result may be found in Equation (15) of the beta ensembles paper. The other observation that we made is that tridiagonalizing doesn’t change the relevant eigenvector component. This is mentioned, for example, in the proof of Corollary 2.2 of the beta ensembles paper.What is interesting is that Paige himself on page 105 refers back to the 1968 paper of Thompson and McEnteggert.
In other words, I had taken the result from Parlett’s book, who had taken it from Paige, who had taken it from Thompson and McEnteggert, which means that there was a linked chain right back to the 1968 source. Thus while search engines might or might not have worked, the academic version of “follow the money trail”, i.e. follow the publication trail, would have worked just fine.
In the classroom in a Random Matrix Theory class and also in a numerical computing class, I have demonstrated this formula with Julia [https://julialang.org/] many many times.
16 November, 2019 at 1:33 pm
Alan Edelman
Regarding my Julia classroom code, the following yields true
using LinearAlgebra
N = 10
A = rand(N,N)
A = A+A’
λ,V = eigen(A)
VV = zeros(N,N)
for i=1:N, j=1:N
𝓘 = setdiff(1:N,j)
VV[i,j] = prod(λ[i].-eigvals(A[𝓘,𝓘]))
end
VV ./= [prod(λ[i]-λ[k] for k∈1:N if k≠i) for i=1:N]
VV ≈ V’.^2
16 November, 2019 at 4:13 pm
J. M.
I would not be overly surprised if J. H. Wilkinson had noted a formula like this one somewhere.
16 November, 2019 at 1:20 pm
Anonymous
Regarding semantic search for math, Mohan Ganesalingam did some work on understanding natural mathematical language that might be relevant. He wrote a PhD thesis a few years ago that got some attention including from Tim Gowers, but then seems to have dropped into obscurity.
The thesis was on the author’s website for a while and it looked interesting, but it was taken off the site and put behind a paywall, making it effectively invisible to many of us.
16 November, 2019 at 1:55 pm
Rui
This identity is interesting in theory. I’d like to know more about its practical use. If we apply this result to infer a egienvector v of a n*n Hermitian matrix A, a three steps process is required. Firstly, all egivalues of A should be determined and it costs O(n^3),then we have to further determine all egienvalues of n (n-1)*(n-1) sub-matrices M_j, which costs O(n^4), and the third one is determining the signs of v_i. In contrast, the complexity of the traditional way is O(n^3). According to this, the computational idea is not optimal.
17 November, 2019 at 2:44 am
J. M.
Yes, your observation on the required computational effort is sound. In addition, numerical problems will arise if the Hermitian matrix (or a particular submatrix of it) has coincident (or nearly-coincident) eigenvalues. For people who want to do experiments about this, try the procedure out on the symmetric tridiagonal Wilkinson matrix, especially the larger cases.
17 November, 2019 at 5:06 am
yp
[3,2,4
2,0,2
4,2,3]
How about this matrix with repeated eigenvalues?A Counter-Example.
17 November, 2019 at 7:47 pm
Anonymous
In this textbook in year 1995:
https://book.douban.com/subject/1031551/
page 323th have already printed out this content.
17 November, 2019 at 7:53 pm
Anonymous
https://max.book118.com/html/2015/0228/12780311.shtm
page323 ,the lemma 3.1 has the almost the same formula.
But….in the last century,computer is not widespreaded…let alone semantic search engine.
18 November, 2019 at 2:52 am
良 王
earlier first, i am very exciting about this news stated that it is basic break in math from weChat, then go through the contents and the comments lead me to here, though it is not same as my first imagine, great thanks for authors who broadcasting this news to China, since this i learning much new knowledge about eigenvalues & eigenvectors and a new perspective for this two totally, thanks….
18 November, 2019 at 5:07 am
Carlo Beenakker
I may have found a 1993 appearance of this formula, https://mathoverflow.net/a/346313/11260
18 November, 2019 at 10:41 am
Terence Tao
Thanks for this!
We are in the process of completely rewriting the paper; at this point it seems more appropriate to present a historical survey of the various places in the literature the identity has appeared (the earliest relevant reference we have currently is a 1934 paper of Loewner, and there are at least 18 other appearances in the literature to our knowledge), and describe the various proofs, generalisations, and applications that we are now aware of. There is also an interesting sociology-of-science aspect to this story which is also worth recording, in particular how it seems that it was not feasible to integrate all the disparate references to this identity in the literature until a popular science article reporting on the identity created enough “common knowledge” to kick off what was effectively a crowdsourced effort to locate all these prior references.
18 November, 2019 at 11:48 am
liuyao
That’s most wonderful.
Though it’s perhaps not appropriate for you to say in the paper, I think how this has turned out has a great deal to do with the fact that your name is associated with it—not only for the initial inclusion in a popular science (online) magazine, but how it got everyone read it: this is one paper of Terry Tao that I could understand the statement of :)
18 November, 2019 at 11:54 am
Craig
The Quanta article got me to read it, even though I follow this blog and saw it (but ignored it) on this blog on it this summer. Popular science magazines play an important role in science.
20 November, 2019 at 8:15 am
Timothy Chow
Regarding integrating disparate references, I’m reminded of a paper by Miklós Ruszinkó, “On the upper bound of the size of the r-cover-free families,” J. Combin. Theory Ser. A 66 (1994), no. 2, 302–310. What he calls “r-cover-free families” was studied independently by several different communities (coding theory, group testing, combinatorics) under different names. I don’t know how Ruszinkó managed to track down all those different references. I myself independently rediscovered the concept and was going to call them “k-Sperner sets.” I got as far as having my paper accepted for publication before I somehow discovered Ruszinkó’s paper, which superseded everything I had proved. I was just in time to withdraw my paper from publication.
19 November, 2019 at 3:40 am
Arturo Portnoy
Looks like this identity could be useful for inverse spectral problems, where information about the eigenvalues and eigenfunctions is used to determine some parameter/coefficients of the operator/matrix.
19 November, 2019 at 7:14 am
Terence Tao
Yes, in fact we have recently learned that the identity is indeed used for inverse eigenvalue problems for Jacobi matrices, see Section 4.5 of this 2002 paper of Chu and Golub.
19 November, 2019 at 8:24 am
Chris Godsil
I’ve listed more appearances at https://mathoverflow.net/questions/346264/consequences-of-eigenvector-eigenvalue-formula-found-by-studying-neutrinos/346421#346421
19 November, 2019 at 11:07 am
Bill Province
How close does this come to resolving the Graph Reconstruction Conjecture (https://en.wikipedia.org/wiki/Reconstruction_conjecture)? I notice that we get the square of the eigenvector element values rather than the values themselves, so I don’t think that in and of itself, this resolves the reconstruction conjecture, but it gives some pretty convincing additional evidence!
In order for the reconstruction conjecture to be false in the face of this, there would need to be two graphs G1, G2 such that they are non-isomorphic, but share the same spectrum, and where the eigenvectors differ only in the choice of sign for the elements (and of course, where it’s not simply that we have one vector that is the negative of the other).
19 November, 2019 at 9:06 pm
Raphael
Due to the existence of cospectral mates, I am not sure that it really would resolve the conjecture.
20 November, 2019 at 10:24 am
Bill Province
Yet the results here are much stronger than merely being co-spectral. Being able to (nearly) completely recover the eigenvectors is something I had not seen before. Indeed, if the eigenvectors are recoverable — and we can properly associate the correct eigenvalue with each eigenvector — then we have recovered the entire matrix. I agree that we have not reached that point yet, and the existence of co-spectral non-isomorphic graphs must at least make us doubt, but this seems to be a really big step in that direction.
19 November, 2019 at 12:43 pm
J. M.
A look at L. F. Richardson’s paper (which I found through J. H. Wilkinson’s classical treatise) apparently uses a variant of the formula to iteratively improve an eigenpair.
20 November, 2019 at 10:56 am
Terence Tao
Hmm, this seems to be a little bit different. What seems to be happening here is that the author is iteratively applying linear operations of the form
for
to isolate the
component of a given vector and damp out the other components. This iteration will lead to spectral multipliers that have a form resembling that used in this identity (namely a ratio of two products of characteristic function type objects) but I’m not sure there is a deeper connection beyond this (for instance, there is no role in that paper played by minors).
20 November, 2019 at 11:44 am
Emanuele Rodolà
From a computational perspective, it might be actually useful in all cases where one only needs specific eigenvector components; in these cases you don’t need to compute the eigenvalues of all sub-matrices M_j, but only for a selection of sub-matrices. I can think of a few practical settings where it could come useful, e.g. in discrete geometry processing or graph analysis.
22 November, 2019 at 5:40 pm
Comments on an arXiv preprint authored by Terence Tao – Feng Qi's Academic Homepage & Blogs
[…] https://terrytao.wordpress.com/2019/08/13/eigenvectors-from-eigenvalues/#comment-528704 […]
22 November, 2019 at 8:47 pm
Eigenvectors and Eigenvalues | Delightful & Distinctive COLRS
[…] Resource: Terry Tao blog, Nov […]
23 November, 2019 at 7:56 pm
Margaret Stawiska-Friedland
Theorem 1 can be generalized to not necessarily Hermitian matrices as follows:
and let
. Let
be an eigenvalue of
of algebraic multiplicity
. It follows that the eigenspace corresponding to
is
-dimensional.
, and so
. This implies that
with
. Further, since
and
is an eigenvalue of
, we have
. Hence
. Similarly we show that
.
such that
,
. We have 
. Hence
. By Jacobi’s formula for derivative of the determinant,
, where
.
Let
By nullity-rank theorem,
There exists a unique
with
23 November, 2019 at 10:12 pm
Xiu Wu
Hello Mr.Tao, I want to ask that how to determine the +/- sign of the calculated elements of the eigenvectors.
24 November, 2019 at 3:35 am
Anonymous
Read the comments above.
30 November, 2019 at 1:19 am
Xiu Wu
Thanks, I found it in one of the comments, Mr.Tao gives a method of determining the signs.
24 November, 2019 at 7:53 pm
Ed
Hi, I am no math major, but I found this paper very interesting to read! I am reading the consistency check section of the paper, and I am not sure how to show “RHS of eq 8 is the n-1 symmetric function of the eigenvalues,S_{n-1}”.
30 November, 2019 at 5:15 pm
Eigenvectors from eigenvalues - Nevin Manimala's Blog
[…] by /u/BeverlyHillsBastet [link] […]
2 December, 2019 at 12:17 am
Anonymous
Some of the popular science articles claim that it’s easier to use a matrix’s eigenvalues than its eigenvectors, at least in context of the neutrino-related research in which this identity was discovered. However, at first glance, computing all eigenvectors using this identity seems to have greater computational complexity than existing methods (which, roughly, are O(n^3)).
Of course, this work will be relevant in particular contexts where the minor matrices’ eigenvalues are already known, or where other constraints are imposed that can simplify computation. But do you think that with some additional research, the formula can be used to improve on existing eigenvector estimation methods more generally?
2 December, 2019 at 9:23 am
Terence Tao
I agree that this identity is unlikely to be a superior method for computing eigenvectors for general matrices, but for special matrices where the characteristic polynomial of the matrix and its minors are relatively easy to compute, the identity appears to be useful. For instance, we have found a number of references in the literature where this identity was applied to tridiagonal matrices to help control the convergence rate of various numerical linear algebra algorithms such as the Rayleigh-Ritz method for computing eigenvectors. So here the identity is not directly used to compute eigenvectors, but it can be used to analyze a different algorithm for (approximately) computing these eigenvectors.
Another thing the identity highlights is that the (square of the) magnitude of an eigenvector component is proportional to the distance between the eigenvalue and the spectrum of a minor. So information about how the spectrum of minors interlace with the spectrum of the full matrix will tell us something about the localization or delocalization properties of eigenvectors, and conversely. This ought to be a useful tool, or at least a useful heuristic, in random matrix theory in which one is often interested in at least one of these two pieces of information, though I do not yet have a concrete use case for this (mostly because our current tools usually do not let us easily understand the coupling between the spectrum of a matrix and the spectrum of a minor).
3 December, 2019 at 9:47 am
Tim Campion
I’m confused by the statement of the identity — are we assuming that the eigenvalues $\lambda_i(A)$ are distinct?
If not, then the identity is hard for me to believe: for instance if $\lambda_1(A) = \lambda_2(A)$, then the identity seems to entail that $|v_{1,j}| = |v_{2,j}|$ for any choice of orthogonal unit vectors $v_1,v_2$ in the eigenspace corresponding to the eigenvalue $\lambda_1(A) = \lambda_2(A)$. But if, say, this eigenspace is spanned by the first two coordinate vectors $e_1,e_2$, then we could take $v_1 = e_1, v_2 = e_2$ and obtain a contradiction.
3 December, 2019 at 9:50 am
Tim Campion
Oh I see — if the eigenvalues are not distinct, then the product on the left hand side is zero, so my reasoning is incorrect.
3 December, 2019 at 8:34 pm
Eigenvectors from Eigenvalues: a survey of a basic identity in linear algebra | What's new
[…] Parke, Xining Zhang, and I have just uploaded to the arXiv a completely rewritten version of our previous paper, now titled “Eigenvectors from Eigenvalues: a survey of a basic identity in linear […]
4 December, 2019 at 9:47 pm
Gautam
In Remark 7 of the updated paper, it appears that Aram Harrow’s name is spelled wrong.
[This will be corrected in the next revision of the ms – T.]
6 December, 2019 at 3:13 pm
Adam Denchfield
I think I found another instance of proof/usage of a special case. In this paper (linked below) by Gaveau and Schulman, “Limited quantum decay”, Equations 2.1-2.6. If this is indeed an example of a special case, then I think this identity is used fairly commonly in physics, because this usage seems familiar.
https://iopscience.iop.org/article/10.1088/0305-4470/28/24/029/pdf
[Yes, this appears to be an independent discovery of Lemma 14 in the survey. We’ll add the reference to the next revision of the ms. -T]