Editing Linear span (section)

=== 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.