Gram matrix · aiwiki.page

A Gram matrix is a square matrix whose entries are the pairwise inner products of a finite ordered collection of vectors. It converts geometric information about vectors into algebraic information about a single matrix. Gram matrices connect linear algebra with geometry, least-squares problems, and kernel-based learning. Their defining structural property is positive semidefiniteness; conversely, every Hermitian positive semidefinite matrix admits a representation as a Gram matrix. (people.cs.uchicago.edu)

Definition and conventions

Let $v_1,\ldots,v_n$ belong to a real or complex vector space equipped with an inner product. Using the convention that a complex inner product is conjugate-linear in its first argument and linear in its second, their Gram matrix is

G_{ij}=\langle v_i,v_j\rangle, \qquad 1\leq i,j\leq n.

Thus, the diagonal entries are squared lengths, while the off-diagonal entries describe pairwise inner products. The vectors need not be distinct, independent, or a basis. (bpb-us-e1.wpmucdn.com)

If the vectors are columns of a coordinate matrix $A$ , expressed in orthonormal coordinates, then

G=A^*A,

where $A^*$ denotes the conjugate transpose. For real coordinates this becomes $G=A^{\mathsf T}A$ , using the ordinary transpose. Authors who take complex inner products to be linear in the first argument may reverse the indices in the definition so that the same matrix formula holds. Stating the convention prevents apparent discrepancies between formulas. (people.cs.uchicago.edu)

The construction also applies to vectors in an infinite-dimensional Hilbert space: any finite collection still produces a finite matrix. (bpb-us-e1.wpmucdn.com)

Positivity, rank, and realization

Conjugate symmetry of the inner product gives $G^*=G$ , so a Gram matrix is Hermitian, or symmetric in the real case. For any coefficient vector $c$ ,

c^*Gc = \left\|\sum_{i=1}^{n}c_i v_i\right\|^2 \geq 0.

This identity proves positive semidefiniteness and relates the matrix directly to linear combinations of the original vectors. It is a positive definite matrix precisely when the vectors satisfy linear independence. All its eigenvalues are therefore nonnegative. (people.cs.uchicago.edu)

Moreover,

\operatorname{rank}(G) = \dim\operatorname{span}\{v_1,\ldots,v_n\}.

Thus, matrix rank measures the dimension of their linear span, not the number of listed vectors. In coordinates, $\ker(A^*A)=\ker(A)$ , because $c^*A^*Ac=\|Ac\|^2$ . (bpb-us-e1.wpmucdn.com)

Conversely, the spectral theorem gives a factorization $G=U\Lambda U^*$ for any Hermitian positive semidefinite matrix. Setting $B=\Lambda^{1/2}U^*$ yields $G=B^*B$ ; the columns of $B$ realize the required vectors. Removing zero-eigenvalue rows gives a realization in dimension $\operatorname{rank}(G)$ , the smallest possible dimension. (people.cs.uchicago.edu)

Geometric information and determinant

For real vectors in Euclidean space, Gram entries determine lengths and angles:

\|v_i\|=\sqrt{G_{ii}}, \qquad \cos\theta_{ij} = \frac{G_{ij}}{\sqrt{G_{ii}G_{jj}}},

where the angle formula requires both vectors to be nonzero. They also determine squared pairwise distances:

\|v_i-v_j\|^2 = G_{ii}+G_{jj}-2G_{ij}.

Consequently, a Gram matrix encodes the geometry of the vectors relative to the origin without specifying their absolute orientation. (tropp.caltech.edu)

The determinant $\det G$ , called the Gram determinant, equals the square of the $n$ -dimensional volume of the parallelotope generated by $n$ real Euclidean vectors:

V=\sqrt{\det G}.

A zero determinant indicates linear dependence and zero $n$ -dimensional volume. For two vectors, this reduces to

\det G = \|v_1\|^2\|v_2\|^2-\langle v_1,v_2\rangle^2,

the squared area of their parallelogram. (pmc.ncbi.nlm.nih.gov)

For example, take $v_1=(1,0)$ and $v_2=(1,1)$ . Direct substitution gives

G= \begin{pmatrix} 1&1\\ 1&2 \end{pmatrix}, \qquad \det G=1.

Their lengths are $1$ and $\sqrt2$ , their angle is $45^\circ$ , and the parallelogram has area $1$ .

Coordinates and changes of basis

When the vectors form a basis, the Gram matrix represents the inner product in that basis. If $x$ and $y$ are coordinate columns, then

\langle x,y\rangle_G=x^*Gy.

An orthonormal basis has Gram matrix equal to the identity. For a new basis obtained through an invertible coordinate matrix $P$ , the matrix transforms by

G_{\mathrm{new}}=P^*GP.

This is a congruence transformation, rather than the similarity transformation used for a linear operator. It preserves positive definiteness but need not preserve individual eigenvalues. (cis.upenn.edu)

Least squares and numerical computation

In ordinary least squares, minimizing $\|Ax-b\|^2$ leads to the normal equations

A^*Ax=A^*b.

Their coefficient matrix is the Gram matrix of the columns of $A$ . Independent columns make it invertible and ensure a unique minimizer. (stanford.edu)

The singular value decomposition shows that the eigenvalues of $A^*A$ are the squared singular values of $A$ . For full column rank,

\kappa_2(A^*A)=\kappa_2(A)^2.

This squaring of the condition number explains why explicitly forming normal equations can amplify numerical difficulties. QR decomposition and singular value decomposition provide alternative least-squares formulations that avoid this squaring. (physbam.stanford.edu)

Kernel methods

In machine learning, a kernel method forms a Gram matrix through a feature map $\phi$ :

K_{ij}=k(x_i,x_j) = \langle\phi(x_i),\phi(x_j)\rangle.

Evaluating $k$ directly can avoid constructing the feature vectors explicitly. For a valid positive semidefinite kernel, every finite sample produces a positive semidefinite Gram matrix. In a support vector machine, the training inputs enter the dual optimization problem through these pairwise kernel values, allowing nonlinear feature-space geometry to be handled through a finite matrix. (web.stanford.edu)