Gram matrix

For vectors $v_1,\dots ,v_n$, the Gram matrix isTwo finite vector families with the same Gram matrix are related by an isometry between their spans; in finite dimensions that isometry can be extended to a unitary map after completing orthonormal bases.

A real matrix product giving pairwise dot products of columns, for $T^{\top }T$, or rows, for $T{T}^{\top }$. It is a positive semidefinite matrix. The kernel of a Gram product is determined by the corresponding factor, which makes these products useful for converting a zero quadratic form into an exact null space condition.

For real vectors $x_i$ in a Euclidean inner product space, their Gram matrix $G_{ij}=x_i^T{x}_j$ satisfies the displayed identity by expanding the squared norm. Thus every Gram matrix is a positive semidefinite matrix, and it is a positive-definite matrix exactly when the vector family is linearly independent. The complex version replaces transposes by conjugate transposes and uses $c^{\ast }Gc=\Vert {\sum }_i{c}_i{x}_i{\Vert }^2$.

For $n\ge 2$, the Gram matrix of $n$ unit vectors with common distinct-pair inner product $t$ is $G=(1-t)I+t11^T$. Its eigenvalues are $1+(n-1)t$ on the all-ones direction and $1-t$ on its orthogonal complement. It is a positive-definite symmetric matrix exactly when $-1/(n-1)<t<1$, permitting a linearly independent realization in ${\mathbb{R}}^n$. An explicit construction takes the columns ofThe two orthogonal projections have product zero, so $B^{T}B=G$; positive eigenvalues also make $B$ invertible. At either endpoint the corresponding eigenspace becomes a linear dependence.

The determinant of a Gram matrix is nonnegative and vanishes precisely when its vectors are linearly dependent. In Euclidean three-dimensional space, three column vectors form a square matrix $V$, whose Gram matrix is $V^{T}V$. Its determinant is $(\det V{)}^2=[v_1\cdot (v_2\times v_3){]}^2$, the square of the scalar triple product and of the parallelepiped volume.

For a basis $(u_i)$ of a finite-dimensional inner product space with conjugate-linear first argument, define $G_{ij}=(u_i,u_j)$ and ${\hat{u}}_k={\sum }_l(G^{-1}{)}_{lk}{u}_l$. Then $(u_i,{\hat{u}}_k)={\delta }_{ik}$ and $({\hat{u}}_j,{\hat{u}}_k)=(G^{-1}{)}_{jk}$. This is the inner-product representation of the dual basis; requiring the dual vectors to lie in the given span is essential.

For a matrix $G$ with independent standard normal entries, $G^{T}G/n$ is a Gaussian empirical Gram matrix and has expectation equal to the identity. With mean known to be zero it is the raw empirical second moment. Subtracting a sample mean would give a different estimator. On any fixed unit vector its quadratic form is a chi-squared variable divided by $n$.

For $G$ with $n$ independent standard Gaussian rows in dimension $k$, combine a constant-radius sphere metric net, the quadratic form net bound, the chi-squared concentration inequality, and a union bound. This gives $P(\Vert G^{T}G/n-I_k{\Vert }_{\mathrm{op}}>1/2)\le 2\exp (k\log B-n/1024)$ for a numerical $B$. Taking $n$ larger than a constant times $k\log p$ gives exponential decay in $k\log p$. The subspace is fixed, so no union over supports is needed.

If $E=A^{T}A/d-I$ has entrywise maximum norm at most $t$, every vector $z$ supported on at most $s$ coordinates satisfies $|z^{T}Ez|\le t\Vert z{\Vert }_1^2\le st\Vert z{\Vert }_2^2$. Thus the squared norm distortion is at most $st$ on all such sparse vectors. Use the quadratic inequality at $z=0$, where a ratio would be undefined.