Gram Matrices and Kernel Matrices

Why This Matters

The Gram matrix appears everywhere in ML, often without being named. When you compute $QK^T$ in attention, that is a Gram matrix. When you do kernel PCA, you operate on a kernel matrix (which is a Gram matrix in feature space). When you compute $X^TX$ for PCA or linear regression, that is a Gram matrix of the columns of $X$.

Understanding the Gram matrix and its properties (especially positive semidefiniteness) is the key link between linear algebra and kernel methods, and between kernel methods and attention.

Definitions

Definition

Gram Matrix

Given vectors $x_1, \ldots, x_n$ in an inner product space, the Gram matrix $G \in \mathbb{R}^{n \times n}$ has entries:

$G_{ij} = \langle x_i, x_j \rangle$

If $X \in \mathbb{R}^{n \times d}$ is the matrix with $x_i$ as its $i$-th row, then $G = XX^T$.

Definition

Kernel Matrix

Given a kernel function $k: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ and data points $x_1, \ldots, x_n \in \mathcal{X}$, the kernel matrix (or Gram matrix of the kernel) has entries:

$K_{ij} = k(x_i, x_j)$

If $k$ is a valid (positive definite) kernel, then by Mercer's theorem, there exists a feature map $\phi$ such that $k(x_i, x_j) = \langle \phi(x_i), \phi(x_j) \rangle$. The kernel matrix is the Gram matrix of the mapped data.

The standard inner product $\langle x, y \rangle = x^T y$ gives the simplest case. The Gram matrix with the standard inner product is just $G = XX^T$. A kernel matrix with kernel $k$ generalizes this to $K_{ij} = k(x_i, x_j)$, which computes inner products in a (possibly infinite-dimensional) feature space.

Positive Semidefiniteness

Theorem

Gram Matrices are Positive Semidefinite

Statement

For any vectors $x_1, \ldots, x_n$ in a real inner product space, the Gram matrix $G$ with $G_{ij} = \langle x_i, x_j \rangle$ is positive semidefinite. That is, for all $c \in \mathbb{R}^n$:

$c^T G c = \left\| \sum_{i=1}^{n} c_i x_i \right\|^2 \geq 0$

Intuition

The quadratic form $c^T G c$ computes the squared norm of a linear combination of the data vectors. Squared norms are always non-negative. This is why Gram matrices are always PSD: they represent inner product structure, and inner products induce non-negative norms.

Proof Sketch

$c^T G c = \sum_{i,j} c_i c_j \langle x_i, x_j \rangle = \left\langle \sum_i c_i x_i, \sum_j c_j x_j \right\rangle = \left\| \sum_i c_i x_i \right\|^2 \geq 0$

The second equality uses bilinearity of the inner product. The inequality follows from the definition of a norm.

Why It Matters

PSD is the central property of Gram matrices. It guarantees that eigenvalues are non-negative, that the matrix defines a valid (semi-)metric on the data, and that kernel methods are well-posed. Any matrix that arises as pairwise inner products must be PSD.

Failure Mode

The Gram matrix is PSD but may not be positive definite. It is singular (has zero eigenvalues) when the vectors $x_1, \ldots, x_n$ are linearly dependent. For $n > d$ (more points than dimensions), the Gram matrix $XX^T$ has rank at most $d$, so at least $n - d$ eigenvalues are zero.

Eigenvalues and Data Geometry

Proposition

Gram Matrix Eigenvalues Reflect Data Geometry

Statement

The non-zero eigenvalues of $G = XX^T$ are the same as the non-zero eigenvalues of $X^TX$. If the SVD of $X$ is $X = U\Sigma V^T$, then:

$G = XX^T = U\Sigma^2 U^T$

The eigenvalues of $G$ are $\sigma_1^2, \ldots, \sigma_r^2, 0, \ldots, 0$ where $r = \text{rank}(X)$ and $\sigma_i$ are the singular values of $X$.

Intuition

The eigenvalues of the Gram matrix tell you how the data is spread in different directions. Large eigenvalues correspond to directions of high variance in the data. This is exactly the information PCA extracts. Computing PCA from $G = XX^T$ (dual PCA) is equivalent to computing it from $X^TX$ (primal PCA), but the matrix sizes differ: $G$ is $n \times n$ while $X^TX$ is $d \times d$.

Proof Sketch

If $X = U\Sigma V^T$, then $XX^T = U\Sigma V^T V\Sigma^T U^T = U\Sigma\Sigma^T U^T = U\Sigma^2 U^T$. Similarly, $X^TX = V\Sigma^2 V^T$. Both have eigenvalues $\sigma_i^2$.

Why It Matters

This duality between $XX^T$ and $X^TX$ is the foundation of kernel PCA. When $d \gg n$ (more features than samples), working with the $n \times n$ Gram matrix is cheaper. When you use a kernel, you only have access to $K$ (the Gram matrix in feature space), and the eigendecomposition of $K$ gives you PCA in feature space.

Failure Mode

Computing the full eigendecomposition of $G$ costs $O(n^3)$. For large $n$, this is prohibitive, and you need approximate methods (randomized SVD, Nystrom approximation). Also, the Gram matrix requires $O(n^2)$ storage, which limits applicability to datasets with many observations.

Connections to ML

Kernel Methods

In kernel methods, you work with $K_{ij} = k(x_i, x_j)$ and never compute the feature map $\phi$ explicitly. The kernel matrix $K$ is all you need for:

• Kernel SVM: the dual formulation involves $K$ directly
• Kernel PCA: eigendecompose $K$ to get principal components in feature space
• Gaussian processes: the kernel matrix (plus noise) is the covariance matrix of the function values

Attention

In a transformer, the attention matrix is:

$A = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)$

The matrix $QK^T$ has entries $(QK^T)_{ij} = q_i^T k_j$, which is a Gram matrix of queries against keys. Before the softmax, this is a linear kernel matrix. The softmax converts it into a row-stochastic matrix, but the underlying structure is a Gram matrix.

PCA and SVD

PCA on $n$ data points in $\mathbb{R}^d$ can be computed from either $X^TX$ ($d \times d$, primal) or $XX^T$ ($n \times n$, dual). The dual formulation uses the Gram matrix and is the starting point for kernel PCA.

Common Confusions

Watch Out

Gram matrix vs covariance matrix

The Gram matrix is $XX^T$ (size $n \times n$, pairwise similarities between data points). The covariance matrix is $X^TX / n$ (size $d \times d$, pairwise relationships between features), assuming centered data. They encode complementary views of the same dataset: point similarities vs feature correlations.

Watch Out

PSD does not mean all entries are non-negative

A Gram matrix can have negative entries. For example, if $x_1 = (1, 0)$ and $x_2 = (-1, 0)$, then $G_{12} = -1$. PSD refers to the quadratic form $c^TGc \geq 0$ for all $c$, not to individual entries.

Key Takeaways

• Gram matrix: $G_{ij} = \langle x_i, x_j \rangle$. For data matrix $X$: $G = XX^T$
• Always PSD. Eigenvalues are non-negative.
• Kernel matrix: same structure with $k(x_i, x_j)$ replacing $\langle x_i, x_j \rangle$
• Eigenvalues of $G$ equal squared singular values of $X$
• Appears in kernel methods, PCA (dual formulation), SVD, and attention ($QK^T$)

Exercises

ExerciseCore

Problem

Given $x_1 = (1, 2)$, $x_2 = (3, 0)$, $x_3 = (0, 1)$, compute the Gram matrix $G = XX^T$ where rows of $X$ are $x_1, x_2, x_3$. Verify that $G$ is PSD by checking that all eigenvalues are non-negative.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Prove that the attention score matrix $QK^T$ in a transformer is a Gram matrix. What does this imply about the eigenvalues of $QK^T$ before the softmax is applied? Is $QK^T$ always PSD?

Hint

Reveal Solution

References

Canonical:

• Horn & Johnson, Matrix Analysis (2013), Chapter 7 (Positive Definite Matrices)
• Scholkopf & Smola, Learning with Kernels (2002), Chapter 2

Current:

• Vaswani et al., "Attention Is All You Need" (2017), for the attention connection
• Murphy, Probabilistic Machine Learning: An Introduction (2022), Chapter 16

Next Topics

• Kernels and RKHS: the theoretical foundation for kernel matrices
• Principal component analysis: PCA from the dual (Gram matrix) perspective
• Attention mechanism theory: where Gram matrices meet modern deep learning