#### Linear Combination, Span, and Linear Independence

##### Linear Combinations

A linear combination of the vectors ${v_1, … v_n} \in V$is a vector $v \in V$ of the form $a_1v_1 + … a_nv_n$ for $a_i \in \mathbb{F}$. Linear combinations of a bunch of vectors is just scaling each vector, and then adding them together.

Next, the span of a set of vectors $v_1, … v_n \in V$ is the set of all linear combinations of those vectors. Specifically, the span of a set $S$ where $S \subset{V}$ is denoted as $Span(S) = {a_1v_1 + … a_nv_n, v_1, … v_n \in S, a_1, … a_n \in \mathbb{F}}$

This is clearly a subset of $V$, since $V$ is closed under linear combination, but it is also a subspace of $V$. This means that the span of a set of vectors, that live in a vector space, produces a subspace of that vector space!

To show this, let’s let $S = {v_1, … v_n} \subset V$. Then, $Span(S) = a_1v_1 + … a_nv_n$. To show that this is closed under linear combination, consider two vectors $m, k \in Span(S)$. Then, we can write $m = \lambda_1v_1 + …\lambda_nv_n$ and $k = \mu_1v_1 + … \mu_nv_n$. We need to show that for $\alpha, \beta \in \mathbb{F}$, $\alpha m + \beta k \in Span(S)$. We have

so we have shown that $Span(S)$ is indeed closed under linear combination.

Since we know that $Span(S)$ is closed under linear combination and it is a subset of $V$,$Span(S)$ is a subspace of $V$.

Defintion: let $S \subset V$ such that $V = Span(S)$. This means that every vector $v \in V$ can be generated by a linear combination of some elements in $S$. We say that $S$ generates $V$. Eventually, we will be interested in sets that generate vector spaces in a minimal way, leading us to bases.

##### Linear Independence

Definition: A set $S = {v_1, … v_n}$ is linearly dependent if there exists a nontrivial linear combination of the vectors producing $0$: $\lambda_1v_1 + … \lambda_n v_n = 0$, and at least one $\lambda_i \neq 0$. Otherwise, if the only linear combination of $0$ is the trivial one, then $S$ is linearly independent.

Proposition: $S = {e_1, … e_n}$ is linearly independent, where $e_i$ is the one-hot vector with $1$ in the ith column, and $0$ everywhere else. We have:

$\lambda_1 e_1 + … \lambda_n e_n = [\lambda_1, …, \lambda_n]^T = 0$ only if all $\lambda_i = 0$, so the set is linearly independent.

Linear independence depends on the field $\mathbb{F}$ that our vector space is defined over. For example, consider the vector space of complex numbers over the field of complex numbers. Then, $S = {1,i}$ is linearly dependent, since $i(1)+ -1(i)= 0$, butin the complex vector space over the real numbers, ${1, i}$ is linearly independent since we can only scale by real numbers, so there is no nontrivial linear combination of $0$.

Theorem - if $S$ is linearly independent, then $S \cup {v}$ is linearly dependent iff $v \in Span(S)$. The “iff” means that this is the only time when $S \cup v$ can be linearly dependent, and means that both of the following statements are true:

1. Forward implication: if $S$ is linearly independent, and $S \cup v$ is linearly dependent, then $v \in Span(S)$.
2. Backward implication: if $S$ is linearly independent and $v \in Span(S)$ then $S \cup v$ is linearly dependent.

Proof: Exercise.

##### Basis - The building blocks of Vector Spaces

Definition: A basis of a vector space is a linearly independent set that spans the vector space. It is therefore the “minimal” set of vectors that span the space, and in a sense contains no “redundant” information - though we will formalize these notions later.

Ex: the list of vectors $[1,0,0]^T, [0,1,0]^T, [0,0,1]^T$ is a (standard) basis for $\mathbb{R}^3$. The list of vectors ${1, x, x^2, x^3, …}$ is a basis for $P(\mathbb{F})$ (the standard basis). This means that bases can be finite-dimensional.

Ex: $1$ is a basis for the complex vector space over the complex numbers, but over the reals, ${1,i}$ is the basis.

Theorem: Let $S$ be finite and $span(S) = V$. Then, there exists a basis $B \subset S$. Proof: let $B = empty$ . Idea: we will build up $B$ by looking at elements in $S$ and adding certain elements to the basis.

Algorithm for constructing $B$: Look at each $v_i$ in $S$. If $B \cup v_i$ is linearly independent, then let $B = B \cup v_i$

This construction results in $B$ being a basis. First, by construction, $B$ is linearly independent, so all we have to show is that $Span(B) = V$. Since each $v_i \in B, v_i \in V$, $Span(B) \subset V$ since vector spaces are closed unear linear combination. If we can show that $V \subset Span(B)$ then we have $V = Span(B)$, since in general $A \in B, B \in A \rightarrow{} A = B$.

Since $V = Span(S)$ this is the same as showing that $Span(S) \in Span(B)$. This is the same as showing that $S \in Span(B)$ - this is because $Span(B)$ is a subspace, and subspaces are closed under linear combination, and $Span(S)$ is just taking linear combinations of vectors in $S$.

To show that $S \in Span(B)$, we can take any $v_i \in S$. There are two cases: $v_i \in B$ or not. If $v_i \in B$, then clearly $v_i \in Span(B)$, otherwise, $v_i \notin B$. By construction, this means that $B \cup v_i$ is linearly dependent, and by the previous theorem, this is only possible if $v_i \in Span(B)$, so either way, $v_i \in Span(B)$.

Since $S \in Span(B)$ we have $Span(S) = V \in Span(B)$

Theorem: Let $B = {v_1, … v_n} \in V$. $B$ is a basis for $V$ iff each $v \in V$ can be written as a unique linear combination of elements in $B$.

Proof: Forward implication states that if $B$ is a basis then any $v \in V$ can be written as $\lambda_1v_1 + .. \lambda_n v_n$ for uniques scalars $\lambda_i$. This means that if $v = \lambda_1v_1 + .. \lambda_n v_n$ and $v = \mu_1 v_1 + … \mu_n v_n$ then $\mu_i = \lambda_i \forall{} i$. To show this, we can subtract the two equalities, and get that $0 = \sum_i (\lambda_i - \mu_i)v_i$, but since $B$ is linearly independent, since it is a basis, the only linear combination that gives $0$ is the trivial one, so we must have $\lambda_i = \mu_i \forall{i}$.

Backward implication: states that if any $v \in V$ can be written as unique combination of scalars $\sum_i \lambda_iv_i$, then $B$ is a basis. First, we note that $B$ clearly generates $V$. Next, since all $v \in V$ can be written as a unique linear combination, then this is also true for $0$. But a linear combination for $0$ is $0 = \sum_i 0v_i$, so there is no other linear combination giving $0$ besides the trivial one, implying that $B$ is also linearly independent, and therefore a basis.