#### 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 \(V\) produces a subspace of \(V\).

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

\[\alpha m + \beta k = \alpha \lambda_1v_1 + … \alpha \lambda_n v_n + \beta \mu_1v_1 + … \beta \mu_nv_n = (\alpha\lambda_1 + \beta\mu_1)v_1 + … (\alpha\lambda_n + \beta\mu_N)v_n \in Span(S)\]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 the idea of *basis*.

##### 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:

- Forward implication: if \(S\) is linearly independent, and \(S \cup v\) is linearly dependent, then \(v \in Span(S)\).
- 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)\) . Thus we have \(V = Span(B)\) and \(B\) is a basis.

**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 *unique*s 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.