Eigenvectors from Eigenvalues: a survey of a basic identity in linear algebra

3 December, 2019 in math.CO, math.HO, math.NA, math.RA, update | Tags: eigenvalues, eigenvectors, Peter Denton, Stephen Parke, Xining Zhang

Peter Denton, Stephen 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 algebra“. This paper is now a survey of the various literature surrounding the following basic identity in linear algebra, which we propose to call the eigenvector-eigenvalue identity:

Theorem 1 (Eigenvector-eigenvalue identity) Let ${A}$ be an ${n \times n}$ Hermitian matrix, with eigenvalues ${\lambda_1(A),\dots,\lambda_n(A)}$ . Let ${v_i}$ be a unit eigenvector corresponding to the eigenvalue ${\lambda_i(A)}$ , and let ${v_{i,j}}$ be the ${j^{th}}$ component of ${v_i}$ . Then

$\displaystyle |v_{i,j}|^2 \prod_{k=1; k \neq i}^n (\lambda_i(A) - \lambda_k(A)) = \prod_{k=1}^{n-1} (\lambda_i(A) - \lambda_k(M_j))$

where ${M_j}$ is the ${n-1 \times n-1}$ Hermitian matrix formed by deleting the ${j^{th}}$ row and column from ${A}$ .

When we posted the first version of this paper, we were unaware of previous appearances of this identity in the literature; a related identity had been used by Erdos-Schlein-Yau and by myself and Van Vu for applications to random matrix theory, but to our knowledge this specific identity appeared to be new. Even two months after our preprint first appeared on the arXiv in August, we had only learned of one other place in the literature where the identity showed up (by Forrester and Zhang, who also cite an earlier paper of Baryshnikov).

The situation changed rather dramatically with the publication of a popular science article in Quanta on this identity in November, which gave this result significantly more exposure. Within a few weeks we became informed (through private communication, online discussion, and exploration of the citation tree around the references we were alerted to) of over three dozen places where the identity, or some other closely related identity, had previously appeared in the literature, in such areas as numerical linear algebra, various aspects of graph theory (graph reconstruction, chemical graph theory, and walks on graphs), inverse eigenvalue problems, random matrix theory, and neutrino physics. As a consequence, we have decided to completely rewrite our article in order to collate this crowdsourced information, and survey the history of this identity, all the known proofs (we collect seven distinct ways to prove the identity (or generalisations thereof)), and all the applications of it that we are currently aware of. The citation graph of the literature that this ad hoc crowdsourcing effort produced is only very weakly connected, which we found surprising:

The earliest explicit appearance of the eigenvector-eigenvalue identity we are now aware of is in a 1966 paper of Thompson, although this paper is only cited (directly or indirectly) by a fraction of the known literature, and also there is a precursor identity of Löwner from 1934 that can be shown to imply the identity as a limiting case. At the end of the paper we speculate on some possible reasons why this identity only achieved a modest amount of recognition and dissemination prior to the November 2019 Quanta article.

39 comments

Comments feed for this article

3 December, 2019 at 7:34 pm

Anonymous

in page 9, remark 7, the name is Aram not Adam.

[Thanks, this will be corrected in the next revision of the ms. -T]

3 December, 2019 at 8:40 pm

kodlu

A commendable effort to bring all these related identities together.

3 December, 2019 at 8:44 pm

kodlu

Is there supposed to be an image (of a graph) after “The citation graph of the literature that this ad hoc crowdsourcing effort produced is only very weakly connected, which we found surprising:”

All that is visible in my browser is “???”

[Corrected, thanks – T.]

3 December, 2019 at 9:26 pm

Raphael

Really cool! Congratulations, I like that you mention chemical GT and the citation graph really rocks. I will consider something like that for my publications in similar cases (minireview by rediscovery) as well!

4 December, 2019 at 12:23 am

Do $PI$-algebras have application to this and vice versa?

4 December, 2019 at 2:42 am

Jochen Voss

The Karl Löwner (1934) references in the article on arXiv is shortened to LӞ4, which looks odd. Probably the surname should be spelled L{\”o}wner instead of L\”owner in bibtex?

[Thanks, this will be corrected in the next revision of the ms. -T]

4 December, 2019 at 6:02 am

3 GiftedNova

Is this an accidental calculation on how neutrinos change resulting in the formula or theorem describing the relationship between eigenvectors and eigenvalues

4 December, 2019 at 6:47 am

Mark Meckes

This is truly a service to the scientific community. Linear algebra, being as it is central to an extremely broad swath of fields of pure and applied mathematics, seems especially prone to this sort of independent rediscovery of useful facts that lie just a bit beyond the level of introductory textbooks. I wasn’t at all surprised by the tree-like nature of the citation graph.

Although it’s not quite the same phenomenon, I was reminded of a talk I heard Barry Simon give (see e.g. here) on a widely unnoticed proof of the main result from the same paper of Löwner that you mentioned.

4 December, 2019 at 1:18 pm

Anonymous

Another example is Heegner’s solution (from 1952) of the class number 1 problem (which unfortunately remained unnoticed for more a decade)

4 December, 2019 at 7:28 am

[Terence Tao's blog] Eigenvectors from Eigenvalues: a survey of a basic identity in linear algebra - Nevin Manimala's Blog

[…] by /u/Valvino [link] […]

4 December, 2019 at 7:58 am

Andrew Krause

I especially enjoyed the sociology of science of all of this. I constantly feel that there must be better ways to organize the enormous enterprise that is research mathematics, but any such organization will undoubtedly have flaws.

A few typos involving repeated words in the preprint: “for for” appears at the end of Section 5, and “the the” at the end of Section 4.

[Thanks, this will be corrected in the next revision of the ms. -T]

4 December, 2019 at 8:57 am

liuyao

A small complaint: the formula is only useful when lambda_i is simple (or else both sides vanish, by Cauchy interlacing), so why not just write it in quotient form? (The only argument may be that the identity does not rely on Cauchy interlacing.)

Also, what is the current state for “fingerprint databases for mathematical theorems”? The paper [BT13] dates from 2013, and one could at least add https://www.lmfdb.org/ to the list.

Not entirely the same, but getting the *statements* in (one agreed-on) proof assistant could be an important step: https://formalabstracts.github.io/

4 December, 2019 at 9:31 am

Terence Tao

The non-quotiented form has the advantage of being valid for all diagonalizable matrices taking values in an arbitrary commutative ring (not just real or complex numbers), as it avoids any requirement of invertibility of any of the quantities involved. (For this generalization one needs to distinguish the left eigenvectors from the right eigenvectors, see equation (11) in the new version of the paper.) There are also variants of the identity that are non-degenerate in the case of multiple eigenvalues; see for instance (15) of the new version of the paper.

The non-quotiented form also has a slightly non-trivial corollary: if $\lambda_i(A)$ lies in the spectrum of $M_j$ , then either $v_{i,j}$ vanishes or $\lambda_i(A)$ is a repeated eigenvalue. I don’t know of a short direct way to see this implication (although the converse implications are not difficult, see consistency checks (iv), (v) in the new version of the paper).

Unfortunately I do not know of any followup work to [BT13], but perhaps there are other readers of this blog who may be aware of more recent developments in this area.

4 December, 2019 at 2:49 pm

Kristoffer Varholm

There is a typo on the first line of page 7. Eigenvectors should be eigen_values_.

[Thanks, this will be corrected in the next revision of the ms – T.]

4 December, 2019 at 3:44 pm

arch1

Typo, penultimate sentence: “…we are not able to guarantee that there is *not* an even earlier reference in the literature…”

[Thanks, this will be corrected in the next revision of the ms – T.]

4 December, 2019 at 4:07 pm

Max

The meaning of $\lambda_k(M_j)$ seems quite obscure to me. For a matrix $B = M_j$ different from A, $\lambda_k(B)$ is just any of the eigenvalues of B (and in addition you have a different B for each j). These are a priori totally unrelated with the { \lambda_k(A) }, even the range of the indices is not the same since the size of B is not that of A.

4 December, 2019 at 4:18 pm

Max

Oops, sorry, please ignore the comment, I now understand that the product is taken over all n-1 eigenvalues of M_j, so it does not matter in which order they are taken. (Yet \lambda_k(M_j) is still ill defined /per se/ and a notation like $\prod_{\mu \in \spec M_j} …$ would IMHO be less confusing.)

6 December, 2019 at 6:28 am

Anonymous

Dear Pro.Tao,
We always trust your ability in solving a famous problem which was 3 centuries ago. Nearly end the year. Super speed! Come on! Only Sir understands our crazy comments! Sweet fruits are waiting for you after you spend a lot of time care , water, fertilizer your lovely tree.

6 December, 2019 at 4:19 pm

Alex Jones

Terry, with all due respect, may I ask why you were an author on the previous paper? I feel like there is a big “P vs NP” phenomenon going on with this identity. I think the big achievement (I’m tempted to say the “sole achievement”) is *finding* the identity rather than proving it once provided. I think you should have been thanked in the acknowledgments section rather than have been a coauthor.

7 December, 2019 at 8:02 am

Terence Tao

There are two previous papers, listed as [DPZ19] and [DPTZ19] in the references to the current version. [DPZ19] is where the identity was (once again) discovered but not proven; I am not an author of that paper. The now-superseded preprint [DPTZ19] consists of little more than two proofs of the identity, which I provided. (One of these proofs we now know to have been discovered multiple times already in the literature, but the other proof appears to be new.)

The four of us did discuss whether to instead add an appendix to [DPZ19] containing at least one of the proofs, but eventually decided on a standalone preprint to draw attention on the identity outside of the neutrino physics community. Needless to say this goal was achieved to a somewhat greater extent than we expected.

7 December, 2019 at 1:58 pm

Stephen Parke

As P of [DPZ19] and [DPTZ19], I fully concur with TT response to this comment.

6 December, 2019 at 10:00 pm

Anonymous

By n-1 th symmetric function you probably meant the n-1 th elementary symmetric function on page 4.

[Thanks, this will be corrected in the next revision of the ms. -T]

7 December, 2019 at 11:49 pm

aquazorcarson

Also the summation is perhaps a product on the next line. Nice observation by the way.

[Thanks, this will be corrected in the next revision of the ms. -T]

6 December, 2019 at 10:13 pm

Darij Grinberg

Kudos for doing the thankless literature review work everyone has been shying away from. Everyone knows the linear algebra literature is self-similar like a fractal, but actually playing the memory game is not something people usually find the stomach for.

A trivial typo: “Sbastien” -> “Sébastien” in [GKV]. This is likely a mojibake issue in your bibliography.

Anyway, here is another proof of the result, which I believe to be more general than the ones in the paper, as it uses neither the base field being a field (let alone the complex numbers), nor diagonalization (only an eigenvector of $A$ and one of $A^T$ ), nor any sort of normality. (Feel free to include it!)

Here is the general form that I’ll be proving:

=== BEGIN THEOREM ===

THEOREM 1: Let $R$ be a commutative ring. Let $A$ be an $n$ -by- $n$ -matrix over $R$ . Let $\lambda \in R$ . Let $v = (v_1, v_2, \dots, v_n)^T$ and $w = (w_1, w_2, \dots, w_n)^T$ be two column vectors in $R^n$ such that $Av = \lambda v$ and $w^T A = \lambda w^T$ . Fix $j \in \{1, 2, \dots, n\}$ , and let M_j be the $(n-1)$ -by- $(n-1)$ -matrix obtained from $A$ by removing row $j$ and column $j$ . Then,

$\displaystyle v_j w_j p_A'(\lambda) = (w^T v) p_{M_j}(\lambda).$

Here, $p_S$ denotes the characteristic polynomial of a matrix $S$ .

=== END THEOREM ===

This is probably closest to the equality (4) in arXiv:1908.03795v2, but the use of $v$ and $w$ (as opposed to a single $v$ ) is from Remark 4. The eigenvectors $v$ and $w$ are not connected to each other apart from corresponding to the same eigenvalue; but there is a fudge factor $w^T v$ on the right hand side that ensures homogeneity of the equality.

The first step to proving Theorem 1 is to simplify it a lot by replacing $A$ by $A - \lambda I$ . (Not my idea; you do the same in the last paragraph of §2.5.) Thus, Theorem 1 reduces to the following simpler fact:

=== BEGIN THEOREM ===

THEOREM 2: Let $R$ be a commutative ring. Let $A$ be an $n$ -by- $n$ -matrix over $R$ . Let $v = (v_1, v_2, \dots, v_n)^T$ and $w = (w_1, w_2, \dots, w_n)^T$ be two column vectors in $R^n$ such that $Av = 0$ and $w^T A = 0$ . Fix $j \in \{1, 2, \dots, n\}$ . For each $k \in \{1, 2, \dots, n\}$ , let $M_k$ be the $(n-1)$ -by- $(n-1)$ -matrix obtained from $A$ by removing row $k$ and column $k$ . Then,

$\displaystyle v_j w_j \sum_{k=1}^n \det(M_k) = (w^T v) \det(M_j).$

=== END THEOREM ===

This is what Theorem 1 boils down to after replacing $A$ by $A - \lambda I$ , because $p_A'(0) = \sum_{k=1}^n \det(M_k)$ .

Here is the first lemma that we will use to prove this:

=== BEGIN LEMMA ===

LEMMA 3: Let $R$ be a commutative ring. Let $A$ be an $n$ -by- $n$ -matrix over $R$ . Let $w = (w_1, w_2, \dots, w_n)^T$ be a column vector in $R^n$ such that $w^T A = 0$ . Fix $j, k \in \{1, 2, \dots, n\}$ . Then,

$w_j (\mathrm{adj} A)_{i, k} = w_k (\mathrm{adj} A)_{i, j}$

for every $i \in \left\{ 1,2,\ldots,n \right\}$ .

=== END LEMMA ===

Here, $U_{i, j}$ denotes the $(i, j)$ -th entry of a matrix $U$ .

PROOF OF LEMMA 3: Let $B$ be the $n$ -by- $n$ matrix obtained from $A$ by multiplying the $j$ -th row by $w_j$ and multiplying the $k$ -th row by $w_k$ . It is thus easy to see that

$w_j (\mathrm{adj} A)_{i, k} = (\mathrm{adj} B)_{i, k}$

and

$w_k (\mathrm{adj} A)_{i, j} = (\mathrm{adj} B)_{i, j}.$

Hence, it remains to prove that $(\mathrm{adj} B)_{i, k} = (\mathrm{adj} B)_{i, j}$ .

But we assumed $w^T A = 0$ , so that

$0 = w^T A = w_1 (\hbox{1-st row of } A) + w_2 (\hbox{2-nd row of } A) + \dots + w_n (\hbox{n-th row of } A).$

Thus, $w_j (\hbox{j-th row of }A) + w_k (\hbox{k-th row of }A)$ is a linear combination of the remaining rows of $A$ . In view of how $B$ was defined, we can rewrite this as follows: $(\hbox{j-th row of } B) + (\hbox{k-th row of } B)$ is a linear combination of the remaining rows of $B$ . From this, it is easy to derive that $(\mathrm{adj} B)_{i, k} = (\mathrm{adj B})_{i, j}$ by simple row operations (indeed, the matrix whose determinant is $(\mathrm{adj} B)_{i, k}$ is obtained from the matrix whose determinant is $(\mathrm{adj} B)_{i, j}$ by some simple row operations). Lemma 3 is proved (not as neatly as I hoped for, but I suspect you can simplify the argument).

Here is a column analogue of Lemma 3:

=== BEGIN LEMMA ===

LEMMA 4: Let $R$ be a commutative ring. Let $A$ be an $n$ -by- $n$ -matrix over $R$ . Let $v = (v_1, v_2, \dots, v_n)^T$ be a column vector in $R^n$ such that $Av = 0$ . Fix $j, k \in \{1, 2, \dots, n\}$ . Then,

$\displaystyle v_j (\mathrm{adj} A)_{k, i} = v_k (\mathrm{adj} A)_{j, i}.$

=== END LEMMA ===

PROOF OF LEMMA 4: Analogous to Lemma 3. (Or, even easier, just apply Lemma 3 to A^T instead of A.)

Combining Lemma 3 with Lemma 4 quickly yields the following:

=== BEGIN COROLLARY ===

COROLLARY 5: Let $R$ be a commutative ring. Let $A$ be an $n$ -by- $n$ -matrix over $R$ . Let $v = (v_1, v_2, \dots, v_n)^T$ and $w = (w_1, w_2, \dots, w_n)^T$ be two column vectors in $R^n$ such that $Av = 0$ and $w^T A = 0$ . Fix $j, k \in {1, 2, \dots, n}$ . Then,

$\displaystyle v_j w_j \mathrm{det}(M_k) = v_k w_k \mathrm{det}(M_j)$

(with notations $M_k$ and $M_j$ as in Theorem 2).

=== END COROLLARY ===

PROOF OF COROLLARY 5: Lemma 3 (applied to $i = k$ ) yields

$\displaystyle w_j (\mathrm{adj} A)_{k, k} = w_k (\mathrm{adj} A)_{k, j}.$

Lemma 4 (applied to $i = j$ ) yields

$\displaystyle v_j (\mathrm{adj} A)_{k, j} = v_k (\mathrm{adj} A)_{j, j}.$

Multiplying the first of these two equalities by $v_j$ and the second by $w_k$ , we obtain

$\displaystyle v_j w_j (\mathrm{adj} A)_{k, k} = v_j w_k (\mathrm{adj} A)_{k, j} = v_k w_k (\mathrm{adj} A)_{j, j}.$

In view of $(\mathrm{adj} A)_{k, k} = \mathrm{det}(M_k)$ and $(\mathrm{adj} A)_{j, j} = \mathrm{det}(M_j)$ , we see that we have obtained precisely the claim of Corollary 5.

PROOF OF THEOREM 2: We have

$\displaystyle v_j w_j \sum_{k=1}^n \mathrm{det}(M_k)$

$\displaystyle = \sum_{k=1}^n v_j w_j \mathrm{det}(M_k)$

$\displaystyle = \sum_{k=1}^n v_k w_k \mathrm{det}(M_j)$ (by Corollary 5)

$\displaystyle = (w^T v) \mathrm{det}(M_j).$

This proves Theorem 2.

[Thanks, we will mention this in the next revision of the ms -T.]

19 December, 2019 at 9:59 am

Darij Grinberg

The handwavy nature of my proof of Lemma 3 in the parent comment kept ruffling my feathers, so here is an alternative proof.

SECOND PROOF OF LEMMA 3. WLOG assume that $j \neq k$ , since otherwise the claim is obvious. Let $c$ be the column vector in $R^n$ whose $j$ -th entry is $w_k$ , whose $k$ -th entry is $-w_j$ , and whose all remaining entries are $0$ . Then, the claim of Lemma 3 is easily seen to be equivalent to the matrix equality $w^T \left( \mathrm{adj} A \right) c = 0$ .

At this point, I want to recall a known fact, but as usual the only place where I remember it from is my own writeup (Theorem 5.14 in https://www.cip.ifi.lmu.de/~grinberg/algebra/trach.pdf ): The adjugate of a square matrix can be written as a polynomial in said matrix. Applying this to $A$ , we conclude that $\mathrm{adj} A$ can be written as a polynomial in $A$ . Hence, in order to prove that $w^T \left( \mathrm{adj} A \right) c = 0$ , it suffices to show that $w^T A^i c = 0$ for each nonnegative integer $i$ . But this is easy: For $i > 0$ , this follows from $w^T A = 0$ , but for $i = 0$ , this follows from $w^T c = 0$ (which is checked by direct verification). And Lemma 3 is proved again.

27 December, 2019 at 1:57 am

Darij Grinberg

PS (or PPS). The “known fact” I used in the second proof of Lemma 3 above has a MathOverflow thread devoted to it: https://mathoverflow.net/questions/32133/expressing-adja-as-a-polynomial-in-a

19 February, 2021 at 5:32 am

Darij Grinberg

The “second proof of Lemma 3” I gave above is wrong. Sorry! (Thanks Ion Zaballa for spotting the error.)

8 December, 2019 at 7:35 am

Zubereitung Inhalt

Dear Professor Tao:

I am the guy who pointed out Löwner’s paper on Quanta. The version as stated by Löwner is very useful — see pp. 224–226 in Demmel’s Applied Numerical Linear Algebra. Your version, on the other hand, is just a consequence of the fact (see Wikipedia) that if an $n \times n$ matrix $A$ has rank $n-1$ , then $\mathrm{adj}(A)$ has rank $1$ and $\mathrm{adj}(A) = \alpha xy^T$ where $Ax =0$ , $A^T y = 0$ . Apply this to $A - \lambda I$ for a simple eigenvalue $\lambda$ and left/right eigenvectors $y$ and $x$ .

8 December, 2019 at 10:59 am

Zubereitung Inhalt

Dear Professor Terry:

Do you think something like a LaTeX-aware search engine for math papers would be a good idea in these kinds of situations? Also do you think that there should be an effort to revive tricki.org?

8 December, 2019 at 1:11 pm

Michael Ruxton

https://www.irishtimes.com/news/science/particle-physics-gives-maths-potentially-powerful-new-tool-1.4095391

9 December, 2019 at 7:15 pm

Margaret Stawiska-Friedland

The argument I posted on November 23, 2019 as a comment under the previous post on eigenvectors from eigenvalues can be made to work for multiple eigenvalues, at least for matrices over the field $\mathbb{K}$ of either real of complex numbers.
Let $A$ be an $n \times n$ matrix over $\mathbb{K}$ . Let $P(\lambda)=\det(A-\lambda I)$ be the characteristic polynomial of $A$ .
For eigenvectors of $A \in M_{n \times n}(\mathbb{K})$ corresponding to an eigenvalue $\lambda$ with geometric multiplicity $k \geq 1$ we get the following expressions, provided that the algebraic multiplicity also equals $k$ : Let $\mathbf{v}_1,..\mathbf{v}_k$ be a basis of eigenvectors corresponding to $\lambda$ . Let $\mathbf{w}_1,...,\mathbf{w}_k$ be a basis of eigenvectors of $A^T$ such that $\mathbf{w}_j^T\mathbf{v}_i=\delta_{ij}$ (here we use the assumption on algebraic multiplicity also being $k$ ). Let $\mathbf{v}=\mathbf{v}_1 \wedge ...\wedge \mathbf{v}_k$ and $\mathbf{w}=\mathbf{w}_1 \wedge ...\wedge \mathbf{w}_k$ . Then $\frac{(-1)^k}{k!}P^{(k)}(\lambda)\mathbf{v}\mathbf{w}^T=\text{adj }_k(A-\lambda I)$ .
This is a matrix equality; I do not attempt to rewrite it entrywise.

Proof:
For $1 \leq k \leq n$ the $k$ -th adjugate of $A$ , denoted by $\text{adj}_k\; A\in \mathbb{K}^{{n\choose k}\times {n\choose k}}$ , is defined as follows:
The entry $(\{1\le i_1<\cdots<i_k\le n\}, \{1\le j_1<\cdots<j_k\le n\})$ is $(-1)^{\sum_{l=1}^k i_l+j_l}$ times the $k \times k$ -minor of $A$ obtained by deleting the rows $i_1,\ldots,i_k$ and columns $j_1,\ldots,j_k$ . Note that the usual adjugate $\text{adj }A$ is $\text{adj}_1\; A$ . We will also use
the $k$ -th compound matrix $C_k(A)$ , which is the matrix in $\mathbb{K}^{{n\choose k}\times {n\choose k}}$ whose entries are the $k\times k$ minors of $A$ arranged in the lexicographical order. (If $A$ represents a linear transformation $T: V \to V$ , then $C_k(A)$ represents $\bigwedge^k T$ in suitable bases.) . It is straightforward to show that that $\textrm{adj}_k\; A=C_k(\Delta_n) C_{n-k}(A) C_k(\Delta_n)^T$ , where $\Delta_n\in\mathbb{K}^{n\times n}$ is the matrix whose $(i,j)$ entry is $(-1)^i \delta_{i(n-j+1)}$ .

The Laplace expansion along minors implies
the following identities ( $1 \leq k \leq n$ ):

$\displaystyle C_k(A)\textrm{adj}_k\; A=(\textrm{adj}_k\; A)C_k(A)=(\det A) I_{n\choose k}.$

From the identity $\text{adj}_k\; A=C_k(\Delta_n) C_{n-k}(A) C_k(\Delta_n)^T$ it follows that $\text{rank } \text{adj}_k\; A=1$ if $\text{rank }A=n-k$ . Hence, if the nullity of $A-\lambda I)$ is $k$ , we can represent $\text{adj}_k(A-\lambda I)$ as $adj_k(A-\lambda I) = \mathbf{x}\mathbf{y}^T$ , where $\mathbf{x}$ and $\mathbf{y}$ are vectors in $\mathbb{K}^{\binom {n}{r}} \setminus \{0\}$ . From the relation between the compound and adjugate matrix it follows that $C_k(A-\lambda I)\mathbf{x} = 0$ and $C_k(A-\lambda I)^T\mathbf{y} = 0$ . Let now $\mathbf{v_1}, ...,\mathbf{v}_k$ be a basis of eigenvectors for $(A-\lambda I)$ . Then $\mathbf{v}_1 \wedge ...\wedge \mathbf{v}_k$ is an eigenvector for $C_k(A)$ corresponding to the eigenvalue $\lambda^k$, which has geometric multiplicity $1$ .
We can take $\mathbf{v}=\mathbf{v}_1 \wedge ...\wedge \mathbf{v}_k$ as a basis for $\text{ker} C_k(A-\lambda I)$ , so $\mathbf{x}=\alpha \mathbf{v}, \ \alpha \ne 0$ . Let $\mathbf{u}:=(1/\alpha)\mathbf{y}$ . Then $adj_k(A-\lambda I) = \mathbf{v}\mathbf{u}^T$ . If the algebraic multiplicity of $\lambda$ as the eigenvalue of $A$ is also $k$ , there exist $\mathbf{w}_1,..., \mathbf{w}_k \in \text{ker} (A-\lambda I)^*$ such that $\mathbf{w}_i(\mathbf{v}_j) =\delta_{ij}$ Taking $\mathbf{w}=\mathbf{w}_1 \wedge...\wedge \mathbf{w}_k$ we get $\mathbf{w} \in \mathbb{K}^{\binom {n}{r}}\setminus \{0\}$ such that $C_k(A-\lambda I)^T\mathbf{w}=0$ , $\mathbf{w}^T\mathbf{v}=1$ . We then have $c\mathbf{w}^T=\mathbf{u}^T$
with $0 \ne c$ and $c = c\mathbf{w}^T\mathbf{v}=\mathbf{u}^T\mathbf{v}= \text{tr }\text{adj}_k(A-\lambda I)$ . Hence $\text{adj}_k(A-\lambda I)=\mathbf{v}\mathbf{u}^T=\text{tr }\text{adj}_k(A-\lambda I)\mathbf{v}\mathbf{w}^T$ .

We can replace $\text{tr }\text{adj}_k(A-\lambda I)$ by the suitably scaled $k$ -th derivative of $P$ evaluated at $\lambda$ thanks to the following formula: for $X,Y$ arbitrary matrices in $M_{n \times n}$ , $\det (X+Y) =\sum_{k=0}^n \text{tr } (\text{adj}_k X \; C_k(Y))$ , proved as Theorem 4.1 in: Prells, Uwe; Friswell, Michael I.; Garvey, Seamus D. (2003-02-08). “Use of geometric algebra: compound matrices and the determinant of the sum of two matrices''. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences. 459 (2003): 273-285. For the purpose of finding the appropriate differential expression, the formula is applied to the matrices $X=(A-\lambda I)$ and $Y=tI$ , and then we take $t \to 0$ in $\mathbb{K}$ (polynomials are identified with polynomial functions, which are smooth).

The assumption of the algebraic multiplicity of the eigenvalue being equal to its geometric multiplicity can be justified by the following easy result:

Let $V$ be an $n$ -dimensional vector space over $\mathbb{K}$ and let $V'$ be its dual space. Let $U \subset V, \ W \subset V'$ be two $k$ -dimensional subspaces. TFAE: (i) $U \cap W^\perp =\{0\}$ ; (ii) $U^\perp \cap W =\{0\}$ ; (iii) There exist bases $\{u_1,...,u_k\}$ , $\{f_1,...,f_k\}$ in $U$ and $W$ , respectively, such that $f_j(u_i)=\delta_{ij}, \ i,j=1,...,k$ .

11 December, 2019 at 5:57 pm

Some Light Winter Break Mathematical Reading – Advice and Resources for Math Graduate Students

[…] be described by a formula involving only the eigenvalues of the matrix and certain submatrices. Tao’s blog has a concise description of the precise statement. Their preprint is worth a look too: after […]

11 December, 2019 at 6:06 pm

Some light winter break math reading – Advice and Resources for Math Graduate Students

[…] described by a formula involving only the eigenvalues of the matrix and certain submatrices. See Tao’s blog for a concise description of the precise statement. Their preprint is worth a look too: after […]

13 December, 2019 at 4:36 pm

Edward Zeng

Dear Professor Tao,

I’m a sophomore math major at Berkeley. Someone told me about this theorem, and I think I found another proof.

Set $j = 1$ . WLOG assume $\lambda_i(A) = 0$ . Then the formula to be proved is
$\displaystyle |v_{i,1}|^2 \prod_{k = 1; k \neq i}^n \lambda_k(A) = \det(M_1).$

First we note any Hermitian matrix $A$ can be diagonalized by a unitary transformation
$T^*AT = \begin{pmatrix} \lambda_1(A) & & \\ & \lambda_2(A) & \\ & & \ddots \end{pmatrix}$
where the column vectors of $T$ form a basis of unit eigenvectors,
$T = (\vec{v}_1, \vec{v}_2, \dots, \vec{v}_n).$

Now observe the following lemma, which follows directly from how determinants are computed.

Lemma 1: Let
$A_t = A + \begin{pmatrix} t & 0 & \dots\\ 0 & 0 & \dots\\ \vdots & \vdots & \ddots \end{pmatrix} = \begin{pmatrix} a_{11} + t & a_{12} & \dots\\ a_{21} & a_{22} & \dots\\ \vdots & \vdots & \ddots \end{pmatrix}.$ Then $\det(A_t) = \det(A) + t\det(M_1)$ .

Applying T-transformation to $A_t$ , we obtain
$T^*A_tT = \begin{pmatrix} \lambda_1(A) & & \\ & \lambda_2(A) & \\ & & \ddots \end{pmatrix} +\begin{pmatrix} t\overline{v_{1,1}}v_{1,1} & t\overline{v_{1,1}}v_{2,j} & \dots\\ t\overline{v_{2,1}}v_{1,1} & t\overline{v_{2,1}}v_{2,j} & \dots\\ \vdots & \vdots & \ddots \end{pmatrix}.$

When we take the determinant on both sides (using Lemma 1 on the LHS) and collect the t-linear terms, we obtain the desired formula.

14 January, 2020 at 3:22 pm

Milad Kiaee Darunkola

This is related to the problem of Stars and Bars in Combinatorics.

20 February, 2020 at 11:15 pm

Cole Green

Our research group simulates photosynthetic nanotubules in Green Sulphur Bacteria. To study systems comparable in size to those found in nature, we must calculate the eigenvectors of large hamiltonians (up to 10,000×10,000). We do this by using LLAPACK’s DSYEV package, but this takes a long time for large systems. Since we only require the magnitude of the eigenvectors’ components for many of our calculations, we tested whether this new method for finding eigenvectors could be implemented in order to create faster programs. We found that this method was considerably slower than DSYEV, but we would like to improve the program if possible. Has anyone attempted something similar to this?

If you would like more information about the results of our comparison or have any suggestions, please contact me at cdgreen@my.loyno.edu or reply to this post

26 February, 2020 at 1:23 am

יומיות 29.12.2019: WT.social, רשת חברתית חדשה למקים ויקיפדיה | ניימן 3.0

[…] זמן קצר הם גילו שהם לא הראשונים שגילו את הזהות, אלא הראשונים שנתנו לה מסגרת וחשיבות משלה. מהר מאד הם […]

21 May, 2020 at 7:22 am

Sylvain Ribault

One way to avoid having to rediscover the wheel too often: write such results more systematically in Wikipedia.

3 June, 2020 at 7:31 am

Server Bug Fix: How do you check that your mathematical research topic is original? - TECHPRPR

[…] is one that is relevant to all mathematicians. An interesting recent example that comes to mind is this story on Terence Tao’s […]

	tt on A Host–Kra F^omega_2-sys…
	Joe Smith on Mathematics for Humanity initi…
	Michael Ruxton on A counterexample to the period…
	KEW on Equidistribution of Syracuse r…
	a on A Host–Kra F^omega_2-sys…
	Alison Playle on A new proof of the density Hal…
	Alison Playle on A new proof of the density Hal…
	Anonymous on A new proof of the density Hal…
	Anonymous on A new proof of the density Hal…
	a on A Host–Kra F^omega_2-sys…
	Anonymous on A Host–Kra F^omega_2-sys…
	Arman on A Host–Kra F^omega_2-sys…
	Solomon Ucko on There’s more to mathematics th…
	Eric Naslund on Density Hales-Jewett and Moser…
	Eric Naslund on Density Hales-Jewett and Moser…

Eigenvectors from Eigenvalues: a survey of a basic identity in linear algebra

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

39 comments

Leave a Reply Cancel reply

For commenters

Eigenvectors from Eigenvalues: a survey of a basic identity in linear algebra

Share this:

Like this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

39 comments

Leave a Reply Cancel reply

For commenters