Source: Abstract Linear Algebra, UIUC
Tags: linear independence, basis, dimension, basis extension, replacement theorem, spanning set, vector space, subspace, generating set, linear combination, linear algebra
Difficulty: Intermediate to Advanced Prerequisites: Matrix rank and inverse (Part 1 notes), determinants (Part 2 notes), comfort with solving systems of linear equations.
Once you know how to row-reduce matrices and compute determinants, the next layer is understanding the structure of vector spaces themselves. Linear independence, bases, and dimension are the vocabulary for describing "how big" a vector space is and what constitutes a minimal, non-redundant description of it. The Replacement Theorem is the engine behind many of the dimension-counting arguments in the course, so it is worth understanding the logic, not just the statement. If you are behind on rank (Part 1), catch up there first: rank is just "the dimension of the row space," so the two topics are the same idea viewed from different angles.
A set of vectors is linearly independent when none of them is a combination of the others. A basis is a linearly independent set that spans the whole space. The Replacement Theorem guarantees that any independent set can be extended to a basis, and that all bases of a given space have the same size (the dimension).
Linearly independent set
A set of vectors {v₁, v₂, …, vₖ} where the only solution to c₁v₁ + c₂v₂ + … + cₖvₖ = 0 is c₁ = c₂ = … = cₖ = 0. In simple terms, no vector in the set is redundant; you cannot build any one of them from the others.
Linearly dependent set
A set that is not linearly independent: at least one vector can be written as a linear combination of the rest. Think of it as having "spare" vectors that add no new information.
Spanning set (generating set)
A set S such that every vector in the space V can be written as a linear combination of vectors in S. In simple terms, S has "enough" vectors to reach every point in V.
Basis
A set that is both linearly independent and spanning. It is the smallest possible spanning set, or equivalently the largest possible independent set, for that space.
Dimension
The number of vectors in any basis of V. All bases of the same space have the same size, which is why dimension is well-defined. In simple terms, it is the number of "free directions" in the space.
The Replacement Theorem (Steinitz Exchange Lemma)
Let G be a finite generating set for V with |G| = n, and let L be a linearly independent subset of V with |L| = m. Then m ≤ n, and there exists a subset H of G with |H| = n – m such that L ∪ H still generates V. In simple terms, you can swap independent vectors into a spanning set one at a time without losing coverage, and an independent set can never be larger than a spanning set.
Set up the equation c₁v₁ + c₂v₂ + … + cₖvₖ = 0 and form the matrix whose columns are the vectors.
Row-reduce. If every column is a pivot column, the set is independent. If any column is free, the set is dependent.
Equivalently, k vectors in ℝⁿ are independent if and only if the matrix they form has rank k.
Start with a linearly independent set L inside a vector space V.
If L does not yet span V, there exists a vector in V that is not a linear combination of L. Add it to L.
Repeat until the set spans V. The result is a basis.
In practice, you formalise this by working with a known spanning set (such as the standard basis) and using the Replacement Theorem to swap vectors in systematically.
Place the vectors of L as columns of a matrix, followed by columns of a known spanning set (e.g. the standard basis vectors e₁, e₂, …, eₙ).
Row-reduce the combined matrix.
The pivot columns indicate which vectors to keep. The original independent vectors will always appear as pivots; the additional vectors you need come from the spanning set columns that also land on pivots.
Setup: V is generated by a set G of n vectors. L is an independent set of m vectors in V.
Conclusion 1: m ≤ n. An independent set cannot be larger than a generating set.
Conclusion 2: You can remove m vectors from G and replace them with the m vectors from L, and the resulting set still generates V.
Why it matters for dimension: Because it forces every basis to have the same number of elements. If you had two bases of different sizes, you could use the theorem to derive a contradiction.
Base case (m = 0): L is empty, so L ∪ G = G still generates V. Nothing to show.
Inductive step: Assume the result holds for m – 1 independent vectors. The m-th vector in L can be written as a combination of the current generating set. Because it is independent of the first m – 1, at least one vector in G must appear with a nonzero coefficient. Swap that vector out for the m-th vector from L. The new set still generates V, and m ≤ n is maintained.
Independence test: form the matrix A = [v₁ | v₂ | … | vₖ] and row-reduce. If rank(A) = k, the set is independent.
Dimension of ℝⁿ: dim(ℝⁿ) = n.
Rank–nullity theorem (related): For an m × n matrix A, rank(A) + nullity(A) = n.
Basis and dimension are the foundation of data compression and signal processing. When you reduce a high-dimensional dataset to its principal components (PCA), you are finding a small basis that captures most of the variance. In control engineering, the dimension of the controllable subspace tells you how many independent inputs you can steer.
Students often confuse "spanning" with "independent." A spanning set can be very large and full of redundancy. A basis is the sweet spot: spanning and independent simultaneously.
A common error is assuming that any n vectors in ℝⁿ form a basis. They do only if they are independent (or equivalently, only if the matrix they form has rank n).
Some students think dimension depends on which basis you choose. It does not; all bases of the same space have the same number of vectors.
Forgetting the direction of the inequality in the Replacement Theorem: it says m ≤ n (independent set size ≤ generating set size), not the other way round.
⚠️ "Show that these vectors are linearly independent" or "extend to a basis" are very common exam problems. Row reduction is your main tool for both.
⚠️ Expect a proof or short-answer question on the Replacement Theorem. You do not always need the full proof by induction, but you should be able to state the theorem precisely and explain the m ≤ n consequence.
⚠️ The statement "all bases of a finite-dimensional vector space have the same number of elements" is a direct consequence of the Replacement Theorem and is frequently tested as a true/false question.
⚠️ Know the difference between spanning, independent, and basis. Exam questions love asking you to identify which of these properties a given set has.
True or false: A set of 4 vectors in ℝ³ can be linearly independent.
Fill in the blank: A basis for a vector space is a set that is both ______ and ______.
True or false: The dimension of a vector space depends on which basis you choose.
Fill in the blank: The Replacement Theorem guarantees that any linearly independent set has size ≤ the size of any ______ set.
True or false: To test independence, you row-reduce and check whether every column is a pivot column.
Answers: 1. False (at most 3 independent vectors in ℝ³). 2. Linearly independent; spanning. 3. False (dimension is the same for all bases). 4. Generating (spanning). 5. True.
Q: How do you test whether a set of vectors {v₁, v₂, v₃} in ℝ⁴ is linearly independent?
A: Form the 4 × 3 matrix with these vectors as columns and row-reduce. If the matrix has rank 3 (three pivot columns), the set is independent. If the rank is less than 3, it is dependent.
Q: You have two linearly independent vectors in ℝ⁴. Describe how to extend them to a basis for ℝ⁴.
A: Place the two vectors as the first two columns of a matrix, then append the four standard basis vectors e₁, e₂, e₃, e₄ as additional columns. Row-reduce. Select the columns corresponding to pivot positions. The two original vectors will be among them; the remaining pivot columns from the standard basis vectors complete the extension to a basis of four vectors.
Q: State the Replacement Theorem in one sentence.
A: If G is a generating set of size n for a vector space V and L is a linearly independent subset of V of size m, then m ≤ n and there exists a subset H of G of size n – m such that L ∪ H generates V.
Q: Why does the Replacement Theorem imply that all bases have the same number of elements?
A: Suppose B₁ and B₂ are both bases, with sizes n₁ and n₂. Applying the theorem with B₁ as the generating set and B₂ as the independent set gives n₂ ≤ n₁. Reversing the roles gives n₁ ≤ n₂. Together, n₁ = n₂.
Linear independence and basis connect backward to rank (the rank of a matrix is the dimension of its column space) and forward to eigenspaces, where you will need to find bases for each eigenspace. The Replacement Theorem underpins the rank–nullity theorem, which is one of the most-used results in the rest of the course. Dimension arguments also appear in differential equations when counting the number of independent solutions.
linear independence, linearly dependent, basis, dimension, spanning set, generating set, replacement theorem, Steinitz exchange lemma, basis extension, vector space, subspace, column space, row space, null space, rank–nullity theorem, pivot columns, free variables, standard basis, PCA, principal components