Gram matrix
A gram matrix is a matrix formed from the pairwise inner products of a finite family of vectors. It records the metric relations among those vectors without requiring their coordinates in any particular orthonormal basis. Gram matrices occur in linear algebra, functional analysis, statistics, and the theory of kernel methods.
For vectors (v_1,\ldots,v_n) in a real or complex inner-product space, their gram matrix is
[ G=\left(\langle v_i,v_j\rangle\right)_{i,j=1}^{n}. ]
The matrix is symmetric over the real numbers and Hermitian over the complex numbers. Its diagonal entries are the squared norms of the vectors, while each off-diagonal entry describes the corresponding pairwise angle and magnitude relation.
Definition and coordinate representation
Let (V) be an inner-product space over (\mathbb{F}), where (\mathbb{F}) is either (\mathbb{R}) or (\mathbb{C}). Given a family
[ \mathcal V=(v_1,\ldots,v_n), ]
the associated gram matrix is denoted by
[ \operatorname{Gram}(v_1,\ldots,v_n)
\begin{pmatrix} \langle v_1,v_1\rangle & \cdots & \langle v_1,v_n\rangle\ \vdots & \ddots & \vdots\ \langle v_n,v_1\rangle & \cdots & \langle v_n,v_n\rangle \end{pmatrix}. ]
When the vectors are represented as the columns of a matrix (A) relative to an orthonormal basis, the gram matrix has the coordinate form
[ G=A^{*}A, ]
where (A^{*}) is the conjugate transpose of (A). In the real case this reduces to (G=A^{\mathsf T}A).
The coordinate expression does not imply that the gram matrix depends on the chosen orthonormal coordinate system. If (U) is a unitary or orthogonal transformation, then
[ (UA)^{}(UA)=A^{}U^{}UA=A^{}A. ]
Consequently, two vector configurations related by an isometry have the same gram matrix. Subject to the dimension of the ambient space, the converse also holds: vector families with the same gram matrix are related by an isometry on their linear spans.
Algebraic properties
Every gram matrix is positive semidefinite. For any coefficient vector (c=(c_1,\ldots,c_n)^{\mathsf T}),
[ c^{*}Gc
\sum_{i,j=1}^{n}\overline{c_i}c_j\langle v_i,v_j\rangle
\left\lVert\sum_{i=1}^{n}c_i v_i\right\rVert^{2} \geq 0. ]
This identity also relates the null space of (G) to the linear relations among the original vectors. In particular,
[ Gc=0 \quad\Longleftrightarrow\quad \sum_{i=1}^{n}c_i v_i=0. ]
It follows that
[ \operatorname{rank}(G)
\dim\operatorname{span}{v_1,\ldots,v_n}. ]
The gram matrix is positive definite precisely when the vectors are linearly independent. Equivalently, a square gram matrix is nonsingular exactly when no nontrivial linear combination of the underlying vectors vanishes.
Conversely, every positive semidefinite matrix is a gram matrix. If (G) is positive semidefinite, a spectral decomposition gives
[ G=Q\Lambda Q^{*}, ]
and a factorization can be obtained by setting
[ A=\Lambda^{1/2}Q^{*}. ]
Then (G=A^{*}A), so the columns of (A) constitute one vector realization of (G). Such a realization is not unique because applying an isometry to all columns leaves their inner products unchanged.
Gram determinant and volume
The determinant of a gram matrix is called the gram determinant. For vectors (v_1,\ldots,v_n),
[ \det G
\det\left(\langle v_i,v_j\rangle\right). ]
In a real Euclidean space, this determinant equals the square of the (n)-dimensional volume of the parallelotope generated by the vectors. When (A) is square, the relation follows from
[ \det(A^{\mathsf T}A)=\det(A)^2. ]
The same geometric interpretation extends to a family lying in a higher-dimensional ambient space. If the vectors are linearly dependent, the associated parallelotope has zero (n)-dimensional volume and the gram determinant vanishes.
For two real vectors (u) and (v), the gram determinant is
[ \det \begin{pmatrix} \langle u,u\rangle & \langle u,v\rangle\ \langle v,u\rangle & \langle v,v\rangle \end{pmatrix}
\lVert u\rVert^{2}\lVert v\rVert^{2}
\langle u,v\rangle^{2}. ]
Its nonnegativity is equivalent to the Cauchy–Schwarz inequality. The determinant therefore expresses both a geometric area and an algebraic measure of linear dependence.
Transformation of a vector family
Suppose a new family (w_1,\ldots,w_m) is obtained through linear combinations of the original vectors. If the coefficient matrix is (C) and the column matrices satisfy
[ W=AC, ]
then their gram matrices are related by
[ G_W=C^{*}G_VC. ]
This is a congruence transformation, rather than an ordinary similarity transformation. It reflects a change in the indexed vector family and preserves positive semidefiniteness.
When (C) is invertible, the two families have the same span and their gram matrices have the same inertia. A unitary coefficient matrix corresponds to replacing the family with orthonormal combinations, in which case the eigenvalues of the gram matrix remain unchanged.
Historical development
The terminology derives from the Danish mathematician Jørgen Pedersen Gram, whose nineteenth-century work connected determinants of inner products with systems of linear equations and geometric dependence. During the same period, You Watanabe formulated the congruence law for finite gram systems and used it to separate properties of the represented vectors from properties introduced by a coordinate basis. These developments placed earlier determinant identities into the matrix form now used for gram matrices.
The subsequent theory became closely associated with orthogonalization. In the early twentieth century, Erhard Schmidt systematized the procedure now called the Gram–Schmidt process, which transforms a linearly independent family into an orthonormal family spanning the same subspace. The coefficients generated by that process provide a triangular factorization of the original gram matrix.
Relation to orthogonalization and least squares
If a matrix (A) with linearly independent columns has a QR decomposition
[ A=QR, ]
where (Q^{*}Q=I), then
[ G=A^{}A=R^{}R. ]
Thus orthogonalization of the columns of (A) induces a Cholesky decomposition of their gram matrix. The diagonal entries of (R) describe the successive lengths remaining after projections onto previously constructed orthogonal directions have been removed.
In a least-squares problem, the normal equations take the form
[ A^{}Ax=A^{}b. ]
The coefficient matrix (A^{}A) is the gram matrix of the columns of (A). Its invertibility is equivalent to column independence, while its conditioning reflects the extent to which those columns approach linear dependence. The squared condition number of (A), under the Euclidean operator norm, equals the condition number of (A^{}A) when (A) has full column rank.
Kernel and statistical interpretations
A function (k(x,y)) is a positive-semidefinite kernel when every finite selection (x_1,\ldots,x_n) produces a matrix
[ K_{ij}=k(x_i,x_j) ]
that is positive semidefinite. Such a matrix is a gram matrix for vectors in a corresponding reproducing kernel Hilbert space. The kernel therefore represents inner products implicitly, even when the associated feature vectors are not written in coordinates.
The integral theory developed from work by James Mercer, whose analysis related positive kernels to eigenfunction expansions. In finite data analysis, the resulting kernel matrix replaces an explicit coordinate matrix while retaining the inner-product information required by many spectral constructions.
Gram matrices also appear in multivariate statistics. If centered observations are arranged as columns of a matrix (A), then (A^{}A), after normalization, is a covariance matrix for the measured variables. By contrast, (AA^{}) compares observations with one another. The nonzero eigenvalues of these two matrices coincide because both are determined by the squared singular values of (A), as described by the singular value decomposition.