Linear Algebra Home

Basis and Dimension

Definition. A basis of a nontrivial subspace $$S$$ of $$\mathbb R^n$$ is a subset $$B$$ of $$S$$ such that

1. $$\operatorname{Span}(B)=S$$ and

2. $$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.

1. 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$$.

2. 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.

1. Since each row is an $$n$$ dimensional vector, $$\operatorname{RS}(A)$$ is a subspace of $$\mathbb R^n$$.

2. The row $$i$$ of $$A$$ is the column $$i$$ of $$A^T$$. Then $$\operatorname{RS}(A)=\operatorname{CS}\left(A^T\right)$$.

3. 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.

1. 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$$.

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$$.

Last edited