Basis and dimension · Linear Algebra

§17.1 developed span (reaching every vector) and independence (no redundancy) separately. A basis is a set with both properties at once — and once a space has one, a single number falls out of it that turns out not to depend on which basis was chosen: the dimension.

Definition

A basis of a vector space V is a set of vectors \{\vec v_1,\dots,\vec v_k\} that is:

Linearly independent (§17.1), and
Spans V (§17.1).

Why both conditions matter. Spanning alone can be wasteful — three vectors might span a plane, with one entirely redundant. Independence alone can fall short — two independent vectors in \mathbb{R}^3 are never redundant with each other, but they still miss most of the space. A basis is exactly large enough to reach everything and exactly small enough that nothing in it is spare.

The defining consequence: every \vec v\in V can be written as a linear combination of basis vectors in exactly one way. Existence follows from spanning; uniqueness follows from independence — if \vec v=\sum c_i\vec v_i=\sum d_i\vec v_i, then \sum(c_i-d_i)\vec v_i=\vec0, and independence forces every c_i-d_i=0. This uniqueness is what makes §17.3's coordinate vectors well-defined at all.

The standard basis of \mathbb{R}^n is \{\vec e_1,\dots,\vec e_n\} (§16.0) — independent (the identity matrix's columns, which trivially row-reduces to I) and spanning (every vector's components literally are its coefficients on this basis). It's the default, but far from the only basis: any n independent vectors in \mathbb{R}^n form one.

Dimension

Every basis of a given vector space has the same number of vectors. This is not obvious from the definition and is worth stating as the theorem it is:

Theorem. If \{\vec u_1,\dots,\vec u_m\} and \{\vec v_1,\dots,\vec v_n\} are both bases of V, then m=n.

(Sketch: if m>n, express each \vec u_i in terms of the \vec v_j's and substitute into a dependence test on the \vec u_i's — the resulting system has more unknowns than equations, so §17.1's "more vectors than the ambient dimension are always dependent" forces the \vec u_i to be dependent, contradicting that they form a basis. Swap the roles for m<n.)

Because the count is basis-independent, it's a genuine property of V itself — the dimension, \dim V. \dim\mathbb{R}^n=n (via the standard basis, matching the intuitive meaning of n). \dim P_n=n+1 (basis \{1,x,x^2,\dots,x^n\} — one more than the degree, easy to miscount). \dim M_{m\times n}=mn (basis: the matrices with a single 1 and zeros elsewhere). \dim\{\vec0\}=0 (the empty set is, slightly awkwardly, a valid basis of the zero space — vacuously independent and vacuously spanning).

Building and trimming a basis

Two practical facts, both following directly from §17.1's pivot test:

A spanning set that's too big can be trimmed to a basis: drop any vector that's a combination of the others (a non-pivot column) and repeat; what's left is independent and still spans.
An independent set that's too small can be extended to a basis: if it doesn't yet span V, some vector of V isn't reachable — throw it in, the set stays independent (else that new vector would already have been reachable), and repeat until it spans.

Both processes terminate, because at each step the set's size moves toward \dim V and can't overshoot it (§17.1's "too many vectors are automatically dependent" caps growth) or undershoot it while still spanning.

Doing it in Python

import sympy as sp

# Trim a spanning set down to a basis by keeping only pivot columns
v1 = sp.Matrix([1, 2, 1])
v2 = sp.Matrix([2, 4, 2])   # = 2*v1, redundant
v3 = sp.Matrix([0, 1, 1])
v4 = sp.Matrix([1, 3, 2])   # = v1 + v3, redundant

A = sp.Matrix.hstack(v1, v2, v3, v4)
rref, pivots = A.rref()
print("pivot columns:", pivots)
basis = [A.col(i) for i in pivots]
print("basis has", len(basis), "vectors, so dim(span) =", len(basis))
for b in basis:
    print(list(b))

pivot columns: (0, 2)
basis has 2 vectors, so dim(span) = 2
[1, 2, 1]
[0, 1, 1]

Confirming that every vector in the space has a unique representation on a basis:

import sympy as sp

# Basis of R^2: not the standard one
b1 = sp.Matrix([1, 1])
b2 = sp.Matrix([1, -1])
v = sp.Matrix([5, 1])

B = sp.Matrix.hstack(b1, b2)
coeffs = B.solve(v)
print("coordinates of v on {b1, b2}:", list(coeffs))
print("check: c1*b1 + c2*b2 =", list(coeffs[0]*b1 + coeffs[1]*b2))

coordinates of v on {b1, b2}: [3, 2]
check: c1*b1 + c2*b2 = [5, 1]

Worked example

Find a basis for, and the dimension of, W=\operatorname{span}\{(1,2,-1),(2,4,-2),(0,1,1),(1,0,-3)\}.

Row-reduce (as columns) A=\begin{pmatrix}1&2&0&1\\2&4&1&0\\-1&-2&1&-3\end{pmatrix}. R_2\leftarrow R_2-2R_1, R_3\leftarrow R_3+R_1:

$\begin{pmatrix}1&2&0&1\\0&0&1&-2\\0&0&1&-2\end{pmatrix}$

R_3\leftarrow R_3-R_2:

$\begin{pmatrix}1&2&0&1\\0&0&1&-2\\0&0&0&0\end{pmatrix}$

Pivots in columns 1 and 3.

$\boxed{\text{basis}=\{(1,2,-1),\,(0,1,1)\},\quad\dim W=2}$

Sanity check. Column 2 is exactly 2\timescolumn 1 (2(1,2,-1)=(2,4,-2) ✓, confirming it correctly dropped as redundant), and column 4 should equal c_1(1,2,-1)+c_2(0,1,1) for the coefficients read off column 4's RREF entries, (1,-2): 1(1,2,-1)+(-2)(0,1,1)=(1,2-2,-1-2)=(1,0,-3) ✓ — matches the original fourth vector exactly, confirming it truly was redundant rather than accidentally discarded.

Your turn

1. Is \{(1,0,0),(0,1,0),(0,0,1),(1,1,1)\} a basis of \mathbb{R}^3? Why or why not?

2. What is \dim P_3 (polynomials of degree \le3)? Name a basis.

3. True or false: every spanning set of \mathbb{R}^n with exactly n vectors is automatically a basis.

Solutions

1. No. It has 4 vectors in \mathbb{R}^3, and \dim\mathbb{R}^3=3 — by the theorem above, a basis of \mathbb{R}^3 has exactly 3 vectors, so any set of 4 (or more) is automatically dependent (§17.1), disqualifying it regardless of whether it spans.

2. \dim P_3=4, basis \{1,x,x^2,x^3\} — one basis vector per power from 0 to 3 inclusive, four powers total, which is the easy place to be off by one.

3. True. This is a genuinely useful shortcut: for a set of exactly \dim V vectors, spanning and independence become equivalent — a spanning set that's the right size can't have room for redundancy (if one vector were dependent on the others, the remaining n-1 would still have to span all of V, contradicting that \dim V=n requires at least n independent vectors to do so). So checking either property alone suffices once the count already matches the dimension.

Check yourself in code

Find a basis for W=\operatorname{span}\{(1,1,2),(2,2,4),(1,0,1),(0,1,1)\} and report \dim W.

Print exactly this:

pivot columns: (0, 2)
dim W = 2

import sympy as sp

v1 = sp.Matrix([1, 1, 2])
v2 = sp.Matrix([2, 2, 4])
v3 = sp.Matrix([1, 0, 1])
v4 = sp.Matrix([0, 1, 1])

A = sp.Matrix.hstack(v1, v2, v3, v4)
rref, pivots = A.rref()
print("pivot columns:", pivots)
# print "dim W = " followed by the number of pivot columns

import sympy as sp

v1 = sp.Matrix([1, 1, 2])
v2 = sp.Matrix([2, 2, 4])
v3 = sp.Matrix([1, 0, 1])
v4 = sp.Matrix([0, 1, 1])

A = sp.Matrix.hstack(v1, v2, v3, v4)
rref, pivots = A.rref()
print("pivot columns:", pivots)
print("dim W =", len(pivots))

A basis is an independent spanning set, giving every vector in the space a unique representation as a linear combination of it. Every basis of a given space has the same size — the space's dimension — and a spanning set can always be trimmed, or an independent set extended, to reach a basis by keeping exactly the pivot vectors.

Next: making the unique representation from this lesson concrete — coordinate vectors, and how they change when the basis does.

9. Basis and dimension