Orthogonal Matrices and Gram-Schmidt

Orthonormal vectors: the letter q

This is the last lecture in the chapter on orthogonality — the chapter that met orthogonal vectors, then orthogonal subspaces like the row space and null space. Today it meets an orthogonal basis and an orthogonal matrix. In Strang’s words, “this chapter cleans up orthogonality.”

The right word is really orthonormal. Strang writes his vectors as $\mathbf{q}_1, \mathbf{q}_2, \ldots, \mathbf{q}_n$ — the letter $q$ is a standing reminder that these are not just any vectors but orthogonal ones.

It’s a natural idea — a basis headed off at ninety-degree angles, all inner products zero. And it’s the basis numerical linear algebra is built around: computations with orthonormal vectors “never get out of hand, they never overflow or underflow.” The lecture has two halves. First: how does having an orthonormal basis make everything nice? Second: if your columns are not orthonormal, how do you make them so? The two names attached to that second, simple idea are Gram and Schmidt.

The matrix Q, and why Q transpose Q equals I

Put the orthonormal vectors into the columns of a matrix $Q$: first column $\mathbf{q}_1$, last column $\mathbf{q}_n$. The whole chapter has been looking at $A^T A$, so it’s natural to look at $Q^T Q$. The beauty is it comes out perfectly. The rows of $Q^T$ are $\mathbf{q}_1^T, \ldots, \mathbf{q}_n^T$, and multiplying rows times columns just asks for all the dot products: first row times first column is $1$; first row times second column is $0$ — that’s the orthogonality. Ones on the diagonal, zeroes everywhere else:

$$Q^T Q = \begin{bmatrix} \mathbf{q}_1^T \\ \vdots \\ \mathbf{q}_n^T \end{bmatrix} \begin{bmatrix} \mathbf{q}_1 & \cdots & \mathbf{q}_n \end{bmatrix} = I$$

Note that $Q$ does not have to be square here — two orthonormal columns with four components each work fine.

A gallery of examples

Permutations. Any permutation matrix qualifies, say

$$Q = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}$$

Unit vectors in the columns, certainly perpendicular to each other. Its transpose is another orthogonal matrix, and $Q^T Q = I$. Easy examples — getting orthogonal columns by putting ones in different places is “like too easy.”

Rotations. Take a unit vector $(\cos\theta, \sin\theta)$; to make the inner product with the second column zero, put a minus sign in:

$$Q = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix}$$

Fixing up lengths. Is $\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$ an orthogonal matrix? Orthogonal columns, yes — but the length squared of each column is $2$, so divide by $\sqrt{2}$:

$$Q = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$$

That’s the rotation matrix at (about) $\theta = \pi/4$.

Hadamard. Repeat that pattern in blocks — the block again, and minus it in the corner:

$$Q = \frac{1}{2}\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{bmatrix}$$

One of the world’s favorite orthogonal matrices: every entry $1$ or $-1$, every pair of columns balancing pluses against minuses, and the length of $(1,1,1,1)$ is $\sqrt{4} = 2$, so divide by $2$. This construction is named after Hadamard, and it works for sizes $2, 4, 16, 64, \ldots$ — but nobody knows exactly which sizes allow an orthogonal matrix of ones and minus ones. Some sizes are known, some are impossible (no $5 \times 5$), and for some sizes it’s still an open question.

A rectangular Q. The columns $\frac{1}{3}(1, 2, 2)$ and $\frac{1}{3}(-2, -1, 2)$ are orthonormal (each length: $\sqrt{1 + 4 + 4} = 3$, hence the division). Two orthonormal columns in $\mathbb{R}^3$: an orthonormal basis for the two-dimensional plane they span. And orthonormal vectors are automatically independent — headed off at ninety degrees, no combination can give zero. To extend to a third column you could run Gram-Schmidt on any independent third vector, or be inspired: the pattern $\frac{1}{3}(2, -2, 1)$ fixes up the signs. That’s about the last example without square roots — the punishing thing in Gram-Schmidt, “maybe we better know that in advance,” is that making unit vectors means dividing by lengths, and lengths are square roots.

What a Q is good for: projections without inversion

Suppose $Q$ has orthonormal columns and I want to project onto its column space. The big projection formula from this chapter had four $A$‘s in a row; with $Q$‘s it reads $P = Q(Q^T Q)^{-1} Q^T$. But $Q^T Q$ is the identity — no inversion to do:

All the messy equations of this chapter become trivial. The most important one was the normal equation $A^T A \hat{\mathbf{x}} = A^T \mathbf{b}$. With $A = Q$ it becomes $Q^T Q\, \hat{\mathbf{x}} = Q^T \mathbf{b}$, and the matrix on the left is the identity. Normally it’s a matrix of inner products — “you’ve got to compute all those dopey inner products and solve the system.” Here it’s gone:

$$\hat{\mathbf{x}} = Q^T \mathbf{b}, \qquad \text{component by component:} \quad \hat{x}_i = \mathbf{q}_i^T \mathbf{b}$$

Gram-Schmidt: making vectors orthonormal

Now the second half. We start with merely independent vectors $\mathbf{a}$ and $\mathbf{b}$ — maybe in two dimensions, maybe in twelve — and want orthonormal $\mathbf{q}_1, \mathbf{q}_2$. This calculation isn’t quite like elimination: there the goal was a triangular matrix, here the goal is orthonormal columns. There’s really only one idea, and Strang jokes that “if Gram had the idea, I don’t know what Schmidt did” — Schmidt’s contribution, it turns out, is dividing by the lengths at the end.

The plan: first produce orthogonal vectors $\mathbf{A}$ and $\mathbf{B}$ (that’s Gram’s part), then normalize, $\mathbf{q}_1 = \mathbf{A}/\lVert\mathbf{A}\rVert$ and $\mathbf{q}_2 = \mathbf{B}/\lVert\mathbf{B}\rVert$ (that’s Schmidt’s).

The first direction is fine as it is: $\mathbf{A} = \mathbf{a}$, no complaint. The trouble is the second direction — $\mathbf{b}$ isn’t orthogonal to $\mathbf{A}$. Where in this chapter did a vector show up that was orthogonal? In the very first calculation: projection split $\mathbf{b}$ into a piece along $\mathbf{a}$ and an error piece $\mathbf{e}$ at ninety degrees. Before, we wanted the projection; now the projection is what we throw away and the error is what we keep:

How is the column space of $Q$ related to the column space of the original $A$ with columns $(1,1,1)$ and $(1,0,2)$? They’re one and the same plane. $\mathbf{B}$ is a combination of $\mathbf{b}$ and $\mathbf{a}$, so we never left the space — we just put ninety-degree angles into it. The original columns were a perfectly good basis; this one is better, because with it every projection and calculation you’d ever want is a cinch.

A = QR

One final point, and it’s just like elimination. We learned elimination’s steps, and then captured the whole process in matrix language: $A = LU$. Gram-Schmidt deserves the same treatment. Nobody working in linear algebra writes out the subtraction formulas each time; they write the connection between the matrix $A$ you start with and the matrix $Q$ you end with:

$$A = QR$$

— “the magic formula,” the expression of Gram-Schmidt. For two columns:

$$\begin{bmatrix} \mathbf{a}_1 & \mathbf{a}_2 \end{bmatrix} = \begin{bmatrix} \mathbf{q}_1 & \mathbf{q}_2 \end{bmatrix} \begin{bmatrix} \mathbf{a}_1^T\mathbf{q}_1 & \mathbf{a}_2^T\mathbf{q}_1 \\ \mathbf{a}_1^T\mathbf{q}_2 & \mathbf{a}_2^T\mathbf{q}_2 \end{bmatrix}$$

The entries of $R$ are the inner products of the original columns with the $\mathbf{q}$‘s. And the main point: $R$ is upper triangular. The entry below the diagonal is $\mathbf{a}_1^T \mathbf{q}_2$, and that’s zero — because the whole point of Gram-Schmidt was to construct the later $\mathbf{q}$‘s perpendicular to all the earlier vectors. The result is extremely satisfactory: a matrix with independent columns factors into a matrix with orthonormal columns times a triangular matrix.

Problems

Work these before revealing the solutions — the lecture’s formulas are all you need.

Problem 17.1 Completing an orthogonal matrix

Verify that $\mathbf{q}_1 = \frac{1}{3}(1, 2, 2)$ and $\mathbf{q}_2 = \frac{1}{3}(2, 1, -2)$ are orthonormal, then find a third column $\mathbf{q}_3$ that makes

$$Q = \begin{bmatrix} \mathbf{q}_1 & \mathbf{q}_2 & \mathbf{q}_3 \end{bmatrix}$$

a square orthogonal matrix.

Show solution

Lengths: $1^2 + 2^2 + 2^2 = 9$ and $2^2 + 1^2 + (-2)^2 = 9$, so dividing by $3$ makes each a unit vector. Orthogonality: $\frac{1}{9}\big(1 \cdot 2 + 2 \cdot 1 + 2 \cdot (-2)\big) = \frac{1}{9}(2 + 2 - 4) = 0$.

For $\mathbf{q}_3$ we need a unit vector perpendicular to both. Try the same pattern of $1$s and $2$s with signs fixed up: $\mathbf{q}_3 = \frac{1}{3}(-2, 2, -1)$. Check: $(1)(-2) + (2)(2) + (2)(-1) = -2 + 4 - 2 = 0$ against $\mathbf{q}_1$, and $(2)(-2) + (1)(2) + (-2)(-1) = -4 + 2 + 2 = 0$ against $\mathbf{q}_2$; its length squared is $4 + 4 + 1 = 9$. So

$$Q = \frac{1}{3}\begin{bmatrix} 1 & 2 & -2 \\ 2 & 1 & 2 \\ 2 & -2 & -1 \end{bmatrix}$$

is orthogonal, and $Q^T = Q^{-1}$.

Problem 17.2 Gram-Schmidt by hand

Apply Gram-Schmidt to

$$\mathbf{a} = \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}, \qquad \mathbf{b} = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix}$$

to produce orthonormal vectors $\mathbf{q}_1$ and $\mathbf{q}_2$.

Show solution

$\mathbf{A} = \mathbf{a}$. Then $\mathbf{A}^T\mathbf{b} = 1$ and $\mathbf{A}^T\mathbf{A} = 2$, so

$$\mathbf{B} = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} - \frac{1}{2}\begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 1/2 \\ -1/2 \\ 1 \end{bmatrix}$$

Check: $\mathbf{A}^T\mathbf{B} = \frac{1}{2} - \frac{1}{2} + 0 = 0$. Normalize: $\lVert \mathbf{A} \rVert = \sqrt{2}$ and $\lVert \mathbf{B} \rVert = \sqrt{\frac{1}{4} + \frac{1}{4} + 1} = \sqrt{\frac{3}{2}}$, so

$$\mathbf{q}_1 = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}, \qquad \mathbf{q}_2 = \frac{1}{\sqrt{6}}\begin{bmatrix} 1 \\ -1 \\ 2 \end{bmatrix}$$

(the square roots showing up, as promised).

Problem 17.3 Projection made trivial

Let $Q$ have the orthonormal columns $\mathbf{q}_1 = \frac{1}{3}(1, 2, 2)$ and $\mathbf{q}_2 = \frac{1}{3}(-2, -1, 2)$. Project $\mathbf{b} = (3, 3, 3)$ onto the column space of $Q$ using $\mathbf{p} = QQ^T\mathbf{b}$, and verify that the error $\mathbf{e} = \mathbf{b} - \mathbf{p}$ is perpendicular to both columns.

Show solution

With an orthonormal basis, each coefficient is a dot product:

$$\mathbf{q}_1^T \mathbf{b} = \frac{3 + 6 + 6}{3} = 5, \qquad \mathbf{q}_2^T \mathbf{b} = \frac{-6 - 3 + 6}{3} = -1$$

So

$$\mathbf{p} = 5\,\mathbf{q}_1 - 1\,\mathbf{q}_2 = \frac{5}{3}\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix} - \frac{1}{3}\begin{bmatrix} -2 \\ -1 \\ 2 \end{bmatrix} = \frac{1}{3}\begin{bmatrix} 7 \\ 11 \\ 8 \end{bmatrix}$$

Then $\mathbf{e} = \mathbf{b} - \mathbf{p} = \frac{1}{3}(2, -2, 1)$, and

$$\mathbf{e}^T\mathbf{q}_1 = \frac{2 - 4 + 2}{9} = 0, \qquad \mathbf{e}^T\mathbf{q}_2 = \frac{-4 + 2 + 2}{9} = 0$$

No matrix was inverted anywhere — that’s the whole point of $P = QQ^T$.

Problem 17.4 Finding R in A = QR

For the vectors of Problem 17.2, write $A = \begin{bmatrix} \mathbf{a} & \mathbf{b} \end{bmatrix}$ and find the matrix $R$ in $A = QR$. Confirm that $R$ is upper triangular and that $QR$ reproduces $A$.

Show solution

Since $Q^T Q = I$, multiplying $A = QR$ by $Q^T$ gives $R = Q^T A$ — inner products of the original columns with the $\mathbf{q}$‘s:

$$R = \begin{bmatrix} \mathbf{q}_1^T\mathbf{a} & \mathbf{q}_1^T\mathbf{b} \\ \mathbf{q}_2^T\mathbf{a} & \mathbf{q}_2^T\mathbf{b} \end{bmatrix} = \begin{bmatrix} \sqrt{2} & 1/\sqrt{2} \\ 0 & \sqrt{6}/2 \end{bmatrix}$$

The zero appears because $\mathbf{q}_2$ was constructed perpendicular to $\mathbf{a}$ — that’s why $R$ is always upper triangular. Check the second column of $QR$:

$$\frac{1}{\sqrt{2}}\,\mathbf{q}_1 + \frac{\sqrt{6}}{2}\,\mathbf{q}_2 = \begin{bmatrix} 1/2 \\ 1/2 \\ 0 \end{bmatrix} + \begin{bmatrix} 1/2 \\ -1/2 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} = \mathbf{b} \checkmark$$

(and the first column is $\sqrt{2}\,\mathbf{q}_1 = \mathbf{a}$).

Problem 17.5 Orthonormal implies independent

The lecture claims orthonormal vectors “have got to be independent.” Prove it: if $\mathbf{q}_1, \ldots, \mathbf{q}_n$ are orthonormal and $c_1\mathbf{q}_1 + \cdots + c_n\mathbf{q}_n = \mathbf{0}$, show every $c_i$ is zero.

Show solution

Take the dot product of the combination with $\mathbf{q}_i$:

$$\mathbf{q}_i^T\big(c_1\mathbf{q}_1 + \cdots + c_n\mathbf{q}_n\big) = c_1\,\mathbf{q}_i^T\mathbf{q}_1 + \cdots + c_n\,\mathbf{q}_i^T\mathbf{q}_n$$

Every term dies except the $i$-th, because $\mathbf{q}_i^T\mathbf{q}_j = 0$ for $j \neq i$, while $\mathbf{q}_i^T\mathbf{q}_i = 1$. So the left side is $\mathbf{q}_i^T\mathbf{0} = 0$ and the right side is $c_i$: hence $c_i = 0$ for every $i$. Only the trivial combination gives zero — the vectors are independent.