Orthogonal Vectors and Subspaces

A ninety-degree chapter

Lecture fourteen starts a new chapter — a chapter about orthogonality. What it means for vectors to be orthogonal, what it means for subspaces to be orthogonal, and eventually what it means for bases to be orthogonal. “This is a ninety-degree chapter,” Strang says.

The motivation is the big picture — the 18.06 picture of the four fundamental subspaces. We already know a lot about it: the row space and null space live in $\mathbb{R}^n$ with dimensions $r$ and $n - r$; the column space and left null space live in $\mathbb{R}^m$ with dimensions $r$ and $m - r$. What the figure has been quietly claiming all along, and what this lecture proves, is that the angle between those paired subspaces is ninety degrees. The row space is orthogonal to the null space; the column space is orthogonal to the left null space. We knew what each subspace was and could compute bases for them. Now we know how they sit relative to each other.

When are two vectors orthogonal?

Orthogonal is just another word for perpendicular: in $n$-dimensional space, the angle between the vectors is ninety degrees — they form a right triangle. So how do you test two vectors for orthogonality?

Why is that the right test? Go back to the Greeks. Pythagoras says: we have a right triangle exactly when the two leg lengths squared add up to the hypotenuse squared. With legs $\mathbf{x}$ and $\mathbf{y}$, the hypotenuse is $\mathbf{x} + \mathbf{y}$, so the right-angle condition is

$$\|\mathbf{x}\|^2 + \|\mathbf{y}\|^2 = \|\mathbf{x} + \mathbf{y}\|^2.$$

Don’t think this is always true — for other triangles it isn’t. It’s equivalent to orthogonality. And the length squared of a vector is itself a transpose product: $\|\mathbf{x}\|^2 = \mathbf{x}^T\mathbf{x} = x_1^2 + \cdots + x_n^2$, a number that’s positive unless $\mathbf{x}$ is the zero vector.

Now the same computation in letters. Expand the right side by matrix multiplication — just follow the rules:

$$(\mathbf{x} + \mathbf{y})^T(\mathbf{x} + \mathbf{y}) = \mathbf{x}^T\mathbf{x} + \mathbf{y}^T\mathbf{y} + \mathbf{x}^T\mathbf{y} + \mathbf{y}^T\mathbf{x}.$$

The $\mathbf{x}^T\mathbf{x}$ and $\mathbf{y}^T\mathbf{y}$ cancel against the left side of Pythagoras. And for real vectors there’s no difference between $\mathbf{x}^T\mathbf{y}$ and $\mathbf{y}^T\mathbf{x}$ — both are $x_1y_1 + x_2y_2 + \cdots$ — so what’s left is $2\,\mathbf{x}^T\mathbf{y} = 0$. Pythagoras boils down exactly to the dot-product test. “It’s just — I just want to say that’s really neat.”

One boundary case: what if $\mathbf{x}$ is the zero vector? Follow the rules — zero dotted with anything is zero — so the zero vector is orthogonal to everybody.

When are two subspaces orthogonal?

Now extend the idea from vectors to subspaces.

To see what that definition really demands, take Strang’s classroom example in $\mathbb{R}^3$: the blackboard, extended to infinity, is a two-dimensional subspace; the floor is another one; put the origin at the crack where they meet — “thereby giving linear algebra its proper importance.” Are the blackboard and the floor orthogonal subspaces? The class votes; some yeses, some noes. No. A forty-five-degree vector in the blackboard and a vector in the floor are not at ninety degrees. Even worse, there’s a vector running along the crack that lies in both planes — and a nonzero vector is certainly not orthogonal to itself. In fact, if two subspaces meet in any nonzero vector, they cannot be orthogonal.

Run through the subspaces of the plane — the zero vector, lines through the origin, the whole plane. When is a line through the origin orthogonal to the whole plane? Never. To the zero subspace? Always. To a different line through the origin? Exactly when the two lines meet at ninety degrees — they intersect only at zero, and they’re orthogonal. That’s the clean picture to hold on to.

The row space is orthogonal to the null space

Here is the neat fact this machinery was built for.

Why? All we know about the null space is the equation $A\mathbf{x} = \mathbf{0}$ — and the proof is just sitting there in that equation. Write it out by rows:

$$\begin{bmatrix} \text{row 1 of } A \\ \text{row 2 of } A \\ \vdots \\ \text{row } m \text{ of } A \end{bmatrix} \mathbf{x} = \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{bmatrix}$$

Each zero on the right says that a row of $A$, dotted with $\mathbf{x}$, gives zero. So $\mathbf{x}$ is orthogonal to row one, to row two, to every row. But strictly speaking that’s not the whole row space — the row space contains all the combinations of the rows too. No problem: if $(\text{row } 1)^T\mathbf{x} = 0$ and $(\text{row } 2)^T\mathbf{x} = 0$, multiply by any $c_1$, $c_2$ and add — still zero:

$$(c_1\,\text{row } 1 + c_2\,\text{row } 2 + \cdots)^T\,\mathbf{x} = 0.$$

“I just added the zeroes and got zero.” So $\mathbf{x}$ is perpendicular to every vector in the row space, and the two subspaces are orthogonal. The statement for the column space and left null space is the same statement applied to $A^T$ — and ”$A^T$ is just as good a matrix as $A$” — so no second proof needed. The big picture is now carved up correctly: $\mathbb{R}^n$ splits into two perpendicular subspaces, and so does $\mathbb{R}^m$.

Orthogonal complements

There’s a little more that’s true, and it comes from the dimensions. Could two perpendicular lines in $\mathbb{R}^3$ be a row space and a null space? No — the dimensions are no good. They must add to $n$: $r + (n - r) = n$, and $1 + 1 \neq 3$.

Try the concrete case: let $A$ have rows $(1, 2, 5)$ and $(2, 4, 10)$. The rank is one, so the row space is a line through $(1, 2, 5)$ — the second row changed nothing, and we could just as well keep the single equation $x_1 + 2x_2 + 5x_3 = 0$. Its solutions form the null space: a plane, dimension $n - r = 2$. And now we see the geometry we missed back in September: it is exactly the plane perpendicular to $(1, 2, 5)$. That “dumb normal vector called N” from calculus — there it is, the row of the matrix.

Coming attraction: solving Ax = b when there is no solution

Now the main problem of the chapter — the last chapter about $A\mathbf{x} = \mathbf{b}$. Strang wants to “solve” the system when there is no solution: when $\mathbf{b}$ is not in the column space. Ridiculous? It’s done all the time — it has to be done. A satellite buzzes along and you make a thousand position measurements, but there are only six or so parameters to find: a thousand equations, six unknowns. Or you measure one pulse rate several times and every measurement carries noise. Typically $m$ is much bigger than $n$, the rank can’t be $m$, and most right-hand sides are unsolvable. The measurements have junk in them — but they also carry real information about $\mathbf{x}$, and the job is to separate the information from the noise.

One bad idea: throw away equations until a nice square invertible system remains. Not satisfactory — there’s no reason to call some measurements perfect and others useless. We want the maximum information from all of them. Elimination won’t rescue us either; it will just certify that there is no solution.

So Strang jumps ahead to the matrix that will play the key role: $A^T A$. If $A$ is $m$ by $n$, then $A^T A$ is $n$ by $n$ — square. And it’s symmetric: transposing gives $(A^T A)^T = A^T (A^T)^T = A^T A$. He even admits the central equation of the chapter right away. When $A\mathbf{x} = \mathbf{b}$ has no solution, multiply both sides by $A^T$ and solve

$$A^T A\,\hat{\mathbf{x}} = A^T \mathbf{b},$$

where the hat on $\hat{\mathbf{x}}$ signals that this is not the (nonexistent) solution of the original system but the best solution — what “best” means is next lecture’s business. Everything hinges on whether $A^T A$ is invertible.

That example is the general pattern. $A^T A$ is not always invertible — it could even be the zero matrix. The fact that always holds, to be proved as soon as possible, is that $N(A^T A) = N(A)$, and so the rank of $A^T A$ equals the rank of $A$. From that comes the conclusion the whole chapter needs:

Next lecture — a crucial one — shows how $A^T A$ enters everything.

Problems

Work these before revealing the solutions — every one uses only this lecture’s tools.

Problem 14.1 Dot product & Pythagoras

Verify that $\mathbf{x} = (1, -2, 2)$ and $\mathbf{y} = (4, 2, 0)$ are orthogonal, and confirm Pythagoras: check that $\|\mathbf{x}\|^2 + \|\mathbf{y}\|^2 = \|\mathbf{x}+\mathbf{y}\|^2$.

Show solution

Orthogonality test: $\mathbf{x}^T\mathbf{y} = (1)(4) + (-2)(2) + (2)(0) = 4 - 4 + 0 = 0$. ✓

Lengths: $\|\mathbf{x}\|^2 = 1 + 4 + 4 = 9$ and $\|\mathbf{y}\|^2 = 16 + 4 + 0 = 20$.

Hypotenuse: $\mathbf{x} + \mathbf{y} = (5, 0, 2)$, so $\|\mathbf{x}+\mathbf{y}\|^2 = 25 + 0 + 4 = 29$.

Indeed $9 + 20 = 29$ — Pythagoras holds, exactly because the dot product is zero.

Problem 14.2 Row space ⊥ null space, concretely

Let

$$A = \begin{bmatrix} 2 & 1 & -3 \\ 4 & 2 & -6 \end{bmatrix}.$$

Describe the row space and the null space geometrically, verify that they are orthogonal, and check that their dimensions add to $n = 3$.

Show solution

The second row is twice the first, so the rank is $r = 1$. The row space is the line through $(2, 1, -3)$.

The null space is the set of solutions of the single equation $2x_1 + x_2 - 3x_3 = 0$ — a plane through the origin with normal vector $(2, 1, -3)$, dimension $n - r = 2$.

Orthogonality: any $\mathbf{x}$ in the null space satisfies $(2, 1, -3)^T\mathbf{x} = 0$, so it is perpendicular to the row $(2,1,-3)$ and hence to every multiple of it — every vector in the row space.

Dimensions: $1 + 2 = 3 = n$. The plane is the orthogonal complement of the line.

Problem 14.3 Dimensions must add up

In $\mathbb{R}^3$, could a line through the origin be the row space of some matrix while a perpendicular line through the origin is its null space? In $\mathbb{R}^4$, could the row space and null space of a matrix both be two-dimensional planes? Explain.

Show solution

In $\mathbb{R}^3$: no. The dimensions of the row space and null space are $r$ and $n - r$, which must add to $n = 3$. Two lines give $1 + 1 = 2 \neq 3$. Orthogonality alone isn’t enough — the null space must be the orthogonal complement, containing all vectors perpendicular to the row space, and in $\mathbb{R}^3$ everything perpendicular to a line is a whole plane.

In $\mathbb{R}^4$: yes. Now $2 + 2 = 4 = n$, so the dimensions are right. For example

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

has row space the $x_1 x_2$-plane and null space the $x_3 x_4$-plane — orthogonal complements in $\mathbb{R}^4$.

Problem 14.4 Computing A^T A

For

$$A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix},$$

compute $A^T A$, decide whether it is invertible, and explain how you could have predicted invertibility from the columns of $A$ alone. Then replace the second column of $A$ by $(2, 2, 2)$ and repeat.

Show solution

$A^T A$ is 2 by 2; its entries are dot products of the columns of $A$:

$$A^T A = \begin{bmatrix} 3 & 3 \\ 3 & 5 \end{bmatrix}.$$

The columns $(3,3)$ and $(3,5)$ are not multiples of each other, so $A^T A$ is invertible. Predicted: the columns $(1,1,1)$ and $(0,1,2)$ of $A$ are independent, and $A^T A$ is invertible exactly when the columns of $A$ are independent.

With second column $(2,2,2) = 2 \times (1,1,1)$, the columns of $A$ are dependent (rank one), and

$$A^T A = \begin{bmatrix} 3 & 6 \\ 6 & 12 \end{bmatrix}$$

has its second column twice its first — rank one, not invertible. The rank of $A^T A$ matched the rank of $A$ both times.

Problem 14.5 Why N(A^T A) = N(A)

Prove the fact Strang promised: $A^T A\,\mathbf{x} = \mathbf{0}$ exactly when $A\mathbf{x} = \mathbf{0}$. Hint for the harder direction: if $A^T A\,\mathbf{x} = \mathbf{0}$, multiply on the left by $\mathbf{x}^T$ and remember what $\mathbf{v}^T\mathbf{v}$ means.

Show solution

Easy direction: if $A\mathbf{x} = \mathbf{0}$, then $A^T A\,\mathbf{x} = A^T(A\mathbf{x}) = A^T\mathbf{0} = \mathbf{0}$. So $N(A) \subseteq N(A^T A)$.

Harder direction: suppose $A^T A\,\mathbf{x} = \mathbf{0}$. Multiply by $\mathbf{x}^T$:

$$\mathbf{x}^T A^T A\,\mathbf{x} = 0, \quad \text{i.e.} \quad (A\mathbf{x})^T(A\mathbf{x}) = 0.$$

But $\mathbf{v}^T\mathbf{v}$ is the length squared of $\mathbf{v}$ — a sum of squares, zero only when $\mathbf{v}$ is the zero vector. So $A\mathbf{x} = \mathbf{0}$.

The two null spaces contain each other, so $N(A^T A) = N(A)$. Since $A^T A$ and $A$ have the same null space and the same number of columns $n$, they have the same rank — and in particular $A^T A$ is invertible exactly when $N(A) = \lbrace\mathbf{0}\rbrace$, i.e. when the columns of $A$ are independent.