Mathematical Immaturity

1.7 Dependent and independent sets in a linear space

Definition.$\quad$ A set $S$ of elements in a linear space $V$ is called dependent if there is a finite set of distinct elements in $S,$ say $x_1, ..., x_k,$ and corresponding set of scalars $c_1, ..., c_k,$ not all zero, such that \begin{align*} \sum_{i=1}^k c_ix_i &= O. \end{align*} The set $S$ is called independent if it is not dependent. In this case, for all choices of distinct elements $x_1, ..., x_k$ in $S$ and scalars $c_1, ..., c_k,$ $$ \sum_{i=1}^k c_ix_i = O \quad \text{implies} \quad c_1 = c_2 = \cdots = c_k = 0. $$

$\text{Theorem 1.5.}\quad$ Let $S$ be an independent set consisting of $k$ elements in a linear space $V$ and let $L(S)$ be the subspace spanned by $S.$ Then, every set of $k + 1$ elements in $L(S)$ is dependent.

Proof.$\quad$ Let $S = \{x_1, ..., x_k\}$ be an independent set of elements in $V,$ and let $T = \{y_1, ..., y_{k + 1}\}$ be a set of $k + 1$ elements in the linear span of $S.$ We will prove by induction that the set $T$ is dependent for all $k \geq 1.$ \begin{align*} \end{align*} First, let $k = 1.$ Then $S = \{x_1\}$ and the linear span of $S$ contains all scalar multiples of $x_1.$ Let $T = \{y_1, y_2\},$ where $y_1 = a_1x_1$ and $y_2 = a_2x_1,$ with $a_1$ and $a_2$ are not both zero. If either $a_1$ or $a_2$ is zero, then $T$ is dependent since it would contain $O.$ Assume then that $a_1$ and $a_2$ are nonzero. If we take $b_1 = a_2$ and $b_2 = -a_1,$ we can see that $$b_1y_1 + b_2y_2 = (a_1a_2 - a_1a_2)x_1 = O.$$ And since $a_1$ and $a_2$ are nonzero, this shows that there exist scalars, not both zero, such that $\sum_{i = 1}^{k + 1}b_iy_i = O.$ Hence, $T$ is dependent for $k = 1.$ \begin{align*} \end{align*} Now that we have proven the theorem for $k - 1,$ let $k \gt 1,$ with $S = \{x_1, ..., x_k\}$ being an independent set of elements in $V$ and $T = \{y_1, ..., y_{k+1}\}$ being a set of $k+1$ elements in $L(S).$ And since $T$ is a set of elements from $L(S),$ we can represent each $y_i$ in $T,$ where $i = 1, ..., k + 1,$ as the sum: \begin{align*} y_i &= \sum_{j=1}^{k}a_{ij}x_j \end{align*} Then, the remainder of the proof falls into one of two cases: \begin{align*} \end{align*} $\text{Case 1.}\quad$ For some $j$ in $\{1, ..., k\}$ every $a_{ij} = 0.$ In this case, $x_j$ is not used and $y_i$ is instead in the linear span of the independent set $S' = \{x_2, ..., x_k\}.$ But this means that each subset of $T$ with $k$ elements is in the linear span of the independent set $S'$ containing $k - 1$ elements. But by induction, we know that the theorem is true in the case of $k - 1$ elements. Thus $T$ is dependent. \begin{align*} \end{align*} $\text{Case 2.}\quad$ For some $j$ in $\{1, ..., k\}$ not all $a_{ij}$ are zero. Suppose that $i = 1$ and $a_{1j} \neq 0.$ Then, for $i = 2, ..., k + 1,$ if we set $c_i = a_{ij}/a_{1j},$ we get \begin{align*} c_iy_1 &= \sum_{j = 1}^{k}c_ia_{1j}x_j \\ \\ &= a_{i1}x_1 + \sum_{j = 2}^{k}c_ia_{1j}x_j \end{align*} Subtracting $y_i$ from the above, we get \begin{align*} c_iy_1 - y_i &= a_{i1}x_1 + \sum_{j = 2}^{k}c_ia_{1j}x_j - \sum_{j = 1}^{k}a_{ij}x_j \\ \\ &= \sum_{j = 2}^{k}(c_ia_{1j} - a_{ij})x_j \end{align*} for $i = 2, ..., k+1.$ But, $c_iy_1 - y_i$ are $k$ vectors in the linear span of the $k - 1$ independent vectors $\{x_2, ..., x_k\}.$ By induction, we know that the vectors $c_iy_1 - y_i$ are dependent. Thus, for some choice of scalars $t_2, ..., t_{k+1},$ not all of which are zero, we have \begin{align*} \sum_{i = 2}^{k + 1}t_i(c_{i}y_1 - y_i) &= O \end{align*} Moreover, we find that \begin{align*} \left(\sum_{i = 2}^{k + 1}t_ic_{i}\right)y_1 - \sum_{i = 2}^{k+1}t_iy_i &= O \end{align*} But, this means that for $i = 1, ..., k+1,$ there exist scalars $q_i,$ not all zero, such that \begin{align*} \sum_{i = 1}^{k+1}q_iy_i &= O \end{align*} Thus, the set $\{y_1, ..., y_{k+1}\}$ is dependent. This completes the proof.