8 1. SOME FUNDAMENTALS

S1. All the eigenvalues of A are real numbers, and thus can be ordered

as

λmin = λn ≤ λn−1 ≤ . . . ≤ λ1 = λmax.

Also there exist eigenvectors

x1,x2,...,xn

of A for λ1,λ2,...,λn,

respectively, that form an orthonormal basis of

n.

S2. For every nonzero vector x ∈

n,

λn ≤

xtAx

xtx

≤ λ1.

Equivalently, for every vector x ∈

n

of length 1, that is,

xtx

= 1,

λn ≤

xtAx

≤ λ1.

In fact,

λ1 =

max{xtAx

:

xtx

= 1} and λn =

min{xtAx

:

xtx

= 1}.

S3. More generally, each of the eigenvalues of A can be characterized

using subspaces of

n.

Let

x1,x2,...,xn

be an orthonormal basis

of

n

consisting of eigenvectors of A for λ1,λ2,...,λn, respectively.

Then for a nonzero vector y ∈

span{xi,...,xn}

λi ≥

ytAy

yty

with equality for y =

xi,

and for y ∈

span{x1,...,xi},

λi ≤

ytAy

yty

with equality for y =

xi.

Thus

λi = inf{sup

ytAy

yty

: y ∈ W : W a subspace of

n

of dimension n − i + 1}.

S4. (Interlacing of eigenvalues I.) Let Q be an n × m real matrix with

orthonormal columns

(QtQ

= Im), and let the eigenvalues of the

m × m matrix

QtAQ

be μ1 ≥ μ2 ≥ · · · ≥ μm. Then

λn−m+i ≤ μi ≤ λi (i = 1, 2,...,m).

S5. (Interlacing of eigenvalues II.) If μ1 ≥ μ2 ≥ · · · ≥ μm are the

eigenvalues of an m × m principal submatrix of A, then

λn−m+i ≤ μi ≤ λi (i = 1, 2,...,m).

In particular, if μ1 ≥ μ2 ≥ · · · ≥ μn−1 are the eigenvalues of an

n − 1 × n − 1 principal submatrix of A, then

λn ≤ μn−1 ≤ λn−1 ≤ · · · ≤ μ2 ≤ λ2 ≤ μ1 ≤ λ1.