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

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)$$ . 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 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.