4.2. Basis and Dimension

4.2.1. Introduction

The space \(\R^n\) is sometimes called “\(n\)-dimensional space”. What do people mean by that? When, for instance, we have a plane in \(\R^3\), and we look at it “from the inside” (like Flat-landers so to speak), things just look as if we ‘lived’ in the plane \(\R^2\). If you want to know about Flat-landers: Flatland on Wikisource, (or: ISBN:9789085711971).

Expressed more formally: a plane in \(\R^3\) is a copy of the plane \(\R^2\), so it makes sense to say that such a plane has dimension 2. In this section we make this idea precise, making use of another important concept related to subspaces, namely the concept of a basis.

4.2.2. Basis of a Subspace

The set of vectors that generates a subspace is in no way unique as the following example shows:

Example 4.2.1

Consider the four sets of vectors

\[\begin{split} {\mathcal A}_1 = \left\lbrace \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} , \begin{bmatrix} 1\\ 1 \\ 0 \end{bmatrix} , \begin{bmatrix} 1\\ 1 \\ 1 \end{bmatrix} \right\rbrace, \quad{\mathcal A}_2 = \left\lbrace \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} , \begin{bmatrix} 1\\ 1 \\ 0 \end{bmatrix} , \begin{bmatrix} 1\\ 1 \\ 1 \end{bmatrix} , \begin{bmatrix} 1\\ 2 \\ 3 \end{bmatrix} \right\rbrace \end{split}\]

and

\[\begin{split} {\mathcal A}_3 = \left\lbrace \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix} , \begin{bmatrix} 0\\ 1 \\ 2 \end{bmatrix} , \begin{bmatrix} 0\\ 0 \\ 1 \end{bmatrix} \right\rbrace, \quad{\mathcal A}_4 = \left\lbrace \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix} , \begin{bmatrix} 0\\ 1 \\2 \end{bmatrix} , \begin{bmatrix} 0\\ 0 \\ 1 \end{bmatrix} , \begin{bmatrix} 1\\ 1 \\ 3 \end{bmatrix} , \begin{bmatrix} 2\\ 1 \\ 8 \end{bmatrix} \right\rbrace. \end{split}\]

The subspaces generated by these vectors are equal:

\[ S = \Span{ {\mathcal A}_1} = \Span{ {\mathcal A}_2} = \Span{ {\mathcal A}_3} = \Span{ {\mathcal A}_4} \]

namely, all four sets span the whole \(\R^3\).

There is no a priori reason why \({\mathcal A}_1\) is a better set of generators than \({\mathcal A}_3\), but these two seem simpler than the two sets of four and even five vectors. These larger sets contain redundant vectors. They can be thinned to the three-vectors sets. By thinning we mean: vectors that are linear combinations of their predecessors can be deleted without reducing the span. The sets \({\mathcal A}_1\) and \({\mathcal A}_3\) each consist of three linearly independent vectors. Because of that, further thinning would reduce the span. A linearly independent set of generators is in that sense a minimal set of generators, and deserves a special name. We call it a basis.

Definition 4.2.1

A set of vectors \({\mathcal B} = \lbrace\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_r\rbrace\) is called a basis of a subspace \(S\) if

1. \(S = \Span{\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_r}\).

2. The set \(\lbrace\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_r\rbrace\) is linearly independent.

Definition 4.2.2

The standard basis for \(\R^n\) is given by the set

\[{\mathcal E} = \lbrace\vect{e}_1, \vect{e}_2, \ldots, \vect{e}_n\rbrace\]

where the vector \(\vect{e}_j\) stands for the \(j\)-th column of the \(n \times n\) identity matrix.

Remark 4.2.1

This basis was already defined in Section 3.1, Equation (3.1.3), along with the standard matrix of a linear transformation.

Example 4.2.2

The standard basis in \(\R^2\) can be visualized as two perpendicular unit vectors, e.g. with \(\vect{e}_1\) pointing to the right and \(\vect{e}_2\) pointing upwards. Likewise we can depict the standard basis \(\mathcal E\) of \(\R^3\). See Figure 4.2.1.

Fig. 4.2.1 The standard bases in \(\R^2\) and \(\R^3\)

Exercise 4.2.1

Check that the set

\[\begin{split} {\mathcal E} = \left\lbrace \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} , \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix} , \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix} , \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} \right\rbrace. \end{split}\]

is indeed a basis for \(\R^4\).

Solution to Exercise 4.2.1 (click to show)

The set is linearly independent:

\[\begin{split} x_1\begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} +x_2 \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix} +x_3 \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix} +x_4 \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} = \begin{bmatrix} x_1 \\x_2\\x_3\\x_4 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} \quad \iff \quad \vect{x} = \begin{bmatrix} x_1 \\x_2\\x_3\\x_4 \end{bmatrix} = \vect{0}. \end{split}\]

The set \(\{\vect{e}_1, \vect{e}_2, \vect{e}_3, \vect{e}_4\}\) also spans the whole \(\R^4\), as for any vector \(\vect{x} = \begin{bmatrix}x_1 \\x_2\\x_3\\x_4 \end{bmatrix}\)
it holds that \(\vect{x} = x_1\vect{e}_1 + x_2\vect{e}_2 + x_3\vect{e}_3 + x_4\vect{e}_4\).

Grasple Exercise 4.2.1

To check whether a set of three vectors forms a basis for \(\R^3\).

Show/Hide Content

Because of Theorem 4.1.1, which states that any subspace \(S\) of \(\R^n\) is of the form

\[ S = \Span{\vect{v}_1, \ldots, \vect{v}_r} \quad \text{with } \lbrace\vect{v}_1, \ldots, \vect{v}_r\rbrace \text{ linearly independent} \]

a basis for a subspace always exists.

If \(S\) is not the trivial subspace \(\lbrace\vect{0}\rbrace\) a basis is not unique. (For the trivial subspace the only basis is the empty set.)

Proposition 4.2.1 (Thinning and extending)

1. Suppose \(S = \Span{\mathcal A} = \Span{\vect{a}_1, \vect{a}_2, \ldots, \vect{a}_{k}}\).

   Then the set \({\mathcal A}\) can be thinned to a basis of \(S\), i.e. there is a subset

   
   
   \[{\mathcal B} \subseteq \mathcal{A}\]

   such that

   
   
   \[{\mathcal B} \text{ is linearly independent and} \quad \Span{\mathcal B} = S.\]

2. If \(S\) is a subspace in \(\R^n\) then any linear independent set \(\mathcal{A}\) of vectors in \(S\) can be extended to a basis of \(S\).

   So, there exists a set \(\mathcal{B}\) containing \(\mathcal{A}\) which is a basis for \(S\).

Proof. The ideas are quite straightforward.

As for the thinning, first of all, if one of the vectors in \(\mathcal A\) is the zero vector, then we can omit that vector.

For the remaining vectors, starting from the second vector we act as follows:

• if the vector is a linear combination of its predecessors: omit it,

• if it is not: keep it,

• go to the next vector.

All along the way the span of the vectors remains intact, so equal to \(S\), while at the end the remaining generators will form a linearly independent set.

As for the other statement, for that we can use an argument as in Proposition 4.1.3. As long as the span of the vectors is not the whole subspace we can add a linearly independent vector from \(S\). Since in \(\R^n\) there are at most \(n\) linearly independent vectors, this process will end after at most \(n\) steps.

Example 4.2.3

Let us find a basis for the column space and the null space of the matrix

\[\begin{split} A = \begin{bmatrix} 1 & -3 & 3 & 5 \\ 2 & -6 & 1 & 5 \end{bmatrix} . \end{split}\]

The first and the third column

\[\begin{split} \begin{bmatrix} 1 \\ 2 \end{bmatrix} \quad \text{and} \quad \begin{bmatrix} 3 \\ 1 \end{bmatrix} \end{split}\]

are obviously independent, and span all of \(\R^2\). Since the columns of \(A\) cannot span more than \(\R^2\), we may conclude

\[ \Col{A} = \R^2 \]

and the two chosen columns give a possible basis (see Figure 4.2.2).

This would also be the basis we get when we apply the thinning process of Proposition 4.2.1: to find a basis for the column space we then start with the set of four columns and from left to right delete columns that are linear combinations of their predecessors. We have

\[ \vect{a}_2 = -3\vect{a}_1 \quad \text{and} \quad \vect{a}_4 \in \Span{\vect{a}_1, \vect{a}_3}, \]

since

\[ \Span{\vect{a}_1, \vect{a}_3} = \mathbb{R}^2. \]

So we can thin the set of four columns as follows

\[ \Span{\vect{a}_1,\vect{a}_2,\vect{a}_3,\vect{a}_4} = \Span{\vect{a}_1,\vect{a}_3,\vect{a}_4} = \Span{\vect{a}_1,\vect{a}_3}, \]

where the two vectors \(\vect{a}_1,\vect{a}_3\) are linearly independent.

Once it is known that \( \Col{A}= \R^2\), any set of two independent vectors (not necessarily columns of \(A\)) may be taken as a basis.

For the null space of \(A\) we have to solve the linear system

\[ A\vect{x} = \vect{0}. \]

Row reduction of the augmented matrix leads to

\[\begin{split} \left[\begin{array}{cccc|c} 1 & -3 & 3 & 5 & 0\\ 2 & -6 & 1 & 5 & 0 \end{array} \right] \sim \left[\begin{array}{cccc|c} 1 & -3 & 3 & 5 & 0\\ 0 & 0 & -5 & -5 & 0 \end{array} \right] \sim \left[\begin{array}{cccc|c} 1 & -3 & 0 & 2 & 0\\ 0 & 0 & 1 & 1 & 0 \end{array} \right] . \end{split}\]

We can read off the solutions:

\[\begin{split} \begin{cases} x_1 = 3x_2 - 2x_4 \\ x_2 = x_2 \\ x_3 = -x_4 \\ x_4= x_4 \end{cases} \quad\Longrightarrow\quad\quad \begin{bmatrix} x_1\\x_2\\x_3\\x_4 \end{bmatrix} = c_1 \begin{bmatrix} 3\\1\\0\\0 \end{bmatrix} + c_2 \begin{bmatrix} -2\\0\\-1\\1 \end{bmatrix} \end{split}\]

We see that the set

\[\begin{split} \left\lbrace \begin{bmatrix} 3\\1\\0\\0 \end{bmatrix} , \begin{bmatrix} -2\\0\\-1\\1 \end{bmatrix} \right\rbrace \end{split}\]

spans the null space. It is also linearly independent, so it is a basis.

Fig. 4.2.2 The basis \(\lbrace\vect{a}_1,\vect{a}_3\rbrace\) of \(\Col{A}\).

Grasple Exercise 4.2.2

To find a basis for span\(\{\vect{b}_1, \ldots, \vect{b}_5\}\) by thinning.

Show/Hide Content

The above example (Example 4.2.3) lends itself to a few more observations that lead to a more efficient way to find bases for the column space and the null space of any matrix.

Remark 4.2.2

First of all: to find a basis for the null space, we have to solve

\[A\vect{x} = \vect{0}. \nonumber\]

We typically do this by row reducing the augmented matrix

\[[ A \,|\, \vect{0} ]. \nonumber\]

However, there is no need to add the column of zeros, as this column remains zero throughout. So we can just row reduce the matrix \(A\).

More importantly, row reduction does not change the linear relations between the columns. Below we will make this precise. For now, look at the above example: all through the reduction process the second column remains equal to \((-3)\) times the first column.

Also, in the final (echelon) matrix

\[\begin{split} [ E \,|\, \vect{0}] = \left[\begin{array}{cccc|c} 1 & -3 & 0 & 2 & 0\\ 0 & 0 & 1 & 1 & 0 \end{array} \right] = \left[\begin{array}{cccc|c} \vect{e}_1 & \vect{e}_2 & \vect{e}_3 & \vect{e}_4 & \vect{0} \end{array} \right] \end{split}\]

the relation

\[\vect{e}_4 = 2\vect{e}_1 + \vect{e}_3 \nonumber\]

can be read off. The same relation holds between the columns of \(A\):

\[\begin{split} \vect{a}_4 = \begin{bmatrix} 5 \\ 5 \end{bmatrix} = 2 \begin{bmatrix} 1 \\ 2 \end{bmatrix} + \begin{bmatrix} 3 \\ 1 \end{bmatrix} = 2\vect{a}_1 + \vect{a}_3, \end{split}\]

a relation that is easily overlooked at first sight.

Most importantly: independent columns of the echelon matrix \(E\), i.e. columns of \(E\) that are not linearly related, correspond to independent columns of \(A\). The pivot columns of \(E\) are obviously a maximal set of linearly independent columns of \(E\), thus the corresponding columns of \(A\) give a maximal set of independent columns of \(A\), i.e. a basis of the column space. In the example these are the first and the third column of \(A\).

The observations in the last remark are formalized in the following proposition.

Proposition 4.2.2

Suppose \(A\) is an \(m\times n\) matrix, and \(E\) is its reduced echelon form. Then we can deduce the following:

1. The pivot columns of the matrix \(A\) give a basis for the column space of \(A\).

2. The null space of \(A\) is equal to the null space of \(E\).

Proof. The main idea of the first statement: row operations do not alter the linear relations between the columns of a matrix. Now why is this so? Let

\[A = \begin{bmatrix} \vect{a}_1&\vect{a}_2&\ldots &\vect{a}_n \end{bmatrix} . \nonumber\]

We have seen before that a non-trivial linear relation

\[c_1\vect{a}_1 + c_2\vect{a}_2+ \ldots + c_n\vect{a}_n = \vect{0} \nonumber\]

between vectors \(\vect{a}_1,\vect{a}_2,\ldots,\vect{a}_n\) corresponds to a non-trivial solution

\[\begin{split}\vect{c} = \begin{bmatrix} c_1 \\ \vdots \\ c_n \end{bmatrix} \neq \vect{0} \nonumber\end{split}\]

of the equation

\[A\vect{x} = \vect{0}. \nonumber\]

Recall that row operations correspond to pre-multiplications with elementary matrices \(E_j\)

\[A \quad \sim \quad E_1A \quad \sim \quad E_2E_1 A \quad \sim \quad \ldots\quad \sim \quad (E_k\cdots E_1)A = E, \nonumber\]

where the last matrix \(E\) is the reduced echelon form of the matrix \(A\).

Since elementary matrices are invertible, and their product is as well, we have

\[A\vect{c} = \vect{0} \quad \iff \quad (E_k\cdots E_1)A\vect{c} = \vect{0} \quad \iff \quad E\vect{c} = \vect{0}. \nonumber\]

This settles statement (ii).

We continue, to prove (i) as well. We have just shown that the linear relations of the columns of \(A\) are exactly the same as the linear relations of the columns of its equivalent reduced echelon form. In a reduced echelon matrix it is clear that the pivot columns give a maximal independent set of columns, i.e., a maximal set of columns for which there are no non-trivial linear relations. The same can then be said about the corresponding columns of \(A\).

Example 4.2.4

We will find bases for the column space and the null space of the matrix

\[\begin{split} A = \begin{bmatrix} 1 & 2 & 4 & 2 \\ 2 & 3 & 5 & 4 \\ 4 & 2 &-2 & 6 \\ 2 & 1 &-1 &7 \end{bmatrix} . \end{split}\]

To this end we first row reduce the matrix:

\[\begin{split} A \sim \begin{bmatrix} 1 & 2 & 4 & 2 \\ 0 &-1 &-3 & 0 \\ 0 &-6 &-18&-2 \\ 0 &-3 &-9 &3 \end{bmatrix} \sim \begin{bmatrix} 1 & 0 &-2 & 2 \\ 0 &-1 &-3 & 0 \\ 0 & 0 & 0 &-2 \\ 0 & 0 & 0 & 3 \end{bmatrix} \sim \begin{bmatrix} 1 & 0 &-2 & 0 \\ 0 & 1 & 3 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} = E. \nonumber \end{split}\]

From the reduced echelon matrix we read off that the pivots are in the first, second and fourth column. Note that these columns are indeed a basis for the column space of \(E\). Because of the previous proposition, the corresponding columns of \(A\) give a (possible) basis for \(\Col{A}\):

\[\begin{split} {\mathcal B} = \left\lbrace \begin{bmatrix} 1 \\ 2 \\ 4 \\ 2 \end{bmatrix} , \begin{bmatrix} 2 \\3 \\ 2 \\ 1 \end{bmatrix} , \begin{bmatrix} 2 \\ 4 \\ 6 \\ 7 \end{bmatrix} \right\rbrace. \end{split}\]

The solution of the equation \(A\vect{x} = \vect{0}\) can also be easily read off from the reduced echelon form:

\[\begin{split}\Nul{A}=\Nul{E}= \Span{ \begin{bmatrix} 2 \\ -3 \\ 1 \\ 0 \end{bmatrix} }. \nonumber\end{split}\]

Note that the number of vectors in this basis for \(\Col{A}\) is equal to the number of pivots, and the number of vectors in this basis for the null space is equal to the number of columns without a pivot.

Exercise 4.2.2

Is the following statement true or false:

if the matrix \(E\) is the reduced echelon form of the matrix \(A\), then

\[ \Col{A} = \Col{E}. \]

Solution to Exercise 4.2.2 (click to show)

The statement is false.
For instance, look at Example 4.2.4. In that example all vectors in \(\Col{(E)}\) have a zero on position four, and there are (many) vectors in \(\Col{(A)}\) that have a nonzero fourth entry. So definitely \(\Col{(A)} \neq \Col{(E)}\).

To find a basis of the column space we only have to look at the pivot columns of any (row) equivalent echelon matrix. The corresponding columns of \(A\) provide a basis for the column space of \(A\). For a basis of the null space it is preferable to work with the equivalent reduced echelon matrix.

To find a basis of the column space by taking the pivot columns is more efficient than do the thinning step-by-step. By omitting the non-pivot columns the thinning is done at one stroke.

Example 4.2.5

It is given that matrix

\[\begin{split} A = \begin{bmatrix} 1 & 1 & 2 & 1 & -1 \\ 2 & 2 & 7 & 0 & 3 \\ 1 & 1 & 5 & 1 & 5 \\ 3 & 3 & 9 & -1 & 1 \end{bmatrix} \end{split}\]

is equivalent to the echelon matrix

\[\begin{split} E = \begin{bmatrix} 1 & 1 & 2 & 1 & -1 \\ 0 & 0 & 3 & -2 & 5 \\ 0 & 0 & 0 & 2 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}. \end{split}\]

The pivots are in the first, the third and the fourth column, so the corresponding columns of \(A\) give a basis for \(\Col{A}\):

\[\begin{split} {\mathcal B} = \left\lbrace \begin{bmatrix} 1 \\ 2 \\1 \\ 3 \end{bmatrix} , \begin{bmatrix} 2 \\ 7 \\5 \\ 9 \end{bmatrix} , \begin{bmatrix} 1 \\ 0 \\1 \\-1 \end{bmatrix} \right\rbrace. \end{split}\]

For a basis of \(\Nul{A}\) we need more work.

Exercise 4.2.3

Find a basis for the null space of the matrix in the previous example.

Solution to Exercise 4.2.3 (click to show)

We row reduce the matrix \(E = \begin{bmatrix} 1 & 1 & 2 & 1 & -1 \\ 0 & 0 & 3 & -2 & 5 \\ 0 & 0 & 0 & 2 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}\) further to row reduced echelon form.

A short computation yields

\[\begin{split} E = \begin{bmatrix} 1 & 1 & 2 & 1 & -1 \\ 0 & 0 & 3 & -2 & 5 \\ 0 & 0 & 0 & 2 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} \quad \sim \quad E_2 = \begin{bmatrix} 1 & 1 & 0 & 1 & -5.5 \\ 0 & 0 & 1 & 0 & 2 \\ 0 & 0 & 0 & 1 & 0.5 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} \end{split}\]

We can read off that a basis for \(\Col{(E)} = \Col{(A)}\) is given by

\[\begin{split} \mathcal{B} = \left\{\begin{bmatrix} -1 \\1\\0\\0\\0\end{bmatrix}, \, \begin{bmatrix} 11/2\\0 \\-2\\-1/2\\1 \end{bmatrix} \right\}. \end{split}\]

A non-trivial subspace of \(\R^n\) has infinitely many bases. They do share one feature, which is captured in the following theorem.

Theorem 4.2.1

Every basis of a fixed subspace \(S\) in \(\R^n\) has the same number of elements.

Theorem 2.5.2.

Let \(\vect{u}_{1},...,\vect{u}_{k}\) and \(\vect{v}_{1},...,\vect{v}_{\ell}\) be vectors in \(\R^{n}\). If \( k< \ell\) and \(\Span{\vect{u}_{1},...,\vect{u}_{k}}\) contains \(\Span{\vect{v}_{1},...,\vect{v}_{\ell}}\) then the set \(\left\lbrace\vect{v}_{1},...,\vect{v}_{\ell}\right\rbrace\) is linearly dependent.

Proof. The proof is an immediate consequence of Theorem 2.5.2 from the section on linear independence. Because of its vital important we restate it here (check the side note).

We can use this as follows.

Suppose

\[ \lbrace\vect{a}_1, \vect{a}_2, \ldots, \vect{a}_k \rbrace \quad \text{and} \quad \lbrace\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_{\ell} \rbrace \]

are two bases for the same subspace \(S\).

So, they are both independent sets, and

\[S = \Span{\vect{a}_1, \vect{a}_2, \ldots, \vect{a}_k } = \Span{\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_{\ell}}. \]

Since

\[\Span{\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_{\ell}} \subseteq \Span{\vect{a}_1, \vect{a}_2, \ldots, \vect{a}_k},\]

the assumption

\[\ell > k \nonumber\]

would imply

\[\text{the set } \lbrace\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_{\ell} \rbrace \text{ is linearly dependent.} \nonumber\]

So \(\ell > k\) leads to a contradiction.

Reversing the two sets we see that \(k > \ell\) is also impossible, and we can conclude that we must have

\[k = \ell. \nonumber\]

Example 4.2.6

Let \(\mathcal{P}\) be the plane in \(\R^3\) described by the equation

\[2x_1 + x_2 - 6x_3 = 0. \nonumber\]

Since the equation is homogeneous, \(\mathcal{P}\) is a subspace in \(\R^3\).

We could also say

\[ {\mathcal P} = \Nul{A}, \quad \text{where} \quad A = \begin{bmatrix} 2 & 1 & -6 \end{bmatrix} . \]

By taking \(x_2\) and \(x_3\) as free variables we find that the general solution of this linear system (of one equation in three unknowns) is given by

\[\begin{split} \left\lbrace \begin{array}{ll} x_1 = & -\tfrac12x_2 + 3x_3\\ x_2 = & x_2\\ x_3 = & x_3 \end{array} \right.\Longrightarrow \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = c_1 \begin{bmatrix} -\nicefrac{1}{2} \\ 1 \\ 0 \end{bmatrix} + c_2 \begin{bmatrix} 3 \\ 0 \\ 1 \end{bmatrix} = c_1\vect{u}_1 + c_2\vect{u}_2. \end{split}\]

Thus \(\{\vect{u}_1, \vect{u}_2\}\) is a basis for \(\mathcal{P}\).

We can also take \(x_1\) and \(x_3\) as free variables, and then find

\[\begin{split} {\mathcal P} = \Span{ \begin{bmatrix} 1 \\ -2 \\ 0 \end{bmatrix} , \begin{bmatrix} 0 \\ 6\\1 \end{bmatrix} }, \end{split}\]

which provides an alternative basis for \(\mathcal{P}\).

Exercise 4.2.4

1. Give another basis of the plane \(\mathcal P\), which does not contain a vector that is a multiple of one of the vectors \(\begin{bmatrix} 1 \\ -2 \\ 0 \end{bmatrix}\), \(\begin{bmatrix}3 \\ 0 \\ 1\end{bmatrix}\) and \(\begin{bmatrix}0 \\ 6\\1\end{bmatrix}\).

2. Show that any set of two independent vectors in the plane \(\mathcal P\) generates the plane, hence forms a basis.

4.2.3. Dimension of a Subspace

Definition 4.2.3

The dimension of a subspace \(S\) is the number of elements in a (i.e., any) basis for \(S\).   Notation:   dim \(S\).

Because of Theorem 4.2.1 this is a good definition.

Example 4.2.7

For the trivial subspace \(S = \lbrace\vect{0}\rbrace\) we postulated that its basis is the empty set. Thus,

\[ \text{dim}\, S = \text{dim}\lbrace\vect{0}\rbrace = 0. \]

For the other trivial subspace, the whole \(\R^n\), the standard basis

\[ {\mathcal E} = \lbrace\vect{e}_1, \vect{e}_2, \ldots, \vect{e}_n\rbrace, \]

has exactly \(n\) elements, So

\[ \text{dim} \,\R^n = n. \]

You can look upon the dimension of a subspace as a means to describe its size. This is not to be confused with the size of a vector which is just the number of entries of the vector.

Exercise 4.2.5

Is the following statement true or false?

The dimension of the vector \(\vect{u} = \begin{bmatrix} 3\\4 \end{bmatrix} \) is 2.

Solution to Exercise 4.2.5 (click to show)

The statement is false. The attribute dimension is only defined for subspaces.

A correct statement would be: the size of the vector \(\vect{u} = \begin{bmatrix} 3\\4 \end{bmatrix} \) is equal to 2.

The following proposition sometimes helps to show that a set of vectors is a basis of a subspace \(S\). We can use it to establish in an indirect way that a set of vectors generates the (whole) subspace.

Proposition 4.2.3

For a set of vectors \( \lbrace\vect{b}_1, \vect{b}\_2, \ldots, \vect{b}_{\ell} \rbrace \) in a subspace \(S\) of dimension \(k\) each pair of the following three properties implies the remaining property.

1. \(\lbrace\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_{\ell} \rbrace\) is linearly independent;

2. \(\Span{\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_{\ell}}=S\);

3. \(\ell = k\).

Another way to put it: once it is known that the dimension of \(S\) equals \(k\), each set that satisfies two of the three properties is a basis for \(S\).

Proof. We first show the “easy” part:

\[ \text{i. and ii.} \quad \Longrightarrow \quad \text{iii.} \]

Well, if \(\lbrace\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_{\ell} \rbrace\) is linearly independent and spans \(S\), then it is a basis for \(S\). Since all bases of \(S\) contain the same number \(k = \) dim \(S\) vectors, it follows that \(\ell = k\).

Next, let us prove

\[ \text{i. and iii.} \quad \Longrightarrow \quad \text{ii.} \]

So suppose \(\lbrace\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_k \rbrace\) is linearly independent, and is contained in \(S\). We have to show that

\[ \Span{\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_k } = S, \]

i.e., each vector \(\vect{s}\) in \(S\) is contained in \(\Span{\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_k }\).
To show this, let \(\vect{s}\) be an arbitrary vector in \(S\).
Furthermore, let

\[ \lbrace\vect{a}_1, \vect{a}_2, \ldots, \vect{a}_{k} \rbrace \]

be any basis of \(S\). Then the set

\[ \lbrace\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_k,\vect{s}\rbrace \]

which contains \(k+1\) elements, is contained in the set

\[ S = \Span{\vect{a}_1, \vect{a}_2, \ldots, \vect{a}_k}. \]

So

\[ \lbrace\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_k, \vect{s}\rbrace \subseteq \Span{\vect{a}_1, \vect{a}_2, \ldots, \vect{a}_k}. \]

Invoking Theorem 2.5.2 we get that \(\lbrace\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_k, \vect{s} \rbrace\) is linearly dependent.

Since we assumed \( \lbrace\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_k\rbrace\) is linearly independent, we may conclude that

\[ \vect{s} \in \Span{\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_k}. \]

Thus we have shown that \(\Span{\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_k }\) indeed contains each vector in \(S\), i.e.

\[ \Span{\vect{b}_1, \vect{b}_2, \ldots, \vect{b}_k } = S. \]

The remaining part we leave to the reader.

Exercise 4.2.6

In Proposition 4.2.3 prove

\[ \text{ii. and iii.} \quad \Longrightarrow \quad \text{i.} \]

Remark 4.2.3

Take another look at Example 4.2.6. We constructed a basis for the plane \(\mathcal P\) given by the equation

\[ 2x_1 + x_2 - 6x_3 = 0. \]

This basis contained two vectors, so

\[ \text{dim}{\mathcal P} = 2. \]

From the Proposition 4.2.3 it follows that any set of two linearly independent vectors in \(\mathcal{P}\) is a basis for \(\mathcal{P}\).

Example 4.2.8

Any set \(S\) of \(n\) independent vectors in \(\R^n\) spans \(\R^n\).

Namely we know that \(\R^n\) has dimension \(n\), so such a set \(S\) satisfies i. and iii. of Proposition 4.2.3.

Of course this statement can also be proved by an argument involving pivots.

We conclude this subsection with a theorem that relates the column space and the null space of an \(m\times n\) matrix \(A\). At first sight there does not seem much to relate: the column space is a subspace of \(\R^m\), whereas the null space ‘lives’ in \(\R^n\). However, the null space, i.e. the solution set of the equation

\[ A\vect{x} = \vect{0}, \]

does say something about the linear relations between the columns of \(A\).

\[ [ \,\vect{a}_1 \,\, \vect{a}_2 \,\, \ldots \,\, \vect{a}_n\, ]\vect{x} = \vect{0} \quad \iff \quad x_1\vect{a}_1+ x_2\vect{a}_2+ \ldots +x_n\vect{a}_n = \vect{0}. \]

The more linear relations there are, i.e., the larger \(\Nul{A}\) is, the smaller will be \(\Span{\vect{a}_1, \vect{a}_2, \ldots, \vect{a}_n}\), i.e. \(\Col{A}\).

Theorem 4.2.2 (Dimension Theorem)

For any \(m\times n\) matrix \(A\):

\[ \text{dim }\Col{A} + \text{dim }\Nul{A} = n. \]

Proof. The proof consists of combining several properties of this section.

We have seen (Proposition 4.2.2) that the dimension of the column space is equal to the number of pivots. Say, this number is given by \(p\).

Likewise, the dimension of the null space is equal to the number of free variables in the solution of

\[ A\vect{x} = \vect{0}, \]

and that is exactly the number of non-pivot columns, which is \(n-p\).

We conclude:

\[ \text{dim Col }A + \text{dim Nul }A = p + (n-p) = n. \]

Example 4.2.9

If \(A\) is a \(3\times5\) matrix, the dimension of the null space of \(A\) must be at least \(2\).

Namely,

\[ \text{Col}\,A \subseteq \R^3 \quad \text{implies} \quad \text{dim Col}\, A \leq 3. \]

From

\[ \text{dim } \Col{A} + \text{dim } \Nul{A} = 5, \]

it then follows that

\[ \text{dim }\Nul{A} = 5 - \text{dim }\Col{A} \geq 5 - 3 = 2. \]

4.2.4. Row Space and Rank

There is a third subspace connected to an \(m\times n\) matrix \(A\), namely, the subspace generated by the rows. This is a subspace of \(\R^n\), and it may come as a small surprise that it has the same dimension as the column space of \(A\), which is a subspace of \(\R^m\). This dimension we will call the rank of a matrix.

Since we are used to write vectors in \(\R^n\) as column vectors, we define the row space of a matrix as follows:

Definition 4.2.4

The row space of a matrix \(A\) is defined as the column space of its transpose:

\[ \text{Row}\,{A} = \Col{A^T}. \]

Example 4.2.10

For the matrix

\[\begin{split} A = \begin{bmatrix} 1 & -3 & 3 & 5 \\ 2 & -6 & 1 & 5 \end{bmatrix} \end{split}\]

the rows are obviously linearly independent, as are the columns of

\[\begin{split} A^T = \begin{bmatrix} 1 & 2 \\ -3 & -6 \\ 3 & 1 \\ 5 & 5 \\ \end{bmatrix}. \end{split}\]

So we find

\[\begin{split} \Row{A} =\Span{ \begin{bmatrix} 1 \\ -3 \\ 3 \\ 5 \end{bmatrix} , \begin{bmatrix} 2 \\ -6 \\ 1 \\ 5 \end{bmatrix} }, \end{split}\]

thus \(\Row{A}\) is a subspace of \(\R^4\) of dimension 2.

This is the same matrix \(A\) as in Example 4.2.3, where we found that the column space is the whole \(\R^2\), which gives a first instance of the property

\[ \text{dim } \Row{A} = \text{dim } \Col{A}, \]

a relation that will appear to hold for every \(m \times n\) matrix (Proposition 4.2.5).

We will work towards that proposition in two steps. First we consider another example, where the matrix is an echelon matrix.

Example 4.2.11

Consider the \(4 \times 5\) matrix

\[\begin{split} M = \begin{bmatrix} 1 & 0 & 4 & 6 & 3 \\ 0 & 2 & 3 & 1 & 5 \\ 0 & 0 & 0 & 4 & 7 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}. \end{split}\]

The matrix is in echelon form, so the three pivot columns give a basis for the column space. Thus

\[ \text{dim } \Col{M} = 3. \]

The nonzero columns of

\[\begin{split} M^T = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 4 & 3 & 0 & 0 \\ 6 & 1 & 4 & 0 \\ 3 & 5 & 7 & 0 \end{bmatrix} , \end{split}\]

which are in a one-one-correspondence with the first three rows of \(M\), give a basis for the row space of \(M\), whence

\[ \text{dim } \Row{M} = 3. \]

Proposition 4.2.4

If \(A\) and \(B\) are equivalent matrices, then

\[ \Row{A} = \Row{B}. \]

Proof. Recall that equivalence here means that by row operations we can transform \(A\) into \(B\) (and vice versa). So we have to show that row operations do not change the row space.

If \(B\) is the result of applying row operations to \(A\), each row of \(B\) will be a linear combination of the rows of \(A\). Thus it follows that the row space of \(B\) is contained in the row space in \(A\). In short,

\[ \Row{B} \subseteq \Row{A}. \]

Since the equivalence works both ways we can interchange \(A\) and \(B\) and conclude that also

\[ \Row{A} \subseteq \Row{B}, \]

and if two sets are contained in each other they must of course be equal.

Proposition 4.2.5

For each matrix \(A\) the row space and the column space have the same dimension.

Proof. If a matrix \(A\) is row reduced to an echelon matrix \(E\) we know that

\[ \Row{A} = \Row{E}. \]

For an echelon matrix it is very easy to find a basis of the row space. As in Example 4.2.11, we can just take the nonzero rows (written as columns). The nonzero rows are the rows that start with a pivot, so we find

\[ \text{dim }\Row{A} = \text{dim }\Row{E}= \text{ number of pivots } = \text{dim } \Col{A}, \]

where at the last step we used Proposition 4.2.2.

Example 4.2.12

Consider the matrix

\[\begin{split} A = \begin{bmatrix} 1 & 2 & 4 & 2 \\ 2 & 3 & 5 & 4 \\ 4 & 2 &-2 & 6 \\ 2 & 1 &-1 &7 \end{bmatrix} \end{split}\]

of Example 4.2.4. In this example we have seen that

\[\begin{split} A \sim \begin{bmatrix} 1 & 0 &-2 & 0 \\ 0 & 1 & 3 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} = E. \end{split}\]

The first three rows of \(E\) are obviously linearly independent, and so are the first three columns of \(E^T\). A possible basis for the row space of \(A\):

\[\begin{split} \Row{A} = \Row{E} = \Span{ \begin{bmatrix} 1 \\ 0 \\-2 \\ 0 \end{bmatrix} , \begin{bmatrix} 0 \\ 1 \\ 3 \\ 0 \end{bmatrix} , \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} }. \end{split}\]

Note that for a basis of the row space we don’t have to go “back” from the rows of the echelon matrix to the corresponding rows of \(A\). As a matter of fact, this may lead to a wrong conclusion, as there is no one-to-one correspondence between the rows of \(A\) and the rows of \(E\). The reason is that during the row reduction process rows may have been swapped.

Example 4.2.13

As an illustration of the last remark, consider the matrix

\[\begin{split} A = \begin{bmatrix} 1 &1 & 1 \\ 2&2&2 \\ 3&3&4 \end{bmatrix} . \end{split}\]

Its reduced echelon form is

\[\begin{split} E = \begin{bmatrix} 1 &1 & 1 \\ 0&0&1 \\ 0&0&0 \end{bmatrix} , \end{split}\]

so as a basis for the row space we can take

\[\begin{split} \left\lbrace \begin{bmatrix} 1 \\1\\1 \end{bmatrix} , \begin{bmatrix} 0 \\0\\1 \end{bmatrix} \right\rbrace, \end{split}\]

corresponding to the first two rows of \(E\). Taking the first two rows of \(A\) (written as columns) in this case leads to the wrong answer.

Exercise 4.2.7

In the above Example 4.2.12 find out how the four rows of the original matrix can be written as linear combinations of the rows of the reduced echelon form.

Solution to Exercise 4.2.7 (click to show)

It can be done ‘by inspection’

\[\begin{split} \begin{array}{ccl} [1, 1, 1] &=& 1\cdot [1,1,1] \,\, (+0\cdot [0, 0, 1] + 0\cdot [0,0,0])\\ [2, 2, 2] &=& 2\cdot [1,1,1] \\ [3, 3, 4] &=& 3\cdot [1,1,1] + 1\cdot [0,0,1] \end{array} \end{split}\]

For future reference this seems to be the place for yet another definition:

Definition 4.2.5

The rank of a matrix is defined as the dimension of its column space (or, for that matter, its row space):

\[ \text{rank} A = \text{dim }\Col{A}. \]

Proposition 4.2.6

The rank of a matrix \(A\) is equal to the number of pivots.

Namely, by Proposition 4.2.2 the dimension of the column space of a matrix is equal to the number of pivots.

Exercise 4.2.8

Prove the identity

\[ \text{rank}\left(A^T\right) = \text{rank}(A). \]

Solution to Exercise 4.2.8 (click to show)

The rank of \(A^T\) is the dimension of the column space of \(A^T\), which is the dimension of the row space of \(A\).
The rank of \(A\) is the dimension of the column space of \(A\).
By Proposition 4.2.5 dim Row\((A) = \) dim Row\((A)\).

The last theorem contains two reformulations of old material:

Theorem 4.2.3 (Rank Theorem)

1. For each \(m\times n\) matrix \(A\):

   \[ \text{rank}\,A = n - \text{dim }\Nul{A} \]

2. For each \(n\times n\) matrix \(A\):

   \[ A \text{ is invertible } \iff \text{ rank}\, A = n. \]

Exercise 4.2.9

The statements in Theorem 4.2.3 are both reformulations of earlier propositions (or theorems). Find these earlier propositions.

Exercise 4.2.10

Suppose that \(A\) and \(B\) are matrices for which the product \(AB\) is defined. Show that

\[ \text{rank}(AB) \leq \text{rank}\,A. \]

Solution to Exercise 4.2.10 (click to show)

The statement in Exercise 4.1.3 that says \(\Col{AB} \subseteq \Col{A}\) immediately gives that

\[ \text{rank}(AB) = \text{dim Col}(AB) \leq \text{dim Col}(A) =\text{rank}\,A. \]

Exercise 4.2.11

Suppose that \(A\) and \(B\) are matrices for which the product \(AB\) is defined. Show that

\[ \text{rank}(AB) \leq \text{rank}\,B. \]

The following proposition combines the results of the last two exercises.

Proposition 4.2.7

Suppose that \(A\) and \(P\) are \(n\times n\) matrices and \(P\) is invertible. Then

\[ \text{rank}(AP) = \text{rank}(A) = \text{rank}(PA). \]

Proof. Suppose \(A\) and \(P\) are as stated. Then by Exercise 4.2.10

\[ \text{rank}(AP) \leq \text{rank}(A) = \text{rank}(APP^{-1}) \leq \text{rank}(AP) \]

The first inequality is the same as the inequality in Exercise 4.2.10 and the second inequality follows from the same exercise by taking \(A = AP\) and \(B = P^{-1}\). This proves \(\text{rank}(AP) = \text{rank}(A)\).
The identity \(\text{rank}(A) = \text{rank}(PA)\) follows by considering the transpose:

\[ \text{rank}(PA) = \text{rank}\left((PA)^T\right) = \text{rank}\left(A^TP^T\right). \]

Here we have a product \(A^TP^T\) with \(P^T\) invertible, so we can use use the identities that we already proved, and find

\[ \text{rank}\left(A^TP^T\right) = \text{rank}\left(A^T\right) = \text{rank}(A). \]

Exercise 4.2.12

Suppose that \(A\) and \(B\) are \(n\times n\) matrices for which

\[ AB = O. \]

Show that

\[ \text{rank}\, A + \text{rank}\, B \leq n. \]

Does the conclusion also hold when \(A\) is an \(m\times n\) matrix and \(B\) is an \(n\times m\) matrix?

4.2.5. Grasple Exercises

Grasple Exercise 4.2.3

To check whether three vectors constitute a basis for \(\R^3\).

Show/Hide Content

Grasple Exercise 4.2.4

To check whether three vectors constitute a basis for \(\R^3\).

Show/Hide Content

Grasple Exercise 4.2.5

To check whether a set of vectors forms a basis for \(\R^3\).

Show/Hide Content

Grasple Exercise 4.2.6

To find a basis for span\(\{\vect{b}_1, \ldots, \vect{b}_5\}\) by thinning.

Show/Hide Content

Grasple Exercise 4.2.7

Finding bases for Col\((A)\) and Nul\((A)\).

Show/Hide Content

Grasple Exercise 4.2.8

Finding bases for Col\((A)\) and Nul\((A)\).

Show/Hide Content

Grasple Exercise 4.2.9

Finding bases for Col\((A)\) and Nul\((A)\).

Show/Hide Content

Grasple Exercise 4.2.10

To find a basis for a subspace of \(\R^4\)

Show/Hide Content

Grasple Exercise 4.2.11

To find a basis and the dimension of span\(\{\vect{v}_1, ... , \vect{v}_4\}\) (in \(\R^4\))

Show/Hide Content

Grasple Exercise 4.2.12

To find rank\((A)\) and dim Nul\((A)\) for a given matrix.

Show/Hide Content

Grasple Exercise 4.2.13

Find rank\((A)\) for a matrix \(A\) containing a parameter \(h\).

Show/Hide Content

Grasple Exercise 4.2.14

Find rank\((A)\) for a matrix \(A\) containing a parameter \(h\).

Show/Hide Content

The exercises below are more theoretical.

Grasple Exercise 4.2.15

Can a subspace in \(\R^3\) have a basis consisting of four vectors?

Show/Hide Content

Grasple Exercise 4.2.16

Can a basis contain the zero vector?

Show/Hide Content

Grasple Exercise 4.2.17

Which of four statements about Col\((A)\) is correct?

Show/Hide Content

Grasple Exercise 4.2.18

Which of five statements about Col\((A)\) is incorrect?

Show/Hide Content

Grasple Exercise 4.2.19

Which of four statements about Nul\((A)\) is incorrect?

Show/Hide Content

Grasple Exercise 4.2.20

To find the rank of a matrix with certain properties

Show/Hide Content

Grasple Exercise 4.2.21

To find the rank of a matrix with certain properties

Show/Hide Content

Grasple Exercise 4.2.22

To find the dimension of the null space of a matrix with certain properties

Show/Hide Content

Grasple Exercise 4.2.23

Does there exist a \(3 \times 4\) matrix with dim Nul\((A) =\) dim Col\((A) = 2\)?

Show/Hide Content

Grasple Exercise 4.2.24

Which three columns of a \(4 \times 5\) matrix can be taken as a basis for its column space?

Show/Hide Content

Grasple Exercise 4.2.25

To give an example of a matrix \(A\) with certain properties

Show/Hide Content

Grasple Exercise 4.2.26

To give an example of a matrix \(A\) with certain properties

Show/Hide Content

Grasple Exercise 4.2.27

Comparing the null spaces of two (\(4\times 4\)) matrices.

Show/Hide Content

Grasple Exercise 4.2.28

Comparing the null spaces of two (\(3\times 5\)) matrices.

Show/Hide Content

Grasple Exercise 4.2.29

Comparing the spans of two sets of vectors.

Show/Hide Content