We will present an alternate proof of the important result given in Proposition 6.6.2 of Smith. The basis for this alternate approach is the understanding we have begun to develop of the process of solving systems of linear equations via elimination of variables. To begin, here is a slightly more precise statement of a general process that can be applied to put the system in "triangular" form with leading terms containing successively larger-numbered variables as you "go down" the system:

To put a general system of m equations in n unknowns

into triangular form:

1. Start with the variable x₁. If there is an equation containing x₁ with a non-zero coefficient (if necessary) interchange equations to put that one first. Otherwise proceed to step 2 below.
   • Subtract multiples of the first equation from all the others in order to cancel the x₁ terms in all equations except the first.
   • After this step, do not change the equation containing x₁ as leading term again.
2. Continue with the variable x₂. If there is an equation containing x₂ with a non-zero coefficient, then (if necessary) interchange equations to put that one immediately after the equation containing x₁ as leading term (if there is one). Otherwise continue with x₃.
   • Subtract multiples of this equation from all the others below it in order to cancel any other x₂ terms.
   • After this step, do not change the equation containing x₂ as leading term again.
3. Continue in the same way with x₃, x₄, etc. until there are no more remaining equations that can be changed.

Note: If an entire equation cancels out, that's OK. It just reduces the actual "effective number" of equations in your system.

Key Observation

If you apply this process to a system of equations with m < n -- that is, a system with more variables than equations, and all the right-hand sides b_i are zero, then at the end of the process, you will have a triangular form system in which some variables do not appear in any leading term. This means that those variables can be assigned values arbitrarily, and the triangular form equations can be used to solve for the other variables that do appear in leading terms. Since the non-leading variables can be given non-zero values:

Proposition 1.

Proposition 2.

Proof. (By contradiction.) Suppose F is a linearly independent subset of L(E) containing at least k + 1 vectors B₁,...,B_k+1. Since each B_j is in the linear span of E, we can write

(1)

for some c_ji in R. Consider a linear combination of the B_j adding up to the zero vector:

Subsitituting for the B_j from (1) and collecting terms, we get:

This equation will be true if the coefficients of the A_i are all zero:

But this is a system of k linear equations in k+1 unknowns (the d_j). Hence, by Proposition 1, there is a solution in which not all the d_j are zero. But this contradicts the hypothesis that F was linearly independent. //

From Proposition 1, we deduce our main result:

Theorem (Invariance of Dimension).

Proof. Applying Proposition 2 to E and the finite spanning set, we see that E is finite. Similarly, F is finite. Say |E| = m and |F| = n. By Proposition 2 again, Since E spans V and F is linearly independent, we have |F| = n <= |E| = m. But by the same reasoning, since F spans V and E is linearly independent, we have |E| = m <= |F| = n. Hence m = n.//

Neat proof, no?