An engineering colleague asked me recently to investigate the relationship between the eigenvalues of a matrix and the eigenvalues of its principal submatrices. This is not an area I know much about, so I started off doing a web search. And I learned about a remarkable fact which goes back to Cauchy:
Suppose is an Hermitian matrix, with eigenvalues
and suppose that is obtained from by removing row and column for some . Then the eigenvalues of
satisfy the interlacing
The shortest proof of this result is due to the late Steve Fisk of Bowdoin College, who is probably best known in the wider mathematical world for his “proof from the book” of Chvátal’s art gallery theorem. His proof (of Cauchy’s interlacing theorem, not the art gallery theorem) can be found here. Fisk’s proof, as you can see, is based on a result of Hermite, which claims that the roots of two polynomials and interlace if and only if all the roots of are real, for all . For a complete proof of this result, from which the eigenvalues result is deduced as a corollary, see Fisk’s “Polynomials, roots, and interlacing“.
Another proof uses the min-max theorem, of which a full account is given by Terry Tao.
A little experiment
If is a diagonal matrix, then its entries will be its eigenvalues, and if is an orthogonal matrix of the same size as then
will be a symmetric matrix with the same eigenvalues as . We can construct an orthogonal matrix using this result of Cayley: if is a skew-symmetric matrix, then
is orthogonal. The proof requires some elementary matrix algebra; see here. Here’s the experiment:
>> n = 4; >> D = diag(1:n); >> R = rand(n); >> S = R - R'; >> Q = inv(S-eye(n))*(S+eye(n)); >> M = Q*D*Q' M = 2.1146941 -0.8411071 -0.5795664 0.1635006 -0.8411071 3.0320881 -0.7959547 -0.7357826 -0.5795664 -0.7959547 2.6104766 -0.0025486 0.1635006 -0.7357826 -0.0025486 2.2427411 >> sort(eig(full(M))') ans = 1.0000 2.0000 3.0000 4.0000 >> i = ceil(n*rand); >> N = M; N(i,:)=; N(:,i)=; >> sort(eig(full(N))') ans = 1.5021 2.0328 3.8546
Note that each eigenvalue of is between two consecutive eigenvalues of .
Filed under: Computation