Gram Matrix

The Gram matrix of real vectors , ..., in is the matrix of their inner products,

(1)

where the superscript denotes the transpose. If has these vectors as its columns, then

(2)

Consequently, is a positive semidefinite matrix, its matrix rank is the dimension of the span of the vectors, and it is a positive definite matrix iff the vectors are linearly independent. The Gram matrix determines the vectors in up to an orthogonal transformation.

The singular value decomposition shows that the eigenvalues of are the squared singular values of , together with additional zeros if has more columns than rows. If the columns of are linearly independent, then , where is the condition number, the ratio of the largest to the smallest singular value of (Watkins 2005).

Gram matrices also give a criterion for realizing prescribed distances in Euclidean space. Let for , ..., , with , and form

(3)

where , ..., . The prescribed distances can be realized by points , ..., in a Euclidean space iff is a positive semidefinite matrix. Its matrix rank is the smallest possible dimension of the affine hull of a realization (Young and Householder 1938). For a realization, this is the Gram matrix of . Conversely, factoring with a real matrix provides coordinates by taking and the columns of as the other points.

For example, prescribe distances between five labels so that and every other distance between distinct labels is 1. Every triple is realizable as either an equilateral triangle of side 1 or a triangle with sides of lengths 1, 1, . Both have area . Nevertheless, the corresponding matrix is

(4)

and its determinant is . It is therefore not a positive semidefinite matrix, so no such five points exist in any Euclidean space. Trott (2006) considers systems prescribing equal triangle areas of a four-dimensional simplex. The example shows why solutions of such algebraic systems must also be tested for Euclidean realizability.