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.