Definition.
A basis of a nontrivial subspace \(S\) of \(\mathbb R^n\) is a subset \(B\) of \(S\) such that
\(\operatorname{Span}(B)=S\) and
\(B\) is linearly independent set.
We define the basis of the trivial subspace \(\{\overrightarrow{0}\}\) to be \(B=\varnothing\). The number of vectors
in a basis \(B\) is the dimension of \(S\) denoted by \(\dim(S)\) or \(\dim S\).
Example.
For the subspace \(S=\left\lbrace \left[\begin{array}{r} x\\y \end{array} \right] \;|\; x,y\in \mathbb R,\; 2x-y=0\right\rbrace\)
of \(\mathbb R^2\),
\[S
=\operatorname{Span}\left\lbrace \left[\begin{array}{r}1\\ 2 \end{array} \right] \right\rbrace.\]
Also \(\left\lbrace \left[\begin{array}{r}1\\ 2 \end{array} \right] \right\rbrace\) is linearly independent.
Thus \(B=\left\lbrace \left[\begin{array}{r}1\\ 2 \end{array} \right] \right\rbrace\) is a basis of \(S\) and
\(\dim(S)=|B|=1\). Note that there infinitely many bases of \(S\).
Among infinitely many bases of \(\mathbb R^n\), \(B=\{\overrightarrow{e_1},\overrightarrow{e_2},\ldots,\overrightarrow{e_n} \}
=\left\lbrace \left[\begin{array}{r} 1\\ 0\\0\\ \vdots\\0 \end{array} \right],
\left[\begin{array}{r} 0\\1\\0\\ \vdots\\0 \end{array} \right],\ldots,
\left[\begin{array}{r} 0\\ 0\\0\\ \vdots\\1 \end{array} \right] \right\rbrace\) is called the standard basis
of \(\mathbb R^n\). For any \(\overrightarrow{x}=[x_1,x_2,\ldots,x_n]^T\in \mathbb R^n\),
\[\overrightarrow{x}=x_1\overrightarrow{e_1}+x_2\overrightarrow{e_2}+\cdots+x_n\overrightarrow{e_n},\]
\[\text{i.e., } \left[\begin{array}{r} x_1\\ x_2\\x_3\\ \vdots\\x_n \end{array} \right]
=x_1\left[\begin{array}{r} 1\\ 0\\0\\ \vdots\\0 \end{array} \right]
+x_2\left[\begin{array}{r} 0\\1\\0\\ \vdots\\0 \end{array} \right]
+\cdots+
x_n \left[\begin{array}{r} 0\\ 0\\0\\ \vdots\\1 \end{array} \right] \in \operatorname{Span}(B).\]
Thus \(\operatorname{Span}(B)=\mathbb R^n\). To show linear independence, let \(x_1\overrightarrow{e_1}+x_2\overrightarrow{e_2}+\cdots+x_n\overrightarrow{e_n}=\overrightarrow{0},\)
\[\text{i.e., }
x_1\left[\begin{array}{r} 1\\ 0\\0\\ \vdots\\0 \end{array} \right]
+x_2\left[\begin{array}{r} 0\\1\\0\\ \vdots\\0 \end{array} \right]
+\cdots+
x_n \left[\begin{array}{r} 0\\ 0\\0\\ \vdots\\1 \end{array} \right]
=\left[\begin{array}{r} x_1\\ x_2\\x_3\\ \vdots\\x_n \end{array} \right]
=\left[\begin{array}{r} 0\\ 0\\0\\ \vdots\\0 \end{array} \right]
\implies x_1=x_2=\cdots=x_n=0.\]
So \(B\) is linearly independent . Thus \(B\) is a basis of \(\mathbb R^n\) and \(\dim\left(\mathbb R^n\right)=|B|=n\).
Now we present some important theorems regarding bases of a subspace of \(\mathbb R^n\).
Theorem.(Unique Representation Theorem)
Let \(S\) be a subspace of \(\mathbb R^n\). Then \(B=\{\overrightarrow{b_1},\overrightarrow{b_2},\ldots,\overrightarrow{b_k}\}\)
is a basis of \(S\) if and only if each vector \(\overrightarrow{v}\) of \(S\) is a unique linear combination of
\(\overrightarrow{b_1},\overrightarrow{b_2},\ldots,\overrightarrow{b_k}\),
i.e.,
\(\overrightarrow{v}=c_1\overrightarrow{b_1}+c_2\overrightarrow{b_2}+\cdots+c_k\overrightarrow{b_k}\) for unique scalars
\(c_1,c_2,\ldots,c_k\).
Let \(B=\{\overrightarrow{b_1},\overrightarrow{b_2},\ldots,\overrightarrow{b_k}\}\) be a basis of \(S\).
Consider a vector \(\overrightarrow{v}\) of \(S\). Since \(S=\operatorname{Span} B\), \(\overrightarrow{v}=c_1\overrightarrow{b_1}+c_2\overrightarrow{b_2}+\cdots+c_k\overrightarrow{b_k}\)
for some scalars \(c_1,c_2,\ldots,c_k\). To show these scalars are unique, let \(\overrightarrow{v}=d_1\overrightarrow{b_1}+d_2\overrightarrow{b_2}+\cdots+d_k\overrightarrow{b_k}\)
for some scalars \(d_1,d_2,\ldots,d_k\). Then
\[\begin{align*}
\overrightarrow{v} -\overrightarrow{v} &=(c_1\overrightarrow{b_1}+c_2\overrightarrow{b_2}+\cdots+c_k\overrightarrow{b_k})- (d_1\overrightarrow{b_1}+d_2\overrightarrow{b_2}+\cdots+d_k\overrightarrow{b_k})\\
\overrightarrow{0} &=(c_1-d_1)\overrightarrow{b_1}+(c_2-d_2)\overrightarrow{b_2}+\cdots+(c_k-d_k)\overrightarrow{b_k}
\end{align*}\]
Since \(B=\{\overrightarrow{b_1},\overrightarrow{b_2},\ldots,\overrightarrow{b_k}\}\) is linearly independent,
\((c_1-d_1)=(c_2-d_2)=\cdots=(c_k-d_k)=0\) which implies \(d_1=c_1,\;d_2=c_2,\cdots,\; d_k=c_k\).
The converse follows similarly (exercise).
Theorem.(Reduction Theorem)
Let \(S\) be a subspace of \(\mathbb R^n\). If a set \(B=\{\overrightarrow{b_1},\overrightarrow{b_2},\ldots,\overrightarrow{b_k}\}\)
of vectors of \(S\) spans \(S\), then either \(B\) is a basis of \(S\) or a subset of \(B\) is a basis of \(S\).
Suppose \(B=\{\overrightarrow{b_1},\overrightarrow{b_2},\ldots,\overrightarrow{b_k}\}\) spans \(S\). If \(B\) is
linearly independent, then \(B\) is a basis of \(S\). Otherwise there is a vector, say \(\overrightarrow{b_1}\), which is
a linear combination of other vectors in \(B\). Let \(B_1=B\setminus \{\overrightarrow{b_1}\}=\{\overrightarrow{b_2},\ldots,\overrightarrow{b_k}\}\).
We can verify that \(\operatorname{Span} (B_1)=\operatorname{Span} (B)=S\). If \(B_1\) is linearly independent, then \(B_1\)
is a basis of \(S\). Otherwise there is a vector, say \(\overrightarrow{b_2}\), which is a linear combination of other vectors in
\(B_1\). Let \(B_2=B_1\setminus \{\overrightarrow{b_2}\}=\{\overrightarrow{b_3},\ldots,\overrightarrow{b_k}\}\).
We can verify that \(\operatorname{Span} (B_2)=\operatorname{Span} (B_1)=S\). Proceeding this way we end up with a subset
\(B_m\) of \(B\) for some \(m\leq k\) such that \(B_m\) is linearly independent and \(\operatorname{Span} (B_m)=S\) which
means \(B_m\) is a basis of \(S\).
Similarly we can prove the following:
Theorem.(Extension Theorem)
Let \(S\) be a subspace of \(\mathbb R^n\). If a set \(B=\{\overrightarrow{b_1},\overrightarrow{b_2},\ldots,\overrightarrow{b_k}\}\)
of vectors of \(S\) is linearly independent, then either \(B\) is a basis of \(S\) or a superset of \(B\) is a basis of
\(S\).
Example.
Use Reduction Theorem to find a basis of \(\operatorname{CS}\left(A\right)\) for \(A=\left[\begin{array}{rrrr}
1&2&3&4\\
1&3&5&8\\
1&2&4&7\end{array} \right]\).
Solution.
Write \(A=[\overrightarrow{a_1}\:\overrightarrow{a_2}\:\overrightarrow{a_3}\:\overrightarrow{a_4}]\) and
\(B=\{\overrightarrow{a_1},\overrightarrow{a_2},\overrightarrow{a_3},\overrightarrow{a_4} \}\). Then
\(\operatorname{CS}\left(A\right)=\operatorname{Span} S\). Verify that \(\overrightarrow{a_4}=-\overrightarrow{a_1}-2\overrightarrow{a_2}+3\overrightarrow{a_3}\) (exercise).
Then \(B\) is not linear independent and
\[\operatorname{CS}\left(A\right)=\operatorname{Span} (B)= \operatorname{Span} \{\overrightarrow{a_1},\overrightarrow{a_2},\overrightarrow{a_3},\overrightarrow{a_4} \} = \operatorname{Span} \{\overrightarrow{a_1},\overrightarrow{a_2},\overrightarrow{a_3}\}.\]
Verify that \(\{\overrightarrow{a_1},\overrightarrow{a_2},\overrightarrow{a_3}\}\) is linearly independent.
Thus \(\{\overrightarrow{a_1},\overrightarrow{a_2},\overrightarrow{a_3}\}\) is a basis of \(\operatorname{CS}\left(A\right)\).
Definition.
The rank of a matrix \(A\), denoted by \(\operatorname{rank}(A)\), is the dimension of its column space, i.e.,
\(\operatorname{rank}(A)=\dim(\operatorname{CS}\left(A\right))\).
Theorem.
The pivot columns of a matrix \(A\) form a basis for \(\operatorname{CS}\left(A\right)\) and \(\operatorname{rank}(A)\)
is the number of pivot columns of \(A\).
Suppose \(R\) is the RREF of \(A\). Then \(A\overrightarrow{x}=\overrightarrow{0}\) if and only if
\(R\overrightarrow{x}=\overrightarrow{0}\), i.e., linear dependence relation among columns of \(A\) is the same as that
of \(R\). Since the pivot columns of \(R\) are linearly independent, so are the pivot columns of \(A\). By Reduction
Theorem we can show that the pivot columns of \(R\) span \(\operatorname{CS}\left(R\right)\). Then the pivot columns of
\(A\) span \(\operatorname{CS}\left(A\right)\). Thus the pivot columns of \(A\) form a basis for \(\operatorname{CS}\left(A\right)\)
and \(\operatorname{rank}(A)=\dim(\operatorname{CS}\left(A\right))\) is the number of pivot columns of \(A\).
Remark.
If \(R\) is the RREF of \(A\), then \(\operatorname{CS}\left(A\right)\neq \operatorname{CS}\left(R\right)\)
in general. Consider \(A=\left[\begin{array}{cc} 1&2\\1&2\end{array} \right]\). Then
\(R=\text{RREF}(A)=\left[\begin{array}{cc} 1&2\\0&0\end{array} \right]\) and
\(\operatorname{CS}\left(A\right)=\operatorname{Span}\left\lbrace \left[\begin{array}{r}1\\1 \end{array} \right] \right\rbrace \neq \operatorname{Span}\left\lbrace \left[\begin{array}{r}1\\0 \end{array} \right] \right\rbrace =\operatorname{CS}\left(R\right)\).
Example.
Find \(\operatorname{rank}(A)\) and a basis of \(\operatorname{CS}\left(A\right)\) for
\(A=\left[\begin{array}{rrrr}
1&2&3&4\\
1&3&5&8\\
1&2&4&7\end{array} \right]\).
Solution.
\[A=\left[\begin{array}{rrrr}
\boxed{1}&2&3&4\\
1&3&5&8\\
1&2&4&7\end{array} \right]
\xrightarrow[-R_1+R_3]{-R_1+R_2}
\left[\begin{array}{rrrr}
\boxed{1}&2&3&4\\
0&\boxed{1}&2&4\\
0&0&\boxed{1}&3 \end{array} \right] (REF)\]
Since \(A\) has 3 pivot columns \(\overrightarrow{a_1}\), \(\overrightarrow{a_2}\), and \(\overrightarrow{a_3}\),
\(\operatorname{rank}(A)=3\) and a basis of \(\operatorname{CS}\left(A\right)\) is
\(\{\overrightarrow{a_1},\overrightarrow{a_2},\overrightarrow{a_3} \},\)
\[\text{i.e., } \left\lbrace
\left[\begin{array}{r} 1\\ 1\\1 \end{array} \right],
\left[\begin{array}{r} 2\\3\\2 \end{array} \right],
\left[\begin{array}{r} 3\\ 5\\4 \end{array} \right] \right\rbrace.\]
Definition.
The nullity of a matrix \(A\), denoted by \(\operatorname{nullity}(A)\), is the dimension of its null space, i.e.,
\(\operatorname{nullity}(A)=\operatorname{dim}(\operatorname{NS}(A))\).
Theorem.
\(\operatorname{nullity}(A)\) is the number of non-pivot columns of \(A\).
Suppose \(B=[\overrightarrow{b_1}\:\overrightarrow{b_2}\:\cdots\overrightarrow{b_n}]\) is the RREF of an \(m\times n\)
matrix \(A\). Then \(A\overrightarrow{x}=\overrightarrow{0}\) if and only if \(B\overrightarrow{x}=\overrightarrow{0}\),
i.e., \(\operatorname{NS}(A)=\operatorname{NS}(B)\). Suppose \(\overrightarrow{b_1}\:\overrightarrow{b_2}\:\cdots\overrightarrow{b_k}\)
are the pivot columns of \(B\) and the rest non-pivot columns. Then for \(i=k+1,\ldots,n\),
\[\overrightarrow{b_i}=c_{i1}\overrightarrow{b_1}+c_{i2}\overrightarrow{b_2}+\cdots+c_{ik}\overrightarrow{b_k}
=\sum_{j=1}^k c_{ij}\overrightarrow{b_j} \text{ for some } c_{ij}\in \mathbb R.\]
\[\begin{align*}
B\overrightarrow{x}=\overrightarrow{0}
&\implies x_1\overrightarrow{b_1}+x_2\overrightarrow{b_2}+\cdots+x_n\overrightarrow{b_n}=\overrightarrow{0}\\
&\implies x_1 \overrightarrow{b_1}+x_2\overrightarrow{b_2}+\cdots+x_k\overrightarrow{b_k}
+x_{k+1} \left( \sum_{j=1}^k c_{k+1,j}\overrightarrow{b_j} \right)
+\cdots+ x_{n} \left( \sum_{j=1}^k c_{n,j}\overrightarrow{b_j} \right)=\overrightarrow{0}\\
&\implies \left( x_1+\sum_{j=k+1}^n x_jc_{j,1} \right) \overrightarrow{b_1}+\cdots+
\left( x_k+\sum_{j=k+1}^n x_jc_{j,k} \right) \overrightarrow{b_k} =\overrightarrow{0}
\end{align*}\]
Since \(\{ \overrightarrow{b_1},\overrightarrow{b_2},\ldots,\overrightarrow{b_k} \}\) is linearly independent,
\(x_i=-\sum_{j=k+1}^n x_jc_{j,i}\) for \(i=1,\ldots,k\). Then we can write \(\overrightarrow{x}\) as a linear
combination of \(n-k\) linearly independent vectors that span \(\operatorname{NS}(B)\) (exercise).
Thus \(\operatorname{dim}(\operatorname{NS}(A))=\operatorname{dim}(\operatorname{NS}(B))=n-k\).
Remark.
The non-pivot columns of \(A\) do not form a basis for \(\operatorname{NS}(A)\).
Example.
Find \(\operatorname{nullity}(A)\) and a basis of \(\operatorname{NS}(A)\) for
\(A=\left[\begin{array}{rrrr}
1&2&3&4\\
1&3&5&8\\
1&2&4&7\end{array} \right]\).
Solution.
\[A=\left[\begin{array}{rrrr}
1&2&3&4\\
1&3&5&8\\
1&2&4&7\end{array} \right]
\longrightarrow
\left[\begin{array}{rrrr}
\boxed{1}&0&0&-1\\
0&\boxed{1}&0&-2\\
0&0&\boxed{1}&3 \end{array} \right] (RREF)\]
Since \(A\) has one non-pivot column, \(\operatorname{nullity}(A)=1\). To find a basis of \(\operatorname{NS}(A)\),
we solve \(A\overrightarrow{x}=\overrightarrow{0}\) which becomes
\[\begin{eqnarray*}
\begin{array}{rcrcrcrcr}
x_1&& &&&-&x_4&=&0\\
&& x_2 &&&-&2x_4&=&0\\
&& &&x_3&+&3x_4&=&0\\
\end{array}
\end{eqnarray*}\]
where \(x_1,x_2\) and \(x_3\) are basic variables and \(x_4\) is a free variable.
\[\begin{eqnarray*}
\begin{array}{rcl}
x_1&=&x_4\\
x_2&=&2x_4\\
x_3&=&-3x_4\\
x_4&=&\text{free}
\end{array}
\end{eqnarray*}\]
\[\operatorname{NS}(A)=\left\lbrace \left[\begin{array}{r} x_4\\2x_4\\ -3x_4\\x_4 \end{array} \right] \; |\; x_4\in \mathbb R \right\rbrace
=\left\lbrace x_4 \left[\begin{array}{r} 1\\2\\ -3\\1 \end{array} \right] \; |\; x_4\in \mathbb R \right\rbrace
=\operatorname{Span}\left\lbrace \left[\begin{array}{r} 1\\ 2\\ -3\\1 \end{array} \right] \right\rbrace.\]
Thus a basis of \(\operatorname{NS}(A)\) is
\[\left\lbrace \left[\begin{array}{r} 1\\ 2\\ -3\\1 \end{array} \right] \right\rbrace\]
because it is linearly independent and spans \(\operatorname{NS}(A)\).
Theorem.(Rank-Nullity Theorem)
For an \(m\times n\) matrix \(A\),
\[\operatorname{rank}(A)+\operatorname{nullity}(A)=n.\]
\(\operatorname{rank}(A)+\operatorname{nullity}(A)=\) the sum of numbers of pivot and non-pivot columns of \(A\)
which is \(n\).
Example.
If \(A\) is a \(4\times 5\) matrix with rank \(3\), then by the Rank-Nullity Theorem
\[\operatorname{nullity}(A)=n-\operatorname{rank}(A)=5-3=2.\]
Now we investigate the relation of \(\operatorname{rank}(A)\) with the dimension of the row space of \(A\).
Definition.
Each row of an \(m\times n\) matrix \(A\) is called a row vector which can be identified with a (column) vector
in \(\mathbb R^n\). The row space of an \(m\times n\) matrix \(A=\left[\begin{array}{c}\overrightarrow{r_1}\\ \overrightarrow{r_2}\\ \vdots\\ \overrightarrow{r_m} \end{array} \right]\),
denoted by \(\operatorname{RS}(A)\) or \(\operatorname{Row}A\), is the span of its row vectors:
\[\operatorname{RS}(A)=\operatorname{Span}\{\overrightarrow{r_1},\overrightarrow{r_2},\ldots,\overrightarrow{r_m}\}.\]
Remark.
Since each row is an \(n\) dimensional vector, \(\operatorname{RS}(A)\) is a subspace of \(\mathbb R^n\).
The row \(i\) of \(A\) is the column \(i\) of \(A^T\). Then \(\operatorname{RS}(A)=\operatorname{CS}\left(A^T\right)\).
Elementary row operations may change the linear dependence relations among rows (unlike columns) but they do not
change the row space. For example,
\[\operatorname{RS}(A)=\operatorname{RS}(\text{RREF of } A).\]
Example.
Consider \(A=\left[\begin{array}{rrrr}2&0&1&0\\
0&1&-1&1\\
2&1&0&1
\end{array} \right]\).
Write \(A=\left[\begin{array}{r}\overrightarrow{r_1}\\ \overrightarrow{r_2}\\ \overrightarrow{r_3}
\end{array} \right]\), where
\(\overrightarrow{r_1}=[2,0,1,0],\;
\overrightarrow{r_2}=[0,1,-1,1],\;
\overrightarrow{r_3}=[2,1,0,1].\)
Then \(\operatorname{RS}(A)=\operatorname{CS}\left(A^T\right)=\operatorname{Span}\{\overrightarrow{r_1},\overrightarrow{r_2},\overrightarrow{r_3}\}\)
is a subspace of \(\mathbb R^4\).
\[A=\left[\begin{array}{rrrr}2&0&1&0\\
0&1&-1&1\\
2&1&0&1
\end{array} \right] %{\substack{-R1+R3\\-R2+R3}}
\longrightarrow
\left[\begin{array}{rrrr}\boxed{2}&0&1&0\\
0&\boxed{1}&-1&1\\
0&0&0&0
\end{array} \right]=R \;(\mbox{REF})\]
Note that \(\overrightarrow{r_3}=\overrightarrow{r_1}+\overrightarrow{r_2}\) in \(A\), but not in \(R\).
Since the row 3 of \(R\) is \(-\overrightarrow{r_1}-\overrightarrow{r_2}+\overrightarrow{r_3}\) in \(A\),
the span of the rows of \(R\) is the same as that of \(A\), i.e., \(\operatorname{RS}(R)=\operatorname{RS}(A)\).
Note that the nonzero rows of \(B\) are linearly independent and span \(\operatorname{RS}(R)=\operatorname{RS}(A)\),
i.e., they form a basis of \(\operatorname{RS}(R)=\operatorname{RS}(A)\).
Definition.
The row rank of a matrix \(A\) is the dimension of its row space.
Theorem.
Let \(A\) be an \(m\times n\) matrix with REF \(R\). Then the nonzero rows of \(R\) form a basis for
\(\operatorname{RS}(R)=\operatorname{RS}(A)\) and the row rank of \(A\) = the (column) rank of \(A\) = the number of pivot
positions of \(A\).
Each nonzero row of \(R\) is not a linear combination of the other nonzero rows. Thus the nonzero rows of \(R\)
are linearly independent and span \(\operatorname{RS}(R)=\operatorname{RS}(A)\), i.e., they form a basis of
\(\operatorname{RS}(R)=\operatorname{RS}(A)\). Recall that the rank of \(A\) is the number of pivot columns (hence
pivot positions) of \(R\). The number of pivot positions of \(R\) equals to the number of nonzero rows of \(R\)
which is the row rank \(R\) and consequently the row rank of \(A\).
Remark.
For an \(m\times n\) matrix \(A\), \(0 \leq \operatorname{rank}(A)\leq \min \{m,n \}\).
Example.
For the \(3\times 4\) matrix \(A\) in the preceding example, \(\operatorname{rank}(A)\leq \min \{3,4 \}=3\).
Since it has two nonzero rows in its REF, the row rank of \(A=\operatorname{rank}(A)=2\).
What is the smallest and largest possible nullity of a \(5\times 7\) matrix \(A\)?
First note \(0\leq \operatorname{rank}(A)\leq \min \{5,7\} =5\). Now by the Rank-Nullity Theorem,
\(\operatorname{nullity}(A)=7-\operatorname{rank}(A)\geq 7-5=2\). So the smallest possible nullity of \(A\) is 2.
In that case the row rank of \(A=\operatorname{rank}(A)=5\). Similarly \(\operatorname{nullity}(A)=7-\operatorname{rank}(A) \leq 7\).
So the largest possible nullity of \(A\) is 7. In that case the row rank of \(A=\operatorname{rank}(A)=0\).