Span, independence, bases and dimension

Lesson 1 showed that vector spaces come in many forms. This lesson gives them a size. In \(\mathbb{R}^3\) everyone agrees that a plane is two-dimensional and a line one-dimensional, but what is the dimension of \(P_2\), or of the trace-zero \(2 \times 2\) matrices, or of the solutions of \(y'' + y = 0\)? The answer comes from three linked ideas you met for column vectors in MATH-125, now stated for any vector space: span, linear independence and basis. The highlight is a theorem that looks obvious and is not: every basis of a space has the same number of vectors. That number is the dimension.

Linear combinations and span

A linear combination of vectors \(\mathbf{v}_1, \dots, \mathbf{v}_k\) in a vector space \(V\) is any vector of the form \(c_1\mathbf{v}_1 + \dots + c_k\mathbf{v}_k\) with scalars \(c_i\). The span of the vectors, written \(\operatorname{span}\{\mathbf{v}_1, \dots, \mathbf{v}_k\}\), is the set of all their linear combinations.

Theorem. The span of any finite list of vectors in \(V\) is a subspace of \(V\), and it is the smallest subspace containing all of them. Proof: the zero vector is the combination with all coefficients zero. A sum of two combinations is a combination (add coefficients), and a multiple of a combination is a combination (multiply coefficients), so the span passes the subspace test. Any subspace containing the \(\mathbf{v}_i\) must contain all their combinations by closure, so it contains the span.

If \(\operatorname{span}\{\mathbf{v}_1, \dots, \mathbf{v}_k\} = V\) we say the vectors span \(V\), or form a spanning set. In \(P_2\), the polynomials \(1, t, t^2\) span, because every \(a + bt + ct^2\) is a combination of them. So do \(1, 1 + t, 1 + t + t^2\): you can check that \(t = (1 + t) - 1\) and \(t^2 = (1 + t + t^2) - (1 + t)\), so every combination of \(1, t, t^2\) is also a combination of the new list.

Deciding whether a vector lies in a span is a question about a linear system. To ask whether \(p(t) = 4 + t - 2t^2\) is in \(\operatorname{span}\{1 + t, t + t^2, 1 + t^2\}\), write \(a(1 + t) + b(t + t^2) + c(1 + t^2) = 4 + t - 2t^2\) and compare coefficients of \(1\), \(t\) and \(t^2\). That gives three equations in \(a, b, c\), which row reduction answers. This translation, from a question about abstract vectors to a question about columns of numbers, is the main working tool of the course, and lesson 4 makes it systematic with coordinates.

Linear independence

Vectors \(\mathbf{v}_1, \dots, \mathbf{v}_k\) are linearly independent if the only way to write the zero vector as their combination is the trivial one:

Otherwise they are linearly dependent, and some non-trivial combination equals zero. Dependence means redundancy: if \(c_j \ne 0\) in a dependence relation, you can solve for \(\mathbf{v}_j\) as a combination of the others, so removing \(\mathbf{v}_j\) does not shrink the span.

Independence in function spaces needs care, because the equation must hold for every value of the variable. The functions \(1, \cos^2 t, \sin^2 t\) are dependent, since \(1 - \cos^2 t - \sin^2 t = 0\) for all \(t\). The functions \(e^t\) and \(e^{2t}\) are independent: if \(a e^t + b e^{2t} = 0\) for all \(t\), put \(t = 0\) to get \(a + b = 0\) and differentiate and put \(t = 0\) to get \(a + 2b = 0\), which force \(a = b = 0\). This differentiate-and-evaluate trick leads to a test using the Wronskian determinant, which you will see in a differential equations course.

Two facts are used constantly. A list containing the zero vector is dependent, since \(1 \cdot \mathbf{0} = \mathbf{0}\) is non-trivial. And a list is dependent exactly when one of its vectors is a combination of the earlier ones. The second fact, sometimes called the linear dependence lemma, is the engine of the main theorem below.

Linear dependence lemma. If \(\mathbf{v}_1, \dots, \mathbf{v}_k\) are dependent and \(\mathbf{v}_1 \ne \mathbf{0}\), then some \(\mathbf{v}_j\) with \(j \ge 2\) is a combination of \(\mathbf{v}_1, \dots, \mathbf{v}_{j-1}\), and removing it leaves the span unchanged. Proof: take a non-trivial relation \(c_1\mathbf{v}_1 + \dots + c_k\mathbf{v}_k = \mathbf{0}\) and let \(j\) be the largest index with \(c_j \ne 0\). If \(j = 1\), then \(c_1\mathbf{v}_1 = \mathbf{0}\) with \(c_1 \ne 0\), forcing \(\mathbf{v}_1 = \mathbf{0}\), which we excluded. So \(j \ge 2\), and dividing by \(c_j\) expresses \(\mathbf{v}_j\) in terms of the earlier vectors. Any combination that used \(\mathbf{v}_j\) can be rewritten without it, so the span is unchanged.

Bases

A basis of \(V\) is a list of vectors that is linearly independent and spans \(V\). The two conditions pull in opposite directions: spanning needs enough vectors, independence forbids too many. A basis has exactly the right number.

The key property of a basis is unique representation. Theorem: \(\mathbf{v}_1, \dots, \mathbf{v}_n\) is a basis of \(V\) if and only if every vector in \(V\) can be written as \(c_1\mathbf{v}_1 + \dots + c_n\mathbf{v}_n\) in exactly one way. Proof: spanning gives at least one way. If there were two, subtracting them gives a combination equal to zero with coefficients \(c_i - d_i\); independence forces every difference to be zero, so the two ways agree. Conversely, uniqueness of the representation of \(\mathbf{0}\) is exactly independence.

The replacement theorem and dimension

Everything now rests on one inequality. Steinitz replacement theorem: if \(\mathbf{u}_1, \dots, \mathbf{u}_m\) are linearly independent in \(V\) and \(\mathbf{w}_1, \dots, \mathbf{w}_n\) span \(V\), then \(m \le n\). In words, an independent list is never longer than a spanning list.

Proof. We swap the \(\mathbf{u}\) vectors into the spanning list one at a time, each time throwing out a \(\mathbf{w}\). Start with the spanning list \(\mathbf{w}_1, \dots, \mathbf{w}_n\). Put \(\mathbf{u}_1\) at the front: the list \(\mathbf{u}_1, \mathbf{w}_1, \dots, \mathbf{w}_n\) still spans, and it is dependent because \(\mathbf{u}_1\) is already a combination of the \(\mathbf{w}\)s. By the dependence lemma some vector after \(\mathbf{u}_1\) is a combination of the earlier ones; it cannot be a \(\mathbf{u}\) (there is only one so far), so it is some \(\mathbf{w}\), and removing it leaves a spanning list of length \(n\) again. Now put \(\mathbf{u}_2\) at the front and repeat. At step \(j\) the list \(\mathbf{u}_j, \mathbf{u}_{j-1}, \dots, \mathbf{u}_1\), followed by the remaining \(\mathbf{w}\)s, is dependent and spans; the lemma removes a vector that is a combination of earlier ones, and it cannot be one of the \(\mathbf{u}\)s, because they are independent. So a \(\mathbf{w}\) is removed each time. If \(m > n\), after \(n\) steps all the \(\mathbf{w}\)s would be gone, leaving \(\mathbf{u}_n, \dots, \mathbf{u}_1\) spanning \(V\); then \(\mathbf{u}_{n+1}\) would be a combination of them, contradicting independence. Hence \(m \le n\).

Corollary: invariance of dimension. Any two bases of a finite-dimensional vector space have the same length. Proof: if \(B\) and \(B'\) are bases of lengths \(n\) and \(n'\), then \(B\) is independent and \(B'\) spans, so \(n \le n'\); swapping roles gives \(n' \le n\).

The common length is the dimension of \(V\), written \(\dim V\). We set \(\dim\{\mathbf{0}\} = 0\). A space is finite-dimensional if it has a finite spanning list, and infinite-dimensional otherwise. \(P\), \(C[0, 1]\) and the space of sequences are infinite-dimensional: for every \(n\) they contain the independent list \(1, t, \dots, t^n\) (or its analog), so no finite list can span them.

Consequences of dimension

Once we know \(\dim V = n\), several useful facts follow quickly from the replacement theorem.

• Any independent list in \(V\) has at most \(n\) vectors, and any spanning list has at least \(n\).

• Any independent list of exactly \(n\) vectors is a basis, and so is any spanning list of exactly \(n\) vectors. You only need to check one of the two conditions.

• Every independent list can be extended to a basis, by adding vectors not in its span one at a time. Every spanning list can be pruned to a basis, by removing vectors that are combinations of earlier ones.

• If \(W\) is a subspace of \(V\), then \(\dim W \le \dim V\), with equality only when \(W = V\).

The last fact settles the claim from lesson 1 about \(\mathbb{R}^3\). A subspace has dimension 0, 1, 2 or 3. Dimension 0 is \(\{\mathbf{0}\}\); dimension 1 is spanned by one non-zero vector, a line through the origin; dimension 2 is a plane through the origin; dimension 3 is the whole space.

Another useful formula concerns two subspaces. For finite-dimensional subspaces \(U\) and \(W\) of \(V\):

The proof extends a basis of \(U \cap W\) to bases of \(U\) and of \(W\) and shows that the combined list is a basis of \(U + W\). In \(\mathbb{R}^3\), two different planes through the origin meet in a line: \(3 = 2 + 2 - 1\). A direct sum is the case \(\dim(U \cap W) = 0\), where dimensions simply add.

Finding a basis in practice

For a subspace of \(\mathbb{R}^n\) given as the span of some vectors, place the vectors as the columns of a matrix and row reduce. The pivot columns of the original matrix form a basis of the span, and the number of pivots is its dimension. This works because row operations do not change the dependence relations among columns. For other spaces, first translate to coordinates: write each polynomial as the column of its coefficients, each matrix as a column of its entries, and so on.

The code below does this exactly, with fractions rather than decimals, so that no rounding can hide a dependence. It finds a basis for the span of four polynomials in \(P_3\).

from fractions import Fraction as F

def rref(rows):
    """Row reduce a list of rows exactly; return (reduced rows, pivot columns)."""
    A = [[F(x) for x in r] for r in rows]
    m, n = len(A), len(A[0])
    pivots, r = [], 0
    for c in range(n):
        p = next((i for i in range(r, m) if A[i][c] != 0), None)
        if p is None:
            continue
        A[r], A[p] = A[p], A[r]
        A[r] = [x / A[r][c] for x in A[r]]
        for i in range(m):
            if i != r and A[i][c] != 0:
                A[i] = [a - A[i][c] * b for a, b in zip(A[i], A[r])]
        pivots.append(c)
        r += 1
    return A, pivots

# polynomials in P3 as coefficient columns (1, t, t^2, t^3)
polys = {
    "p1 = 1 + t":           [1, 1, 0, 0],
    "p2 = t + t^2":         [0, 1, 1, 0],
    "p3 = 1 + 2t + t^2":    [1, 2, 1, 0],
    "p4 = t^3 - 1":         [-1, 0, 0, 1],
}
names = list(polys)
cols = list(polys.values())
matrix = [[cols[j][i] for j in range(len(cols))] for i in range(4)]
R, piv = rref(matrix)
print("pivot columns:", [names[j].split(" =")[0] for j in piv])
print("dimension of the span:", len(piv))
# express the non-pivot column in terms of the pivot columns
for j in range(len(cols)):
    if j not in piv:
        coeffs = {names[piv[k]].split(" =")[0]: R[k][j] for k in range(len(piv))}
        print(names[j].split(" =")[0], "=", " + ".join(f"{v}*{k}" for k, v in coeffs.items() if v != 0))

pivot columns: ['p1', 'p2', 'p4']
dimension of the span: 3
p3 = 1*p1 + 1*p2

The pivot columns are \(p_1, p_2, p_4\), so the span is three-dimensional, a proper subspace of the four-dimensional \(P_3\). The reduced form also reveals the dependence \(p_3 = p_1 + p_2\), which you can confirm by adding the polynomials.

Coordinates

If \(\mathcal{B} = (\mathbf{b}_1, \dots, \mathbf{b}_n)\) is a basis of \(V\), unique representation means each vector \(\mathbf{v}\) determines a unique list of coefficients. The coordinate vector of \(\mathbf{v}\) relative to \(\mathcal{B}\) is

Order matters: a basis here is an ordered list. The coordinate map \(\mathbf{v} \mapsto [\mathbf{v}]_{\mathcal{B}}\) turns every vector of an \(n\)-dimensional space into a column in \(\mathbb{R}^n\), and it respects the operations: \([\mathbf{u} + \mathbf{v}]_{\mathcal{B}} = [\mathbf{u}]_{\mathcal{B}} + [\mathbf{v}]_{\mathcal{B}}\) and \([c\mathbf{v}]_{\mathcal{B}} = c[\mathbf{v}]_{\mathcal{B}}\). Lesson 3 will call such a map an isomorphism. Its practical meaning is enormous: every finite-dimensional vector space behaves exactly like \(\mathbb{R}^n\) once a basis is chosen, so all the matrix methods of MATH-125 apply.

Why dimension is the right measure of size

Dimension counts degrees of freedom. The trace-zero \(2 \times 2\) matrices form a subspace of the four-dimensional \(M_{2 \times 2}\) cut out by one linear equation, so you expect dimension 3, and indeed \(E_{12}, E_{21}, E_{11} - E_{22}\) is a basis. The solutions of a second-order linear homogeneous differential equation form a two-dimensional space, which is why you need two initial conditions to pin down a solution. A plane in \(\mathbb{R}^3\) through the origin has two degrees of freedom, so any two non-parallel vectors in it form a basis. Lesson 3 turns this counting into the rank–nullity theorem, which says exactly how many degrees of freedom a linear map destroys.