Linear Independence, Spanning Sets, and Bases

Linear independence, spanning sets, and bases are the three interlocking concepts that capture the "size" and "coordinate structure" of a vector space. A set is linearly independent if no vector is a redundant combination of the others; it spans if every vector in the space can be built from it; a basis is a set that does both — a minimal spanning set / maximal independent set. Every vector space has a basis, and all bases have the same cardinality (the dimension). These ideas are foundational throughout linear algebra and were crystallized in the late 19th and early 20th centuries (Grassmann, Peano, Steinitz).

Given a vector space $V$ over a field $F$ , a finite set ${v_{1}, \dots, v_{n}}$ is linearly independent when the only solution of $c_{1} v_{1} + \dots + c_{n} v_{n} = 0$ is $c_{1} = \dots = c_{n} = 0$ , and it spans $V$ when every $v \in V$ is some linear combination $\sum c_{i} v_{i}$ . A basis is a linearly independent spanning set; it provides a unique coordinate representation for every vector. These three notions matter because they reduce the infinite-looking object $V$ to a finite, manageable list and let us treat abstract spaces (polynomials, matrices, functions) exactly like $R^{n}$ . A surprising fact: the dimension is an honest invariant — you can choose bases in infinitely many ways, yet they always have the same number of elements, a theorem that fails to be obvious and required real proof.

The Core Insight

A basis is the sweet spot between two failure modes. Too few vectors and you can't reach everything (you fail to span). Too many vectors and you have redundancy (you fail to be independent). A basis is exactly the threshold where you can reach every vector in exactly one way. The "exactly one way" — uniqueness of representation — is the property that makes coordinates, matrices, and the entire computational apparatus of linear algebra possible.

Formal Statement

Linear Combination

Let $V$ be a vector space over a field $F$ and $v_{1}, \dots, v_{n} \in V$ . A linear combination of these vectors is any vector of the form

w = c_{1} v_{1} + c_{2} v_{2} + \dots + c_{n} v_{n} = i = 1 \sum n c_{i} v_{i}, c_{i} \in F .

⟳This is the definition; it uses only the two vector-space operations — scalar multiplication

c_{i} v_{i}

and vector addition — applied finitely many times.

Here $v_{i} \in V$ are vectors, $c_{i} \in F$ are scalars (coefficients), and $w \in V$ is the resulting vector. The scalars $c_{i}$ are called the weights of the combination.

Linear Independence

A set ${v_{1}, \dots, v_{n}} \subseteq V$ is linearly independent if the only choice of scalars making the combination zero is the trivial one:

c_{1} v_{1} + \dots + c_{n} v_{n} = 0 ⟹ c_{1} = c_{2} = \dots = c_{n} = 0.

⟳

0

on the left is the zero vector of

V

; the implication must hold for ALL scalar tuples, so the only relation among the

v_{i}

is the trivial one.

If some nontrivial choice (not all $c_{i}$ zero) gives $0$ , the set is linearly dependent. An infinite set is independent iff every finite subset is independent.

Span

The span of a set $S = {v_{1}, \dots, v_{n}}$ is the set of all linear combinations:

span (S) = {i = 1 \sum n c_{i} v_{i} c_{i} \in F} .

⟳Take the collection of all outputs of equation [1] as the

c_{i}

range over

F

; closure under

+

and scalar multiplication makes this a subspace.

span (S)

is the smallest subspace of $V$ containing $S$ . If

span (S) = V

, we say

S

spans

V

or is a spanning (generating) set.

Basis

A basis of $V$ is a set $B \subseteq V$ that is both linearly independent and spans $V$ . Equivalently, $B$ is a basis iff every $v \in V$ has a unique representation

v = i = 1 \sum n c_{i} v_{i}, c_{i} \in F,

⟳Spanning gives existence of the

c_{i}

; independence gives uniqueness — if two representations existed, their difference would be a nontrivial relation

\sum (c_{i} - c_{i}^{'}) v_{i} = 0

The unique scalars $(c_{1}, \dots, c_{n})$ are the coordinates of $v$ relative to $B$ .

Invariance of Dimension (Cardinality of Bases)

If $V$ has a finite basis, then every basis of $V$ has the same number of elements. This common number is the dimension $dim V$ . More precisely (the Steinitz Exchange Lemma): if ${u_{1}, \dots, u_{m}}$ is linearly independent and ${w_{1}, \dots, w_{n}}$ spans $V$ , then $m \leq n$ .

Existence and Characterizations of a Basis

Let $dim V = n < \infty$ . Then:

Every linearly independent set can be extended to a basis.
Every spanning set can be reduced to a basis.
Any linearly independent set of size $n$ is automatically a basis.
Any spanning set of size $n$ is automatically a basis.
(Axiom of Choice) Every vector space — even infinite-dimensional — has a basis (a Hamel basis).

Why It Holds / Derivation

Steinitz Exchange Lemma ⟹ Invariance of Dimension

We prove that an independent set is never larger than a spanning set; invariance follows.

Setup. Let

U = {u_{1}, \dots, u_{m}}

be linearly independent and

W = {w_{1}, \dots, w_{n}}

span

V

. We show

m \leq n

by swapping the

u

's into

W

one at a time. Step 1 — Insert $u_{1}$ . Since

W

spans, write

u_{1} = a_{1} w_{1} + a_{2} w_{2} + \dots + a_{n} w_{n} .

⟳spanning guarantees existence of scalars

a_{j}

; this is equation [3] applied to

u_{1} \in V = span (W)

Some $a_{j} \neq = 0$ (else $u_{1} = 0$ , contradicting independence). Relabel so $a_{1} \neq = 0$ . Solve for $w_{1}$ :

w_{1} = a_{1}^{- 1} (u_{1} - j = 2 \sum n a_{j} w_{j}) .

⟳divide [5] by

a_{1}

and isolate

w_{1}

; legal because

a_{1} \neq = 0

in the field

F

So ${u_{1}, w_{2}, \dots, w_{n}}$ still spans $V$ (we can recover $w_{1}$ , hence everything).

Step 2 — Inductive swap. Suppose after

k

steps the set

{u_{1}, \dots, u_{k}, w_{k + 1}, \dots, w_{n}}

spans (with

k \leq n

). Express

u_{k + 1}

in it:

u_{k + 1} = i = 1 \sum k b_{i} u_{i} + j = k + 1 \sum n a_{j} w_{j} .

⟳again use spanning of the current set; existence of the coefficients is guaranteed.

If all the $a_{j}$ ( $j > k$ ) were zero, then [7] would express $u_{k + 1}$ as a combination of $u_{1}, \dots, u_{k}$ — a nontrivial relation contradicting independence of $U$ . So some $a_{j} \neq = 0$ ; in particular there must still be at least one $w$ left, forcing $k + 1 \leq n$ . Relabel so $a_{k + 1} \neq = 0$ and swap $w_{k + 1}$ out for $u_{k + 1}$ . The new set spans.

Step 3 — Conclude. The induction can run until all

m

of the

u

's are inserted, and each step required an available

w

. Therefore

m \leq n

. Invariance. If

B_{1}

and

B_{2}

are both bases, apply the lemma twice:

B_{1}

(independent) vs.

B_{2}

(spanning) gives

∣ B_{1} ∣ \leq ∣ B_{2} ∣

; reversing roles gives

∣ B_{2} ∣ \leq ∣ B_{1} ∣

. Hence

∣ B_{1} ∣ = ∣ B_{2} ∣

■

:::proof[Uniqueness of Coordinates (Equation [4])] Suppose $v = \sum c_{i} v_{i} = \sum c_{i}^{'} v_{i}$ with ${v_{i}}$ a basis. Subtracting,

i = 1 \sum n (c_{i} - c_{i}^{'}) v_{i} = 0.

⟳subtract the two representations of the same vector

v

; vector-space axioms allow regrouping by index

i

Since ${v_{i}}$ is linearly independent, equation [2] forces every coefficient $c_{i} - c_{i}^{'} = 0$ , i.e. $c_{i} = c_{i}^{'}$ . Existence of some representation comes from spanning. Hence the representation is unique. $■$

Hermann Grassmann | 1809–1877

A schoolteacher in Stettin, Grassmann developed in his Ausdehnungslehre (Theory of Extension, 1844; revised 1862) what we now recognize as the first abstract theory of vector spaces, independence, and dimension — decades ahead of his time and so cryptically written that it was almost ignored. He introduced the idea that geometric magnitudes ("extensive quantities") could be combined linearly, and he understood that a set of independent vectors determines the dimension of the space they generate. Giuseppe Peano gave the modern axiomatic definition of a vector space in 1888, explicitly citing Grassmann; Ernst Steinitz supplied the rigorous exchange argument for invariance of dimension in 1913. Grassmann never saw his work mainstreamed in his lifetime — he died believing his linguistic studies (he was also a noted Sanskrit scholar) were his lasting legacy.

Building Intuition

Think of vectors as directions you're allowed to walk in.

Spanning asks: Can I reach every point in the room using these directions? If I can only walk North–South and East–West, I span the floor but not the ceiling height.
Independence asks: Is any direction wasted? If my allowed moves are "North," "East," and "Northeast," then "Northeast" is redundant — it's already North + East. That redundancy is linear dependence.
A basis is a set of directions that is just enough: you can reach everywhere (span) with no wasted directions (independent). The number of directions you need is the dimension.

The deep payoff is uniqueness: with a basis, every destination has exactly one set of "walking instructions." That's why a basis turns an abstract space into ordinary coordinate tuples — the basis is the dictionary between $V$ and $F^{n}$ .

Three vectors in the plane: two form a basis, the third is dependent

Worked Examples

Testing Independence and Finding a Basis in ℝ³

Given. The three vectors

v_{1} = (1, 2, 3), v_{2} = (2, 4, 6), v_{3} = (1, 0, 1) \in R^{3} .

Determine whether

{v_{1}, v_{2}, v_{3}}

is independent, and extract a basis for

span

. Step 1 — Set up the dependence equation. We seek

c_{1}, c_{2}, c_{3}

with

c_{1} v_{1} + c_{2} v_{2} + c_{3} v_{3} = 0

. Step 2 — Spot the obvious relation. Note

v_{2} = 2 v_{1}

exactly. So

2 v_{1} - v_{2} + 0 \cdot v_{3} = (2, 4, 6) - (2, 4, 6) = (0, 0, 0) .

This is a nontrivial relation (

c_{1} = 2, c_{2} = - 1, c_{3} = 0

). Therefore the set is linearly dependent. Step 3 — Discard the redundant vector. Remove

v_{2}

. Check whether

{v_{1}, v_{3}}

is independent: from

c_{1} (1, 2, 3) + c_{3} (1, 0, 1) = 0

, the second coordinate gives

2 c_{1} = 0 \Rightarrow c_{1} = 0

, then the first gives

c_{3} = 0

. Independent. ✓ Step 4 — Determine the span's dimension. Since

{v_{1}, v_{3}}

is independent and spans the same set as the original three,

dim span {v_{1}, v_{2}, v_{3}} = 2

(a plane through the origin in

R^{3}

{v_{1}, v_{3}} is a basis of the span; dim = 2

Coordinates Relative to a Basis of P₂ (polynomials)

Given. In

P_{2} = {

real polynomials of degree

\leq 2}

, take the basis

B = {1, 1 + t, 1 + t + t^{2}} .

Find the coordinates of

p (t) = 3 + 2 t + 5 t^{2}

relative to

B

. Step 1 — Write the coordinate equation. We want scalars

c_{1}, c_{2}, c_{3}

such that

c_{1} (1) + c_{2} (1 + t) + c_{3} (1 + t + t^{2}) = 3 + 2 t + 5 t^{2} .

Step 2 — Collect by powers of $t$ .

t^{2} : t^{1} : t^{0} : c_{3} = 5, c_{2} + c_{3} = 2, c_{1} + c_{2} + c_{3} = 3.

Step 3 — Back-substitute.

$c_{3} = 5$ .
$c_{2} = 2 - c_{3} = 2 - 5 = - 3$ .
$c_{1} = 3 - c_{2} - c_{3} = 3 - (- 3) - 5 = 1$ .

Step 4 — Verify.

1 (1) + (- 3) (1 + t) + 5 (1 + t + t^{2}) = (1 - 3 + 5) + (- 3 + 5) t + 5 t^{2} = 3 + 2 t + 5 t^{2}

. ✓

[p]_{B} = (1, - 3, 5)

The same polynomial in the standard basis

{1, t, t^{2}}

has coordinates

(3, 2, 5)

— different basis, different coordinates, same vector.

Common Misconceptions

Pitfall 1 — "More vectors means more span." Adding vectors can never shrink the span, but once a set spans

V

, throwing in more vectors gains nothing and only destroys independence. Bigger is not better. Pitfall 2 — "The zero vector can be in a basis." Never. Any set containing

0

is automatically dependent:

1 \cdot 0 = 0

is a nontrivial relation. Pitfall 3 — "Independence is a property of individual vectors." It is a property of the whole set. A single nonzero vector is independent; a vector is never "independent" by itself relative to others without naming the set. Pitfall 4 — "Spanning sets and independent sets are the same kind of thing." They pull in opposite directions: spanning is about being big enough, independence about being small enough. A basis is where they meet. Pitfall 5 — Confusing the number of vectors with dimension. A set of

n

vectors in an

n

-dimensional space is a basis only if it is independent (equivalently spans). Three vectors in

R^{3}

might span only a plane (Example 1). Claim (false): "If a set of vectors is pairwise independent — no one is a scalar multiple of another — then the whole set is linearly independent." Counterexample. In

R^{2}

take

v_{1} = (1, 0), v_{2} = (0, 1), v_{3} = (1, 1) .

No vector is a scalar multiple of any other (pairwise "independent" in the naïve sense). Yet

v_{1} + v_{2} - v_{3} = (1, 0) + (0, 1) - (1, 1) = (0, 0),

a nontrivial relation. The set is dependent. Linear independence is a statement about all the vectors at once, not about pairs.

Connections

Linear independence, span, and bases sit at the hub of linear algebra:

Dimension of a Vector Space is defined as the common cardinality of any basis — the whole machinery above exists to make this well-defined.
Rank of a Matrix equals the dimension of the column space (a span of columns) and the row space; the column rank = row rank theorem is independence/span in disguise.
Coordinate Vectors and Change of Basis uses the uniqueness from equation [4]; switching bases is a linear isomorphism $V ≅ F^{n}$ .
Linear Transformations are completely determined by their action on a basis — define $T$ on basis vectors arbitrarily and it extends uniquely.
The Four Fundamental Subspaces (column, row, null, left-null spaces) are all spans, and their dimensions are tied by the Rank–Nullity Theorem.
Inner Product Spaces and Orthogonality refine "basis" to "orthonormal basis," via Gram–Schmidt Orthogonalization.

Real-World Applications

Computer graphics & robotics. Object pose is stored as coordinates in a chosen basis (frame); rendering and forward kinematics are change-of-basis operations. A camera "view matrix" is a basis change.
Principal Component Analysis (PCA). Data is re-expressed in an orthonormal basis of eigenvectors of the covariance matrix; keeping the top few basis directions compresses data while preserving variance.
JPEG / signal compression. The Discrete Cosine Transform expresses an image block in a basis of cosine waveforms; small coefficients are discarded — a basis chosen for sparsity.
Quantum mechanics. A quantum state is a vector in Hilbert space; measurement bases (e.g., position, momentum, spin-up/spin-down) are orthonormal bases, and "expressing a state in a basis" gives measurement amplitudes.
Error-correcting codes. A linear code is the span (row space) of a generator matrix over a finite field $F_{q}$ ; the basis (generator rows) encodes messages, and independence guarantees distinct codewords.
Numerical PDE solvers (Finite Element Method). Solutions are approximated in the span of finite-element basis functions ("hat functions"); the dimension of this basis controls accuracy.
Chemistry / reaction networks. The independent set of chemical reactions (basis of the stoichiometric subspace) determines how many reaction extents are truly free.

Historical Development

1844 — Hermann Grassmann publishes Die lineale Ausdehnungslehre, introducing extensive quantities, linear combinations, independence, and dimension — the conceptual birth of vector spaces, largely overlooked.
1862 — Grassmann issues a heavily rewritten second edition hoping for recognition; it again finds few readers.
1888 — Giuseppe Peano, in Calcolo geometrico, gives the first fully axiomatic definition of a (finite-dimensional) vector space and defines dimension and independence rigorously, crediting Grassmann.
1900s — Hilbert and Schmidt develop infinite-dimensional spaces; the notion of basis splinters into algebraic (Hamel) and topological (Schauder) versions.
1905 — Georg Hamel constructs a basis of $R$ as a $Q$ -vector space, showing infinite-dimensional bases require the Axiom of Choice.
1913 — Ernst Steinitz formalizes the Exchange Lemma, giving the first clean proof that all bases have equal cardinality (invariance of dimension).
1918 — Hermann Weyl's Raum, Zeit, Materie popularizes the abstract vector-space viewpoint in physics (relativity).
1920s–1930s — Banach, van der Waerden, and Bourbaki standardize the modern axiomatic treatment; bases, spans, and dimension take their current textbook form.
1948 — Claude Shannon's information theory and the rise of linear coding theory give independence/span a starring computational role over finite fields.

Subtleties & Limits

Infinite-dimensional subtleties. In infinite dimensions the clean picture cracks:

A Hamel (algebraic) basis of an infinite-dimensional space like $R$ over $Q$ , or $C [0, 1]$ , exists only by invoking the Axiom of Choice — it can never be explicitly written down, and such bases are necessarily uncountable for complete normed spaces (Baire category theorem). So "every vector space has a basis" is equivalent to the Axiom of Choice (Blass, 1984).
For functional analysis one instead uses a Schauder basis (allowing infinite sums via a topology), but Per Enflo (1973) constructed a separable Banach space with no Schauder basis — disproving a long-standing conjecture of Banach.
The notion of "dimension" remains invariant for Hamel bases (any two have equal cardinality), but the interplay with topology — when does an algebraic basis respect convergence? — is genuinely delicate.
Open in spirit: explicit, constructive bases for many natural infinite-dimensional spaces simply do not and cannot exist, marking a sharp boundary between the finite-dimensional theory (fully constructive) and the infinite case (entangled with set theory).