p.28, example 2.4
$$ \begin{bmatrix}2&1&17\\1&-2&-4\\-3&4&5\end{bmatrix}\rightarrow\begin{bmatrix}2&1&17\\1&-2&-4\\-1&5&22\end{bmatrix}\rightarrow\begin{bmatrix}2&1&17\\1&-2&-4\\0&3&18\end{bmatrix}\rightarrow\begin{bmatrix}1&-2&-4\\2&1&17\\0&3&18\end{bmatrix} $$
$$ \rightarrow\begin{bmatrix}1&-2&-4\\0&5&25\\0&3&18\end{bmatrix}\rightarrow\begin{bmatrix}1&-2&-4\\0&1&5\\0&1&6\end{bmatrix}\rightarrow\begin{bmatrix}1&-2&-4\\0&1&5\\0&0&1\end{bmatrix} $$
p.30-31, Polynomials as a Vector Space
Proposition W.2.1 $\mathscr{P}(\mathbb{F})$ (the set of all polynomials with coefficients in $\mathbb{F}$) is a subspace of $\mathbb{F}^\mathbb{F}$, the vector space of functions from $\mathbb{F}$ to $\mathbb{F}$. This is equivalent to saying that $\mathscr{P}(\mathbb{F})$ is a vector space over $\mathbb{F}$.
Proof
- Define $0_{\mathscr{P}(\mathbb{F})}(z)\equiv0$ for all $z\in \mathbb{F}$. Then $0_{\mathscr{P}(\mathbb{F})}\in\mathscr{P}(\mathbb{F})$ since $0_{\mathscr{P}(F)}(z)=\sum_{i=0}^{m}0z^{i}$ for any $z\in \mathbb{F}$ and any nonnegative integer $m$. And $0_{\mathscr{P}(\mathbb{F})}$ is the additive identity since $p(z)+0_{\mathscr{P}(\mathbb{F})}(z)=p(z)$ for any $p\in \mathscr{P}(\mathbb{F})$ and for any $z\in \mathbb{F}$.
- Closed under addition: define $p_1(z)\equiv\sum_{i=0}^sa_iz^i$ and $p_2(z)\equiv\sum_{i=0}^tb_iz^i$. Then $(p_1+p_2)(z)\equiv p_1(z)+p_2(z)=\sum_{i=0}^{\max(s,t)}(a_i+b_i)z^i$ (where we extend the $a_i$’s or $b_i$’s to zero where appropriate). Hence $p_1+p_2\in\mathscr{P}(\mathbb{F})$.
- Closed under scalar multiplication: for $c\in \mathbb{F}$, $p(z)\equiv\sum_{i=0}^sa_iz^i$, and $(cp)(z)\equiv c\sum_{i=0}^sa_iz^i=\sum_{i=0}^sca_iz^i$. Then $cp\in\mathscr{P}(\mathbb{F})$.
$\blacksquare$
p.31, Example 2.14, $\mathscr{P}_m(\mathbb{F})$
Proposition W.2.2 For a nonnegative integer $m$, let $\mathscr{P}_m(\mathbb{F})$ denote the set of all polynomials with coefficients in $\mathbb{F}$ and degree at most $m$. Then $\mathscr{P}_m(\mathbb{F})$ is a finite-dimensional vector space for each nonnegative integer $m$.
Proof First let’s show that $\mathscr{P}_m(\mathbb{F})$ is a subspace of $\mathscr{P}(\mathbb{F})$.
- Define $0_{\mathscr{P}_{m}(\mathbb{F})}(z)\equiv0$ for all $z\in \mathbb{F}$. Then $0_{\mathscr{P}_{m}(\mathbb{F})}\in\mathscr{P}_{m}(\mathbb{F})$ since $0_{\mathscr{P}_{m}(F)}(z)=\sum_{i=0}^{m}0z^{i}$ for any $z\in \mathbb{F}$. And $0_{\mathscr{P}_{m}(\mathbb{F})}$ is the additive identity since $p(z)+0_{\mathscr{P}_{m}(\mathbb{F})}(z)=p(z)$ for any $p\in \mathscr{P}_{m}(\mathbb{F})$ and for any $z\in \mathbb{F}$.
- Closed under addition: define $p_1(z)\equiv\sum_{i=0}^sa_iz^i$ where $s\leq m$ and $p_2(z)\equiv\sum_{i=0}^tb_iz^i$ where $t\leq m$. Then $(p_1+p_2)(z)\equiv p_1(z)+p_2(z)=\sum_{i=0}^{\max(s,t)}(a_i+b_i)z^i$ (where we extend the $a_i$’s or $b_i$’s to zero where appropriate). Hence $p_1+p_2\in\mathscr{P}_{m}(\mathbb{F})$.
- Closed under scalar multiplication: for $c\in \mathbb{F}$, $p(z)\equiv\sum_{i=0}^sa_iz^i$ where $s\leq m$, and $(cp)(z)\equiv c\sum_{i=0}^sa_iz^i=\sum_{i=0}^sca_iz^i$. Then $cp\in\mathscr{P}_{m}(\mathbb{F})$.
Next, recall that a vector space is called finite-dimensional if some list of vectors in it spans the space. So it’s sufficient to show that $\mathscr{P}_m(\mathbb{F})=\text{span}(1,z,…,z^{m})$, where we slightly abuse notation by letting $z^{k}$ denote a function.
Let $p\in\mathscr{P}_m(\mathbb{F})$. Then $p=\sum_{i=0}^{m}a_iz^{i}\in\text{span}(1,z,…,z^{m})$ with $a_i\in\mathbb{F}$. $\blacksquare$
Contrapositive Intuition
For a statement $P\implies Q$, there are several related statements:
$$ \begin{array}{l} P\implies Q&\text{it's raining}\implies\text{grass is wet}&\text{shape is square}\implies\text{two pairs of parallel sides} \\ \text{Converse: }Q\implies P&\text{grass is wet}\implies\text{it's raining}&\text{two pairs of parallel sides}\implies\text{shape is square} \\ \text{Inverse: }\lnot P\implies\lnot Q&\text{it's not raining}\implies\text{grass isn't wet}&\text{shape isn't square}\implies\text{not two pairs of parallel sides} \\ \text{Contrapositive: }\lnot Q\implies\lnot P&\text{grass isn't wet}\implies\text{it's not raining}&\text{not two pairs of parallel sides}\implies\text{shape isn't square} \\ \end{array} $$
Notice that the converse and inverse statements may or may not be true when the original statement is true. But the contrapositive statement is true when the original statement is true. Also notice that the contrapositive of the contrapositive is the original statement.
In a proof by contrapositive, we prove $P\implies Q$ by assuming $\lnot Q$ and reasoning until we obtain $\lnot P$.
By comparison, in a proof by contradiction, we prove $P\implies Q$ by assuming both $P$ and $\lnot Q$ and deduce some other contradiction $R\wedge\lnot R$.
Let’s look at a simple comparison of contradiction vs contrapositive proofs:
Proposition: Suppose $A\subseteq B$. Then if $x\notin B$, then $x\notin A$.
Contradiction Proof: Assume $x\notin B$ and $x\in A$. Then, since $A\subseteq B$, we have $x\in B$. Contradiction. $\blacksquare$
Contrapositive Proof: Assume $x\in A$. Then, since $A\subseteq B$, we have $x\in B$. $\blacksquare$
Before we formally prove the equivalence of $P\implies Q$ and its contrapositive $\lnot Q\implies\lnot P$, let’s formally define the “implies” symbol $\implies$.
Definition The notation $A\implies B$ means that if $A$ occurs, then $B$ must occur. Hence, if $B$ doesn’t occur, then $A$ doesn’t occur. $\blacksquare$
Contrapositive Proposition W.2.3 $(P\implies Q)\iff(\lnot Q\implies\lnot P)$.
Proof Suppose $P\implies Q$. Then by the definition of “$\implies$”, if $Q$ doesn’t occur, then $P$ doesn’t occur. That is $\lnot Q\implies\lnot P$.
Now suppose that $\lnot Q\implies\lnot P$. If $P$ occurs, then $\lnot P$ doesn’t occur and by the definition of “$\implies$”, it must be that $\lnot Q$ doesn’t occur. That is, if $P$ occurs, then $Q$ occurs. $\blacksquare$
p.33, example 2.18
Proposition W.2.4 $(1,0,0),(0,1,0),(0,0,1)$ is linearly independent in $\mathbb{F}^3$.
Proof We wish to show that
$$ a(1,0,0)+b(0,1,0)+c(0,0,1)=0 $$
implies that $0=a=b=c$. We have
$$ \begin{bmatrix}0\\0\\0\end{bmatrix}=a\begin{bmatrix}1\\0\\0\end{bmatrix}+b\begin{bmatrix}0\\1\\0\end{bmatrix}+c\begin{bmatrix}0\\0\\1\end{bmatrix}=\begin{bmatrix}a\\b\\c\end{bmatrix} $$
$\blacksquare$
Proposition W.2.5 For each nonnegative integer $m$, the list $1,z,…,z^m$ is linearly independent in $\mathscr{P}(\mathbb{F})$. That is, if $0=a_0+a_1z^1+\dots+a_mz^m$ for all $z\in\mathbb{F}$, then $0=a_0=a_1=\dots=a_m$.
We offer three different proofs. Although the contradiction and contrapositive proofs are nearly identical, I present both to show how similar they are.
Proof By Differentiation Let $f(z)=0=a_0+a_1z^1+\dots+a_mz^m$. Note that $f=0$ is constant hence all its derivatives are zero. Hence $0=f^{(m)}(0)=m!a_m$. Hence $a_m=0$ and $f(z)=a_0+a_1z^1+\dots+a_{m-1}z^{m-1}$. Similarly $0=f^{(m-1)}(0)=(m-1)!a_{m-1}$. Hence $a_{m-1}=0$ and $f(z)=a_0+a_1z^1+\dots+a_{m-2}z^{m-2}$. Continuing in this way, we see that $0=a_0=a_1=\dots=a_m$.
Proof By Contradiction Let $f(z)=a_0+a_1z^1+\dots+a_mz^m$. The claim is that $f(z)=0$ for all $z\in\mathbb{F}$ implies that $0=a_0=a_1=\dots=a_m$.
Suppose instead that there exist $a_0,a_1,…,a_m$ not all zero such that $f(z)=0$ for all $z\in\mathbb{F}$. Let $a_j$ be the non-zero coefficient of greatest degree and let $I$ denote the set of indices with non-zero coefficients. Then
$$ \Big\lvert\lim_{\lvert z\rvert\rightarrow\infty}f(z)\Big\rvert=\Big\lvert\lim_{\lvert z\rvert\rightarrow\infty}\sum_{i\in I}a_iz^i\Big\rvert=\Big\lvert\lim_{\lvert z\rvert\rightarrow\infty}z^j\sum_{i\in I}a_iz^{i-j}\Big\rvert=\Big\lvert\lim_{\lvert z\rvert\rightarrow\infty}z^j\Big\rvert\Big\lvert\lim_{\lvert z\rvert\rightarrow\infty}\sum_{i\in I}a_iz^{i-j}\Big\rvert=\infty $$
since
$$ \lim_{\lvert z\rvert\rightarrow\infty}\sum_{i\in I}a_iz^{i-j}=\sum_{i\in I}\lim_{\lvert z\rvert\rightarrow\infty}a_iz^{i-j}=\lim_{\lvert z\rvert\rightarrow\infty}a_jz^{j-j}+\sum_{i\in I,i\lt j}\lim_{\lvert z\rvert\rightarrow\infty}a_iz^{i-j}=a_j+0 $$
But the condition that $f(z)=0$ for all $z\in\mathbb{F}$ implies that $\big\lvert\lim_{\lvert z\rvert\rightarrow\infty}f(z)\big\rvert=0$.
Proof by Contrapositive Let $f(z)=a_0+a_1z^1+\dots+a_mz^m$. The claim is that $f(z)=0$ for all $z\in\mathbb{F}$ implies that $0=a_0=a_1=\dots=a_m$.
Suppose there exist $a_0,a_1,…,a_m$ not all zero. Let $a_j$ be the non-zero coefficient of greatest degree and let $I$ denote the set of indices with non-zero coefficients. If $f(z)=0$ for all $z\in\mathbb{F}$ then $\big\lvert\lim_{\lvert z\rvert\rightarrow\infty}f(z)\big\rvert=0$. But
$$ \Big\lvert\lim_{\lvert z\rvert\rightarrow\infty}f(z)\Big\rvert=\Big\lvert\lim_{\lvert z\rvert\rightarrow\infty}\sum_{i\in I}a_iz^i\Big\rvert=\Big\lvert\lim_{\lvert z\rvert\rightarrow\infty}z^j\sum_{i\in I}a_iz^{i-j}\Big\rvert=\Big\lvert\lim_{\lvert z\rvert\rightarrow\infty}z^j\Big\rvert\Big\lvert\lim_{\lvert z\rvert\rightarrow\infty}\sum_{i\in I}a_iz^{i-j}\Big\rvert=\infty $$
since
$$ \lim_{\lvert z\rvert\rightarrow\infty}\sum_{i\in I}a_iz^{i-j}=\sum_{i\in I}\lim_{\lvert z\rvert\rightarrow\infty}a_iz^{i-j}=\lim_{\lvert z\rvert\rightarrow\infty}a_jz^{j-j}+\sum_{i\in I,i\lt j}\lim_{\lvert z\rvert\rightarrow\infty}a_iz^{i-j}=a_j+0 $$
Hence $f(z)\neq0$ from some $z\in\mathbb{F}$.
$\blacksquare$
Proposition W.2.6 Suppose $v_1,…,v_n$ is linearly independent in a vector space $V$ over $\mathbb{F}$. If $U$ is a subspace of $V$ over $\mathbb{F}$ and $v_1,…,v_n\in U$, then $v_1,…v_n$ is linearly independent in $U$.
Proof If
$$ 0=\sum_{i=1}^{n}a_iv_i $$
for some $a_1,…,a_n\in\mathbb{F}$, then the linear independence of $v_1,…,v_n$ in $V$ over $\mathbb{F}$ implies that $0=a_1=\dots=a_n$. $\blacksquare$
Corollary W.2.7 For each nonnegative integer $m$, the list $1,z,…,z^m$ is linearly independent in $\mathscr{P}_{m}(\mathbb{F})$.
Proof Above we showed that $\mathscr{P}_{m}(\mathbb{F})$ is a subspace of $\mathscr{P}(\mathbb{F})$ over $\mathbb{F}$. We also showed that $1,z,…,z^m$ is linearly independent in $\mathscr{P}(\mathbb{F})$. Then it suffices to show that $1,z,…,z^m\in\mathscr{P}_{m}(\mathbb{F})$, which is clear. $\blacksquare$
Proposition W.2.8 If some vectors are removed from a linearly independent list, the remaining list is also linearly independent.
Proof by Contradiction Let $v_1,…,v_{n+j}$ be linearly independent. Then
$$ 0=\sum_{i=1}^{n+j}a_iv_i $$
implies that $0=a_1=\dotsb=a_{n+j}$. Suppose $v_1,…,v_n$ is linearly dependent. Then there exist $b_1,…,b_n$ not all zero such that
$$ 0=\sum_{i=1}^{n}b_iv_i $$
But this implies that
$$ 0=\sum_{i=1}^{n}b_iv_i+\sum_{i=n+1}^{n+j}a_iv_i $$
since the $a_i$’s are zero. But this means that $v_1,…,v_{n+j}$ is linearly dependent. $\blacksquare$
p.33, Example 2.20
Proposition W.2.9 Given a list of vectors in a vector space, the list is linearly dependent if and only if some vector in the list is a linear combination of the other vectors.
Proof Suppose $v_1$ is a linear combination of the other vectors. Then there exist scalars $a_2,…,a_n$ not all zero such that
$$ v_1=\sum_{i=2}^{n}a_iv_i $$
or
$$ v_1+\sum_{i=2}^{n}(-a_i)v_i=v_1-\sum_{i=2}^{n}a_iv_i=0 $$
Hence the list $v_1,…,v_n$ is linearly dependent.
In the other direction, suppose $v_1,…,v_n$ is linearly dependent. Then there exist scalars $a_1,…,a_n$ not all zero such that
$$ \sum_{i=1}^{n}a_iv_i=0 $$
Without loss of generality, let $a_1\neq0$. Then
$$ a_1v_1=-\sum_{i=2}^{n}a_iv_i $$
Dividing through by the none-zero $a_1$, we get
$$ v_1=\sum_{i=2}^{n}-\frac{a_i}{a_1}v_i $$
Hence $v_1$ is a linear combination of the other vectors.
$\blacksquare$
p.35, 2.23 Length of linearly independent list $\leq$ length of spanning list
In Step 1, it reads “Thus by the Linear Dependence Lemma (LDL), we can remove one of the $w$’s so that…” Looking back at the text just after the LDL proof, we note that if it was possible to remove $u_1$ such that … then $u_1\in\text{span}\{\}=\{0\}$. That is, it’s only possible to remove $u_1$ if $u_1=0$. But $u_1\neq0$ because it’s part of a linearly independent list. That’s why we must remove one of the $w$’s.
p.36, 2.26 Finite Dimensional Subspaces
In the proof, it reads “… we have constructed a list of vectors such that no vector in this list is in the span of the previous vectors. Thus after each step we have constructed a linearly independent list, by the Linear Dependence Lemma.”
This statement follows from the contrapositive of the Linear Dependence Lemma. Let $v_1,…,v_m$ be a list of vectors in $V$.
Part (a) of the Linear Dependence Lemma: If $v_1,…,v_m$ is linearly dependent, then there exists $j\in\{1,2,…,m\}$ such that $v_j\in\text{span}\{v_1,…,v_{j-1}\}$.
The contrapositive is: If there does not exist $j\in\{1,2,…,m\}$ such that $v_j\in\text{span}\{v_1,…,v_{j-1}\}$, then $v_1,…,v_m$ is linearly independent.
Next we write out the contrapositive of the Proposition statement. The original statement is: Every subspace of a finite-dimensional vector space is finite-dimensional.
Let $U$ be a subspace of $V$.
Proposition If $V$ is finite-dimensional, then $U$ is finite-dimensional.
Contrapositive If $U$ is infinite-dimensional, then $V$ is infinite-dimensional.
Infinite-Dimensional Vector Spaces
Proposition W.2.10 A vector space $V$ is infinite-dimensional if and only if there exists a sequence of vectors $v_1,v_2,…$ in $V$ such that the list $v_1,v_2,…,v_n$ is linearly independent for every positive integer $n$.
Proof Suppose there exists an infinite sequence $v_1,v_2,…$ of vectors in $V$ such that $v_1,…,v_n$ is linearly independent for any positive integer $n$. If $V$ is finite dimensional, then there is a list of vectors $u_1,…,u_m\in V$ such that $V=\text{span}(u_1,…,u_m)$. Now the list $v_1,…,v_{m+1}$ is linearly independent and longer than $u_1,…,u_m$. But this is a contradiction since the length of every linearly independent list in $V$ must be less than or equal to $m$.
Conversely, suppose $V$ is infinite-dimensional and let $v_1,v_2,…,v_n$ be a list of linearly independent vectors. Such a list exists for some positive integer $n$ since $V\neq\{0\}$. This list cannot span $V$. Hence there exists a vector $v_{n+1}\in V$ such that $v_{n+1}\notin\text{span}(v_1,v_2,…,v_n)$. Hence the expanded list $v_1,v_2,…,v_n,v_{n+1}$ in $V$ is linearly independent. Since any list (which is finite by definition) cannot span $V$, we can repeat this procedure indefinitely. That is, we can create a sequence of vectors $v_1,v_2,…$ such that $v_1,v_2,…,v_n$ is linearly independent for every positive integer $n$.
$\blacksquare$
p.42, unmarked example at top of page
The list $(2,3,4),(9,6,8)$ is linearly independent:
$$ a(2,3,4)+b(9,6,8)=0\rightarrow\begin{bmatrix}2a+9b\\3a+6b\\4a+8b\end{bmatrix}=\begin{bmatrix}0\\0\\0\end{bmatrix}\rightarrow\begin{bmatrix}2&9&0\\3&6&0\\4&8&0\end{bmatrix}\rightarrow\begin{bmatrix}2&9&0\\1&2&0\\1&2&0\end{bmatrix} $$
$$ \rightarrow\begin{bmatrix}1&2&0\\2&9&0\\0&0&0\end{bmatrix}\rightarrow\begin{bmatrix}1&2&0\\0&5&0\\0&0&0\end{bmatrix}\rightarrow\begin{bmatrix}1&2&0\\0&1&0\\0&0&0\end{bmatrix}\rightarrow\begin{bmatrix}1&0&0\\0&1&0\\0&0&0\end{bmatrix}\rightarrow 0=a=b $$
Define $B\equiv u_1,u_2,w_1,w_2,w_3$ where
$$ u_1\equiv\begin{bmatrix}2\\3\\4\end{bmatrix}\quad u_2\equiv\begin{bmatrix}9\\6\\8\end{bmatrix}\quad w_1\equiv\begin{bmatrix}1\\0\\0\end{bmatrix}\quad w_2\equiv\begin{bmatrix}0\\1\\0\end{bmatrix}\quad w_3\equiv\begin{bmatrix}0\\0\\1\end{bmatrix} $$
Perform procedure:
Step-1: If $v_1=0$, delete $v_1$ from $B$, otherwise leave $B$ unchanged.
Step-j: If $v_j\in\text{span}(v_1,…,v_{j-1})$, delete $v_j$ from $B$, otherwise leave $B$ unchanged.
Execute:
Step-2: $u_2\notin\text{span}(u_1)$ since $u_1,u_2$ is linearly independent.
Step-3: $w_1\in\text{span}(u_1,u_2)$:
$$ a(2,3,4)+b(9,6,8)=(1,0,0)\rightarrow\begin{bmatrix}2a+9b\\3a+6b\\4a+8b\end{bmatrix}=\begin{bmatrix}1\\0\\0\end{bmatrix}\rightarrow\begin{bmatrix}2&9&1\\3&6&0\\4&8&0\end{bmatrix}\rightarrow\begin{bmatrix}2&9&1\\1&2&0\\1&2&0\end{bmatrix} $$
$$ \rightarrow\begin{bmatrix}1&2&0\\2&9&1\\0&0&0\end{bmatrix}\rightarrow\begin{bmatrix}1&2&0\\0&5&1\\0&0&0\end{bmatrix}\rightarrow\begin{bmatrix}1&2&0\\0&1&\frac{1}{5}\\0&0&0\end{bmatrix}\rightarrow\begin{bmatrix}1&0&-\frac{2}{5}\\0&1&\frac{1}{5}\\0&0&0\end{bmatrix}\rightarrow\begin{matrix}a=-\frac{2}{5}\\b=\frac{1}{5}\end{matrix} $$
Hence we remove $w_1$ from $B$ and get $B=u_1,u_2,w_2,w_3$.
Step-4: $w_2\notin\text{span}(u_1,u_2)$:
$$ a(2,3,4)+b(9,6,8)=(0,1,0)\rightarrow\begin{bmatrix}2a+9b\\3a+6b\\4a+8b\end{bmatrix}=\begin{bmatrix}0\\1\\0\end{bmatrix}\rightarrow\begin{bmatrix}2&9&0\\3&6&1\\4&8&0\end{bmatrix}\rightarrow\begin{bmatrix}2&9&0\\1&2&\frac{1}{3}\\1&2&0\end{bmatrix} $$
$$ \rightarrow\begin{bmatrix}1&2&\frac{1}{3}\\2&9&0\\0&0&-\frac{1}{3}\end{bmatrix}\rightarrow\text{ no solutions for }a\text{ and }b $$
Or check their linear independence:
$$ a(2,3,4)+b(9,6,8)+c(0,1,0)=(0,0,0)\rightarrow\begin{bmatrix}2a+9b+0c\\3a+6b+1c\\4a+8b+0c\end{bmatrix}=\begin{bmatrix}0\\0\\0\end{bmatrix}\rightarrow\begin{bmatrix}2&9&0&0\\3&6&1&0\\4&8&0&0\end{bmatrix} $$
$$ \rightarrow\begin{bmatrix}1&\frac{9}{2}&0&0\\3&6&1&0\\4&8&0&0\end{bmatrix}\rightarrow\begin{bmatrix}1&\frac{9}{2}&0&0\\0&6-3\cdot\frac{9}{2}&1&0\\0&8-4\cdot\frac{9}{2}&0&0\end{bmatrix}\rightarrow\begin{bmatrix}1&\frac{9}{2}&0&0\\0&\frac{12}{2}-\frac{27}{2}&1&0\\0&\frac{16}{2}-\frac{36}{2}&0&0\end{bmatrix} $$
$$ \rightarrow\begin{bmatrix}1&\frac{9}{2}&0&0\\0&-\frac{15}{2}&1&0\\0&-\frac{20}{2}&0&0\end{bmatrix}\rightarrow\begin{bmatrix}1&\frac{9}{2}-\frac{9}{20}\frac{20}{2}&0&0\\0&-\frac{15}{2}&1&0\\0&-\frac{20}{2}+\frac{4}{3}\frac{15}{2}&-\frac{4}{3}&0\end{bmatrix}\rightarrow\begin{bmatrix}1&0&0&0\\0&-\frac{15}{2}&1&0\\0&0&-\frac{4}{3}&0\end{bmatrix} $$
$$ \rightarrow\begin{bmatrix}1&0&0&0\\0&-\frac{15}{2}&1&0\\0&0&1&0\end{bmatrix}\rightarrow\begin{bmatrix}1&0&0&0\\0&-\frac{15}{2}&0&0\\0&0&1&0\end{bmatrix}\rightarrow0=a=b=c $$
Step-5: $w_3\in\text{span}(u_1,u_2,w_2)$:
$$ a(2,3,4)+b(9,6,8)+c(0,1,0)=(0,0,1)\rightarrow\begin{bmatrix}2a+9b+0c\\3a+6b+1c\\4a+8b+0c\end{bmatrix}=\begin{bmatrix}0\\0\\1\end{bmatrix}\rightarrow\begin{bmatrix}2&9&0&0\\3&6&1&0\\4&8&0&1\end{bmatrix} $$
$$ \rightarrow\begin{bmatrix}1&\frac{9}{2}&0&0\\3&6&1&0\\4&8&0&1\end{bmatrix}\rightarrow\begin{bmatrix}1&\frac{9}{2}&0&0\\0&6-3\cdot\frac{9}{2}&1&0\\0&8-4\cdot\frac{9}{2}&0&1\end{bmatrix}\rightarrow\begin{bmatrix}1&\frac{9}{2}&0&0\\0&\frac{12}{2}-\frac{27}{2}&1&0\\0&\frac{16}{2}-\frac{36}{2}&0&1\end{bmatrix} $$
$$ \rightarrow\begin{bmatrix}1&\frac{9}{2}&0&0\\0&-\frac{15}{2}&1&0\\0&-\frac{20}{2}&0&1\end{bmatrix}\rightarrow\begin{bmatrix}1&\frac{9}{2}-\frac{9}{20}\frac{20}{2}&0&\frac{9}{20}\\0&-\frac{15}{2}&1&0\\0&-\frac{20}{2}+\frac{4}{3}\frac{15}{2}&-\frac{4}{3}&1\end{bmatrix}\rightarrow\begin{bmatrix}1&0&0&\frac{9}{20}\\0&-\frac{15}{2}&1&0\\0&0&-\frac{4}{3}&1\end{bmatrix} $$
$$ \rightarrow\begin{bmatrix}1&0&0&\frac{9}{20}\\0&-\frac{15}{2}&1&0\\0&0&1&-\frac{3}{4}\end{bmatrix}\rightarrow\begin{bmatrix}1&0&0&\frac{9}{20}\\0&-\frac{15}{2}&0&\frac{3}{4}\\0&0&1&-\frac{3}{4}\end{bmatrix}\rightarrow\begin{bmatrix}1&0&0&\frac{9}{20}\\0&1&0&-\frac{2}{15}\frac{3}{4}\\0&0&1&-\frac{3}{4}\end{bmatrix} $$
$$ \rightarrow\begin{bmatrix}1&0&0&\frac{9}{20}\\0&1&0&-\frac{1}{10}\\0&0&1&-\frac{3}{4}\end{bmatrix}\rightarrow\begin{matrix}a=\frac{9}{20}\\b=-\frac{1}{10}\\c=-\frac{3}{4}\end{matrix} $$
import numpy as np
a,b,c=9/20,-1/10,-3/4
u1,u2,w2=np.array([2,3,4]),np.array([9,6,8]),np.array([0,1,0])
a*u1+b*u2+c*w2
array([ 0., 0., 1.])
Hence we remove $w_3$ from $B$ and get $B=u_1,u_2,w_2$.
p.47, 2.43 Dimension of a sum
In the proof, it reads “Clearly $\text{span}(u_1,…,u_m,v_1,…,v_j,w_1,…,w_k)$ contains $U_1$ and $U_2$ and hence equals $U_1+U_2$”.
Let’s prove each of these claims.
To show that $\text{span}(u_1,…,u_m,v_1,…,v_j,w_1,…,w_k)$ contains $U_1$, let $q\in U_1$. Since $u_1,…,u_m,v_1,…,v_j$ is a basis of $U_1$, then for some $a_1,…,a_m,b_1,…,b_j\in\mathbb{F}$, we have
$$\begin{align*} q &= a_1u_1+\dots+a_mu_m+b_1v_1+\dots+b_jv_j\\ &= a_1u_1+\dots+a_mu_m+b_1v_1+\dots+b_jv_j+0w_1+\dots+0w_k\\ &\in\text{span}(u_1,...,u_m,v_1,...,v_j,w_1,...,w_k) \end{align*}$$
Similarly, we can show that $\text{span}(u_1,…,u_m,v_1,…,v_j,w_1,…,w_k)$ contains $U_2$.
And we want to show that $\text{span}(u_1,…,u_m,v_1,…,v_j,w_1,…,w_k)=U_1+U_2$.
To show that $U_1+U_2\subset \text{span}(u_1,…,u_m,v_1,…,v_j,w_1,…,w_k)$, recall 1.39 (p.20): “Suppose $U_1$ and $U_2$ are subspaces of $V$. Then $U_1+U_2$ is the smallest subspace of $V$ containing $U_1$ and $U_2$”. So it suffices to show that $\text{span}(u_1,…,u_m,v_1,…,v_j,w_1,…,w_k)$ contains $U_1$ and $U_2$, which we just did.
To show that $\text{span}(u_1,…,u_m,v_1,…,v_j,w_1,…,w_k)\subset U_1+U_2$, recall 2.7 (p.29): “The span of a list of vectors in $V$ is the smallest subspace of $V$ containing all the vectors in the list”. So it suffices to show that $U_1+U_2$ contains all the vectors in the list $u_1,…,u_m,v_1,…,v_j,w_1,…,w_k$.
Note that $u_1,…,u_m\in U_1\cap U_2\subset U_1+U_2$. And note that $v_1,…,v_j\in U_1\subset U_1+U_2$. And note that $w_1,…,w_k\in U_2\subset U_1+U_2$. $\blacksquare$
Direct Sums
Proposition W.2.11 Let $U_1,…,U_m$ be finite subspaces of $V$. Let $u_1^{(i)},…,u_{n_i}^{(i)}$ be a basis for $U_i$ for $i=1,…,m$ and define the list $W\equiv u_1^{(1)},…,u_{n_1}^{(1)},u_1^{(2)},…,u_{n_2}^{(2)},…,u_1^{(m)},…,u_{n_m}^{(m)}$. That is, $W$ is the list of all of the vectors in all of the given bases for $U_1,…,U_m$. Then
$$ U_1+\dots+U_m=\text{span}(W) $$
and these conditions are equivalent:
$\quad(1)\quad \dim{(U_1+\dots+U_m)}=\text{len}(W)$
$\quad(2)\quad W$ is linearly independent in $U_1+\dots+U_m$
$\quad(3)\quad U_1+\dots+U_m=U_1\oplus\dots\oplus U_m$ is a direct sum
where $\text{len}(W)$ denotes the number of vectors in the list $W$.
Proof Let $u\in U_1+\dots+U_m$. Then $u=u_1+\dots+u_m$ for some $u_1\in U_1,…,u_m\in U_m$. And
$$ u_i=a_1^{(i)}u_1^{(i)}+\dots+a_{n_i}^{(i)}u_{n_i}^{(i)}=\sum_{j=1}^{n_i}a_j^{(i)}u_{j}^{(i)} $$
for some $a_j^{(i)}\in\mathbb{F}$ since $u_i\in U_i=\text{span}(u_1^{(i)},…,u_{n_i}^{(i)})$. Hence
$$ u=\sum_{i=1}^{m}u_i=\sum_{i=1}^{m}\big(a_1^{(i)}u_1^{(i)}+\dots+a_{n_i}^{(i)}u_{n_i}^{(i)}\big)=\sum_{i=1}^{m}\sum_{j=1}^{n_i}a_j^{(i)}u_j^{(i)}\in\text{span}(W) $$
The “$\in\text{span}(W)$” holds because $W$ is the list of all the $u_j^{(i)}$ for $i=1,…,m$ and $j=1,…,n_i$. Hence $U_1+\dots+U_m\subset\text{span}(W)$.
In the other direction, let $w\in\text{span}(W)$. Then we can write $w$ as $w=\sum_{i=1}^{m}\sum_{j=1}^{n_i}a_j^{(i)}u_j^{(i)}$. Note that $\sum_{j=1}^{n_i}a_j^{(i)}u_j^{(i)}\in U_i$ since $U_i=\text{span}(u_1^{(i)},…,u_{n_i}^{(i)})$. Define $u_i\equiv\sum_{j=1}^{n_i}a_j^{(i)}u_j^{(i)}\in U_i$. Then
$$ w=\sum_{i=1}^{m}\sum_{j=1}^{n_i}a_j^{(i)}u_j^{(i)}=\sum_{i=1}^{m}u_i\in U_1+\dots+U_m $$
and $\text{span}(W)\subset U_1+\dots+U_m$. Hence $\text{span}(W)=U_1+\dots+U_m$. In other words
$$\begin{align*} U_1+\dots+U_m &\equiv \{u_1+\dots+u_m:u_1\in U_1,...,u_m\in U_m\}\\ &= \Big\{\sum_{j=1}^{n_1}a_j^{(1)}u_j^{(1)}+\dots+\sum_{j=1}^{n_m}a_j^{(m)}u_j^{(m)}:a_j^{(i)}\in\mathbb{F}\Big\}\\ &= \Big\{\sum_{i=1}^{m}\sum_{j=1}^{n_i}a_j^{(i)}u_j^{(i)}:a_j^{(i)}\in\mathbb{F}\Big\}\\ &\equiv\text{span}(W) \end{align*}$$
Now let’s show that $\dim{(U_1+\dots+U_m)}=\text{len}(W)$ if and only if $W$ is linearly independent in $U_1+\dots+U_m$.
Suppose $W$ is linearly independent. Then $W$ spans and is linearly independent in $U_1+\dots+U_m$. Hence $W$ is a basis for $U_1+\dots+U_m$ and $\dim{(U_1+\dots+U_m)}=\text{len}(W)$.
In the other direction, suppose $\dim{(U_1+\dots+U_m)}=\text{len}(W)$. Since $\text{span}(W)=U_1+\dots+U_m$, we know, from 2.31 (p.40-41), that $W$ contains a basis for $U_1+\dots+U_m$. If $W$ is linearly dependent, then the Linear Dependence Lemma (2.21, p.34) tells us that $u_1^{(1)}=0$ or that at least one of the vectors in $W$ is in the span of the previous vectors. Then steps $1$ and $j$ from the proof of 2.31 will remove at least one vector from $W$ to get a basis $B$ for $U_1+\dots+U_m$. Then $\text{len}(W)\gt\text{len}(B)=\dim{(U_1+\dots+U_m)}$. Contradiction and $W$ is linearly independent.
Now let’s show that $W$ is linearly independent if and only if $U_1+\dots+U_m=U_1\oplus\dots\oplus U_m$ is a direct sum.
Suppose that $U_1+\dots+U_m$ is a direct sum and let $u\in U_1+\dots+U_m$. By the definition of direct sum, $u$ can be written in exactly one way as a sum $u=\sum_{i=1}^{m}u_i$ where $u_i\in U_i$. By 2.29 (p.39), $u_i$ can be written in exactly one way as a linear combination of the basis $u_1^{(i)},…,u_{n_i}^{(i)}$. That is, for some unique list of $a_j^{(i)}$’s, we have
$$ u=\sum_{i=1}^{m}u_i=\sum_{i=1}^{m}\sum_{j=1}^{n_i}a_j^{(i)}u_j^{(i)} $$
In particular, for $u=0$, we have
$$ 0=\sum_{i=1}^{m}\sum_{j=1}^{n_i}a_j^{(i)}u_j^{(i)} $$
Note that if we take $a_j^{(i)}=0$ for all $i$ and $j$, then this equation is satisfied. Again, these $0=a_j^{(i)}$’s are unique, which is to say that no other linear combination of the $u_j^{(i)}$’s will equal $0$. Hence $W$ is linearly independent in $U_1+\dots+U_m$.
In the other direction, suppose that $W$ is linearly independent and let $0=u_1+\dots+u_m$ for some $u_1\in U_1,…,u_m\in U_m$. Then $u_i=\sum_{j=1}^{n_i}a_j^{(i)}u_j^{(i)}$ for some $a_j^{(i)}\in\mathbb{F}$ and
$$ 0=\sum_{i=1}^{m}u_i=\sum_{i=1}^{m}\sum_{j=1}^{n_i}a_j^{(i)}u_j^{(i)} $$
The linear independence of $W$ implies that $a_j^{(i)}=0$ for all $i$ and $j$. Hence $u_i=\sum_{j=1}^{n_i}a_j^{(i)}u_j^{(i)}=0$ for all $i$. By 1.44 (p.23), this implies that $U_1+\dots+U_m=U_1\oplus\dots\oplus U_m$ is a direct sum. $\blacksquare$
Proposition W.2.11.a Let $v_1,…,v_{n-1},v_n$ be a basis for $V$. Let $a\in V$ be nonzero. Then $a$ is in at most one of $\text{span}(v_1,…,v_{n-1})$ or $\text{span}(v_n)$.
Proof Suppose $a\in\text{span}(v_1,…,v_{n-1})$ and $a\in\text{span}(v_n)$. Then
$$ a_nv_n=a=\sum_{i=1}^{n-1}a_iv_i $$
or
$$ a_nv_n+\sum_{i=1}^{n-1}(-a_i)v_i=a_nv_n-\sum_{i=1}^{n-1}a_iv_i=0 $$
But $v_1,…,v_{n-1},v_n$ is linearly independent. Hence $0=-a_1=\dotsb=-a_{n-1}=a_n$. Hence $a=0$. But this is a contradiction since we’re given that $a\neq0$. $\blacksquare$
Dimensional and Space Equality
Proposition W.2.12 Suppose $V$ is finite-dimensional and $U$ is a subspace of $V$. Then $\dim{V}=\dim{U}$ if and only if $V=U$.
Proof Suppose $\dim{V}=\dim{U}$. Let $u_1,…,u_n$ be a basis for $U$. Then $n=\dim{U}=\dim{V}$ and $u_1,…,u_n\in V$. By 2.39 (p.45), $u_1,…,u_n$ is a basis for $V$. Hence $V=\text{span}(u_1,…,u_n)=U$.
In the other direction, suppose $V=U$. Then $\dim{V}=\dim{U}$. $\blacksquare$
Corollary W.2.13 Suppose $V$ is finite-dimensional and $U$ is a subspace of $V$. If $\dim{U}<\dim{V}$, then $U\neq V$.
Proof $\dim{U}<\dim{V}\implies\dim{U}\neq\dim{V}\implies U\neq V$ $\blacksquare$
Combinations of Basis
The standard basis of $\mathbb{R}^2$ is $(1,0),(0,1)$. Note that $(1,0),(1,0)+(0,1)=(1,0),(1,1)$ is also a basis for $\mathbb{R}^2$:
$$ 0=a(1,0)+b(1,1)=(a,0)+(b,b)=(a+b,b)\implies0=b\implies0=a+b=a+0=a $$
Hence $(1,0),(1,0)+(0,1)=(1,0),(1,1)$ is linearly independent. This list also spans $\mathbb{R}^2$:
$$ (x,y)=a(1,0)+b(1,1)=(a+b,b)\implies b=y\implies x=a+b=a+y\implies a=x-y $$
Hence $(1,0),(1,0)+(0,1)=(1,0),(1,1)$ is a basis for $\mathbb{R}^2$. Let’s generalize this:
Proposition W.2.14 Suppose $v_1,v_2$ is a basis for $V$. Then for any nonzero scalars $c_1,c_2$, this is also a basis:
$$ c_1v_1,c_1v_1+c_2v_2 $$
Proof Let $v=a_1v_1+a_2v_2\in V$ and let $c_1,c_2$ be any nonzero scalars. Define $b_2\equiv\frac{a_2}{c_2}$ and $b_1\equiv\frac{a_1}{c_1}-b_2$. Then
$$ \frac{a_1}{c_1}=b_1+b_2\iff a_1=(b_1+b_2)c_1 $$
and
$$\begin{align*} v&=a_1v_1+a_2v_2 \\ &=(b_1+b_2)c_1v_1+\frac{a_2}{c_2}c_2v_2 \\ &=b_1c_1v_1+b_2c_1v_1+b_2c_2v_2 \\ &=b_1c_1v_1+b_2(c_1v_1+c_2v_2) \end{align*}$$
Hence $c_1v_1,c_1v_1+c_2v_2$ spans $V$. This list is also linearly independent:
$$\begin{align*} 0&=b_1c_1v_1+b_2(c_1v_1+c_2v_2) \\ &=(b_1+b_2)c_1v_1+b_2c_2v_2 \end{align*}$$
Since $v_1,v_2$ is linearly independent, then $b_2c_2=0$ and $(b_1+b_2)c_1=0$. But $c_2\neq0$, hence $b_2=0$. And
$$ b_1c_1=(b_1+0)c_1=(b_1+b_2)c_1=0 $$
implies that $b_1=0$ since $c_1\neq0$. Hence $c_1v_1,c_1v_1+c_2v_2$ is a basis for $V$. $\blacksquare$
Proposition W.2.15 Any nonzero scaling of a basis is a basis. That is, suppose $v_1,…,v_n$ is a basis for $V$. Then for any nonzero scalars $c_1,…,c_n$, this is also a basis:
$$ c_1v_1,...,c_nv_n $$
Proof Let $v=\sum_{k=1}^na_kv_k\in V$ and let $c_1,…,c_n$ be any nonzero scalars. Define $b_k\equiv\frac{a_k}{c_k}$. Then
$$ v=\sum_{k=1}^na_kv_k=\sum_{k=1}^n\frac{a_k}{c_k}c_kv_k=\sum_{k=1}^nb_kc_kv_k $$
Hence $c_1v_1,…,c_nv_n$ spans $V$. This list is also linearly independent:
$$ 0=\sum_{k=1}^nd_kc_kv_k $$
The linear independence of $v_1,…,v_n$ implies that $0=d_kc_k$ for $k=1,…,n$. Since $c_k\neq0$, then $0=d_k$ for $k=1,…,n$. $\blacksquare$
Definition WD.2.1 Given a particular ordering for a basis, any basis vector that precedes a given basis vector $b$ is called a previous basis vector for the basis vector $b$. The term previous basis vectors refers to the list of all such vectors. Notice that previous basis vectors are particular to an ordering. For example, consider these two different orderings:
$$ \text{ordering 1: }v_1,v_2,v_3,v_4,v_5 \quad\quad\quad \text{ordering 2: }v_5,v_4,v_3,v_2,v_1 $$
In the first ordering, the previous basis vectors of $v_3$ are $v_1,v_2$. In the second ordering, the previous basis vectors of $v_3$ are $v_5,v_4$. In the second ordering, the previous basis vectors of $v_5$ is a list of length $0$.
Definition WD.2.2 Given a particular ordering of a basis, adding all previous basis vectors to the basis refers to the process of adding all previous basis vectors to each and every basis vector in that ordering. For example, if $v_1,…,v_n$ is a basis of $V$, then adding all previous basis vectors gives
$$ v_1,v_1+v_2,v_1+v_2+v_3,...,\sum_{i=1}^{n-1}v_i,\sum_{i=1}^nv_i\\ =v_1,\sum_{i=1}^2v_i,\sum_{i=1}^3v_i,...,\sum_{i=1}^{n-1}v_i,\sum_{i=1}^nv_i $$
Again, note that the process of adding all previous basis vectors is unique to each possible ordering of a basis.
Proposition W.2.16 Adding all previous basis vectors to the basis gives a basis. That is, suppose $v_1,v_2,…,v_n$ is a basis for $V$. Then this is also a basis:
$$ v_1,v_1+v_2,v_1+v_2+v_3,...,\sum_{i=1}^{n-1}v_i,\sum_{i=1}^nv_i\\ =v_1,\sum_{i=1}^2v_i,\sum_{i=1}^3v_i,...,\sum_{i=1}^{n-1}v_i,\sum_{i=1}^nv_i $$
Proof by Induction First let’s show that $v_1,v_1+v_2,v_3,…,v_n$ is a basis for $V$. Let $v=\sum_{k=1}^na_kv_k\in V$. Then
$$\begin{align*} v&=a_1v_1+a_2v_2+\sum_{k=3}^na_kv_k \\ &=a_1v_1-a_2v_1+a_2v_1+a_2v_2+\sum_{k=3}^na_kv_k \\ &=(a_1-a_2)v_1+a_2(v_1+v_2)+\sum_{k=3}^na_kv_k \\ \end{align*}$$
Hence $v_1,v_1+v_2,v_3,…,v_n$ spans $V$. This list is also linearly independent:
$$\begin{align*} 0&=b_1v_1+b_2(v_1+v_2)+\sum_{k=3}^nb_kv_k \\ &=(b_1+b_2)v_1+b_2v_2+\sum_{k=3}^nb_kv_k \end{align*}$$
Since $v_1,v_2,…,v_n$ is linearly independent, then $0=b_2=(b_1+b_2)=b_3=\dotsb=b_n$. And $b_1=b_1+0=b_1+b_2=0$. Hence $v_1,v_1+v_2,v_3,…,v_n$ is a basis for $V$.
Now assume that this is a basis:
$$ \psi\equiv v_1,\sum_{i=1}^2v_i,\sum_{i=1}^3v_i,...,\sum_{i=1}^{n-1}v_i,v_n $$
It suffices to show that this is a basis:
$$ \phi\equiv v_1,\sum_{i=1}^2v_i,\sum_{i=1}^3v_i,...,\sum_{i=1}^{n-1}v_i,\sum_{i=1}^nv_i $$
Let $v\in V$. Then it can be written as a linear combination of $\psi$:
$$\begin{align*} v&=a_1v_1+a_2\sum_{i=1}^2v_i+a_3\sum_{i=1}^3v_i+\dotsb+a_{n-1}\sum_{i=1}^{n-1}v_i+a_nv_n \\ &=a_1v_1+a_2\sum_{i=1}^2v_i+a_3\sum_{i=1}^3v_i+\dotsb+a_{n-1}\sum_{i=1}^{n-1}v_i-a_n\sum_{i=1}^{n-1}v_i+a_n\sum_{i=1}^{n-1}v_i+a_nv_n \\ &=a_1v_1+a_2\sum_{i=1}^2v_i+a_3\sum_{i=1}^3v_i+\dotsb+(a_{n-1}-a_n)\sum_{i=1}^{n-1}v_i+a_n\sum_{i=1}^nv_i \end{align*}$$
Hence $\phi$ spans $V$. Let’s check linear independence:
$$\begin{align*} 0&=b_1v_1+b_2\sum_{i=1}^2v_i+b_3\sum_{i=1}^3v_i+\dotsb+b_{n-2}\sum_{i=1}^{n-2}v_i+b_{n-1}\sum_{i=1}^{n-1}v_i+b_n\sum_{i=1}^nv_i \\ &=\Big(\sum_{i=1}^{n}b_i\Big)v_1+\Big(\sum_{i=2}^{n}b_i\Big)v_2+\Big(\sum_{i=3}^{n}b_i\Big)v_3+\dotsb+\Big(\sum_{i=n-2}^{n}b_i\Big)v_{n-2}+\Big(\sum_{i=n-1}^{n}b_i\Big)v_{n-1}+b_nv_n \end{align*}$$
Since $v_1,…,v_n$ is linearly independent, then
$$\begin{align*} 0&=b_n \\ &=b_n+b_{n-1} \\ &=b_n+b_{n-1}+b_{n-2} \\ &=b_n+b_{n-1}+b_{n-2}+\dotsb+b_3 \\ &=b_n+b_{n-1}+b_{n-2}+\dotsb+b_3+b_2 \\ &=b_n+b_{n-1}+b_{n-2}+\dotsb+b_3+b_2+b_1 \\ \end{align*}$$
Hence $0=b_n=b_{n-1}=b_{n-2}=\dotsb=b_3=b_2=b_1$. $\blacksquare$
Proposition W.2.17 Suppose $v_1,v_2,…,v_n$ is a basis for $V$. Then for any nonzero scalars $c_1,c_2,…,c_n$, this is also a basis:
$$ c_1v_1,c_1v_1+c_2v_2,c_1v_1+c_2v_2+c_3v_3,...,\sum_{i=1}^{n-1}c_iv_i,\sum_{i=1}^nc_iv_i\\ =c_1v_1,\sum_{i=1}^2c_iv_i,\sum_{i=1}^3c_iv_i,...,\sum_{i=1}^{n-1}c_iv_i,\sum_{i=1}^nc_iv_i $$
Proof Fix any nonzero scalars $c_1,c_2,…,c_n$. Then proposition W.2.15 gives that this is a basis:
$$ c_1v_1,...,c_nv_n $$
Define $w_k=c_kv_k$. Then $w_1,…,w_n$ is a basis and proposition W.2.16 gives that this is a basis:
$$ w_1,\sum_{i=1}^2w_i,\sum_{i=1}^3w_i,...,\sum_{i=1}^{n-1}w_i,\sum_{i=1}^nw_i \\ =c_1v_1,\sum_{i=1}^2c_iv_i,\sum_{i=1}^3c_iv_i,...,\sum_{i=1}^{n-1}c_iv_i,\sum_{i=1}^nc_iv_i\quad\blacksquare $$
Let’s look at an example. Let $V=\mathbb{R}^4$ and define the standard basis there:
$$ v_1\equiv\begin{bmatrix}1\\0\\0\\0\end{bmatrix} \quad\quad v_2\equiv\begin{bmatrix}0\\1\\0\\0\end{bmatrix} \quad\quad v_3\equiv\begin{bmatrix}0\\0\\1\\0\end{bmatrix} \quad\quad v_4\equiv\begin{bmatrix}0\\0\\0\\1\end{bmatrix} $$
Let $a,b,c,d$ be any nonzero scalars. Then proposition W.2.17 gives that this is also a basis for $\mathbb{R}^4$:
$$\begin{matrix} av_1=\begin{bmatrix}a\\0\\0\\0\end{bmatrix} \quad\quad av_1+bv_2=\begin{bmatrix}a\\0\\0\\0\end{bmatrix}+\begin{bmatrix}0\\b\\0\\0\end{bmatrix} =\begin{bmatrix}a\\b\\0\\0\end{bmatrix} \quad\quad av_1+bv_2+cv_3=\begin{bmatrix}a\\0\\0\\0\end{bmatrix}+\begin{bmatrix}0\\b\\0\\0\end{bmatrix} +\begin{bmatrix}0\\0\\c\\0\end{bmatrix} =\begin{bmatrix}a\\b\\c\\0\end{bmatrix} \\\\ av_1+bv_2+cv_3+dv_4=\begin{bmatrix}a\\0\\0\\0\end{bmatrix}+\begin{bmatrix}0\\b\\0\\0\end{bmatrix} +\begin{bmatrix}0\\0\\c\\0\end{bmatrix}+\begin{bmatrix}0\\0\\0\\d\end{bmatrix} =\begin{bmatrix}a\\b\\c\\d\end{bmatrix} \end{matrix}$$
More succintly, this is a basis for $\mathbb{R}^4$:
$$ \begin{bmatrix}a\\0\\0\\0\end{bmatrix} \quad\quad \begin{bmatrix}a\\b\\0\\0\end{bmatrix} \quad\quad \begin{bmatrix}a\\b\\c\\0\end{bmatrix} \quad\quad \begin{bmatrix}a\\b\\c\\d\end{bmatrix} $$
But this is a bit restrictive. For example, look at the third vector in this basis: $(a,b,c,0)$. Wouldn’t we still have a basis if we replaced this with $(5a,-3b,-71c,0)$? How about if we replaced this with $(5a,0,-71c,0)$ or $(5a,-3b,0,0)$?
For additional nonzero scalars $e,f,g,h$, this should also be a basis for $\mathbb{R}^4$:
$$ av_1=\begin{bmatrix}a\\0\\0\\0\end{bmatrix} \quad\quad bv_1+cv_2=\begin{bmatrix}b\\c\\0\\0\end{bmatrix} \quad\quad dv_2+ev_3=\begin{bmatrix}0\\d\\e\\0\end{bmatrix} \quad\quad fv_1+gv_3+hv_4=\begin{bmatrix}f\\0\\g\\h\end{bmatrix} $$
Certainly this list spans $\mathbb{R}^4$. We can also show that it’s linearly independent (we will soon do so more generally).
Notice that we now allow for different scalars for different basis vectors. For instance, in the first basis vector, we scale $v_1$ by $a$. In the second basis vector, we scale the same $v_1$ by $b$, not by $a$.
We also allow for some zero scalars. For instance, in the last basis vector, we take $0v_2$. But we must be careful when applying a zero scalar to an original basis vector. For instance, suppose we set $h=0$. Then this list no longer spans $\mathbb{R}^4$ because the $4^{th}$ dimension is unreachable. That is, the $4^{th}$ row would be all zeros. Similarly, if $0=c=d$, then the $2^{nd}$ dimension is unreachable and the list doesn’t span $\mathbb{R}^4$.
So how can we determine which scalars can be zero and which scalars must be nonzero? Notice that we will span $\mathbb{R}^4$ so long as $a,c,e,h$ are nonzero. And we can allow $b,d,f,g$ to be zero without disrupting the span. So it seems we can state this: Adding any linear combination (zero or not) of previous basis vectors to any nonzero scaling of basis vectors produces a basis.
As a quick check, let’s reverse the order of the original basis vectors and see if this works. That is, redefine
$$ v_1\equiv\begin{bmatrix}0\\0\\0\\1\end{bmatrix} \quad\quad v_2\equiv\begin{bmatrix}0\\0\\1\\0\end{bmatrix} \quad\quad v_3\equiv\begin{bmatrix}0\\1\\0\\0\end{bmatrix} \quad\quad v_4\equiv\begin{bmatrix}1\\0\\0\\0\end{bmatrix} $$
Again we add some arbitrary linear combination (zero or not) of previous basis vectors to a nonzero scaling of the original basis vectors:
$$ av_1=\begin{bmatrix}0\\0\\0\\a\end{bmatrix} \quad\quad bv_1+cv_2=\begin{bmatrix}0\\0\\c\\b\end{bmatrix} \quad\quad dv_2+ev_3=\begin{bmatrix}0\\e\\d\\0\end{bmatrix} \quad\quad fv_1+gv_3+hv_4=\begin{bmatrix}h\\g\\0\\f\end{bmatrix} $$
Once again, we can choose $b,d,f,g$ to be zero or not and we will still get a basis, so long as we restrict $a,c,e,h$ to be nonzero.
Proposition W.2.18 For any ordering and nonzero scaling of a basis, adding any linear combination (zero or not) of previous basis vectors produces a basis. More specifically:
Let $v_1,…,v_n$ be a basis for $V$ and let $c_1,…,c_n$ be any nonzero scalars. Let $d_{i,j}$ be any scalars (zero or not) for $i=2,…,n$ and $j=1,…,i-1$. Define
$$ w_1\equiv c_1v_1\quad\quad\quad w_i\equiv c_iv_i+\sum_{j=1}^{i-1}d_{i,j}v_j\quad\text{for }i=2,...,n $$
Then $\text{span}(v_1,…,v_i)=\text{span}(w_1,…,w_i)$ and $w_1,…,w_i$ is linearly independent for $i=1,…,n$.
Proof This is trivial with one basis vector. Let $s\in\text{span}(v_1,v_2)$ and define $a_2\equiv\frac{s_2}{c_2}$ and $a_1\equiv\frac{s_1}{c_1}-\frac{a_2d_{2,1}}{c_1}$. Then
$$\begin{align*} s&=s_1v_1+s_2v_2 \\ &=\frac{s_1}{c_1}c_1v_1-a_2d_{2,1}v_1+a_2d_{2,1}v_1+a_2c_2v_2 \\ &=\frac{s_1}{c_1}c_1v_1-\frac{a_2d_{2,1}}{c_1}c_1v_1+a_2(c_2v_2+d_{2,1}v_1) \\ &=a_1c_1v_1+a_2(c_2v_2+d_{2,1}v_1) \\ &=a_1w_1+a_2w_2 \\ &\in\text{span}(w_1,w_2) \end{align*}$$
Conversely, let $s\in\text{span}(w_1,w_2)$ and define $b_1\equiv s_1c_1+s_2d_{2,1}$ and $b_2\equiv s_2c_2$. Then
$$\begin{align*} s&=s_1w_1+s_2w_2 \\ &=s_1c_1v_1+s_2\big(c_2w_2+d_{2,1}v_1\big) \\ &=s_1c_1v_1+s_2d_{2,1}v_1+s_2c_2w_2 \\ &=b_1v_1+b_2v_2 \\ &\in\text{span}(v_1,v_2) \end{align*}$$
Assume that $\text{span}(v_1,…,v_i)=\text{span}(w_1,…,w_i)$. Let $s\in\text{span}(v_1,…,v_i,v_{i+1})$ and define $a_{i+1}\equiv\frac{s_{i+1}}{c_{i+1}}$. Then
$$\begin{align*} s&=\sum_{k=1}^{i+1}s_kv_k \\ &=\sum_{k=1}^{i}s_kv_k+s_{i+1}v_{i+1} \\ &=\sum_{k=1}^{i}\big(s_kv_k-a_{i+1}d_{i+1,k}v_k+a_{i+1}d_{i+1,k}v_k\big)+s_{i+1}v_{i+1} \\ &=\sum_{k=1}^{i}\big(s_kv_k-a_{i+1}d_{i+1,k}v_k\big)+\sum_{k=1}^{i}a_{i+1}d_{i+1,k}v_k+s_{i+1}v_{i+1} \\ &=\sum_{k=1}^{i}\big(s_k-a_{i+1}d_{i+1,k}\big)v_k+a_{i+1}\sum_{j=1}^{i}d_{i+1,j}v_j+a_{i+1}c_{i+1}v_{i+1} \\ &=\sum_{k=1}^{i}a_kw_k+a_{i+1}\Big(c_{i+1}v_{i+1}+\sum_{j=1}^id_{i+1,j}v_j\Big) \\ &=\sum_{k=1}^{i+1}a_kw_k \\ &\in\text{span}(w_1,...,w_i,w_{i+1}) \end{align*}$$
In the next-to-last equality, note that $\sum_{k}^{i}(s_k-a_{i+1}d_{i+1,k})v_k\in\text{span}(v_1,…,v_i)=\text{span}(w_1,…,w_i)$.
Conversely, let $s\in\text{span}(w_1,…,w_i,w_{i+1})$. Then
$$\begin{align*} s&=\sum_{k=1}^{i+1}s_kw_k \\ &=\sum_{k=1}^{i}s_kw_k+s_{i+1}w_{i+1} \\ &=\sum_{k=1}^{i}b_kv_k+s_{i+1}\Big(c_{i+1}v_{i+1}+\sum_{k=1}^id_{i+1,k}v_k\Big) \\ &=\sum_{k=1}^{i}b_kv_k+s_{i+1}c_{i+1}v_{i+1}+\sum_{k=1}^is_{i+1}d_{i+1,k}v_k \\ &=\sum_{k=1}^{i}\big(b_k+s_{i+1}d_{i+1,k}\big)v_k+s_{i+1}c_{i+1}v_{i+1} \\ &\in\text{span}(v_1,...,v_i,v_{i+1}) \end{align*}$$
In the third equality, note that $\sum_k^is_kw_k\in\text{span}(w_1,…,w_i)=\text{span}(v_1,…,v_i)$.
It suffices to show that $w_1,…,w_n$ is linearly independent since any sublist will be too. If this isn’t true, then the Linear Dependence Lemma 2.21, p34 gives the existence of $i\in\{1,…,n\}$ such that $w_i\in\text{span}(w_1,…,w_{i-1})$. This gives the second equality:
$$ c_{i}v_{i}+\sum_{k=1}^{i-1}d_{i,k}v_k=w_i=\sum_{k=1}^{i-1}\psi_kw_k=\sum_{k=1}^{i-1}\phi_kv_k $$
The last equality holds because $\sum_{k=1}^{i-1}\psi_kw_k\in\text{span}(w_1,…,w_{i-1})=\text{span}(v_1,…,v_{i-1})$. This is equivalent to
$$ c_{i}v_{i}+\sum_{k=1}^{i-1}(d_{i,k}-\phi_k)v_k=0 $$
The linear independence of $v_1,…,v_i$ implies that $c_i=0$. Contradiction. $\blacksquare$
Proposition W.2.19 Incomplete Let $V$ be a finite-dimensional vector space with dimension $n$. And let $W$ denote the set of all bases for $V$. Then $W$ can be constructed from proposition W.2.18 and $W\cup\{0\}$ is a finite dimensional vector space with dimension $\frac{n(n+1)}{2}$.
Proof Incomplete Let $a,b\in W$ where $a=a_1,…,a_n$ and $b=b_1,…,b_n$. Define
$$ a+b\equiv a_1+b_1,a_2+b_2,...,a_n+b_n $$
We want to show that $a+b$ is a basis for $V$ or $a+b=0$. If $a_k=-b_k$ for $k=1,…,n$, then $a+b=0$ and we’re done. Suppose $a_k\neq-b_k$. Then for $v\in V$, we have
$$ \sum_{k=1}^nc_ka_k=v=\sum_{k=1}^nd_kb_k $$
or
$$ 2v=v+v=\sum_{k=1}^nc_ka_k+\sum_{k=1}^nd_kb_k=\sum_{k=1}^n(c_ka_k+d_kb_k)=\sum_{k=1}^n(c_ka_k+\frac{d_k}{c_k}c_kb_k) $$
$\blacksquare$
Largest Linearly Independent Sublist
Proposition W.2.20 Let $v_1,\dots,v_n\in V$ and let $L$ denote the length of any of the largest linearly independent sublists of $v_1,\dots,v_n$. Then
$$ \dim{\text{span}(v_1,\dots,v_n)}=L $$
Proof This proof is really a more detailed proof of proposition 2.31, p.41.
We perform a sequence of steps to reduce $v_1,\dots,v_n$ to a sublist $\phi$. Start with $\phi\equiv v_1,\dots,v_n$. Then
Step 1 If $v_1=0$, discard $v_1$ from $\phi$. If $v_1\neq0$, leave $\phi$ unchanged.
Step j If $v_j$ is in $\text{span}(v_1,\dots,v_{j-1})$, discard $v_j$ from $\phi$. Otherwise leave $\phi$ unchanged.
Note that these steps have discarded only those vectors that were already in the span of the previous vectors. Hence $\text{span}(\phi)=\text{span}(v_1,\dots,v_n)$. Let’s prove this. Let $v\in\text{span}(v_1,\dots,v_n)$. Then
$$ v=\sum_{j=1}^na_jv_j=\sum_{v_j\in\phi}a_jv_j+\sum_{v_j\notin\phi}a_jv_j $$
The sum on the right is a linear combination of $\phi$ since $v_j\notin\phi$ implies that $v_j$ is a linear combination of $\phi$. Hence $v\in\text{span}(\phi)$.
This process ensures that no vector in $\phi$ is in the span of the previous ones. Hence the contrapositive statement of the Linear Dependence Lemma implies that $\phi$ is linearly independent. Since $\phi$ spans and is linearly independent in $\text{span}(v_1,\dots,v_n)$, then $\phi$ is a basis for $\text{span}(v_1,\dots,v_n)$.
Since $\phi$ spans $\text{span}(v_1,\dots,v_n)$, then proposition 2.23, p.35 gives that the length of any linearly independent list in $\text{span}(v_1,\dots,v_n)$ must less than or equal to $\text{len}(\phi)$. In particular, the length of any linearly independent sublist of $v_1,\dots,v_n$ must less than or equal to $\text{len}(\phi)$. Hence $\phi$ is as long or longer than any linearly independent sublist of $v_1,\dots,v_n$. Hence $\text{len}(\phi)=L$ and
$$ \dim{\text{span}(v_1,\dots,v_n)}=\dim{\text{span}(\phi)}=\text{len}(\phi)=L\quad\blacksquare $$