Multi-Page Printing

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 W ⊥ i−1 has dimension n − i + 1, and hence there ex- ists a nonzero vector zi ∈ Vi ∩ W ⊥ i−1 . Then (Qzi)txj = (zi)tQtxj = 0 for j = 1, 2,...,i − 1, and so Qzi ∈ U ⊥ i−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.