Column Space, Row Space and Rank, linear algebra I lesson

Take the 3 by 3 matrix $M$ with columns $(1, 2, 3)$ , $(2, 4, 6)$ and $(1, 0, 1)$ , where each tuple stands for a column vector. The second column is twice the first, so the outputs $M\mathbf{x}$ cannot fill all of $\mathbb{R}^3$ . Which plane do they fill, and how can we find such a plane when the dependence is harder to see? This lesson finds bases for the column space and the row space of a matrix by elimination, shows that the two spaces always have the same dimension, and uses that number, the rank, to factor the matrix.

Key terms

Column space

Definition Let $A$ be a real $m \times n$ matrix with columns $\mathbf{a}_1, \dots, \mathbf{a}_n$ . The column space of $A$ is the span of its columns,

\begin{aligned} \operatorname{Col} A &= \operatorname{span}\{\mathbf{a}_1, \dots, \mathbf{a}_n\} \\[0.4em] &= \{A\mathbf{x} \mid \mathbf{x} \in \mathbb{R}^n\}. \end{aligned}

The two descriptions agree because $A\mathbf{x} = x_1\mathbf{a}_1 + \cdots + x_n\mathbf{a}_n$ . Each column has $m$ entries, so $\operatorname{Col} A$ is a subspace of $\mathbb{R}^m$ , the output space of $A$ . The system $A\mathbf{x} = \mathbf{b}$ has a solution exactly when $\mathbf{b}$ lies in $\operatorname{Col} A$ .

In plain words The column space is the set of all outputs the matrix can produce. Each output is a combination of the columns, weighted by the entries of the input.

Example Write the matrix from the opening as

M = \begin{bmatrix} 1 & 2 & 1 \\ 2 & 4 & 0 \\ 3 & 6 & 1 \end{bmatrix}.

In each column the third entry is the sum of the first two, so every output $M\mathbf{x}$ lies in the plane $w_3 = w_1 + w_2$ of $\mathbb{R}^3$ . The columns $(1, 2, 3)$ and $(1, 0, 1)$ are not parallel, so they span a two-dimensional subspace of that plane, which is therefore the whole plane. Thus $\operatorname{Col} M$ is the plane $w_3 = w_1 + w_2$ . The target $(1, 1, 5)$ is not in it, since $5 \ne 1 + 1$ , so the system $M\mathbf{x} = (1, 1, 5)$ has no solution.

Row space

Definition The row space of a real $m \times n$ matrix $A$ is the span of its $m$ rows, where each row is identified with the vector of $\mathbb{R}^n$ that has the same entries. Equivalently $\operatorname{Row} A = \operatorname{Col} A^{\top}$ , a subspace of $\mathbb{R}^n$ , the input space of $A$ . Row operations do not change the row space, because each new row is a combination of the old rows and each operation can be undone. The nonzero rows of any echelon form of $A$ are linearly independent, since in a zero combination of them the pivot columns, read from left to right, force each coefficient to be zero in turn. So those nonzero rows form a basis of $\operatorname{Row} A$ .

In plain words The row space collects every combination of the rows. It lives in the input space, so its vectors have one entry for each column of $A$ , even when the matrix is square and the input and output spaces are both $\mathbb{R}^n$ .

Example For $M$ , the operations $R_2 \to R_2 - 2R_1$ and $R_3 \to R_3 - 3R_1$ come first. Then $R_3 \to R_3 - R_2$ , $R_2 \to -\tfrac{1}{2}R_2$ and $R_1 \to R_1 - R_2$ give the reduced row echelon form $F$ .

\begin{aligned} M &\to \begin{bmatrix} 1 & 2 & 1 \\ 0 & 0 & -2 \\ 0 & 0 & -2 \end{bmatrix} \\[0.4em] &\to \begin{bmatrix} 1 & 2 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix} = F. \end{aligned}

So $\operatorname{Row} M$ has basis $(1, 2, 0)$ , $(0, 0, 1)$ . It consists of the vectors $(a, 2a, b)$ , the plane $x_2 = 2x_1$ in $\mathbb{R}^3$ . All three rows of $M$ are nonzero, but row 3 is row 1 plus row 2, so counting the nonzero rows of $M$ itself would overstate the dimension.

Pivot columns of the original matrix

Definition Let $A$ be a real $m \times n$ matrix and $F$ an echelon form of $A$ . The columns of $A$ with the same indices as the pivot columns of $F$ form a basis of $\operatorname{Col} A$ . The reason is that $F = EA$ for an invertible matrix $E$ , the product of the elementary matrices of the row operations, so $A\mathbf{x} = \mathbf{0}$ exactly when $F\mathbf{x} = \mathbf{0}$ . Hence the columns of $A$ and the columns of $F$ satisfy the same linear relations. In $F$ the pivot columns are independent and every other column is a combination of them, so the same holds for the columns of $A$ . The pivot columns of $F$ itself need not lie in $\operatorname{Col} A$ , because row operations can change the column space.

In plain words Let the echelon form tell you which columns to keep, then take those columns from the original matrix. Row operations keep the relations among the columns but can change the columns themselves.

Example The reduced form $F$ of $M$ has pivots in columns 1 and 3, so the first and third columns of $M$ , namely $(1, 2, 3)$ and $(1, 0, 1)$ , form a basis of $\operatorname{Col} M$ . The second column is twice the first in $F$ and in $M$ alike. The pivot columns of $F$ are $(1, 0, 0)$ and $(0, 1, 0)$ , and neither lies in $\operatorname{Col} M$ . For instance, the third entry of $(1, 0, 0)$ is $0$ , not the sum $1 + 0$ of its first two entries. The column space of $F$ is the plane $w_3 = 0$ , a different plane.

Rank

Definition The rank of a real $m \times n$ matrix $A$ is the dimension of its column space,

\operatorname{rank} A = \dim \operatorname{Col} A.

Since the pivot columns of $A$ form a basis of $\operatorname{Col} A$ , the rank equals the number of pivots in any echelon form of $A$ . Each pivot uses its own row and its own column, so $\operatorname{rank} A \le \min(m, n)$ .

In plain words The rank counts the independent directions among the outputs. It is the number of columns you really need once the redundant ones are dropped.

Example The matrix $M$ has two pivots, so $\operatorname{rank} M = 2$ and its outputs fill a plane rather than all of $\mathbb{R}^3$ . The zero $m \times n$ matrix has rank $0$ , and the $n \times n$ identity matrix has rank $n$ .

Equality of row rank and column rank

Definition The row rank of a real $m \times n$ matrix $A$ is $\dim \operatorname{Row} A$ , and its column rank is $\dim \operatorname{Col} A$ . For every such matrix the two are equal,

\dim \operatorname{Row} A = \dim \operatorname{Col} A.

Both numbers equal the number $r$ of pivots in an echelon form of $A$ , so the row rank and the column rank are the same number, the rank. Proof. Reduce $A$ to an echelon form with $r$ pivots. The $r$ pivot columns of $A$ form a basis of $\operatorname{Col} A$ , and the nonzero rows of the echelon form, one for each pivot, form a basis of $\operatorname{Row} A$ . Both bases have $r$ vectors. The proof uses two different facts, that row operations keep the row space itself and that they keep the linear relations among the columns. Since $\operatorname{Col} A^{\top} = \operatorname{Row} A$ , it follows that $\operatorname{rank} A^{\top} = \operatorname{rank} A$ .

In plain words The largest number of independent rows of a matrix equals the largest number of independent columns, even when the rows and the columns have different lengths and the two spaces are different.

Example Let

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

Its two rows are independent, and its first two columns are $\mathbf{e}_1$ and $\mathbf{e}_2$ of $\mathbb{R}^2$ , so the row rank and the column rank are both $2$ . Yet $\operatorname{Col} A = \mathbb{R}^2$ , while $\operatorname{Row} A$ consists of the vectors $(a, b, a + b)$ , the plane $x_3 = x_1 + x_2$ in $\mathbb{R}^3$ . Equal dimensions do not make two spaces equal, and here the spaces do not even lie in the same $\mathbb{R}^k$ .

Rank factorization

Definition Let $A$ be a real $m \times n$ matrix of rank $r \ge 1$ . A rank factorization of $A$ is a product

A = CR,

where $C$ is $m \times r$ with linearly independent columns and $R$ is $r \times n$ with linearly independent rows. One always exists. Take for $C$ the pivot columns of $A$ , in order, and for $R$ the $r$ nonzero rows of the reduced row echelon form of $A$ . Column $j$ of $R$ then lists the coefficients that write column $j$ of $A$ as a combination of the columns of $C$ . In every rank factorization the columns of $C$ form a basis of $\operatorname{Col} A$ and the rows of $R$ form a basis of $\operatorname{Row} A$ .

In plain words The matrix $C$ keeps a basis of the outputs, and $R$ records how to rebuild every column from that basis. Applying $A$ becomes two steps. First $R$ turns the input into $r$ weights, then $C$ combines its columns with those weights.

Example For $M$ the pivot columns are columns 1 and 3, and the nonzero rows of $F$ are $(1, 2, 0)$ and $(0, 0, 1)$ , so

\begin{aligned} M &= CR \\[0.4em] &= \begin{bmatrix} 1 & 1 \\ 2 & 0 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 0 \\ 0 & 0 & 1 \end{bmatrix}. \end{aligned}

The columns of $R$ are $(1, 0)$ , $(2, 0)$ and $(0, 1)$ . They say that the columns of $M$ are the first column of $C$ , twice the first column of $C$ , and the second column of $C$ . For the input $\mathbf{x} = (2, 1, -1)$ the first step gives $R\mathbf{x} = (4, -1)$ , and the second gives

4 \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix} - \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 3 \\ 8 \\ 11 \end{bmatrix},

which is $M\mathbf{x}$ . The rows of $M$ confirm it directly, since $2 + 2 - 1 = 3$ , $4 + 4 + 0 = 8$ and $6 + 6 - 1 = 11$ .

Check yourself

A real 3 by 5 matrix $A$ has rank $r$ . In which spaces do $\operatorname{Col} A$ and $\operatorname{Row} A$ lie, and what is the largest possible value of $r$ ?

Show the answer

Each column has $3$ entries, so $\operatorname{Col} A$ is a subspace of $\mathbb{R}^3$ . Each row has $5$ entries, so $\operatorname{Row} A$ is a subspace of $\mathbb{R}^5$ . There are only three rows to hold pivots, so $r \le \min(3, 5) = 3$ . The value $3$ does occur, for example when the first three columns of $A$ are $\mathbf{e}_1$ , $\mathbf{e}_2$ and $\mathbf{e}_3$ , so the largest possible rank is $3$ . In particular the row space is never all of $\mathbb{R}^5$ .

A student reduces the matrix below to reduced row echelon form and offers its pivot columns $(1, 0, 0)$ and $(0, 1, 0)$ as a basis of $\operatorname{Col} A$ . Explain the error and give a correct basis.

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

Show the answer

The operation $R_2 \to R_2 - 2R_1$ gives the row $(0, 1, 1)$ , and then $R_3 \to R_3 - R_2$ gives a zero row. The reduced form has rows $(1, 0, 1)$ , $(0, 1, 1)$ and $(0, 0, 0)$ , with pivots in columns 1 and 2. Those positions are right, but they select columns of $A$ itself, here $(1, 2, 0)$ and $(0, 1, 1)$ , and these form a basis of $\operatorname{Col} A$ . Every combination of them has the form $(a, 2a + b, b)$ , so every vector $\mathbf{w}$ in $\operatorname{Col} A$ satisfies $2w_1 - w_2 + w_3 = 0$ . The vector $(1, 0, 0)$ gives $2$ and $(0, 1, 0)$ gives $-1$ , so neither is in $\operatorname{Col} A$ at all. The rank is $2$ .

Find the rank of the matrix below, a basis of its column space, a basis of its row space and a rank factorization.

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

Show the answer

The operations $R_2 \to R_2 - 2R_1$ and $R_3 \to R_3 - R_1$ come first, then $R_3 \to R_3 - R_2$ and $R_1 \to R_1 - R_2$ .

\begin{aligned} A &\to \begin{bmatrix} 1 & 2 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{bmatrix} \\[0.4em] &\to \begin{bmatrix} 1 & 2 & 0 & -1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}. \end{aligned}

The pivots are in columns 1 and 3, so $\operatorname{rank} A = 2$ . A basis of $\operatorname{Col} A$ in $\mathbb{R}^3$ is $(1, 2, 1)$ , $(1, 3, 2)$ , the first and third columns of $A$ . A basis of $\operatorname{Row} A$ in $\mathbb{R}^4$ is $(1, 2, 0, -1)$ , $(0, 0, 1, 1)$ . A rank factorization is

\begin{gathered} A = CR, \quad C = \begin{bmatrix} 1 & 1 \\ 2 & 3 \\ 1 & 2 \end{bmatrix}, \\[0.4em] R = \begin{bmatrix} 1 & 2 & 0 & -1 \\ 0 & 0 & 1 & 1 \end{bmatrix}. \end{gathered}

As a check, the last column of $R$ says that column 4 of $A$ is $-(1, 2, 1) + (1, 3, 2) = (0, 1, 1)$ , which is correct.

Column Space, Row Space and Rank

Key terms

Column space

Row space

Pivot columns of the original matrix

Rank

Equality of row rank and column rank

Rank factorization

Check yourself

How this lesson connects

Builds on

Used later in