There are two competing definitions for a collection of vectors in a vector space:
A spanning set for a vector space has to have enough vectors to make sure that every element of the vector space is some linear combination of the spanning set. If a set of vectors has too few vectors, then it cannot span the entire vector space.
A linearly independent set of vectors has so few vectors that no vector in the set is a linear combination of the others.
Example 1 - Too Few Vectors to Span¶
The set $\left\{ \ihat,\ \jhat \right\}$ does not span all of $\mathbb{R}^3$; $\hat{k}$ is not a linear combination of $\ihat$ and $\jhat$. The set is too small; there are not enough vectors in this set to span all of $\mathbb{R}^3$.
Example 2 - Too Many Vectors to be Linearly Independent¶
The set $\left\{\,\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix},\ \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix},\ \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix},\ \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}\,\right\}$ is linearly dependent because the fourth vector is a linear combination of the first three vectors. This set has too many vectors to be linearly independent.
- a set of vectors with too few vectors cannot span the entire vector space.
- a set of vectors with too many vectors cannot be linearly independent.
Definition¶
Basis
A basis for a vector space $V$ is a linearly independent, spanning subset of vector space $V$.
Example 3 - Basis¶
Show that the set $B = \left\{\,\begin{bmatrix} 1 \\ 2 \end{bmatrix},\ \begin{bmatrix} 2 \\ 1 \end{bmatrix}\,\right\}$ is a basis for $\mathbb{R}^2$.
We want to know if the set $B$ spans the entire vector space. For every vector $\mathbf{b}\in\mathbb{R}^2$, is the following linear system consistent?
$$ x_1\begin{bmatrix} 1 \\ 2 \end{bmatrix} + x_2\begin{bmatrix} 2 \\ 1 \end{bmatrix} = \mathbf{b}$$
We must determine whether the linear system is consistent for every vector $\mathbf{b}$ in the vector space $\mathbb{R}^2$. Then we must determine if the vectors are linearly independent. We know that they are linearly independent because we can reduce matrix $A$.
$$ A = \begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix} \xrightarrow{R_2-2R_1} \begin{bmatrix} 1 &\ \ 2 \\ 0 & -3 \end{bmatrix} \xrightarrow{-R_2/3} \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix} \xrightarrow{R_1-2R_2} \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} $$
Since both columns of matrix $A$ are pivot columns, the columns of matrix $A$ are linearly independent. This also means that the matrix $A$ is a nonsingular matrix. We can conclude that the linear system is consistent for every vector $\mathbf{b}\in\mathbb{R}^2$. This establishes that the set of two vectors is a basis for $\mathbb{R}^2$.
Alternatively, the determinant of matrix $A$ is
$$|A| = \begin{vmatrix}\ 1\ &\ 2\ \\ \ 2\ &\ 1\ \end{vmatrix} = 1 - 4 = -3 \neq 0$$
Matrix $A$ is non-singular. Hence the two vectors are linearly independent, and the matrix is invertible. A solution exists for every $\mathbf{b}\in\mathbb{R}^2$,
$$\mathbf{x} = A^{-1}\mathbf{b}$$
Thus the set spans all of $\mathbb{R}^2$. Therefore the set is a basis.
Example 4 - Another Basis¶
Show that the set $B = \left\{\, 4x^3 - 3x^2 + 4x + 3, -2x^2 - 4x + 1, 4x^3 - 3x^2 + 4x + 4, -3x^3 + 3x^2 + 4 \,\right\}$ is a basis for $P_3$.
We can represent polynomials in $P_3$ as vectors of coefficients in $\mathbb{R}^4$. This is equivalent to determining if the set $B' = \left\{\, \begin{bmatrix}\ \ 3\ \\ \ \ 4\ \\ -3\ \\ \ 4\ \end{bmatrix},\ \begin{bmatrix}\ \ 1\ \\ -4\ \\ -2\ \\ \ \ 0\ \end{bmatrix},\ \begin{bmatrix}\ \ 4\ \\ \ \ 4\ \\ -3\ \\ \ \ 4\ \end{bmatrix},\ \begin{bmatrix}\ \ 4\ \\ \ \ 0\ \\ \ \ 3\ \\ -3\ \end{bmatrix} \,\right\}$ is a basis for $\mathbb{R}^4$.
$$\begin{align*} \begin{bmatrix}\ \ 3\ &\ \ 1\ &\ \ 4\ &\ \ 4\ \\ \ \ 4\ & -4\ &\ \ 4\ &\ \ 0\ \\ -3\ & -2\ & -3\ &\ \ 3\ \\ \ \ 4\ &\ \ 0\ &\ \ 4\ & -3\ \end{bmatrix} &\xrightarrow{\substack{R_1+R_3 \\ R_2+R_3 \\ R_4+R_3 }} \begin{bmatrix}\ \ 0\ & -1\ &\ \ 1\ &\ \ 7\ \\ \ \ 1\ & -6\ &\ \ 1\ &\ \ 3\ \\ -3\ & -2\ & -3\ &\ \ 3\ \\ \ \ 1\ & -2\ &\ \ 1\ &\ \ 0\ \end{bmatrix} \xrightarrow{R_4\leftrightarrow R_1} \begin{bmatrix}\ \ 1\ & -2\ &\ \ 1\ &\ \ 0\ \\ \ \ 1\ & -6\ &\ \ 1\ &\ \ 3\ \\ -3\ & -2\ & -3\ &\ \ 3\ \\ \ \ 0\ & -1\ &\ \ 1\ &\ \ 7\ \end{bmatrix} \xrightarrow{\substack{R_2-R_1 \\ R_3+3R_1}} \\ \\ \begin{bmatrix}\ \ 1\ & -2\ &\ \ 1\ &\ \ 0\ \\ \ \ 0\ & -4\ &\ \ 0\ &\ \ 3\ \\ \ \ 0\ & -8\ &\ \ 0\ &\ \ 3\ \\ \ \ 0\ & -1\ &\ \ 1\ &\ \ 7\ \end{bmatrix} &\xrightarrow{R_2\leftrightarrow R_4} \begin{bmatrix}\ \ 1\ & -2\ &\ \ 1\ &\ \ 0\ \\ \ \ 0\ & -1\ &\ \ 1\ &\ \ 7\ \\ \ \ 0\ & -8\ &\ \ 0\ &\ \ 3\ \\ \ \ 0\ & -4\ &\ \ 0\ &\ \ 3\ \end{bmatrix} \xrightarrow{R_3-2R_4} \begin{bmatrix}\ \ 1\ & -2\ &\ \ 1\ &\ \ 0\ \\ \ \ 0\ & -1\ &\ \ 1\ &\ \ 7\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ & -3\ \\ \ \ 0\ & -4\ &\ \ 0\ &\ \ 3\ \end{bmatrix} \xrightarrow{R_3\leftrightarrow R_4} \\ \\ \begin{bmatrix}\ \ 1\ & -2\ &\ \ 1\ &\ \ 0\ \\ \ \ 0\ & -1\ &\ \ 1\ &\ \ 7\ \\ \ \ 0\ & -4\ &\ \ 0\ &\ \ 3\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ & -3\ \end{bmatrix} &\xrightarrow{R_3-4R_2} \begin{bmatrix}\ \ 1\ & -2\ &\ \ 1\ &\ \ 0\ \\ \ \ 0\ & -1\ &\ \ 1\ &\ \ 7\ \\ \ \ 0\ &\ \ 0\ & -4\ & -25\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ & -3\ \end{bmatrix} \end{align*}$$
All four columns are pivot columns, so the four polynomials in set $B$ are linearly independent. The matrix is non-singular, so the linear system $B'\mathbf{x}=\mathbf{b}$ is consistent for every $\mathbf{b}\in\mathbb{R}^4$. This is equivalent to saying that $B$ spans $P_3$. Therefore $B$ is a basis for $P_3$ because $B$ is a linearly independent, spanning set in $P_3$.
Alternatively,
$$\begin{align*} |B'| = \begin{vmatrix}\ \ 3\ &\ \ 1\ &\ \ 4\ &\ \ 4\ \\ \ \ 4\ & -4\ &\ \ 4\ &\ \ 0\ \\ -3\ & -2\ & -3\ &\ \ 3\ \\ \ \ 4\ &\ \ 0\ &\ \ 4\ & -3\ \end{vmatrix} &= (-1)^3\begin{vmatrix}\ \ 1\ & -2\ &\ \ 1\ &\ \ 0\ \\ \ \ 0\ & -1\ &\ \ 1\ &\ \ 7\ \\ \ \ 0\ &\ \ 0\ & -4\ & -25\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ & -3\ \end{vmatrix} = (-1)^3\,1(-1)(-4)(-3) = 12 \neq 0 \end{align*}$$
The leading factor $(-1)^3$ is the result of $3$ row exchanges in the reduction. A nonzero determinant implies that matrix $B'$ is non-singular. Hence the columns of $B'$ and the polynomials in $B$ are linearly independent. Moreover $B'$ is invertible so the linear system $B'\mathbf{x}=\mathbf{b}$ is consistent for every $\mathbf{b}\in\mathbb{R}^4$. This is equivalent to saying that $B$ spans $P_3$. Therefore $B$ is a basis for $P_3$ because $B$ is a linearly independent, spanning set in $P_3$.
Theorem 1¶
Linearly Dependent Sets
If $B = \left\{\mathbf{v}_1,\ \dots,\ \mathbf{v}_n\right\}$ is a spanning set for vector space $V$, then any set of $m\gt n$ vectors $\left\{\mathbf{u}_1,\ \dots,\ \mathbf{u}_m\right\}$ in $V$ is linearly dependent.
Proof of Theorem 1¶
Let $B = \left\{\mathbf{v}_1,\ \dots,\ \mathbf{v}_n\right\}$ be a spanning set for vector space $V$ and consider any set of vectors $\left\{\mathbf{u}_1,\ \dots,\ \mathbf{u}_m\right\}$ in $V$ with $m>n$ elements. Each vector $\mathbf{u}_j$ can be written as a linear combination of vectors in spanning set $B$.
$$ \mathbf{u}_j = \displaystyle\sum_{k=1}^n a_{jk}\mathbf{v}_k = a_{j1}\mathbf{v}_1 +\ \cdots\ + a_{jn}\mathbf{v}_n$$
Any linear combination of the set $\left\{\mathbf{u}_1,\ \mathbf{u}_2,\ \dots,\ \mathbf{u}_m\right\}$ can be written
$$ \begin{align*} \displaystyle\sum_{i=1}^m c_i\mathbf{u}_i &= c_1\mathbf{u}_1 +\ \cdots\ + c_m\mathbf{u}_m \\ &= c_1\left(\displaystyle\sum_{k=1}^n a_{1k}\mathbf{v}_k\right) +\ \cdots\ + c_m\left(\displaystyle\sum_{k=1}^n a_{mk}\mathbf{v}_k\right) \\ \\ &= \left(\displaystyle\sum_{k=1}^n c_1a_{1k}\mathbf{v}_k\right) +\ \cdots\ + \left(\displaystyle\sum_{k=1}^n c_ma_{mk}\mathbf{v}_k\right) \\ \\ &= \displaystyle\sum_{i=1}^m \left(\displaystyle\sum_{k=1}^n c_ia_{ik}\mathbf{v}_k\right) = \displaystyle\sum_{k=1}^n \left(\displaystyle\sum_{i=1}^m c_ia_{ik}\mathbf{v}_k\right) = \displaystyle\sum_{k=1}^n \left(\displaystyle\sum_{i=1}^m c_ia_{ik}\right)\mathbf{v}_k \end{align*} $$
Consider the equation
$$ c_1\mathbf{u}_1 + c_2\mathbf{u}_2 +\ \cdots\ + c_m\mathbf{u}_m = \mathbf{0} $$
Using the decomposition above we obtain the linear system of equations
$$ \begin{align*} \sum_{i=1}^m c_ia_{i1} &= a_{11}c_1 + a_{21}c_2 + \cdots + a_{m1}c_m = 0 \\ \ddots \\ \sum_{i=1}^m c_ia_{in} &= a_{1n}c_1 + a_{2n}c_2 + \cdots + a_{mn}c_m = 0 \end{align*}$$This system can be expressed in matrix form as follows: $$A\mathbf{c} = \mathbf{0}$$ This linear system is underdetermined because $m\gt n$. This system is consistent because $c_1=c_2=\dots=c_m=0$ is a solution, and thus has infinitely many solutions because the linear system is underdetermined. Let $\mathbf{\hat{c}}\neq\mathbf{0}$ be such a nontrivial solution. Then
$$ \displaystyle\sum_{i=1}^m \hat{c}_i\mathbf{u}_i = \displaystyle\sum_{k=1}^n \left(\displaystyle\sum_{i=1}^m \hat{c}_ia_{ik}\right)\mathbf{v}_k = \displaystyle\sum_{k=1}^n 0\mathbf{v}_k = \mathbf{0}. $$
The existence of a nontrivial solution implies that the larger set of vectors $\left\{\mathbf{u}_1,\ \mathbf{u}_2,\ \dots,\ \mathbf{u}_m\right\}$ is linearly dependent. $\blacksquare$
Theorem 1 tells us that any set with more elements than a spanning set is linearly dependent.
Hence, if a set is linearly independent, it has at most the same number of elements as a spanning set.
Theorem 2¶
Two Finite Bases Have the Same Number of Elements
If $W = \left\{\mathbf{w}_1,\ \dots,\ \mathbf{w}_n\right\}$ and $U = \left\{\mathbf{u}_1,\ \dots,\ \mathbf{u}_m\right\}$ are both finite bases for vector space $V$, then $m = n$.
Proof of Theorem 2¶
Suppose $W = \left\{\mathbf{w}_1,\ \dots,\ \mathbf{w}_n\right\}$ and $U = \left\{\mathbf{u}_1,\ \dots,\ \mathbf{u}_m\right\}$ are both finite bases for vector space $V$. Using Theorem 1,
- because $W$ is a spanning set and $U$ is linearly independent, $m\le n$.
- because $U$ is a spanning set and $W$ is linearly independent, $n\le m$.
Therefore, $m=n$. $\blacksquare$
Definition¶
The dimension or algebraic dimension of a vector space is the number of vectors in any basis if it is finite, or the cardinality if it is infinite.
Example 5 - Dimension¶
The dimensions of the following previously discussed vector spaces.
- The dimension of $\mathbb{R}^2$ is two.
- The dimension of $\mathbb{R}^n$ is $n$.
- The dimension of $P_n$ is $n+1$.
- The dimension of the trivial vector space $\left\{\,\mathbf{0}\,\right\}$ is zero.
- The dimension of $\mathbb{R}^{m\times n}$ is $m\cdot n$.
- The dimension of $P$ is infinite.
- The dimension of $C^n[-1,1]$ is infinite.
Theorem 3¶
Properties of Bases
If $V$ is a finite dimensional vector space of dimension $n \gt 0$, then
any set of $n$ linearly independent vectors is a basis for $V$, and hence a spanning set of $V$.
any set of $n$ vectors that spans $V$ is a basis, and therefore linearly independent.
Proof of Theorem 3¶
Let $V$ be a finite dimensional vector space with dimension $n \gt 0$. This implies that there must be a basis, or linearly independent spanning set $\mathcal{B} = \left\{ \mathbf{v}_1, \dots, \mathbf{v}_n \right\}$ for $V$.
Let $U = \left\{ \mathbf{u}_1, \dots, \mathbf{u}_n \right\}$ be a set of $n$ linearly independent vectors. Suppose that there exists a nonzero vector $\mathbf{w}\in V\setminus\mathrm{Span}(U)$. The set $U\cup\left\{\mathbf{w}\right\}$ has $n+1$ elements, more than the $n$ elements in spanning set $\mathcal{B}$. By Theorem 1, the set $U\cup\left\{\mathbf{w}\right\}$ is linearly dependent. Consider the following linear equation:$$c_1\mathbf{u}_1 + \dots + c_n\mathbf{u}_n + c_{n+1}\mathbf{w} = \mathbf{0}$$ If $c_{n+1}=0$, then $c_1\mathbf{u}_1 + \dots + c_n\mathbf{u}_n=\mathbf{0}$ and $c_1=\dots=c_n=0$ because set $U$ is linearly independent. This implies that the only solution to $$c_1\mathbf{u}_1 + \dots + c_n\mathbf{u}_n + c_{n+1}\mathbf{w} = \mathbf{0}$$ with $c_{n+1}=0$ is the trivial solution. If $c_{n+1}\neq 0$,$$\begin{align*} c_1\mathbf{u}_1 + \dots + c_n\mathbf{u}_n &= -c_{n+1}\mathbf{w} \\ \\ \mathbf{w} &= -\frac{c_1}{c_{n+1}}\mathbf{u}_1 - \dots - \frac{c_n}{c_{n+1}}\mathbf{u}_n \end{align*} $$ Thus, $\mathbf{w}$ is a linear combination of the vectors in $U$, so $\mathbf{w}\in\text{Span}(U)$. Since every nonzero vector in $V$ is an element of the span of $U$, $V=\text{Span}(U)$ and $U$ is a linearly independent, spanning set. In other words, $U$ is a basis for $V$.
Let $U = \left\{ \mathbf{u}_1, \dots, \mathbf{u}_n \right\}$ be a spanning set of $V$ with exactly $n$ elements. Suppose that set $U$ is linearly dependent. Then $V = \text{Span}(U) = \text{Span}\left\{ \mathbf{u}_{j_1},\dots,\mathbf{u}_{j_k}\right\}$, where $k\lt n$. Thus $\left\{ \mathbf{u}_{j_1},\dots,\mathbf{u}_{j_k}\right\}$ is a basis for $V$ with fewer than the number of elements in $\mathcal{B}$. This is false by Theorem 2. By contradiction, $U$ is linearly independent. Therefore $U$ is a basis for $V$ and spans $V$. $\blacksquare$
Proving that every infinite dimensional vector space has a basis, and any two bases for an infinite dimensional vector space are sets with the same cardinality, is beyond the scope of this course. We need to understand, utilize, and remember the following theorems about vector spaces.
Theorem 4¶
Every Vector Space has a Basis
Every vector space has a basis or linearly independent spanning set. Any two bases for a finite dimensional vector space have the same number of elements. Any two bases for an infinite dimensional vector space have the same cardinality.
When we are working with linear models in applications we will also frequently use the following theorem.
Theorem 5¶
Basis Construction
If $ V$ is a vector space, then
any linearly independent vectors can be extended to a basis for vector space $V$.
any spanning set can be reduced by removing vectors to form a basis for vector space $V$.
This theorem states that
we can judiciously add linearly independent vectors to a linearly independent set until it spans the vector space. This process yields a basis for $V$.
we can carefully remove dependent vectors from a spanning set until all that remains are linearly independent vectors that span $V$. Again this process yields a basis for $V$.
Exercise 1 - Reduce a Spanning Set¶
The set $S$ below spans $\mathbb{R}^3$. Because it has more than three vectors it is linearly dependent and cannot be a basis. Find a subset of $S$ that is a basis for $\mathbb{R}^3$.$$S = \left\{\,\mathbf{a}_1 = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix},\ \mathbf{a}_2 = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix},\ \mathbf{a}_3 = \begin{bmatrix} 2 \\ 3 \\ 5 \end{bmatrix},\ \mathbf{a}_4 = \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix},\ \mathbf{a}_5 = \begin{bmatrix} 2 \\ 1 \\ 1 \end{bmatrix} \,\right\}$$
The set $S$ below spans $\mathbb{R}^4$. Because it has more than four vectors it is linearly dependent and cannot be a basis. Find a subset of $S$ that is a basis for $\mathbb{R}^4$. $$ S = \left\{\, \mathbf{a}_1 = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 1 \end{bmatrix},\ \mathbf{a}_2 = \begin{bmatrix} 0 \\ 1 \\ 0 \\ 1 \end{bmatrix},\ \mathbf{a}_3 = \begin{bmatrix} 0 \\ 0 \\ 1 \\ 1 \end{bmatrix},\ \mathbf{a}_4 = \begin{bmatrix}\ \ 2 \\ -1 \\\ \ 1 \\\ \ 2 \end{bmatrix},\ \mathbf{a}_5 = \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \end{bmatrix},\ \mathbf{a}_6 = \begin{bmatrix} 2 \\ 1 \\ 0 \\ 1 \end{bmatrix}\,\right\}$$
View Solution - 1.
Form the matrix $A = \begin{bmatrix} \mathbf{a}_1 & \mathbf{a}_2 & \mathbf{a}_3 & \mathbf{a}_4 & \mathbf{a}_5 \end{bmatrix}$ and reduce to reduced row echelon form.
$$ \begin{align*} A = \begin{bmatrix} 1 & 0 & 2 &\ \ 1 &\ \ 2 \\ 0 & 1 & 3 &\ \ 1 &\ \ 1 \\ 1 & 1 & 5 &\ \ 0 &\ \ 1 \end{bmatrix} &\xrightarrow{R_3 - R_1} \begin{bmatrix} 1 & 0 & 2 &\ \ 1 &\ \ 2 \\ 0 & 1 & 3 &\ \ 1 &\ \ 1 \\ 0 & 1 & 3 & -1 & -1 \end{bmatrix} \xrightarrow{R_3 - R_2} \begin{bmatrix} 1 & 0 & 2 &\ \ 1 &\ \ 2 \\ 0 & 1 & 3 &\ \ 1 &\ \ 1 \\ 0 & 0 & 0 & -2 & -2 \end{bmatrix} \\ \\ &\xrightarrow{-\frac{1}{2}R_3} \begin{bmatrix} 1 & 0 & 2 &\ \ 1 &\ \ 2 \\ 0 & 1 & 3 &\ \ 1 &\ \ 1 \\ 0 & 0 & 0 &\ \ 1 &\ \ 1 \end{bmatrix} \xrightarrow{\substack{R_1 - R_3 \\ R_2 - R_3}} \begin{bmatrix} 1 & 0 & 2 & 0 & 1 \\ 0 & 1 & 3 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix} \end{align*} $$
Columns $1$, $2$, and $4$ are pivot columns; columns $3$ and $5$ are free. The free columns are linear combinations of the pivot columns to their left,
$$ \mathbf{a}_3 = 2\mathbf{a}_1 + 3\mathbf{a}_2, \qquad \mathbf{a}_5 = \mathbf{a}_1 + \mathbf{a}_4, $$
so $\mathbf{a}_3$ and $\mathbf{a}_5$ are removed. The pivot-column vectors are three linearly independent vectors in $\mathbb{R}^3$, hence a basis:
$$ \left\{\, \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix},\ \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix},\ \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} \,\right\} $$
View Solution - 2.
Form the matrix $A = \begin{bmatrix} \mathbf{a}_1 & \mathbf{a}_2 & \mathbf{a}_3 & \mathbf{a}_4 & \mathbf{a}_5 & \mathbf{a}_6 \end{bmatrix}$ and reduce to reduced row echelon form.
$$ \begin{align*} A = \begin{bmatrix} 1 & 0 & 0 &\ \ 2 &\ \ 1 &\ \ 2 \\ 0 & 1 & 0 & -1 &\ \ 1 &\ \ 1 \\ 0 & 0 & 1 &\ \ 1 &\ \ 0 &\ \ 0 \\ 1 & 1 & 1 &\ \ 2 &\ \ 0 &\ \ 1 \end{bmatrix} &\xrightarrow{R_4 - R_1} \begin{bmatrix} 1 & 0 & 0 &\ \ 2 &\ \ 1 &\ \ 2 \\ 0 & 1 & 0 & -1 &\ \ 1 &\ \ 1 \\ 0 & 0 & 1 &\ \ 1 &\ \ 0 &\ \ 0 \\ 0 & 1 & 1 &\ \ 0 & -1 & -1 \end{bmatrix} \xrightarrow{R_4 - R_2} \begin{bmatrix} 1 & 0 & 0 &\ \ 2 &\ \ 1 &\ \ 2 \\ 0 & 1 & 0 & -1 &\ \ 1 &\ \ 1 \\ 0 & 0 & 1 &\ \ 1 &\ \ 0 &\ \ 0 \\ 0 & 0 & 1 &\ \ 1 & -2 & -2 \end{bmatrix} \\ \\ &\xrightarrow{R_4 - R_3} \begin{bmatrix} 1 & 0 & 0 &\ \ 2 &\ \ 1 &\ \ 2 \\ 0 & 1 & 0 & -1 &\ \ 1 &\ \ 1 \\ 0 & 0 & 1 &\ \ 1 &\ \ 0 &\ \ 0 \\ 0 & 0 & 0 &\ \ 0 & -2 & -2 \end{bmatrix} \xrightarrow{-\frac{1}{2}R_4} \begin{bmatrix} 1 & 0 & 0 &\ \ 2 &\ \ 1 &\ \ 2 \\ 0 & 1 & 0 & -1 &\ \ 1 &\ \ 1 \\ 0 & 0 & 1 &\ \ 1 &\ \ 0 &\ \ 0 \\ 0 & 0 & 0 &\ \ 0 &\ \ 1 &\ \ 1 \end{bmatrix} \\ \\ &\xrightarrow{\substack{R_1 - R_4 \\ R_2 - R_4}} \begin{bmatrix} 1 & 0 & 0 &\ \ 2 & 0 & 1 \\ 0 & 1 & 0 & -1 & 0 & 0 \\ 0 & 0 & 1 &\ \ 1 & 0 & 0 \\ 0 & 0 & 0 &\ \ 0 & 1 & 1 \end{bmatrix} \end{align*} $$
Columns $1$, $2$, $3$, and $5$ are pivot columns; columns $4$ and $6$ are free. The free columns are linear combinations of the pivot columns to their left,
$$ \mathbf{a}_4 = 2\mathbf{a}_1 - \mathbf{a}_2 + \mathbf{a}_3, \qquad \mathbf{a}_6 = \mathbf{a}_1 + \mathbf{a}_5, $$
so $\mathbf{a}_4$ and $\mathbf{a}_6$ are removed. The pivot-column vectors are four linearly independent vectors in $\mathbb{R}^4$, hence a basis:
$$ \left\{\, \begin{bmatrix} 1 \\ 0 \\ 0 \\ 1 \end{bmatrix},\ \begin{bmatrix} 0 \\ 1 \\ 0 \\ 1 \end{bmatrix},\ \begin{bmatrix} 0 \\ 0 \\ 1 \\ 1 \end{bmatrix},\ \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \end{bmatrix} \,\right\} $$
Exercise 2 - Prove Theorem 5¶
Let $V$ be a finite-dimensional vector space. Prove Theorem 5 (Basis Construction):
- every linearly independent subset of $V$ can be extended to a basis for $V$;
- every spanning set of $V$ can be reduced to a basis for $V$ by removing vectors.
View Solution
Let $V$ be a finite-dimensional vector space with $\dim V = n$.
Part 1 — Extension. Let $L = \left\{ \mathbf{u}_1, \dots, \mathbf{u}_k \right\}$ be a linearly independent subset of $V$. By Theorem 1, an independent set in an $n$-dimensional space cannot have more than $n$ vectors, so $k \le n$.
If $\text{Span}(L) = V$, then $L$ is an independent spanning set, hence a basis, and there is nothing to add.
Otherwise $\text{Span}(L) \subsetneq V$, so choose a vector $\mathbf{u}_{k+1} \in V \setminus \text{Span}(L)$. The enlarged set $L \cup \left\{ \mathbf{u}_{k+1} \right\}$ is still linearly independent: if
$$c_1\mathbf{u}_1 + \dots + c_k\mathbf{u}_k + c_{k+1}\mathbf{u}_{k+1} = \mathbf{0},$$
then $c_{k+1} = 0$ — otherwise $\mathbf{u}_{k+1} = -\frac{1}{c_{k+1}}\left( c_1\mathbf{u}_1 + \dots + c_k\mathbf{u}_k \right) \in \text{Span}(L)$, contradicting the choice of $\mathbf{u}_{k+1}$ — and then $c_1 = \dots = c_k = 0$ because $L$ is linearly independent.
Repeat this step. Each repetition enlarges the independent set by one vector, and by Theorem 1 an independent set never exceeds $n$ vectors, so the process stops after at most $n - k$ steps. It can stop only when the current independent set spans $V$; otherwise another vector could be adjoined. The resulting set is a linearly independent spanning set — a basis for $V$ — that contains $L$. $\blacksquare$
(Equivalently, the process halts once the independent set reaches $n$ vectors, which is a basis by Theorem 3, part 1.)
Part 2 — Reduction. Let $S = \left\{ \mathbf{w}_1, \dots, \mathbf{w}_m \right\}$ be a spanning set for $V$, so $\text{Span}(S) = V$.
If $S$ is linearly independent, it is already a basis.
Otherwise $S$ is linearly dependent, so some $\mathbf{w}_j$ is a linear combination of the others,
$$\mathbf{w}_j = \sum_{i \neq j} c_i \mathbf{w}_i.$$
Removing $\mathbf{w}_j$ does not change the span: any linear combination that used $\mathbf{w}_j$ can be rewritten with the remaining vectors by substituting the expression above, so $\text{Span}\left( S \setminus \left\{ \mathbf{w}_j \right\} \right) = \text{Span}(S) = V$.
Repeat this step. Each removal deletes one vector while preserving the spanning property, and $S$ is finite, so the process stops after finitely many removals. It stops precisely when no remaining vector is a linear combination of the others — that is, when the remaining set is linearly independent. That set still spans $V$, so it is a basis for $V$ contained in $S$. $\blacksquare$
(Equivalently, the process halts once the spanning set is reduced to $n$ vectors, which is a basis by Theorem 3, part 2.)
In the previous section one reduces a matrix $A\in\mathbb{R}^{m\times n}$ (or $\mathbb{C}^{m\times n}$) into upper triangular, row echelon or reduced row echelon form to obtain the pivot columns. The pivot columns of the original matrix $A$ are linearly independent and form a basis for the column space $C(A)$.
In section 4.3 we defined the column space of a matrix $C(A)$, and the null space $N(A)$. We performed backward substitution to find the null space of the reduced form of matrix $A$.
Could one repeat this process upon $A^T$?
Definition¶
Row Space
For any $m\times n$ matrix $A$, the column space of $A^T$, $C(A^T)$, is called the row space of matrix $A$.
The row space of matrix $A$ is the span of the columns of matrix $A^T$; the span of the transposes of all of the rows of matrix $A$.
$$C(A^T) = \mathrm{Span}\left\{\, (\mathbf{a}^1)^T,\ \dots,\ (\mathbf{a}^m)^T \,\right\}$$
Example 6 - Determine the Row Space¶
In Exercise 1-1. we reduced the following matrix $$A = \begin{bmatrix} 1 & 0 & 2 &\ \ 1 &\ \ 2 \\ 0 & 1 & 3 &\ \ 1 &\ \ 1 \\ 1 & 1 & 5 &\ \ 0 &\ \ 1 \end{bmatrix} \rightarrow \begin{bmatrix} {\color{royalblue}1} & 0 & 2 & 0 & 1 \\ 0 & {\color{royalblue}1} & 3 & 0 & 0 \\ 0 & 0 & 0 & {\color{royalblue}1} & 1 \end{bmatrix}$$
From the reduced row echelon form of $A$ we determined that
$$C(A) = \mathrm{Span}\left\{\, \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix},\ \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix},\ \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} \,\right\}$$
One concludes this from the pivots in columns $1$, $2$, and $4$ of the reduced matrix. They also indicate pivot rows, that is, pivot columns of $A^T$. One concludes that the row space is given by
$$C(A^T) = C\left( \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 2 & 3 & 5 \\ 1 & 1 & 0 \\ 2 & 1 & 1 \end{bmatrix} \right) = \mathrm{Span}\left\{\, \begin{bmatrix} 1 \\ 0 \\ 2 \\ 1 \\ 2 \end{bmatrix},\ \begin{bmatrix} 0 \\ 1 \\ 3 \\ 1 \\ 1 \end{bmatrix},\ \begin{bmatrix} 1 \\ 1 \\ 5 \\ 0 \\ 1 \end{bmatrix} \,\right\}$$
Theorem 6¶
Nonsingular Invariance of Independence
If $n\times n$ matrix $A$ is non-singular, and $S$ is a linearly independent set of vectors in $\mathbb{R}^n$, then $AS = \left\{\, A\mathbf{x} \,:\, \mathbf{x}\in S \,\right\}$ is also linearly independent.
Proof of Theorem 6¶
Suppose we have a set of linearly independent vectors $U = \left\{\,\mathbf{u}_1,\ \dots,\ \mathbf{u}_k\,\right\}$ in vector space $\mathbb{R}^n$, and non-singular $n\times n$ matrix $A$. We must show that $\left\{\, A\mathbf{u}_1,\ \dots,\ A\mathbf{u}_k \,\right\}$ is a linearly independent set. Let $\mathbf{c}$ be a solution to
$$c_1A\mathbf{u}_1 + \dots + c_kA\mathbf{u}_k = \mathbf{0}$$
then
$$\mathbf{0} = c_1A\mathbf{u}_1 + \dots + c_kA\mathbf{u}_k = A\left( c_1\mathbf{u}_1 + \dots + c_k\mathbf{u}_k \right)$$
$A$ is non-singular so it is invertible. Hence
$$ \mathbf{0} = A^{-1}\mathbf{0} = A^{-1}A\left( c_1\mathbf{u}_1 + \dots + c_k\mathbf{u}_k \right) = c_1\mathbf{u}_1 + \dots + c_k\mathbf{u}_k $$
Therefore, $c_1=\dots=c_k=0$ since the vectors $\left\{\,\mathbf{u}_1,\ \dots,\ \mathbf{u}_k\,\right\}$ is a linearly independent set of vectors. Because the only solution to the homogeneous equation is the trivial solution, vectors $\left\{\,A\mathbf{u}_1,\ \dots,\ A\mathbf{u}_k\,\right\}$ is also a linearly independent set. $\blacksquare$
Theorem 7¶
Row Operations Preserve the Row Space
Performing a row operation on an $m\times n$ matrix $A$ preserves the row space of matrix $A$.
Proof of Theorem 7¶
Consider $m\times n$ matrix $A$. We can create an $m\times m$ non-singular matrix $E$ such that the product (composition) matrix $EA$ is the result of performing a Type I, II, or III row operation upon matrix $A$. Let us consider each type of row operation
- A type I row operation reorders the rows without changing them in any way. Any linear combination is unaffected by the order of addition by axiom 1 of vector spaces. The span of the rows is unaffected.
- A type II row operation multiplies one row by a nonzero scalar. If $t\neq0$, then replace row $\mathbf{a}^k$ with $t\mathbf{a}^k$. Any linear combination $c_1\mathbf{a}^1 + \cdots + c_k\mathbf{a}^k + \cdots c_m\mathbf{a}^m$ gets replaced with $c_1\mathbf{a}^1 + \cdots + t\frac{c_k}{t}\mathbf{a}^k + \cdots c_m\mathbf{a}^m$. The span is not affected.
- A type III row operation adds a nonzero multiple of one row to another. Let us add $t\mathbf{a}^j$ to $\mathbf{a}^k$. Then $$c_1\mathbf{a}^1 + \cdots + c_k(\mathbf{a}^k + t\mathbf{a}^j) + \cdots c_m\mathbf{a}^m = c_1\mathbf{a}^1 + \cdots + c_k\mathbf{a}^k + \cdots c_m\mathbf{a}^m + tc_k\mathbf{a}^j$$ This can be adjusted by $$c_1\mathbf{a}^1 + \cdots + c_k\mathbf{a}^k + \cdots c_m\mathbf{a}^m = c_1\mathbf{a}^1 + \cdots + c_k(\mathbf{a}^k + t\mathbf{a}^j) + \cdots c_m\mathbf{a}^m - tc_k\mathbf{a}^j$$The span is still unaffected. $\blacksquare$
This means that we are free to use the pivot rows of any form of a matrix for the row space. This includes
- the original matrix $A$,
- the upper triangular form of $A$,
- the row echelon form of $A$, or
- the reduced row echelon form of matrix $A$.
Theorem 8¶
Dimension of the Column Space
The dimension of the column space of $m\times n$ matrix $A$ is the number of pivots in the reduced row echelon form of the matrix.
Proof of Theorem 8¶
Consider $m\times n$ matrix $A$ with column-rank factorization $CR$. The columns of matrix $C$ are the pivot columns of $A$, and the columns of $R$ indicate the linear combination of each pivot column that results in a column of $A$. Since the columns of matrix $C$ are also columns in matrix $A$, $\dim(C(A))\ge\dim(C(C))$. Since every free column in matrix $A$ is a linear combination of the columns in matrix $C$, and every pivot column in matrix $A$ is a column in matrix $C$, $\dim(C(A))\le\dim(C(C))$. This completes the proof because the number of pivots is equal to the number of pivot columns $=\dim(C(A))$. $\blacksquare$
Example 7 - Row Space¶
Give a basis for the row space of $$A = \begin{bmatrix}\ \ 1\ &\ \ 4\ &\ \ 6\ &\ \ 1\ \\ \ \ 1\ &\ \ 0\ &\ \ 1\ &\ \ 0\ \\ \ \ 1\ &\ \ 6\ &\ \ 6\ & -1\ \\ \ \ 1\ &\ \ 2\ &\ \ 1\ & -2\ \end{bmatrix}$$
$$\begin{align*} \begin{bmatrix}\ \ 1\ &\ \ 4\ &\ \ 6\ &\ \ 1\ \\ \ \ 1\ &\ \ 0\ &\ \ 1\ &\ \ 0\ \\ \ \ 1\ &\ \ 6\ &\ \ 6\ & -1\ \\ \ \ 1\ &\ \ 2\ &\ \ 1\ & -2\ \end{bmatrix} &\xrightarrow{\substack{R_2 - R_1 \\ R_3 - R_1 \\ R_4 - R_1}} \begin{bmatrix}\ \ 1\ &\ \ 4\ &\ \ 6\ &\ \ 1\ \\ \ \ 0\ & -4\ & -5\ & -1\ \\ \ \ 0\ &\ \ 2\ &\ \ 0\ & -2\ \\ \ \ 0\ & -2\ & -5\ & -3\ \end{bmatrix} \xrightarrow{R_3\leftrightarrow R_2} \begin{bmatrix}\ \ 1\ &\ \ 4\ &\ \ 6\ &\ \ 1\ \\ \ \ 0\ &\ \ 2\ &\ \ 0\ & -2\ \\ \ \ 0\ & -4\ & -5\ & -1\ \\ \ \ 0\ & -2\ & -5\ & -3\ \end{bmatrix} \xrightarrow{\substack{R_3 + 2R_2 \\ R_4 + R_2}} \\ \\ \begin{bmatrix}\ \ 1\ &\ \ 4\ &\ \ 6\ &\ \ 1\ \\ \ \ 0\ &\ \ 2\ &\ \ 0\ & -2\ \\ \ \ 0\ &\ \ 0\ & -5\ & -5\ \\ \ \ 0\ &\ \ 0\ & -5\ & -5\ \end{bmatrix} &\xrightarrow{\substack{R_1 - 2R_2 \\ R_4 - R_3}} \begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 6\ &\ \ 5\ \\ \ \ 0\ &\ \ 2\ &\ \ 0\ & -2\ \\ \ \ 0\ &\ \ 0\ & -5\ & -5\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \end{bmatrix} \xrightarrow{\substack{R_2/2 \\ -R_3/5}} \begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 6\ &\ \ 5\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ & -1\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \end{bmatrix} \xrightarrow{R_1-6R_3} \\ \\ \begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 0\ & -1\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ & -1\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \end{bmatrix} &\ \end{align*}$$ The row space $$ C(A^T) = \mathrm{Span}\left\{\, \begin{bmatrix}\ \ 1\ \\ \ \ 0\ \\ \ \ 0\ \\ -1\ \end{bmatrix},\ \begin{bmatrix}\ \ 0\ \\ \ \ 1\ \\ \ \ 0\ \\ -1\ \end{bmatrix},\ \begin{bmatrix}\ \ 0\ \\ \ \ 0\ \\ \ \ 1\ \\ \ \ 1\ \end{bmatrix} \,\right\}$$
Definition¶
Left Null Space
For any $m\times n$ matrix $A$ the null space of $A^T$, $N(A^T)$, is called the left null space of matrix $A$.
If $\mathbf{x}$ is in the left null space of matrix $A$ ($\mathbf{x}\in N(A^T)$), then $A^T\mathbf{x} = \mathbf{0}$. Thus $\mathbf{0}^T = \mathbf{x}^TA$. Multiplying matrix $A$ on the left by $\mathbf{x}^T$ yields the zero row $\mathbf{0}^T$. Hence $\mathbf{x}$ is a left null vector and $N(A^T)$ is the left null space.
Example 8 - Left Null Space¶
We find the left null space of $A$ by determining the null space of $A^T$.
$$\begin{align*} \begin{bmatrix}\ \ 1\ &\ \ 1\ &\ \ 1\ &\ \ 1\ \\ \ \ 4\ &\ \ 0\ &\ \ 6\ &\ \ 2\ \\ \ \ 6\ &\ \ 1\ &\ \ 6\ &\ \ 1\ \\ \ \ 1\ &\ \ 0\ & -1\ & -2\ \end{bmatrix} &\xrightarrow{\substack{R_2-4R_1 \\ R_3 - 6R_1\\ R_4-R_1}} \begin{bmatrix}\ \ 1\ &\ \ 1\ &\ \ 1\ &\ \ 1\ \\ \ \ 0\ & -4\ &\ \ 2\ & -2\ \\ \ \ 0\ & -5\ &\ \ 0\ & -5\ \\ \ \ 0\ & -1\ & -2\ & -3\ \end{bmatrix} \xrightarrow{R_2\leftrightarrow -R_3/5} \begin{bmatrix}\ \ 1\ &\ \ 1\ &\ \ 1\ &\ \ 1\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 1\ \\ \ \ 0\ & -4\ &\ \ 2\ & -2\ \\ \ \ 0\ & -1\ & -2\ & -3\ \end{bmatrix} \xrightarrow{\substack{R_3+4R_2 \\ R_4+R_2}} \\ \\ \begin{bmatrix}\ \ 1\ &\ \ 1\ &\ \ 1\ &\ \ 1\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ &\ \ 2\ &\ \ 2\ \\ \ \ 0\ &\ \ 0\ & -2\ & -2\ \end{bmatrix} &\xrightarrow{R_3/2\quad} \begin{bmatrix}\ \ 1\ &\ \ 1\ &\ \ 1\ &\ \ 1\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ & -2\ & -2\ \end{bmatrix} \xrightarrow{\substack{R_1-R_3 \\ R_4+2R_3}\quad} \begin{bmatrix}\ \ 1\ &\ \ 1\ &\ \ 0\ &\ \ 0\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \end{bmatrix} \xrightarrow{R_1-R_2} \\ \\ &\qquad\qquad\begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 0\ & -1\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \end{bmatrix} \end{align*}$$
$$y_4 = t\in\mathbb{R},\ y_3 = -t,\ y_2 = -t,\ y_1 = t$$
$$N(A^T) = \mathrm{Span}\left\{\, \begin{bmatrix}\ \ 1\ \\ -1\ \\ -1\ \\ \ \ 1\ \end{bmatrix} \,\right\}$$
Bases for a vector space are not unique. We will find in this chapter that a basis for a vector space is chosen. One chooses a basis that is convenient for a particular application, or to illustrate specific properties of a linear model. There are default bases that get used most often.
The canonical basis or standard basis for finite dimensional vector space $\mathbb{R}^n$ is given by
$$ \mathbf{e}_1 = \begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0 \\ \vdots \\ 0 \end{bmatrix},\ \cdots,\ \mathbf{e}_k = \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 1 \\ \vdots \\ 0 \end{bmatrix},\ \cdots,\ \mathbf{e}_n = \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0 \\ \vdots \\ 1 \end{bmatrix} $$
The standard basis for $\mathbb{R}^2$ is
$$ \left\{\,\mathbf{e}_1, \mathbf{e}_2\,\right\} = \left\{\,\ihat,\ \jhat\,\right\} = \left\{\,\begin{bmatrix} 1 \\ 0 \end{bmatrix},\ \begin{bmatrix} 0 \\ 1 \end{bmatrix}\,\right\} $$
The standard basis for $\mathbb{R}^3$ is
$$ \left\{\,\mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3\,\right\} = \left\{\,\ihat,\ \jhat,\ \khat\,\right\} = \left\{\ \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix},\ \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix},\ \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}\ \right\} $$
The standard basis for $\mathbb{R}^n$ is
$$ \left\{\,\mathbf{e}_1,\ \dots,\ \mathbf{e}_n\,\right\} = \left\{\ \begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{bmatrix},\ \dots,\ \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 1 \end{bmatrix}\ \right\} $$
The canonical basis for $P_n$ is the set of polynomial terms
$$\left\{\, \mathbf{e}_1,\ \mathbf{e}_2,\ \dots,\ \mathbf{e}_{n+1} \,\right\} = \left\{\, 1,\ x,\ \dots,\ x^n \,\right\}$$
The canonical basis for $\mathbb{R}^{2\times 2}$ is given by
$$\left\{\,\mathbf{e}_1,\ \mathbf{e}_2,\ \mathbf{e}_3,\ \mathbf{e}_4\,\right\} = \left\{\, \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\}$$
The canonical basis for vector space $P$ consists of an infinite number of polynomial terms.
$$\left\{\, \mathbf{e}_k\,:\,k\in\mathbb{Z}^+ \,\right\} = \left\{\, x^{k-1} \,:\, k\in\mathbb{Z}^+ \,\right\}$$
We have already met one infinite-dimensional space: the polynomials $P$, with basis $\left\{\,1,\ x,\ x^2,\ \dots\,\right\}$. No finite list of powers spans it, so its dimension is infinite. But notice that every individual polynomial still stops at a highest power — its coordinate list $\left\{\,a_0,\ a_1,\ \dots,\ a_n,\ 0,\ 0,\ \dots\,\right\}$ is eventually all zeros.
This raises a natural question: is there a space of functions whose members genuinely do not stop — where a single function needs infinitely many powers of $x$?
The functions you already know from calculus answer it. The exponential
$$ e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots $$
is not a polynomial, yet its series looks like a polynomial that never ends. The same is true of $\sin x$, $\cos x$, and $\dfrac{1}{1-x}$ on $(-1, 1)$.
If we let the degree of a polynomial run off to infinity, we get a power series. A power series is a limit of polynomials
$$p_n(x) = a_0 + a_1x + \cdots + a_nx^n $$
Grant Sanderson demonstrates how to build such a series for a smooth function on a closed and bounded interval 
Taylor Series. A function that equals its power series near every point of an interval is called real analytic.
Definition¶
Real Analytic Function
A function $f:\,I\rightarrow\mathbb{R}$ on an interval $I\subset\mathbb{R}$ that has an absolutely convergent power series with positive radius of convergence at every point $x\in I$ is called a real analytic function.
$$ f(x) = \displaystyle\lim_{N\rightarrow\infty}\ \displaystyle\sum_{k=0}^{N} a_k(x-x_0)^k := \displaystyle\sum_{k=0}^{\infty} a_k(x-x_0)^k $$
Every partial sum
$$s_n(x) = \displaystyle\sum_{k=0}^n a_k(x-x_0)^k = a_0 + a_1(x-x_0) + \dots + a_n(x-x_0)^n$$
is a polynomial, so an analytic function is a limit of polynomials.
Example 9 - Continuous but not Analytic¶
Not every continuous function is analytic. Three kinds of failure:
- The absolute value $f(x) = |x|$, with a corner at the origin where no derivative exists.
- Other corner functions, such as the ramp $f(x) = \max\left\{\,0,\ x\,\right\}$ (the "ReLU" of machine learning). It is continuous everywhere, but the left slope $0$ and right slope $1$ disagree at $x = 0$, so it has no derivative there.
- Piecewise-defined functions, such as
$$ f(x) = \begin{cases} e^{-1/x}, & x > 0 \\[4pt] 0, & x \le 0 \end{cases} $$
This one is infinitely differentiable at the origin, yet every derivative there equals $0$. Its Maclaurin series is therefore the zero series, which fails to reproduce $f(x)$ for $x > 0$. A function can be perfectly smooth and still not analytic.
Example 10 - Functions as Coordinate Lists¶
In STEM we often restrict the enormous space $C[a,b]$ to the smaller subspace of analytic functions $C^{\omega}[a,b]$. On $\left[-\pi, \pi\right]$, take the Maclaurin series
$$ f(x) = \displaystyle\sum_{k=0}^{\infty} a_kx^k $$
against the independent set $\left\{\,1,\ x,\ x^2,\ \dots\,\right\}$. The one difference from the polynomial case is that here we allow infinitely many terms in the combination, not just finitely many — so each function is recorded by a list of coordinates that may run forever:
$$ f(x)\ \leftrightarrow\ \left\{\,a_0,\ a_1,\ a_2,\ \dots\,\right\} = \left\{\,a_k\,\right\}_{k=0}^{\infty} $$
A polynomial's list is eventually all zeros; an analytic function's need not be. That is the sense in which this subspace is larger than $P$.
Example 11 - Coordinates for Cosine¶
From calculus, the Maclaurin series for cosine is
$$ \cos(x) = \displaystyle\sum_{n=0}^{\infty} (-1)^n\frac{x^{2n}}{(2n)!} $$
so the vector $\cos$ has the coordinates
$$ \left\{\,1,\ 0,\ -\frac{1}{2},\ 0,\ \frac{1}{24},\ 0,\ -\frac{1}{720},\ 0,\ \dots,\ \frac{(-1)^n}{(2n)!},\ \dots\,\right\} $$
Exercise 3 - Coordinates for Sine¶
Find the coordinate list for $\sin x$ against the independent set $\left\{\,1,\ x,\ x^2,\ \dots\,\right\}$ on $\left[-1, 1\right]$.
View Solution
The Maclaurin series for sine is $$ \sin x = \displaystyle\sum_{n=0}^{\infty} (-1)^n\frac{x^{2n+1}}{(2n+1)!} = x - \frac{x^3}{6} + \frac{x^5}{120} - \cdots $$ Only the odd powers appear, so every even coordinate is zero: $$ \sin x\ \leftrightarrow\ \left\{\,0,\ 1,\ 0,\ -\frac{1}{6},\ 0,\ \frac{1}{120},\ 0,\ -\frac{1}{5040},\ \dots\,\right\} $$
Exercise 4 - Coordinates for a Non-Trigonometric Function¶
Find the coordinate list for $e^x$ against the independent set $\left\{\,1,\ x,\ x^2,\ \dots\,\right\}$ on $\left[-1, 1\right]$.
View Solution
The Maclaurin series for the exponential is $$ e^x = \displaystyle\sum_{k=0}^{\infty} \frac{x^k}{k!} = 1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \cdots $$ Every power appears, so no coordinate is zero: $$ e^x\ \leftrightarrow\ \left\{\,1,\ 1,\ \frac{1}{2},\ \frac{1}{6},\ \frac{1}{24},\ \dots,\ \frac{1}{k!},\ \dots\,\right\} $$
Exercise 5 - Show the Set of Vectors Forms a Basis¶
Show that the set of vectors $\left\{\,\begin{bmatrix}\ 0\ \\ \ 4\ \\ -2\ \\ \ 1\ \end{bmatrix},\ \begin{bmatrix} \ 0\ \\ \ 3\ \\ \ 3\ \\ -1\ \end{bmatrix},\ \begin{bmatrix} \ 1\ \\ \ 1\ \\ \ 2\ \\ \ 2\ \end{bmatrix},\ \begin{bmatrix} \ 3\ \\ -1\ \\ \ 2\ \\ \ 2\ \end{bmatrix}\,\right\}$ is a basis for $\mathbb{R}^4$.
View Solution
We need to show that these four vectors are linearly independent in a four dimensional vector space. Create the $4\times 4$ matrix $A = \begin{bmatrix} \mathbf{u}_1 & \mathbf{u}_2 & \mathbf{u}_3 & \mathbf{u}_4 \end{bmatrix}$ and reduce it to upper triangular form to determine the number of pivot columns. $$ \begin{align*} A &= \begin{bmatrix} \ \ 0\ &\ \ 0\ &\ \ 1\ &\ \ 3\ \\ \ \ 4\ &\ \ 3\ &\ \ 1\ & -1\ \\ -2\ &\ \ 3\ &\ \ 2\ &\ \ 2\ \\ \ \ 1\ & -1\ &\ \ 2\ &\ \ 2\ \end{bmatrix} \xrightarrow{R_1\leftrightarrow R_4} \begin{bmatrix} \ \ 1\ & -1\ &\ \ 2\ &\ \ 2\ \\ \ \ 4\ &\ \ 3\ &\ \ 1\ & -1\ \\ -2\ &\ \ 3\ &\ \ 2\ &\ \ 2\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ \ 3\ \end{bmatrix} \xrightarrow{\substack{R_2-4R_1 \\ R_3+2R_1}} \begin{bmatrix} \ \ 1\ & -1\ &\ \ 2\ &\ \ 2\ \\ \ \ 0\ &\ \ 7\ & -7\ & -9\ \\ \ \ 0\ &\ \ 1\ &\ \ 6\ &\ \ 6\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ \ 3\ \end{bmatrix} \xrightarrow{\substack{R_3 \\ R_4 \\ R_2-7R_3}} \\ \\ &= \begin{bmatrix} \ \ 1\ & -1\ &\ \ 2\ &\ \ 2\ \\ \ \ 0\ &\ \ 1\ &\ \ 6\ &\ \ 6\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ \ 3\ \\ \ \ 0\ &\ \ 0\ & -49\ & -51\ \end{bmatrix} \xrightarrow{R_4+49R_3} \begin{bmatrix} \ \ 1\ & -1\ &\ \ 2\ &\ \ 2\ \\ \ \ 0\ &\ \ 1\ &\ \ 6\ &\ \ 6\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ \ 3\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ & \ 96\ \end{bmatrix} \end{align*} $$ All four columns of matrix $A$ are pivot columns, so all four column vectors are linearly independent. Therefore the set of vectors is a basis for $\mathbb{R}^4$.Exercise 6 - Show the Set of Vectors Does Not Form a Basis¶
Show that the set of vectors
$$ \mathbf{x}_1 = \begin{bmatrix}\ 2\ \\ \ 1\ \\ \ 3\ \end{bmatrix},\qquad\mathbf{x}_2 = \begin{bmatrix}\ 1\ \\ \ 3\ \\ \ 2\ \end{bmatrix} $$
is not a basis for $\mathbb{R}^3$.
View Solution
The two given vectors are linearly independent, but there are only two vectors for a three dimensional vector space. The set of vectors $\left\{ \mathbf{x}_1, \mathbf{x}_2 \right\}$ is not a basis for $\mathbb{R}^3$ because there are not enough vectors.
Exercise 7 - Show the Set of Vectors is Dependent¶
Show that the set of vectors
$$ U = \left\{\,\begin{bmatrix} \ 2 \\ \ 1 \\ -1 \end{bmatrix},\ \begin{bmatrix} \ 3 \\ \ 2 \\ \ 0 \end{bmatrix},\ \begin{bmatrix} \ 1 \\ \ 0 \\ -2 \end{bmatrix},\ \begin{bmatrix} -1 \\ -2 \\ -1 \end{bmatrix}\,\right\} $$
is linearly dependent and find a subset of these vectors that constitute a basis for $\mathbb{R}^3$.
View Solution
The set $U$ is a set of four vectors in a three dimensional vector space so they are linearly dependent! To distinguish the linearly independent vectors from the linearly dependent vectors form the matrix $A = \begin{bmatrix} \mathbf{u}_1 & \mathbf{u}_2 & \mathbf{u}_3 & \mathbf{u}_4 \end{bmatrix}$ and reduce it to reduced row echelon form. $$ \begin{align*} A &= \begin{bmatrix} \ \ 2\ &\ \ 3\ &\ \ 1\ & -1\ \\ \ \ 1\ &\ \ 2\ &\ \ 0\ & -2\ \\ -1\ &\ \ 0\ & -2\ & -1\ \end{bmatrix} \xrightarrow{R_1-R_2} \begin{bmatrix} \ \ 1\ &\ \ 1\ &\ \ 1\ &\ \ 1\ \\ \ \ 1\ &\ \ 2\ &\ \ 0\ & -2\ \\ -1\ &\ \ 0\ & -2\ & -1\ \end{bmatrix} \xrightarrow{\substack{R_2-R_1 \\ R_3+R_1}} \begin{bmatrix} \ \ 1\ &\ \ 1\ &\ \ 1\ &\ \ 1\ \\ \ \ 0\ &\ \ 1\ & -1\ & -3\ \\ \ \ 0\ &\ \ 1\ & -1\ &\ \ 0\ \end{bmatrix} \\ \\ &\xrightarrow{R_3-R_2} \begin{bmatrix} \ \ 1\ &\ \ 1\ &\ \ 1\ &\ \ 1\ \\ \ \ 0\ &\ \ 1\ & -1\ & -3\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 3\ \end{bmatrix} \xrightarrow{\substack{R_1-R_3/3 \\ R_2+R_3 \\ R_3/3}} \begin{bmatrix} \ \ 1\ &\ \ 1\ &\ \ 1\ &\ \ 0\ \\ \ \ 0\ &\ \ 1\ & -1\ &\ \ 0\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 1\ \end{bmatrix} \xrightarrow{R_1-R_2} \begin{bmatrix} \ \ 1\ &\ \ 0\ &\ \ 2\ &\ \ 0\ \\ \ \ 0\ &\ \ 1\ & -1\ &\ \ 0\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 1\ \end{bmatrix} \end{align*} $$ Columns one, two and four are pivot columns and column three is a free column, so vectors $\mathbf{u}_1$, $\mathbf{u}_2$, $\mathbf{u}_4$ are linearly independent. However using the reduced row echelon form of matrix $A$, $\mathbf{a}_3 = 2\mathbf{a}_1 - \mathbf{a}_2$. Since the pivot columns are three linearly independent vectors in a three dimensional vector space the set $$ \left\{\,\begin{bmatrix} \ \ 2\ \\ \ \ 1\ \\ -1\ \end{bmatrix},\ \begin{bmatrix} \ 3 \\ \ 2 \\ \ 0 \end{bmatrix},\ \begin{bmatrix} -1 \\ -2 \\ -1 \end{bmatrix}\,\right\} $$ is a basis for vector space $\mathbb{R}^3$.
