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.
