Editing Linear span (section)

== Theorems ==
=== Equivalence of definitions ===
The set of all linear combinations of a subset {{mvar|S}} of {{mvar|V}}, a vector space over {{mvar|K}}, is the smallest linear subspace of {{mvar|V}} containing {{mvar|S}}.

:''Proof.'' We first prove that {{math|span ''S''}} is a subspace of {{mvar|V}}. Since {{mvar|S}} is a subset of {{mvar|V}}, we only need to prove the existence of a zero vector {{math|'''0'''}} in {{math|span ''S''}}, that {{math|span ''S''}} is closed under addition, and that {{math|span ''S''}} is closed under scalar multiplication. Letting <math>S = \{ \mathbf v_1, \mathbf v_2, \ldots, \mathbf v_n \}</math>, it is trivial that the zero vector of {{mvar|V}} exists in {{math|span ''S''}}, since <math>\mathbf 0 = 0 \mathbf v_1 + 0 \mathbf v_2 + \cdots + 0 \mathbf v_n</math>. Adding together two linear combinations of {{mvar|S}} also produces a linear combination of {{mvar|S}}: <math>(\lambda_1 \mathbf v_1 + \cdots + \lambda_n \mathbf v_n) + (\mu_1 \mathbf v_1 + \cdots + \mu_n \mathbf v_n) = (\lambda_1 + \mu_1) \mathbf v_1 + \cdots + (\lambda_n + \mu_n) \mathbf v_n</math>, where all <math>\lambda_i, \mu_i \in K</math>, and multiplying a linear combination of {{mvar|S}} by a scalar <math>c \in K</math> will produce another linear combination of {{mvar|S}}: <math>c(\lambda_1 \mathbf v_1 + \cdots + \lambda_n \mathbf v_n) = c\lambda_1 \mathbf v_1 + \cdots + c\lambda_n \mathbf v_n</math>. Thus {{math|span ''S''}} is a subspace of {{mvar|V}}.

:It follows that <math>S \subseteq \operatorname{span} S</math>, since every {{math|'''v'''<sub>''i''</sub>}} is a linear combination of {{mvar|S}} (trivially). Suppose that {{mvar|W}} is a linear subspace of {{mvar|V}} containing {{mvar|S}}. Since {{mvar|W}} is closed under addition and scalar multiplication, then every linear combination <math>\lambda_1 \mathbf v_1 + \cdots + \lambda_n \mathbf v_n</math> must be contained in {{mvar|W}}. Thus, {{math|span ''S''}} is contained in every subspace of {{mvar|V}} containing {{mvar|S}}, and the intersection of all such subspaces, or the smallest such subspace, is equal to the set of all linear combinations of {{mvar|S}}.

=== Size of spanning set is at least size of linearly independent set ===
Every spanning set {{mvar|S}} of a vector space {{mvar|V}} must contain at least as many elements as any [[Linear independence|linearly independent]] set of vectors from {{mvar|V}}.

:''Proof.'' Let <math>S = \{ \mathbf v_1, \ldots, \mathbf v_m \}</math> be a spanning set and <math>W = \{ \mathbf w_1, \ldots, \mathbf w_n \}</math> be a linearly independent set of vectors from {{mvar|V}}. We want to show that <math>m \geq n</math>.

:Since {{mvar|S}} spans {{mvar|V}}, then <math>S \cup \{ \mathbf w_1 \}</math> must also span {{mvar|V}}, and <math>\mathbf w_1</math> must be a linear combination of {{mvar|S}}. Thus <math>S \cup \{ \mathbf w_1 \}</math> is linearly dependent, and we can remove one vector from {{mvar|S}} that is a linear combination of the other elements. This vector cannot be any of the {{math|'''w'''<sub>''i''</sub>}}, since {{mvar|W}} is linearly independent. The resulting set is <math>\{ \mathbf w_1, \mathbf v_1, \ldots, \mathbf v_{i-1}, \mathbf v_{i+1}, \ldots, \mathbf v_m \}</math>, which is a spanning set of {{mvar|V}}. We repeat this step {{mvar|n}} times, where the resulting set after the {{mvar|p}}th step is the union of <math>\{ \mathbf w_1, \ldots, \mathbf w_p \}</math> and {{mvar|m - p}} vectors of {{mvar|S}}.

:It is ensured until the {{mvar|n}}th step that there will always be some {{math|'''v'''<sub>''i''</sub>}} to remove out of {{mvar|S}} for every adjoint of {{math|'''v'''}}, and thus there are at least as many {{math|'''v'''<sub>''i''</sub>}}'s as there are {{math|'''w'''<sub>''i''</sub>}}'s—i.e. <math>m \geq n</math>. To verify this, we assume by way of contradiction that <math>m < n</math>. Then, at the {{mvar|m}}th step, we have the set <math>\{ \mathbf w_1, \ldots, \mathbf w_m \}</math> and we can adjoin another vector <math>\mathbf w_{m+1}</math>. But, since <math>\{ \mathbf w_1, \ldots, \mathbf w_m \}</math> is a spanning set of {{mvar|V}}, <math>\mathbf w_{m+1}</math> is a linear combination of <math>\{ \mathbf w_1, \ldots, \mathbf w_m \}</math>. This is a contradiction, since {{mvar|W}} is linearly independent.

=== Spanning set can be reduced to a basis ===
Let {{mvar|V}} be a finite-dimensional vector space. Any set of vectors that spans {{mvar|V}} can be reduced to a [[Basis (linear algebra)|basis]] for {{mvar|V}}, by discarding vectors if necessary (i.e. if there are linearly dependent vectors in the set). If the [[axiom of choice]] holds, this is true without the assumption that {{mvar|V}} has finite dimension. This also indicates that a basis is a minimal spanning set when {{mvar|V}} is finite-dimensional.