1.2. SYMMETRIC MATRICES 9

Proofs of S1 to S5: Properties S1 to S3 are standard and proofs can be

found in many references. Property S4 in this general form was formulated

by Haemers (see e.g [4]). To prove it, let

x1,x2,...,xn

be orthonormal eigen-

vectors of A for its eigenvalues λ1,λ2,...,λn, respectively. Let

y1,y2,...,ym

be orthonormal eigenvectors of

QtAQ

for its eigenvalues μ1,μ2,...,μm, re-

spectively. Let Vi be the subspace of dimension i of

n

spanned by the

vectors

y1,y2,...,yi

(i = 1, 2,...,m), let Ui−1 be the subspace of dimension

i − 1 spanned by

x1,x2,...,xi−1,

and let Wi−1 be the subspace of dimen-

sion i − 1 spanned by

Qtx1,Qtx2,...,Qtxi−1

(i = 2, 3,...,n + 1). The

orthogonal complement

Wi⊥

−1

has dimension n − i + 1, and hence there ex-

ists a nonzero vector

zi

∈ Vi ∩

Wi⊥

−1

. Then

(Qzi)txj

=

(zi)tQtxj

= 0 for

j = 1, 2,...,i − 1, and so

Qzi

∈

Ui⊥

−1

, the subspace of dimension n − i + 1

spanned by

xi,xi+1,...,xn.

Thus by S2 and S3,

λi ≥

(Qzi)tA(Qzi)

(Qzi)t(Qzi)

=

(zi)tQtAQzi

(zi)tzi

≥ μi−1.

The other inequality follows by applying this argument to −A. This proves

S4. To prove S5, consider the m × m principal submatrix A[i1,i2,...,im]

determined by rows and columns with indices i1,i2,...,im. Let Q be the

n × m matrix whose columns are the (orthonormal) standard unit vectors

ei1

,

ei2

, . . . ,

eim

. Then A[i1,i2,...,im] =

QtAQ,

and S5 follows from S4.

A useful corollary also due to Haemers can be derived from property S5.

Corollary 1.8. Let A be an n×n real symmetric matrix with eigenval-

ues λ1 ≥ λ2 ≥ · · · ≥ λn. Let α1,α2,...,αm be a partition of {1.2,...,n} into

m nonempty sets of consecutive integers, where |αi| = ni (i = 1, 2,...,n),

and let

⎡

⎢

⎢

⎢

⎣

A11 A12 · · · A1m

A21 A22 · · · A2m

.

.

.

.

.

.

...

.

.

.

Am1 Am2 · · · Amm

⎤

⎥

⎥

⎥

⎦

be the corresponding partition of A (the matrix Aij is the submatrix A[αi|αj]

of A determined by the rows with index in αi and columns with index in

αj). Finally, let B = [bij] be the m × m symmetric matrix where

bij =

the sum of the entries of Aij

ni

(i, j = 1, 2,...,m),

the average row sum of Aij. Then the eigenvalues of B interlace the eigen-

values of A.

Proof. Define the n × m matrix Q where, for i = 1, 2,...,m, the ith

column has 1/

√

ni in the positions of αi and 0s elsewhere. The matrix Q

has orthonormal columns and

QtAQ

= B. Now apply S5.