24
$\begingroup$

This article describes the discovery by three physicists, Stephen Parke of Fermi National Accelerator Laboratory, Xining Zhang of the University of Chicago, and Peter Denton of Brookhaven National Laboratory, of a striking relationship between the eigenvectors and eigenvalues of Hermitian matrices, found whilst studying neutrinos.

Their result has been written up in collaboration with Terence Tao here. From what I understand, although very similar results had been observed before, the link to eigenvector computation had not been explicitly made prior to now. For completeness here is the main result, "Lemma 2" from their paper:

Let $A$ be a $n × n$ Hermitian matrix with eigenvalues $\lambda_i(A)$ and normed eigenvectors $v_i$. The elements of each eigenvector are denoted $v_{i,j}$. Let $M_j$ be the $(n − 1) × (n − 1)$ submatrix of $A$ that results from deleting the $j^{\text{th}}$ column and the $j^{th}$ row, with eigenvalues $\lambda_k(M_j)$.

Lemma 2. The norm squared of the elements of the eigenvectors are related to the eigenvalues and the submatrix eigenvalues, $$|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))$$

I was wondering what are the mathematical consequences of this beautiful result?

For example are there any infinite dimensional generalisations? Does it affect matrix algorithms or proofs therein? What about singular values?

$\endgroup$
  • 2
    $\begingroup$ there is a very extensive discussion on Tao's blog $\endgroup$ – Carlo Beenakker Nov 17 at 22:06
  • 2
    $\begingroup$ The Quanta Magazine article of four days ago has also now been republished in The Atlantic. $\endgroup$ – jeq Nov 18 at 0:25
  • $\begingroup$ @CarloBeenakker Thanks for the heads up. There isn't much discussion of potential applications there - I guess we will have to wait and see. $\endgroup$ – Ivan Meir Nov 18 at 1:13
  • $\begingroup$ "What about singular values?" - presumably, one could use this result on the matrix $$\mathbf G=\begin{pmatrix}&\mathbf B^\ast\\\mathbf B&\end{pmatrix}$$, since if $\mathbf B$ has singular values $\sigma_k$, then $\mathbf G$ has eigenvalues $\pm\sigma_k$. $\endgroup$ – J. M. is not a mathematician Nov 18 at 16:23
  • $\begingroup$ Additionally, even if $\mathbf B$ is rectangular, $\mathbf G^\ast=\mathbf G$. (On another note, this paper might be of interest.) $\endgroup$ – J. M. is not a mathematician Nov 18 at 16:58
33
$\begingroup$

The OP asks about generalisations and applications of the formula in arXiv:1908.03795.

$\bullet$ Concerning generalisations: I have found an older paper, from 1993, where it seems that the same result as in the 2019 paper has been derived for normal matrices (with possibly complex eigenvalues) --- rather than just for Hermitian matrices: On the eigenvalues of principal submatrices of normal, hermitian and symmetric matrices, by Peter Nylen, Tin-Yau Tam & Frank Uhlig (1993): theorem 2.2 (with the identification $b_{ij}=|u_{ij}|^2$ made at the very end of the proof).

A further generalisation to a signed inner product has been given in On the eigenvalues of principal submatrices of J-normal matrices (2011). In that case $b_{ij}=\epsilon_i\epsilon_j|u_{ij}|^2$, with $\epsilon_i=\pm 1$ the signature of the inner product: $(x,y)=\sum_i \epsilon_i x_i^\ast y_i$.

$\bullet$ Concerning applications: in the 1993 paper the theorem is used to solve the following problem: when does a normal $n\times n$ matrix $A$ with principal sub-matrices $M_j$ exist, given the sets of distinct (complex) eigenvalues $\lambda_i(A)$ of $A$ and $\lambda_k(M_j)$ of $M_j$. The answer is that the matrix $B$ with elements $$b_{ij}=\frac{\prod_{k=1}^{n-1}(\lambda_i(A)-\lambda_k(M_j))}{\prod_{k=1;k\neq i}^n(\lambda_i(A)-\lambda_k(A))}$$ should be unistochastic, meaning that $b_{ij}=|u_{ij}|^2$, where the matrix $U$ with elements $u_{ij}$ is the eigenvector matrix of $A$.


Since the 1993 paper is behind a paywall, I reproduce the relevant page:

A brief Mathematica file to test the formula is here.


Addendum: following up on the trail pointed out by Alan Edelman on Tao's blog: this 1966 paper by R.C. Thompson, "Principal submatrices of normal and Hermitian matrices", has the desired formula in the general case of normal matrices as Equation (15).

where $\theta_{ij}=|u_{ij}|^2$ when all eigenvalues $\mu_\alpha$ of $A$ are distinct (the $\xi_{ij}$'s are eigenvalues of $M_i$). The older papers mentioned in the comments below do not seem to have an explicit formula for $|u_{ij}|^2$.

Because this appears to be the earliest appearance of the eigenvector/eigenvalue identity, it might be appropriate to refer to it as "Thompson's identity",$^*$ as a tribute to professor Robert Thompson (1931-1995). It would fit in nicely with this quote from the obituary:

Among Thompson's many services to research was his help in dispelling the misinformed view that linear algebra is simple and uninteresting. He often worked on difficult problems, and as much as anyone, he showed that core matrix theory is laden with deeply challenging and intellectually compelling problems that are fundamentally connected to many parts of mathematics.

$^*$ "Thompson's identity" to distinguish from Thompson's formula

$\endgroup$
  • 2
    $\begingroup$ Thanks Carlo this is excellent! $\endgroup$ – Ivan Meir Nov 18 at 14:01
  • 3
    $\begingroup$ note this thread:linkedin.com/pulse/… where the author gives reference as back as 1930! $\endgroup$ – Piyush Grover Nov 18 at 17:14
  • 2
    $\begingroup$ thanks @PiyushGrover; I tried to follow up on the links you mention; Eq. (2.2.26) in the 1986 paper is a formula for the overlap squared of the eigenvectors of $A$ and $M_i$; Eq. (2.29) in the 1960 paper gives the overlap squared between an eigenvector and its Rayleigh-Ritz approximation; presumably the 1993 formula for $|u_{ij}|^2$ can be easily obtained from these earlier results, but $|u_{ij}|^2$ is not explicitly given, as far as I can tell. $\endgroup$ – Carlo Beenakker Nov 18 at 18:36
  • 3
    $\begingroup$ Formula 8 in Löwner's paper looks awfully like the currently popular result. $\endgroup$ – J. M. is not a mathematician Nov 18 at 19:24
  • 2
    $\begingroup$ @J.M.isnotamathematician -- the left-hand-side of Eq. 8 of Löwner is again an overlap of eigenvectors of two different matrices, rather than the absolute value squared $|u_{ij}|^2$ of the eigenvector of a single matrix. (I am not implying one cannot obtain a result for $|u_{ij}|^2$ from such an overlap, but as far as I can tell, the 1993 paper is the earliest where that particular quantity is expressed in terms of eigenvalues.) $\endgroup$ – Carlo Beenakker Nov 18 at 19:32
12
$\begingroup$

I want to add to the list of places where this identity has been used previously.

For a recent one, see arXiv:1710.02181 “State transfer in strongly regular graphs with an edge perturbation”. Equation (2) in Section 2 of this reads \[ \frac{\phi(X\setminus a,t)}{\phi(X,t)} = \sum_r \frac{(E_r)_{a,a}}{t-\theta_r} \] If the eigenvalue $\theta_r$ is simple. $E_r=z_rz_r^T$ and we have formula (2.3) in the pdf given in Carlos's reply. I have used it in a number of places in work on continuous quantum walks, e.g - Lemma 7.1 and Corollary 7.2 in arXiv:1011.0231 "When can perfect state transfer occur?"

It is used implicitly in my paper with Brendan McKay: "Spectral conditions for the reconstructibility of a graph", JCT B (30), 1981, 285–289.

We missed the connection to neutrinos :-(

There is an extensive treatment in Chapter 4 of my book "Algebraic Combinatorics". Chapman & Hall, New York, 1993.

Related identities appear in C. A. Coulson and H. C. Longuet-Higgins: "The electronic structure of conjugated systems I. General theory", Proc. Roy. Soc. London A191 (1947), 39–60. They prove that if $G$ is a graph with adjacency matrix $A$ and characteristic polynomial $\phi(G,t)$ and $\phi_{ij}(G)$ is the $ij$-entry of $\phi(G,t)(tI-A)^{-1}$, then \[ \phi_{ij}(G,t) = \sum_P \phi(G\setminus P,t) \] (where the sum is over all paths $P$ in $G$ from $i$ to $j$, and $G\setminus P$ is $G$ with all vertices in $P$ deleted). Further \[ \phi_{ij}(G,t) = \sqrt{\phi(G\setminus i,t)\phi(G\setminus j,t)-\phi(G,t)\phi(G\setminus {i,j},t)}. \]

The connection with eigenvectors arises because if $A=\sum_r \theta_r E_r$ is the spectral decomposition of $A$, then \[ \frac{\phi_{ij}(G,\theta_r)}{\phi'(G,\theta_r)} = (E_r)_{i,j}. \]

Essentially, the identity relates diagonal entries of spectral idempotents of Hermitian matrices to characteristic polynomials of principal submatrices. The off-diagonal entries are related to Green's functions, and I expect that there are papers in the physics literature where versions of the identity appear.

$\endgroup$
  • 1
    $\begingroup$ There is nothing new under the sun. $\endgroup$ – Christian Remling Nov 19 at 16:25
  • 1
    $\begingroup$ it might be helpful if you could perhaps include some of these identities in your answer; I checked the 1947 paper and have difficulty locating it, and I'm also unsure how to extract it from the more recent papers you mention. $\endgroup$ – Carlo Beenakker Nov 19 at 16:26
  • 3
    $\begingroup$ I would like to second Carlo's request. I have also just searched through all the references you mention and was unable to locate identities close to the one discussed here. The identity $\frac{\phi_{ij}(G,\theta_r)}{\phi'(G,\theta_r)} = (E_r)_{i,j}$ you mention is somewhat close to our identity, but I wasn't able to locate it in any of the references you gave. $\endgroup$ – Terry Tao Nov 19 at 18:03
  • 1
    $\begingroup$ I hope I have come closer to satisfying Carlo's request now. $\endgroup$ – Chris Godsil Nov 19 at 19:11
  • 1
    $\begingroup$ @ChrisGodsil Thanks for your comprehensive research on this subject Chris, very much appreciated. In the interests of keeping things on topic I just wanted to to steer things towards my specific question which was really about the mathematical consequences of this result rather than previous possible occurrences of related results in the literature. For example can you describe in a way that's accessible to as wide an audience as possible, the application you allude to in your paper with Brendan McKay. Thanks! $\endgroup$ – Ivan Meir Nov 20 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.