First of all, I’d like to express my sympathies to everyone who is enduring hardships due to COVID-19. Stay well and be strong.

In this previous post, I discussed two important classical results giving examples of polynomials whose roots interlace:

Theorem 1: The roots of a real-rooted polynomial and its derivative interlace.

Theorem 2: (Cauchy’s interlacing theorem) The eigenvalues of a real symmetric matrix interlace with those of any principal minor.

In this post, I’d like to explain a general method, based on partial fraction expansions of rational functions, which gives a unified approach to proving Theorems 1 and 2 and deserves to be better known.

Interlacing and rational functions

Suppose and are real-rooted polynomials. We say that the roots of and interlace if and that they strictly interlace if strict inequalities hold throughout.

Theorem 3: Suppose and , where and are real-rooted polynomials of degree and , respectively. Then the roots of and interlace (rest. strictly interlace) if and only if with (resp. ) for all .

Proof (Sketch): We prove the strict case, assuming that the zeros of are simple; the general case follows by a continuity argument. Let be the partial fractions decomposition of , and assume that . If each then for all . Since , for all , and it follows that has a unique root in for all and no other roots. Hence the zeros of and interlace. The converse is proved similarly.

• 

• 

Figure 1: In the left-hand plot, the zeros of p(x) and q(x) interlace. In the right-hand plot, they do not.

Interlacing of the roots of and

Theorem 1, which asserts that the roots of and its derivative interlace, is usually proved using Rolle’s theorem. We establish it here as a consequence of Theorem 3:

Proof of Theorem 1: Let Then , so if with each a positive integer, then . By Theorem 3, the zeros of and interlace.

Spectral decomposition and the functional calculus

If is an real symmetric matrix and is the set of eigenvalues of , then has the well-known spectral decomposition where is the principal idempotent corresponding to orthogonal projection onto the eigenspace of .

More generally, we have the following result which is a special case of the so-called holomorphic functional calculus:

Theorem 4: If is a rational function which does not have a pole at any eigenvalue of then satisfies .

If is a polynomial then Theorem 4 is proved in a number of standard linear algebra texts, and the general case follows by a suitable limiting argument.

In particular, applying Theorem 4 to we obtain the formula Since this is true for all , we obtain the following identity:

Corollary 5 (Spectral decomposition of the resolvent):

Cauchy’s interlacing theorem

Let be an real symmetric matrix, and let be the principal minor obtained by deleting row and column from . Let (resp. ) denote the characteristic polynomial of (resp. ). By the cofactor formula for the inverse of a matrix, we have:

Lemma 6:

Proof of Theorem 2: By Corollary 5 and Lemma 6, we have

where denotes the standard basis vector. Since

the result now follows from Theorem 3.

Concluding remarks:

1. I learned Theorem 3 from this paper by McKee and Smyth, and I learned the proof of Theorem 2 that we’ve given here from Section 8 of the book Algebraic Graph Theory by Godsil and Royle.

2. For more details on the holomorphic functional calculus (which can also be used, for example, to define and when has positive eigenvalues) and the spectral decomposition of the resolvent, see e.g. these notes by Rodica Costin or this Wikipedia page.