Linear Algebra/Column and Row Spaces

The column space is an important vector space used in studying an m x n matrix. If we consider multiplication by a matrix as a sort of transformation that the vectors undergo, then the null space and the column space are the two natural collections of vectors which need to be studied to understand how this transformation works. While the null space focussed on those vectors which vanished under action of the matrix (i.e. the solutions of Ax = 0) the column space corresponds to the transformed vectors themselves (i.e. all Ax). It is the totality of all the vectors after the transformation. Those readers who have studied abstract algebra can relate the null space to the kernel of a homomorphism and the column space to the range.

Another important space associated with the matrix is the row space. Like its name suggests it is built entirely out of the rows of the matrix. We shall later see that the row space can be identified with the column space in a particular sense. In the special case of an invertible matrix, the row space and the column space are exactly equal.

The Column Space

Given an m x n matrix A the column space of A, denoted by C(A), is the collection of all the vectors formed by linear combinations of the columns of A.

More precisely if the columns of A are $c_{1},c_{2}\cdots c_{n}$, where each $c_{i}$ is an m-dimensional vector then,

${\hbox{C}}(A)=\{\mathbf {v} \in \mathbb {R} ^{m}:\mathbf {v} =\mathbf {\alpha _{1}c_{1}+\alpha _{2}c_{2}+\cdots \alpha _{n}c_{n}} ,\ \alpha _{i}\in \mathbb {R} \}$

The column space is thus essentially built out of the columns of the matrix. It is the linear span of the columns and in that capacity is also a vector space with the standard operations. (Recall that span of any collection of vectors is always a vector space). Also as the columns are vectors in the m - dimensional space so the column space is naturally a subspace of $\mathbb {R} ^{m}$.

Clearly if we let,

$x={\begin{pmatrix}\alpha _{1}\\\alpha _{2}\\\vdots \\\alpha _{n}\end{pmatrix}}$

then we can say that,

$Ax={\begin{pmatrix}c_{1}&c_{2}&\ldots &c_{n}\end{pmatrix}}{\begin{pmatrix}\alpha _{1}\\\alpha _{2}\\\vdots \\\alpha _{n}\end{pmatrix}}=\alpha _{1}c_{1}+\alpha _{2}c_{2}+\ldots +\alpha _{n}c_{n}$

Hence our definition can be modified to,

${\hbox{C}}(A)=\{\mathbf {v} \in \mathbb {R} ^{m}:\mathbf {v} =\mathbf {Ax} ,\ x\in \mathbb {R} ^{n}\}$

This gives us the idea that the column space is precisely the set of transformed vectors by the action of multiplication by the matrix.

Basis for the column space

We shall now prove a theorem regarding the basis for the column space of a matrix. This constructive proof will also allow us to state a very important theorem called the rank-nullity theorem as a corollary.

Theorem: The columns of the m x n matrix A corresponding to the basic variables form a basis of the column space of A.

Proof: First note that the column space of A is formed by the span of all the columns, $c_{1},c_{2}$...$c_{n}$. If we take the basis of the null space of A as outlined previously, then as

$v_{1}\in {\hbox{Null Space}}(A)$

so $Av_{1}$=0. But this shows us that the column associated with $v_{1}$ is a linear combination of the columns associated with the basic variables. (Note that the contribution of the other free variable columns is 0 and that of the $v_{1}$ linked column is 1.) In this way all the free variable associated columns are linear combinations of the basic variable associated columns. So all the basic variable linked columns span the entire column space.

Now suppose that the row echelon form of $A$ is $U$, and if we take the basic variable columns the submatrix obtained from A is $A_{1}$ and that obtained from U is $U_{1}$. Clearly $U_{1}$ is the row echelon form of $A_{1}$ (see exercises) and so the two share the same null space. Now $U_{1}$ has only basic variables associated with it because we take only basic variables from A to A1 and so its nullity is zero. This tells us that $U_{1}x=0$ has only the trivial solution. Hence $A_{1}x=0$ also has only the trivial solution and so its nullity is zero as well. It follows that the columns of $A_{1}$ which were the basic variable linked columns of A are linearly independent.

Thus the basic variable columns are both linearly independent and spanning as a result of which they form a basis of the column space. Q.E.D

Let us look at an example:

Suppose $A={\begin{pmatrix}1&2&0&2&5\\-2&-5&1&-1&-8\\0&-3&3&4&1\\3&6&0&-7&2\end{pmatrix}}$

The first step involves reducing A to its row echelon form U.

Now $U={\begin{pmatrix}1&0&2&0&1\\0&1&-1&0&1\\0&0&0&1&1\\0&0&0&0&0\end{pmatrix}}$

We encircle the first non zero entries in each row by brackets:

$U={\begin{pmatrix}(1)&0&2&0&1\\0&(1)&-1&0&1\\0&0&0&(1)&1\\0&0&0&0&0\end{pmatrix}}$

Clearly the basic variables are $x_{1},x_{2}$ and $x_{4}$ and the free variables are $x_{3}$ and $x_{5}$.

So by the theorem, the basis of the column space of A consists of the columns $c_{1},c_{2}$ and $c_{4}$ and is given by:

${\Bigg \{}{\begin{pmatrix}1\\-2\\0\\3\end{pmatrix}},{\begin{pmatrix}2\\-5\\-3\\6\end{pmatrix}},{\begin{pmatrix}2\\-1\\4\\-7\end{pmatrix}}{\Bigg \}}$

Note that the nullity of A is 2 which is equal to the difference between the total number of columns and the number of elements in the column space.

The Row Space

The row space, as, the name suggests is the space built out by the rows of the matrix. Given an m x n matrix A the row space of A, denoted by RS(A), is defined as the collection of all the vectors formed by linear combinations of the rows of A.

More precisely if the rows of A are $r_{1},r_{2}$...$r_{m}$, where each $r_{i}$ is an n-dimensional vector then,

${\hbox{RS}}(A)=\{\mathbf {v} \in \mathbb {R} ^{n}:\mathbf {v} =\mathbf {\alpha _{1}r_{1}+\alpha _{2}r_{2}+\cdots \alpha _{m}r_{m}} ,\ \alpha _{i}\in \mathbb {R} \}$

The row space is thus the linear span of the rows and so is also a vector space with the standard operations. It is a subspace of $\mathbb {R} ^{n}$.

Basis of the row space

The basis of the row space of A consists of precisely the non zero rows of U where U is the row echelon form of A. This fact is derived from combining two results which are:

1. R(A) = R(U) if U is the row echelon form of A.
2. The non zero rows of a matrix in row echelon form are linearly independent.

The proofs are outlined in the exercises.

Let us look at an example:

Suppose $A={\begin{pmatrix}1&2&0&2&5\\-2&-5&1&-1&-8\\0&-3&3&4&1\\3&6&0&-7&2\end{pmatrix}}$

If we take its row echelon form then we have,

$U={\begin{pmatrix}1&0&2&0&1\\0&1&-1&0&1\\0&0&0&1&1\\0&0&0&0&0\end{pmatrix}}$

The first three rows are non zero and so the basis of the row space is: $\{(1,\ 0,\ 2,\ 0,\ 1),(0,\ 1,\ -1,\ 0,\ 1),(0,\ 0,\ 0,\ 1,\ 1)\}$

Rank of a matrix

Notice that in our example the basis of the row space has 3 elements which is the same number as that in the basis of the column space which we derived earlier. This is not a coincidence. It is in fact always true that the number of elements in the basis of the row space and that in of the column space is equal. The steps in the reasoning are as follows:

1. The number of non zero rows in U is equal to the number of pivots (or leading non zero entries in each row) in U.
2. The number of basic variables by their definition equals the number of pivot containing columns (and so equal the number of pivots).
3. By the previous theorem the number of basic variables equals the number of elements in the basis of the column space.
4. It follows that the bases have equal number of elements.

This unique number of elements in the two bases is called the rank of the matrix. Clearly since the rows of a matrix are the columns of its transpose, so a matrix and its transpose have the same rank. The rank of a matrix A is often written as Rank (A) just as the nullity is written as Nullity (A).

The rank nullity theorem

We now proceed to a very important theorem of linear algebra, called the rank nullity theorem. Another form of this theorem will appear in the chapter on linear transformations. The theorem, in our context, is :

For an m x n matrix A,

Rank (A) + Nullity (A) = n = Number of columns of A

The logic behind this theorem is clear. The rank, as we have seen earlier, corresponds to the number of basic variables and the nullity to the number of free variables. Since any column is either basic or free (but not both) obviously the theorem is true.

Readers acquainted with the first isomorphism theorem of groups can note that this theorem can be related with it. We shall later see how this is done.

Exercises

1. Evaluate bases for the column and row spaces for:

1. ${\begin{pmatrix}2&1&-2\\1&-2&1\\-3&1&1\end{pmatrix}}$

2. ${\begin{pmatrix}-2&-1&4&2\\1&-2&1&1\\-3&3&-5&-3\end{pmatrix}}$

3. ${\begin{pmatrix}1&1&1\\1&0&1\\0&1&1\end{pmatrix}}$

2. Show that if A is an m x n matrix then the row space of A coincides with that of its row echelon form U.

Hint: Prove that an elementary row transformation on any row of A doesn't alter the fact that it is a linear combination of the rows of A.

3. Show that the non zero rows of a matrix in row echelon form are linearly independent.

Hint: Suppose $\alpha _{1}r_{1}+\cdots \alpha _{m}r_{m}=0$ where $\alpha _{i}$ are scalars and $r_{i}$ the non zero rows. Now if the first pivot occurs at the (1,j)th position of the matrix then the jth component of each row other then of $r_{1}$ is 0. So $\alpha _{1}$ is zero. Similarly all other $\alpha _{i}$'s are also necessarily zero.

4. Combine the above two results to show that the non zero rows of a matrix in its row echelon form U form a basis of both R(A) and R(U).

5. Show that a n order square matrix is invertibile $\iff$ its rank is n $\iff$ R(A) = C(A) = $\mathbb {R} ^{n}$ $\iff$ Ax = b has a unique solution for each m dimensional vector b.

6. Show that if A is a m x n and B a n x p matrix then:

1. C(AB) $\subseteq$ C(A).

2. R(AB) $\subseteq$ R(B).

Hint: For (1) note that $\{ABx:x\in \mathbb {R} ^{p}\}\subseteq \{Ay:y\in \mathbb {R} ^{n}\}$ and for (2) note that $R(AB)=C((AB)^{T})=C(B^{T}A^{T})\subseteq C(B^{T})=R(B)$

7. A submatrix of a matrix A is a matrix obtained by deleting some rows and/or columns of A. Show that for every submatrix C of A, we have Rank (C) $\leq$ Rank (A).

Hint: Consider a matrix B formed by deleting rows of A not in C. Then Rank (B) $\leq$ Rank (A) and Rank (C) $\leq$ Rank (B).

8. Show that a m x n matrix A of rank r has at least one r x r submatrix of rank r, that is, A has an invertible submatrix of order r.

Hint: Let B be the matrix consisting of r linearly independent row vectors of A. Since Rank (B) = r so we can take r linearly independent vectors of B to get an r x r invertible submatrix C.