The Four Fundamental Subspaces

An error corrected: the rows know about the columns

Strang opens by fixing “the blackboard with that awful error” from lecture nine. He had wanted three vectors that form a basis for $\mathbb{R}^3$, started with $(1,1,2)$ and $(2,2,5)$ — independent — and knew that $(3,3,7)$, their sum, wouldn’t do. So “in my innocence” he wrote $(3,3,8)$, figuring that if $(3,3,7)$ lies in the plane of the first two, then $(3,3,8)$ probably sticks a little bit out of it.

After class a student told him: that third vector is not independent. And she didn’t hunt for the combination that produces it. She looked at the matrix with those three columns,

$$A = \begin{bmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \\ 2 & 5 & 8 \end{bmatrix},$$

and saw two identical rows. A square matrix with two equal rows is not invertible — its rows are obviously dependent, and that forces its columns to be dependent too. The row space of this matrix is only two-dimensional, so the rank is two, so only two columns can be independent.

The four subspaces

Here they are — “really the heart of this approach to linear algebra.” For an $m \times n$ matrix $A$:

1. The column space $C(A)$ — all combinations of the columns.
2. The null space $N(A)$ — all solutions of $A\mathbf{x} = \mathbf{0}$.
3. The row space — all combinations of the rows.
4. The null space of $A^T$, written $N(A^T)$ — the fourth guy.

Where do the four spaces live? Vectors in $N(A)$ have $n$ components (they’re solutions $\mathbf{x}$), so $N(A)$ is in $\mathbb{R}^n$ — and so is the row space, since rows of $A$ have $n$ components. Columns have $m$ components, so $C(A)$ is in $\mathbb{R}^m$ — and so is $N(A^T)$. Two subspaces sit in $\mathbb{R}^n$, two in $\mathbb{R}^m$. Strang draws his famous picture: row space and null space on the $\mathbb{R}^n$ side, column space and left null space on the $\mathbb{R}^m$ side. (He notices the fourth space “is already getting second-class citizen treatment and it doesn’t deserve it.”)

To understand these spaces means answering two questions for each: how do you construct a basis, and what is the dimension? The dimension is just a number, so it has a real short answer — and Strang can’t resist giving all four short answers first.

The dimensions: r, r, n − r, m − r

Where do these come from?

Column space: a basis is the pivot columns — the pivot columns of the original $A$, not of $R$. There are $r$ of them; the rank counts them.

Null space: a basis is the special solutions, one for each free variable — set that free variable to $1$, the other free variables to $0$, and solve for the pivot variables. There are $n - r$ free variables, so $\dim N(A) = n - r$. And that’s just restating the count of variables: $n$ variables, $r$ pivot variables, $n - r$ free ones — $r + (n-r) = n$.

Left null space: “it’s got to be $m - r$.” Why? Because ”$A^T$ is just as good a matrix as $A$.” It happens to be $n \times m$, so it has $m$ columns, hence $m$ variables in $A^T\mathbf{y} = \mathbf{0}$; its rank is also $r$, leaving $m - r$ free variables. Same rule, applied to the transpose.

That leaves the row space’s dimension $r$ — and its basis — to be earned, which is the next job.

A basis for the row space

You could find the row space basis by transposing $A$, row-reducing $A^T$, and taking its pivot columns — but that means doing all that elimination over again. The work already done on $A$ ought to reveal it. Take the matrix from last lecture:

Now, a warning first. The column space changed: $(1,1,1)$ is certainly in $C(A)$ and certainly not in $C(R)$. Row operations do not preserve the column space. But they do preserve the row space — every operation replaced a row by a combination of rows, so at every step you stay inside the row space of $A$. And the steps reverse: undoing the subtractions writes the original rows as combinations of the rows of $R$. Same row space, both directions.

So a basis for the row space of $A$ is sitting in $R$: the first $r$ rows of $R$. Here, $(1,0,1,1)$ and $(0,1,1,0)$. Not the first $r$ rows of $A$ — sometimes that works, but not necessarily. They’re in the row space, there are $r$ of them, and they’re visibly independent (look at the identity sitting in the pivot columns). In fact this is the best basis: “if the columns of the identity matrix are the best basis for $\mathbb{R}^n$, the rows of this matrix are the best basis for the row space” — as clean as it can be made.

The left null space, and the matrix E

For this same $3 \times 4$ example, $r = 2$ and $m = 3$, so the left null space should be $m - r = 1$-dimensional: there is one combination of the three rows of $A$ that produces the zero row. (For the null space you combine columns to get the zero column; for the left null space you combine rows to get the zero row.) But the special-solutions trick reads off $N(A)$, not $N(A^T)$ — the left null space “is not jumping out at me here.” The trick is to keep a record of the elimination steps.

Remember Gauss–Jordan, where you tack the identity onto a square invertible matrix? Do the same for rectangular $A$: row-reduce the long matrix $\begin{bmatrix} A & I \end{bmatrix}$, with $I$ the $m \times m$ identity, all the way to

$$\begin{bmatrix} A_{m\times n} & I_{m \times m} \end{bmatrix} \;\longrightarrow\; \begin{bmatrix} R_{m\times n} & E_{m \times m} \end{bmatrix}.$$

All the row reduction amounts to multiplying on the left by one matrix — some product of elementary matrices. That something took $I$ to $E$, so that something was $E$, and therefore

$$EA = R.$$

In chapter two, when $A$ was square and invertible, $R$ was $I$, and $EA = I$ meant $E = A^{-1}$. For a rectangular $A$ there’s no inverse, but there is still an $E$.

Review of all four: the row space and null space are in $\mathbb{R}^n$, dimensions adding to $n$; the column space and left null space are in $\mathbb{R}^m$, dimensions adding to $m$.

A new vector space: matrices as “vectors”

In the last minutes, Strang pushes to a new type of vector space. Every space so far has been a subspace of some $\mathbb{R}^n$. Now take $M$ = all $3 \times 3$ matrices, and call the matrices themselves the “vectors.” Is that allowed? Yes — because they obey the rules. You can add two matrices; you can multiply a matrix by a scalar like $7$; you can take combinations like three of one matrix minus five of another; there’s a zero matrix that changes nothing when added. All eight vector-space rules are easily satisfied. The fact that you can also multiply two matrices is irrelevant — “I’m not interested in $AB$ for now.”

Subspaces of $M$: all upper triangular matrices; all symmetric matrices. The intersection of two subspaces is a subspace, and here the intersection — symmetric and upper triangular — is the diagonal matrices $D$, smaller than both. “Smaller” can now be made precise by dimension. For $D$, Strang produces a basis of three matrices:

$$\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \quad \begin{bmatrix} 1 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \quad \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 7 \end{bmatrix}$$

— three independent diagonal matrices whose combinations give every diagonal matrix. So $\dim D = 3$. The idea of basis and dimension stretches from $\mathbb{R}^n$ to matrix space without changing at all.

Problems

Work these before revealing the solutions — each one uses only the four-subspace machinery from the lecture.

Problem 10.1 All four subspaces

Find the dimension of, and a basis for, each of the four fundamental subspaces of

$$A = \begin{bmatrix} 1 & 2 & 4 \\ 2 & 4 & 8 \end{bmatrix}.$$

Show solution

Row reduce: subtract $2$ of row 1 from row 2 to get $R = \begin{bmatrix} 1 & 2 & 4 \\ 0 & 0 & 0 \end{bmatrix}$. One pivot, so $r = 1$, with $m = 2$, $n = 3$.

Column space ($\dim = r = 1$): the pivot column of $A$, basis $\begin{bmatrix} 1 \\ 2 \end{bmatrix}$.

Row space ($\dim = r = 1$): the first $r$ rows of $R$, basis $(1, 2, 4)$.

Null space ($\dim = n - r = 2$): free variables $x_2, x_3$. Special solutions: $x_2 = 1, x_3 = 0$ gives $(-2, 1, 0)$; $x_2 = 0, x_3 = 1$ gives $(-4, 0, 1)$. Those two are a basis.

Left null space ($\dim = m - r = 1$): the combination of rows giving the zero row is $-2$ of row 1 plus row 2, so a basis is $\mathbf{y} = (-2, 1)$. Check: $\mathbf{y}^T A = \mathbf{0}^T$. ✓

Problem 10.2 Rows expose the columns

Without finding any explicit combination, show that the three vectors

$$\begin{bmatrix} 1 \\ 1 \\ 3 \end{bmatrix}, \quad \begin{bmatrix} 2 \\ 2 \\ 7 \end{bmatrix}, \quad \begin{bmatrix} 4 \\ 4 \\ 13 \end{bmatrix}$$

are dependent — use the student’s argument from the start of the lecture.

Show solution

Put the vectors as the columns of a matrix:

$$A = \begin{bmatrix} 1 & 2 & 4 \\ 1 & 2 & 4 \\ 3 & 7 & 13 \end{bmatrix}.$$

Rows 1 and 2 are identical, so the rows are dependent and the row space has dimension at most $2$. The row space and column space have the same dimension $r$, so $r \le 2$ while there are $3$ columns. Three columns in a space of dimension at most two must be dependent — no combination needed.

Problem 10.3 Row space vs column space of R

Row reduce

$$A = \begin{bmatrix} 1 & 3 & 5 \\ 2 & 6 & 10 \\ 1 & 4 & 7 \end{bmatrix}$$

to $R$. Give a basis for the row space of $A$ from $R$, and then exhibit one vector that is in the column space of $A$ but not in the column space of $R$.

Show solution

Subtract $2$ of row 1 from row 2, and row 1 from row 3:

$$\begin{bmatrix} 1 & 3 & 5 \\ 0 & 0 & 0 \\ 0 & 1 & 2 \end{bmatrix} \;\longrightarrow\; \begin{bmatrix} 1 & 3 & 5 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \end{bmatrix} \;\longrightarrow\; R = \begin{bmatrix} 1 & 0 & -1 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \end{bmatrix}$$

(exchange rows 2 and 3, then subtract $3$ of the new row 2 from row 1). Rank $r = 2$.

Row space basis — the first two rows of $R$: $(1, 0, -1)$ and $(0, 1, 2)$. Row operations preserved the row space, so these span the row space of $A$ too.

Column spaces differ: every column of $R$ has third component $0$, so $C(R)$ lies in the plane $z = 0$. But column 1 of $A$, namely $(1, 2, 1)$, has third component $1$ — it is in $C(A)$ and cannot be in $C(R)$.

Problem 10.4 Finding E and the left null space

For

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

row reduce $\begin{bmatrix} A & I \end{bmatrix}$ to $\begin{bmatrix} R & E \end{bmatrix}$, verify $EA = R$, and read off a basis for $N(A^T)$.

Show solution

Start with $\begin{bmatrix} A & I \end{bmatrix}$ and eliminate. Subtract row 1 from row 2, and $2$ of row 1 from row 3:

$$\begin{bmatrix} 1 & 0 & 1 & \big| & 1 & 0 & 0 \\ 0 & 1 & 1 & \big| & -1 & 1 & 0 \\ 0 & 1 & 1 & \big| & -2 & 0 & 1 \end{bmatrix}$$

Subtract row 2 from row 3:

$$\begin{bmatrix} 1 & 0 & 1 & \big| & 1 & 0 & 0 \\ 0 & 1 & 1 & \big| & -1 & 1 & 0 \\ 0 & 0 & 0 & \big| & -1 & -1 & 1 \end{bmatrix} = \begin{bmatrix} R & E \end{bmatrix}, \qquad E = \begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ -1 & -1 & 1 \end{bmatrix}.$$

$R$ is already reduced (row 1 has a $0$ above the second pivot). Check $EA$: row 2 of $EA$ is $-\text{row 1} + \text{row 2} = (0,1,1)$ ✓; row 3 is $-\text{row 1} - \text{row 2} + \text{row 3} = (0,0,0)$ ✓. So $EA = R$.

Rank $r = 2$, so $\dim N(A^T) = m - r = 1$. The zero row of $R$ came from the last row of $E$, so a basis for the left null space is $\mathbf{y} = (-1, -1, 1)$: indeed row 3 of $A$ equals row 1 plus row 2.

Problem 10.5 Dimensions in matrix space

In the vector space $M$ of all $3 \times 3$ matrices, find the dimension of the subspace $U$ of upper triangular matrices and of the subspace $S$ of symmetric matrices, by producing a basis for each. Check that $U \cap S$ has the dimension found in lecture.

Show solution

Upper triangular: a $3 \times 3$ upper triangular matrix has $6$ free entries — three on the diagonal, three above. A basis is the six matrices with a single $1$ in one of those positions and zeros elsewhere. Any upper triangular matrix is a unique combination of them, so $\dim U = 6$.

Symmetric: a symmetric matrix is determined by its diagonal ($3$ entries) and the entries above the diagonal ($3$ entries) — the below-diagonal entries are copies. A basis: three matrices with a single $1$ on the diagonal, plus three matrices with a $1$ in position $(i,j)$ and in position $(j,i)$ for each pair $i \ne j$. So $\dim S = 6$.

Intersection: a matrix in $U \cap S$ is symmetric with zeros below the diagonal, hence zeros above too — it is diagonal. The three single-entry diagonal matrices are a basis, so $\dim(U \cap S) = 3$, matching the lecture’s answer for the diagonal matrices $D$.