A few weeks ago, a few physicists (Peter Denton, Stephen Parke, and Xining Zhang) and one notable mathematician (Terence Tao) posted a short 3-page note to the arXiv, containing a “new” identity relating to eigenvectors to eigenvalues. Many people rushed to explain that it was not new; it has existed at least since 1966 and has been used many times by people who took no credit for it. The authors have since amended their paper and converted it into a survey containing all seven proofs of this identity, but not before it was picked up by Quanta. Now, in response to collaborators asking if I knew it and co-authors inquiring if I’ve thought about using it, I’m writing about how we usually arrive at identity in algebraic graph theory.

the adjacency matrix

Say we have a graph \(G\) on \(n\) vertices. The adjacency matrix \(A\) of \(G\) is an \(n\times n\) matrix with rows and columns indexed by the vertices of \(G\); \(A_{u,v} = 1\) if \(u\) is adjacent to \(v\) and \(A_{u,v} = 0\) otherwise. It may not be immediately apparent, but this matrix has the following property: \[ A^k_{u,v} = \text{the number of walks from } u \text{ to } v \text{ of length }k. \] We will write \(\phi(G,t)\) for the characteristic polynomial of \(A\).

the walk-generating function

Now we may consider the walk-generating function of \(u\) and \(v\) in \(G\), denoted \(W_{u,v}(G,t)\). This is a formal power series in variable \(t\), where the coefficient of \(t^k\) is the number of walks from \(u\) to \(v\) of length \(k\). But, oh wait, we already know how to count those! We have that \[ W_{u,v}(G,t) = \sum_{k=0}^{\infty} A^k_{u,v} t^k. \] If we look carefully at each term being summed, we are just extracting the \(u,v\) entry of some matrix and then multiplying by \(t^k\), so we can just do the extraction later and get: \[ W_{u,v}(G,t) = \sum_{k=0}^{\infty} (tA)^k_{u,v}. \] In fact, we could just take the whole sum first and then extraction the \(u,v\) entry and so \[ W_{u,v}(G,t) = \left(\sum_{k=0}^{\infty} (tA)^k\right)_{u,v}. \]

And now, we need to recall from calculus the following equality (keeping in mind that, since we work with these series as formal power series, we are not troubled by things like convergence): \[ 1 +x + x^2 + x^3 + \cdots = \frac{1}{1-x}. \] We can apply it to our expression for \(W_{u,v}(G,t)\) where \(x = tA\) and get \[ W_{u,v}(G,t) = (I-tA)^{-1}_{u,v}. \] While this looks a bit better, I’d much rather work with \(tI-A\), whose determinant is the characteristic polynomial of \(A\). So, we will do a change of variables as follows: \[ t^{-1}W_{u,v}(G,t^{-1}) = (tI-A)^{-1}_{u,v}. \] From this point forward, we will work with the expression \((tI-A)^{-1}_{u,v}\), with the knowledge that it gives the walk-generating function.

Cramer’s rule

We will use Cramer’s rule to simplify the diagonal entries of \((tI-A)^{-1}\); we can also do off-diagonal entries, see Godsil’s Algebraic Combinatorics but it involves a small amount of mess.

Cramer’s rule says that you can get the \(u,u\) entry of a matrix \(M\) by dividing the adjoint at \(u\) by the determinant. If you remove the \(u\)th row and the \(u\)th column from \(A\), you get an \(n-1\times n-1\) matrix which happens to be the adjacency matrix of \(G\) with the vertex \(u\) deleted, which we denote \(G\setminus u\). Thus \[ (tI-A)^{-1}_{u,u} = \frac{\phi(G\setminus u, t)}{\phi(G,t)}. \quad \quad \quad \quad (*) \] We will call this equation ([/latex]*[/latex]) mostly because I don’t know how to enable equation numbering in MathJax.

spectral decomposition

Now we will use spectral decomposition to obtain another expression for \((tI-A)^{-1}_{u,u}\). Since \(A\) is a real symmetric matrix, it is diagonalizable. Why is that so? It’s explained in a previous post. We may write \(A\) as follows: \[ A = \sum_{r=0}^d \theta_r E_r \] where the \(\theta\)s are the distinct eigenvalues of \(A\) and \(E_r\) is the idempotent projector for the \(\theta_r\)-eigenspace of \(A\). I always find this cool to use because we defined our matrix \(A\) to record adjacencies in \(G\), but now we are considering \(A\) as a matrix operator acting on the \(n\)-dimensional vector space; its action is entirely determined by how it acts on its eigenspaces, the subspaces on which it acts as scalar multiplication.

Recalling that eigenvectors of different eigenspaces are orthogonal, it’s not difficult to convince yourself that \[ A^2 = \sum_{r=0}^d \theta_r^2 E_r, \] where we notice that we only had to square the eigenvalues to square \(A\). In fact, \[ f(A) = \sum_{r=0}^d f(\theta_r) E_r, \] for all “reasonable” functions \(f\). We will not discuss the technical details of what it means to be reasonable, but it suffices to say that polynomial, rational functions and power series are all reasonable. In particular, \(\frac{1}{t-x}\) is reasonable and so \[ (tI-A)^{-1}_{u,u} = \sum_{r=0}^d \frac{1}{t- \theta_r} (E_r)_{u,u}. \quad \quad \quad (\dagger) \]

putting it all together

Putting together equation \((\dagger)\) and \((*)\), we get the following: \[ \frac{\phi(G\setminus u, t)}{\phi(G,t)} = \sum_{r=0}^d \frac{1}{t- \theta_r} (E_r)_{u,u}. \quad \quad (\dagger\dagger) \] You may complain that it’s not exactly what they have in their paper, but it’s actually just one short trick away.

Fix \(s \in \{0,\ldots,r\}\) and we will find the expression for \((E_s)_{u,u}\). We multiply everything by \(t-\theta_s\) to get \[\frac{(t-\theta_s)\phi(G\setminus u, t)}{\phi(G,t)} = \sum_{r\neq s} \frac{t-\theta_s}{t- \theta_r} (E_r)_{u,u} + (E_s)_{u,u}.\] Now we evaluate at \(t = \theta_s\) and get the desired eigen-magicks: \[ \frac{(t-\theta_s)\phi(G\setminus u, t)}{\phi(G,t)} |_{t = \theta_s} = (E_s)_{u,u}. \] You may think we need to take a limit; Gabriel Coutinho’s notes has a limit here, but it is, in fact, unnecessary. Suppose \(G\) has \(\theta_s\) as an eigenvalue with multiplicity \(m\). By the Interlacing Theorem, removing one vertex can only decrease the multiplicity by at most one and thus, there are also \(m\) factors of \(t-\theta_s\) appear on the top of the left hand side and everything cancels.

some uses of the eigen-magicks

I use equation \((\dagger\dagger)\) and the corresponding equation for the off-diagonal entries often; in the study of state transfers of quantum walks, we need to investigate something called strong cospectrality of pairs of vertices. In particular, in a paper with Chris Godsil, Mark Kempton and Gabor Lippner (which is cited by the new survey version of the paper by Denton et al.), we use these equations to perturb an edge of a strongly regular graph, so that the endpoints become strongly cospectral. For those interested, the arXiv version from 2017 is here and the JCTA version is here.

If you stare at equation \((\dagger)\) long enough, you may be tempted, as I was, to substitute \(t=0\) and obtain the entries of the inverse of \(A\). This is somewhat legitimate since, when \(A\) is invertible, \(t=0\) is not a pole of the right hand side. This is essential what I do for the class of invertible trees in a recent paper. I reprove a result of Godsil’s on the inverses of trees from the 80s, but I do it in such a way that I am able to define a combinatorial operation on a tree which strictly increases (or decreases, if you apply the inverse of the operation) the median eigenvalue of the tree. It’s surprising that you can do this; eigenvalues relate to combinatorial structure of the graph, but the relationship is, in general, not quid pro quod, as it is in this case. This gives a partial order on the class of trees with a perfect matching and I find the maximal and minimal elements. I leave its height and Moebius function as open problems for readers.