linear independence

A linearly independent list is a list of vectors such that there is one unique choice of scalars to be able to construct each member of their span.

Based on the same technique as in the proof that a sum of subsets is a direct sum IFF there is only one way to write $0$, we can show that in a linearly independent list, there is (IFF) only one way to write the zero vector as a linear combination of that list of vectors —namely, the trivial representation of taking each vector to $0$. In fact, we will actually use that as the formal definition of linear independence.

This definition of linear independence is the result of the definition for direct sum.

constituents

A list of vectors $v_1, \dots, v_{m}$ in $V$

requirements

Formally, a linearly independent list is defined by there being only one choice of scalars $a_1, \dots, a_{m} \in \mathbb{F}$ to write $0$ as a linear combination of $v_{1},\dots, v_{m}$: namely, by taking each $a_1, \dots a_{m}$ to $0$.

We also declare $()$ to be linearly independent.

additional information

linearly dependent

a list is linearly dependent if…. its not linearly independent.

oh. my. god.

Based on the same formal definition, this means that a linearly dependent list is defined by the fact that there can be more than one way of writing $0$ as a linear combination of that list of vectors, where one of the ways makes it so that writing $0$ does not require all zero scalars.

length of linearly-independent list $\leq$ length of spanning list

A linearly independent list should be smaller or equal in length to a spanning list.

The canonical proof is one by induction.

Suppose $u_1, \dots u_{m}$ is an linearly independent list in $V$. Take also a list $w_1, \dots w_{n}$ spans $V$. We desire that $m\leq n$. We create a list of length $n$ containing all of the $w$ thus far. Our invariant is that $len(B) = n$. This proof essentially uses Floyd’s Invariant Method (compsci topic for Jack’s understanding only.)

base case

take the spanning list of $V$ we declared named $w_1, \dots w_{n}$. Given it spans, adding any other vector in $V$, if $w_1, \dots w_{n}$ isn’t already linearly dependent, will make it linearly dependent. This is because you can write the new vector $v \in V$ which you add as a linear combination of the previous vectors already as they already span $V$.

By the Linear Dependence Lemma, you can remove one of the vectors in the new linearly dependent list while keeping the list still spanning $V$.

Now, construct the list:

\begin{equation} u_1, w_1, \dots w_{n} \end{equation}

where, $u_{1} \in V$ is taken from that linearly independent list in $V$. By the statement above, via applying the Linear Dependence Lemma, we can create a list that spans the same space by taking away one of the $w_{j}$ (we can’t take $u_1$ because it is at the first position, and we can’t grantee its $0$—see the issue with the Linear Dependence Lemma). We now have a list $B$ with length $n$ with $u_1$ and the rest of the $w$ not taken away which span $V$

case number $j$

Given a spanning list $B$ of $V$ with length $n$, with some parts $u_1, \dots, u_{j-1}, w_{j}, \dots w_{n}$. We now include $u_{j}$ in the list, placing it after $u_{j-1}$. As the list pre-inclusion is already a spanning list of $V$, any new vectors from $V$ added will necessarily be able to be written as a linear combination of the other vectors already in the list. Therefore, we know that—if not already pre-inclusion—the list is linearly dependent.

Because the first half ($u_1,\dots u_{j}$) of this new list is linearly independent (given), the bit that “causes” the linear dependence is in the $w$ (i.e. each $u$ cannot be written by other $u$.) Therefore, we can say that the first condition of Linear Dependence Lemma allows us to remove one of the $w$ while spanning the same space, creating again a spanning list of length $n$.

induction

repeat the procedure $m$ times, resulting in all the $u_{j}$ being included in our new list $B$ of length still $n$. Given we contained a list of length $m$ in a list of length $n$, $m \leq n$.