Orthonormal bases and Gram–Schmidt

Skewed axes make coordinates hard; square axes make them two dot products. Watch two skewed arrows straighten up.

Square axes are easier

Suppose you want the coordinates of the point $(5,4)$ along the arrows $(2,1)$ and $(1,2)$: how many of each make $(5,4)$? You have to solve two equations, as in Two pictures of a linear system. The answer is 2 and 1, but it took a solve.

Along perpendicular arrows of length 1 there is nothing to solve. Each coordinate is the length of a shadow, from Projections, and a shadow on a unit arrow is one dot product. In the picture at the top of the page, the two coordinates of $(5,4)$ along $\mathbf{q}_1$ and $\mathbf{q}_2$ are

Check with lengths: $6.261^2+1.342^2=39.2+1.8=41$, which is $5^2+4^2$. The right-angle rule holds because the axes are square.

Orthonormal

Arrows that are all at right angles to each other and all of length 1 are orthonormal. In symbols,

The symbol $\delta_{pq}$, with two subscripts, is the Kronecker delta. Signal processing’s impulse $\delta[n]$ has square brackets; the two are told apart that way. Put orthonormal arrows side by side as the columns of a matrix $\mathbf{Q}$, and the rule becomes $\mathbf{Q}^\top\mathbf{Q}=\mathbf{I}$: entry $(p,q)$ of $\mathbf{Q}^\top\mathbf{Q}$ is $\mathbf{q}_p\cdot\mathbf{q}_q$. Any vector is then the sum of its shadows:

“Orthogonal” alone means at right angles; “orthonormal” adds length 1. The difference matters. The arrows $(2,1)$ and $(-1,2)$ are at a right angle, but they are not of length 1.

Orthogonal matrices

A square matrix with orthonormal columns is called an orthogonal matrix, an old name that really means orthonormal columns. For it, $\mathbf{Q}^\top=\mathbf{Q}^{-1}$, and it keeps every length:

From the top picture, $\mathbf{Q}=\tfrac1{\sqrt5}\begin{bmatrix}2&-1\\1&2\end{bmatrix}$. It is the rotation by 26.57°, which is 0.4636 radians: its first column points at that angle. It sends $(5,4)$ to $\tfrac1{\sqrt5}(6,13)$, whose squared length is $(36+169)/5=41$, the same as before.

Rotations and reflections are the orthogonal matrices of the plane. The reflection $\tfrac15\begin{bmatrix}3&4\\4&-3\end{bmatrix}$ is one too: its columns $(3,4)/5$ and $(4,-3)/5$ have length 1 and are at a right angle.

Gram–Schmidt

What if the arrows you have are skewed? The Gram–Schmidt process straightens them one at a time, and the picture at the top of the page shows it in two dimensions:

1. Shrink the first arrow to length 1: $\mathbf{q}_1=\mathbf{a}_1/\lVert\mathbf{a}_1\rVert=(2,1)/\sqrt5$.
2. From the second arrow, take away its shadow on $\mathbf{q}_1$. The shadow is $(\mathbf{q}_1\cdot\mathbf{a}_2)\,\mathbf{q}_1=(1.6,0.8)$, and what is left, $(-0.6,1.2)$, is at a right angle to $\mathbf{q}_1$.
3. Shrink what is left to length 1. Its length is $\sqrt{1.8}=1.342$, so $\mathbf{q}_2=(-1,2)/\sqrt5$.

For more arrows, each new arrow loses its shadows on all the $\mathbf{q}$‘s found so far, then shrinks to length 1:

Watch it in three dimensions with $\mathbf{a}_1=(1,1,0)$, $\mathbf{a}_2=(1,0,1)$ and $\mathbf{a}_3=(0,1,1)$.

The numbers are short. First, $\mathbf{q}_1=(1,1,0)/\sqrt2$. The shadow of $\mathbf{a}_2$ on it is $(0.5,0.5,0)$, which leaves $(0.5,-0.5,1)$, of length $\sqrt{1.5}=1.2247$, so $\mathbf{q}_2=(1,-1,2)/\sqrt6$. The shadows of $\mathbf{a}_3$ on $\mathbf{q}_1$ and $\mathbf{q}_2$ are $(0.5,0.5,0)$ and $\tfrac16(1,-1,2)$, which leaves $(-\tfrac23,\tfrac23,\tfrac23)$, of length $1.1547$, so $\mathbf{q}_3=(-1,1,1)/\sqrt3$. Check: $\mathbf{q}_3\cdot\mathbf{q}_1$ is proportional to $-1+1+0=0$, and $\mathbf{q}_3\cdot\mathbf{q}_2$ to $-1-1+2=0$.

Two things to notice. The order matters: start with $\mathbf{a}_2$ instead, and $\mathbf{q}_1$ becomes $(1,0,1)/\sqrt2$, so all three results change. In two dimensions, starting with $(1,2)$ gives $\mathbf{q}_1=(1,2)/\sqrt5$. And the first $k$ new arrows always span the same line, plane or space as the first $k$ old ones. Gram–Schmidt changes the axes, never the space they cover.

If an arrow lies in the space of the earlier ones, nothing is left after its shadows are taken away. With $(1,2)$ and then $(2,4)$, the second leaves $\mathbf{0}$, which cannot be shrunk to length 1. That is how Gram–Schmidt notices dependent arrows.

Worked example

1. Two arrows. $(2,1)$ and $(1,2)$ give $\mathbf{q}_1=(0.894,0.447)$ and $\mathbf{q}_2=(-0.447,0.894)$.
2. Coordinates. $(5,4)$ has coordinates $6.261$ and $1.342$ along them, and $39.2+1.8=41$.
3. A test. Are $(3,4)/5$ and $(-4,3)/5$ orthonormal? Yes: lengths 1, dot product $(-12+12)/25=0$.
4. Lengths kept. $\lVert\mathbf{Q}\mathbf{x}\rVert=\lVert\mathbf{x}\rVert$ for every orthogonal $\mathbf{Q}$.
5. Three arrows. $(1,1,0)$, $(1,0,1)$, $(0,1,1)$ give $(1,1,0)/\sqrt2$, $(1,-1,2)/\sqrt6$ and $(-1,1,1)/\sqrt3$.
6. A Fourier basis. The four arrows $(1,1,1,1)$, $(1,0,-1,0)$, $(0,1,0,-1)$ and $(1,-1,1,-1)$ are at right angles, with squared lengths 4, 2, 2 and 4. So the coordinates of $(4,0,0,0)$ along them are $4/4$, $4/2$, $0$ and $4/4$: that is $(1,2,0,1)$. Scaled to length 1, the coordinates become $(2,\ 2.828,\ 0,\ 2)$, and their squares add up to 16, the squared length of $(4,0,0,0)$.

Where you’ll meet this

The discrete Fourier transform and the discrete cosine transform are orthonormal bases, up to a scale. A JPEG image is cut into blocks of 64 pixels, and each block’s 64 coefficients are 64 dot products with the cosine basis; their squares add up to the block’s energy. A phone that turns its motion sensor’s readings into the screen’s directions uses an orthogonal matrix, so no length is distorted.

Recording the shadows and lengths of Gram–Schmidt gives a factorisation of the matrix of arrows, the subject of QR factorisation.

Reference card