Gram matrices

Real symmetric $n \times n$-matrices $G$ are in bijective correspondence with quadratic forms $q$ on ${\mathbb{R}}^n$ via the relation

$$q(x) = x^\top G x ~~~~ ( x \in {\mathbb{R}}^n ) .$$

Two quadratic forms $q$ and $q'$ on ${\mathbb{R}}^n$ are congruent, i.e., there is a nonsingular $n \times n$-matrix $S$ such that $q(x) = q' ( Sx)$ for all $x \in {\mathbb{R}}^n$, if and only if their corresponding matrices $G$ and $G'$ satisfy $G = S^\top G' S$. Moreover, this occurs for some $S$ if and only if $G$ and $G'$ 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 $G$ be a real symmetric $n \times n$-matrix. Then (i) and (ii) are equivalent:

(i) For all $x \in {\mathbb{R}}^n$, $x^\top G x \ge 0$.

(ii) All eigenvalues of $G$ are nonnegative.

Proof:     There is an orthogonal matrix $Q$ and a diagonal matrix $D$ whose nonzero entries are the eigenvalues of $G$ such that $G = Q^\top D Q$. If (ii) holds, then $x^\top G x = (Qx)^\top D(Qx) \ge 0$ implies (i). Conversely, (ii) follows from (i) by choosing $x$ to be an eigenvector. $\Box$

A symmetric $n \times n$-matrix $G$ satisfying (i) and (ii) is called positive semidefinite. It is called positive definite when $x^\top G x = 0$ implies $x = 0$, or, equivalently, when all its eigenvalues are positive. For any collection $X$ of vectors of ${\mathbb{R}}^n$, we define its Gram matrix as the square matrix $G$ indexed by $X$ (or by some index set for $X$) whose $(x,y)$-entry $G_{x y}$ is the inner product $( x , y ) = x^\top y$. This matrix is always positive semidefinite, and it is definite if and only if the vectors in $X$ are linearly independent. (Indeed, if we use $H$ to denote the $n \times \vert X \vert$-matrix whose columns are the vectors of $X$, then $G = H^\top H$, and $x^\top G x = (Hx,Hx) \ge 0$.) Conversely, if $G$ is an arbitrary symmetric positive semidefinite matrix of rank $n$ then $G$ is congruent to a diagonal matrix consisting of zeros and $n$ ones,

$$G = ( S_{11}^{\top} ~ S_{12}^\top ) \left(\begin{array}{cc} ... ...} S_{11} \\ S_{12} \end{array}\right) = S_{11}^\top ~ S_{11},$$

so that $G$ is the Gram matrix of the set of columns of $S_{11}$ in ${\mathbb{R}}^n$.