Source: Friedberg, Insel & Spence, Linear Algebra 4th Ed., Ch. 1.6–1.7
Tags: basis, dimension, finite-dimensional, infinite-dimensional, replacement theorem, standard basis, Lagrange interpolation, Lagrange polynomials, maximal linearly independent subset, Friedberg chapter 1
Difficulty: Intermediate to Advanced Prerequisites: All preceding sections (1.1–1.5). Solid grasp of linear independence and span.
This is the capstone section of Chapter 1 and arguably the most important. Everything you have studied so far, including vector space axioms, subspaces, span, and linear independence, converges into one concept: the basis. A basis is a linearly independent spanning set, and it provides a coordinate system for the vector space. The replacement theorem proves that every basis for a given finite-dimensional space has the same number of vectors, which defines the dimension. This single number governs what is possible in the space: how large independent sets can be, how small spanning sets can be, and how subspaces relate to the parent space. The Lagrange interpolation formula is an elegant application of these ideas to polynomial spaces.
A basis is a linearly independent set that spans the vector space. Every finite-dimensional vector space has a basis, and all bases have the same number of vectors, called the dimension. The replacement theorem is the engine behind these results. Lagrange interpolation uses a clever basis for Pₙ(F) to construct the unique polynomial of degree ≤ n passing through n + 1 given points.
Basis
A linearly independent subset β of a vector space V that generates V. Equivalently, β is a basis if every vector in V can be uniquely expressed as a linear combination of vectors in β.
In simple terms, a basis is a minimal spanning set with no redundancy, and it gives every vector a unique "address."
Standard basis for Fⁿ
The set {e₁, e₂, ..., eₙ}, where eⱼ has a 1 in position j and 0 elsewhere.
Standard basis for Pₙ(F)
The set {1, x, x², ..., xⁿ}.
Finite-dimensional
A vector space that has a basis consisting of a finite number of vectors.
Dimension (dim(V))
The number of vectors in any basis for a finite-dimensional vector space V. This is well-defined because all bases have the same size (Corollary 1 of the replacement theorem).
Infinite-dimensional
A vector space that is not finite-dimensional. Equivalently, it contains an infinite linearly independent subset.
Replacement theorem (Theorem 1.10)
If V is generated by a set G of n vectors, and L is a linearly independent set of m vectors in V, then m ≤ n, and there exists a subset H of G with n − m vectors such that L ∪ H generates V.
In simple terms, you can "swap in" independent vectors for generating vectors without losing coverage, and you can never have more independent vectors than generators.
Lagrange polynomials
Given distinct scalars c₀, c₁, ..., cₙ in an infinite field F, the Lagrange polynomial fᵢ(x) is defined by:
fᵢ(x) = ∏(k≠i) (x − cₖ)/(cᵢ − cₖ)
It satisfies fᵢ(cⱼ) = 1 if i = j, and fᵢ(cⱼ) = 0 if i ≠ j.
Lagrange interpolation formula
For any polynomial g ∈ Pₙ(F): g = Σᵢ g(cᵢ)fᵢ, where fᵢ are the Lagrange polynomials. This gives the unique polynomial of degree ≤ n taking prescribed values at c₀, ..., cₙ.
Maximal linearly independent subset
A linearly independent subset B of a set S such that no linearly independent subset of S properly contains B. A maximal linearly independent subset of V is the same thing as a basis for V.
A basis β for V satisfies two properties simultaneously:
β is linearly independent (no redundancy)
span(β) = V (full coverage)
These two conditions together imply a powerful uniqueness property.
β = {u₁,...,uₙ} is a basis for V if and only if every v ∈ V can be uniquely expressed as:
v = a₁u₁ + a₂u₂ + ... + aₙuₙ
for unique scalars a₁,...,aₙ.
Proof idea: Spanning gives existence of a representation. Independence gives uniqueness (if two representations existed, subtracting gives a nontrivial combination equalling zero, contradicting independence).
Vector Space | Standard Basis | Dimension |
|---|---|---|
{0} | ∅ | 0 |
Fⁿ | {e₁, ..., eₙ} | n |
M_{m×n}(F) | {Eⁱʲ : 1 ≤ i ≤ m, 1 ≤ j ≤ n} | mn |
Pₙ(F) | {1, x, x², ..., xⁿ} | n + 1 |
P(F) | {1, x, x², ...} | infinite |
Note: the dimension of Pₙ(F) is n + 1, not n. This is a common exam trap.
If V is generated by a finite set S, then some subset of S is a basis for V. Procedure:
Pick any nonzero vector u₁ from S.
Check if the next vector in S is linearly independent from the ones chosen so far.
If yes, include it. If no (it is in the span of the current selection), skip it.
Repeat until you have processed all vectors in S.
The surviving vectors form a basis.
This is the most powerful result in Chapter 1.
Statement: If G generates V and |G| = n, and L is linearly independent with |L| = m, then m ≤ n and there exists H ⊆ G with |H| = n − m such that L ∪ H generates V.
Key corollaries:
Corollary 1 (All bases have the same size): If V has a finite basis, every basis for V has the same number of vectors. This makes "dimension" well-defined.
Corollary 2 (Three powerful tests): Let dim(V) = n. Then:
(a) Any generating set for V has ≥ n vectors. A generating set with exactly n vectors is a basis.
(b) Any linearly independent subset of V has ≤ n vectors. An independent set with exactly n vectors is a basis.
(c) Every linearly independent subset of V can be extended to a basis by adding vectors from any given basis.
The practical upshot: in an n-dimensional space, if you have n vectors, you only need to check one of the two basis conditions. If they are independent, they automatically span. If they span, they are automatically independent.
If W is a subspace of a finite-dimensional space V, then:
W is finite-dimensional
dim(W) ≤ dim(V)
If dim(W) = dim(V), then W = V
Corollary: Any basis for a subspace W of V can be extended to a basis for V.
dim(R²) = 2, so subspaces have dimensions 0, 1, or 2: the origin, lines through the origin, or all of R².
dim(R³) = 3, so subspaces have dimensions 0, 1, 2, or 3: the origin, lines through the origin, planes through the origin, or all of R³.
The set of symmetric n × n matrices has dimension n(n+1)/2.
The set of diagonal n × n matrices has dimension n.
The set of n × n matrices with trace zero has dimension n² − 1.
The set of upper triangular n × n matrices has dimension n(n+1)/2.
If W₁ and W₂ are finite-dimensional subspaces of V:
dim(W₁ + W₂) = dim(W₁) + dim(W₂) − dim(W₁ ∩ W₂)
V = W₁ ⊕ W₂ if and only if dim(V) = dim(W₁) + dim(W₂) and W₁ + W₂ = V.
Given n + 1 distinct scalars c₀, c₁, ..., cₙ in an infinite field F, define:
fᵢ(x) = ∏(k=0, k≠i)ⁿ (x − cₖ)/(cᵢ − cₖ)
Each fᵢ is a polynomial of degree n satisfying:
fᵢ(cⱼ) = 1 if i = j, and 0 if i ≠ j
Key results:
{f₀, f₁, ..., fₙ} is linearly independent in Pₙ(F). (Proof: if Σ aᵢfᵢ = 0, evaluate at cⱼ to get aⱼ = 0.)
Since Pₙ(F) has dimension n + 1, this set is a basis (by Corollary 2(b)).
Every g ∈ Pₙ(F) satisfies: g = Σᵢ g(cᵢ)fᵢ
This is the unique polynomial of degree ≤ n passing through the points (c₀, g(c₀)), ..., (cₙ, g(cₙ)).
Worked example: Find the polynomial of degree ≤ 2 through (1, 8), (2, 5), (3, −4).
f₀(x) = (x−2)(x−3)/((1−2)(1−3)) = ½(x² − 5x + 6)
f₁(x) = (x−1)(x−3)/((2−1)(2−3)) = −(x² − 4x + 3)
f₂(x) = (x−1)(x−2)/((3−1)(3−2)) = ½(x² − 3x + 2)
g(x) = 8f₀(x) + 5f₁(x) + (−4)f₂(x) = −3x² + 6x + 5
For infinite-dimensional spaces, mathematical induction no longer suffices, and the maximal principle (equivalent to the Axiom of Choice) is needed.
A maximal linearly independent subset of V is a basis for V (Theorem 1.12).
Every linearly independent subset can be extended to a maximal one (Theorem 1.13).
Corollary: every vector space has a basis, even infinite-dimensional ones.
Lagrange polynomial:
fᵢ(x) = ∏(k=0, k≠i)ⁿ (x − cₖ) / (cᵢ − cₖ)
Lagrange interpolation:
g(x) = Σᵢ₌₀ⁿ g(cᵢ) · fᵢ(x)
Dimension of symmetric matrices:
dim = n(n + 1)/2
Dimension formula for sums:
dim(W₁ + W₂) = dim(W₁) + dim(W₂) − dim(W₁ ∩ W₂)
Lagrange interpolation is used in numerical analysis to approximate functions from sampled data points, in cryptography (Shamir's secret sharing scheme splits a secret into shares using polynomial interpolation), and in computer graphics for curve fitting. The concept of dimension governs the degrees of freedom in engineering systems: a structure with n independent parameters lives in an n-dimensional space.
The dimension of Pₙ(F) is n + 1, not n. The basis {1, x, ..., xⁿ} has n + 1 elements. This is one of the most frequent errors on exams.
The dimension of M_{m×n}(F) is mn, not m + n. You need mn independent entries.
Students sometimes think that "any n vectors in an n-dimensional space form a basis." This is wrong. You still need either independence or spanning; but by Corollary 2, you only need to check one of them.
A basis is not unique. Many different bases exist for the same space. What is unique is the number of vectors (the dimension).
The zero vector space {0} has dimension 0 and its basis is the empty set ∅, not {0}. The set {0} is linearly dependent.
⚠️ Know the dimensions of the standard spaces: dim(Fⁿ) = n, dim(M_{m×n}(F)) = mn, dim(Pₙ(F)) = n + 1. These are tested constantly.
⚠️ The "n vectors in an n-dimensional space" shortcut (Corollary 2) saves significant work. If you have n vectors and you show they are independent, you can immediately conclude they form a basis without separately checking spanning.
⚠️ Be able to reduce a spanning set to a basis and extend an independent set to a basis. Both procedures are standard exam questions.
⚠️ The replacement theorem itself is sometimes tested as a proof question. Understand the induction argument and how vectors are "swapped."
⚠️ Lagrange interpolation: be able to construct the Lagrange polynomials for given nodes and compute the interpolating polynomial. Also know that f ∈ Pₙ(F) with n + 1 zeros must be the zero polynomial.
⚠️ The dimension formula for subspace sums (dim(W₁ + W₂) = dim(W₁) + dim(W₂) − dim(W₁ ∩ W₂)) appears in exam problems about finding dimensions of intersections.
True or false: the zero vector space has no basis.
True or false: the dimension of Pₙ(F) is n.
True or false: if a vector space has a finite basis, the number of vectors in every basis is the same.
Fill in the blank: the dimension of M_{m×n}(F) is ______.
True or false: if V has dimension n and S is a subset of V with n vectors, then S is linearly independent if and only if S spans V.
Answers: 1. False (its basis is ∅). 2. False (it is n + 1). 3. True. 4. mn. 5. True (Corollary 2).
Q: Determine whether {(1, 0, −1), (2, 5, 1), (0, −4, 3)} is a basis for R³.
A: Since dim(R³) = 3 and we have 3 vectors, it suffices to check independence. Solve a(1,0,−1) + b(2,5,1) + c(0,−4,3) = (0,0,0). The system: a + 2b = 0, 5b − 4c = 0, −a + b + 3c = 0. From the first, a = −2b. Substituting into the third: 3b + 3c = 0, so c = −b. From the second: 5b − 4(−b) = 9b = 0, so b = 0, hence a = c = 0. Linearly independent. By Corollary 2(b), it is a basis.
Q: Use Lagrange interpolation to find the polynomial of degree ≤ 1 through (−1, 5) and (1, 3).
A: f₀(x) = (x − 1)/(−1 − 1) = −(x − 1)/2. f₁(x) = (x + 1)/(1 + 1) = (x + 1)/2. g(x) = 5·f₀(x) + 3·f₁(x) = 5·(−(x−1)/2) + 3·((x+1)/2) = (−5x + 5 + 3x + 3)/2 = (−2x + 8)/2 = −x + 4.
Q: Let W = {(a₁,a₂,a₃,a₄,a₅) ∈ F⁵ : a₁ + a₃ + a₅ = 0, a₂ = a₄}. Find a basis and the dimension.
A: From a₁ = −a₃ − a₅ and a₂ = a₄, vectors have the form (−a₃ − a₅, a₂, a₃, a₂, a₅). Setting free variables: a₃ = 1, a₂ = a₅ = 0 gives (−1,0,1,0,0). a₅ = 1, a₂ = a₃ = 0 gives (−1,0,0,0,1). a₂ = 1, a₃ = a₅ = 0 gives (0,1,0,1,0). These three vectors are linearly independent and span W. Basis: {(−1,0,1,0,0), (−1,0,0,0,1), (0,1,0,1,0)}. dim(W) = 3.
Q: Prove that if dim(W) = dim(V) for a subspace W of a finite-dimensional V, then W = V.
A: A basis for W is a linearly independent subset of V with dim(V) vectors. By Corollary 2(b) of the replacement theorem, this set is also a basis for V. Hence span equals V, so W = V.
Q: The set of symmetric 2 × 2 matrices has what dimension? Give a basis.
A: Dimension is 2(3)/2 = 3. A basis is { [[1,0],[0,0]], [[0,0],[0,1]], [[0,1],[1,0]] }.
Bases and dimension are the foundation for coordinate vectors and linear transformations in Chapter 2. The matrix representation of a linear transformation depends on choosing bases for the domain and codomain. The rank-nullity theorem (Chapter 2) relates the dimensions of the null space and range. In Chapter 5, eigenspaces are subspaces whose dimensions (geometric multiplicities) govern diagonalisability. The Lagrange interpolation formula reappears in numerical methods and approximation theory.
basis, dimension, finite-dimensional, infinite-dimensional, standard basis, replacement theorem, Steinitz exchange lemma, Lagrange interpolation, Lagrange polynomials, interpolating polynomial, maximal linearly independent subset, maximal principle, Axiom of Choice, reducing spanning set, extending independent set, dim Pn is n+1, Friedberg chapter 1 section 6