Interlaced eigenvalues

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 A is an n\times n Hermitian matrix, with eigenvalues

\lambda_1\le\lambda_2\le\lambda_3\le\cdots\le\lambda_n

and suppose that B is obtained from A by removing row and column i for some 1\le i\le n. Then the eigenvalues of B

\mu_1\le\mu_2\le\mu_3\le\cdots\le\mu_{n-1}

satisfy the interlacing

\lambda_1\le \mu_1\le\lambda_2\le \mu_2\le\lambda_3\le\mu_3\le\cdots\le\mu_{n-1}\le\lambda_n.

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 f and g interlace if and only if all the roots of f+\alpha g are real, for all \alpha\in\mathbb{R}. 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

We shall use Matlab/Octave here, and instead of general Hermitian matrices we shall restrict ourselves to real symmetric matrices.

If D is a diagonal matrix, then its entries will be its eigenvalues, and if Q is an orthogonal matrix of the same size as D then

QDQ^T

will be a symmetric matrix with the same eigenvalues as D. We can construct an orthogonal matrix using this result of Cayley: if S is a skew-symmetric matrix, then

(S-I)^{-1}(S+I)

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 N is between two consecutive eigenvalues of M.

About these ads

2 responses to “Interlaced eigenvalues

  1. Pingback: Weekend miscellany — The Endeavour

  2. Hi there, I found your site by means of Google
    at the same time as searching for a related matter,
    your site came up, it looks great. I have bookmarked it
    in my google bookmarks.
    Hello there, just changed into alert to your weblog via Google, and found that it’s truly informative.
    I’m going to be careful for brussels. I’ll appreciate if you
    proceed this in future. Numerous other people will probably be benefited from your writing.
    Cheers!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s