Next: Diagonally dominant matrices Up: The spectrum of a Previous: The second largest eigenvalue

# Gram matrices

Real symmetric -matrices are in bijective correspondence with quadratic forms on via the relation

Two quadratic forms and on are congruent, i.e., there is a nonsingular -matrix such that for all , if and only if their corresponding matrices and satisfy . Moreover, this occurs for some if and only if and have the same rank and the same number of nonnegative eigenvalues (Sylvester [31]'s `law of inertia for quadratic forms', cf. Gantmacher [12], Vol. 1, Chapter X, §2); recall the basic fact that every real symmetric square matrix has real eigenvalues only, and an orthonormal basis of eigenvectors. We shall now be concerned with matrices having nonnegative eigenvalues only.

Lemma 1.13.1   Let be a real symmetric -matrix. Then (i) and (ii) are equivalent:

(i) For all , .

(ii) All eigenvalues of are nonnegative.

Proof:     There is an orthogonal matrix and a diagonal matrix whose nonzero entries are the eigenvalues of such that . If (ii) holds, then implies (i). Conversely, (ii) follows from (i) by choosing to be an eigenvector.

A symmetric -matrix satisfying (i) and (ii) is called positive semidefinite. It is called positive definite when implies , or, equivalently, when all its eigenvalues are positive. For any collection of vectors of , we define its Gram matrix as the square matrix indexed by (or by some index set for ) whose -entry is the inner product . This matrix is always positive semidefinite, and it is definite if and only if the vectors in are linearly independent. (Indeed, if we use to denote the -matrix whose columns are the vectors of , then , and .) Conversely, if is an arbitrary symmetric positive semidefinite matrix of rank then is congruent to a diagonal matrix consisting of zeros and ones,

so that is the Gram matrix of the set of columns of in .

Subsections

Next: Diagonally dominant matrices Up: The spectrum of a Previous: The second largest eigenvalue
Andries Brouwer 2003-09-30