Linear Independence, Bases and Dimension

Objective. This page discharges the promise made at the end of Vector Spaces, Linear Subspaces, Span and Direct Sums, which says in as many words that it does not develop linear independence, bases or dimension. Here they are developed, over an arbitrary field and for an arbitrary vector space: what it means for a list or a set of vectors to be linearly independent, what a basis is, that any two finite bases of a space have the same number of elements, and what that number — the dimension — controls. Three definitions, six lemmas, six theorems and five corollaries make up the page, thirteen of them marked as landmarks in the flowchart above.

Two notions of independence, defined together because the page needs both. Linear independence: a finite list $v:n\to V$ is independent when ${\sum }_{i<n}{\lambda }_i{v}_i=0_V$ forces every ${\lambda }_i=0_F$, and a subset $S\subseteq V$ is independent when every injective finite list into $S$ is independent calls a finite list $v:n\to V$ independent when ${\sum }_{i<n}{\lambda }_i{v}_i=0_V$ forces every ${\lambda }_i=0_F$, and calls a subset $S\subseteq V$ independent when every injective finite list into $S$ is. The injectivity clause is load bearing and the definition says why: a linear combination as fixed by Linear combination of a finite list, and the span $\mathrm{span}(S)$ as the smallest linear subspace containing $S$ is indexed by an arbitrary list, which may repeat, and $1_{F}w+(-1_F)w=0_V$ would make every nonempty set dependent if repetitions were allowed. Lists carry order, and an ordered list is what a coordinate system is; subsets carry no order, and it is subsets that the Zorn argument runs over. That the two notions agree — a list is independent exactly when it is injective with independent image — is claim 6 of Finite sums re-indexed along an injection, with a zero term deleted, and concatenated; and the closure properties of linear independence: an independent list is injective and never $0_V$, its sublists are independent, a list is independent exactly when it is injective with linearly independent image, and every subset of a linearly independent set is linearly independent, which also collects the three facts about finite sums the page uses throughout: re-indexing a sum along an injection, deleting an index carrying $0_V$, and concatenating two lists. The boundary cases are treated as cases: the empty list and $\mathrm{\varnothing }$ are independent, and $\{0_V\}$ is dependent.

Dependence without lists, and the one-vector step. A subset $S\subseteq V$ is linearly dependent if and only if some $s\in S$ lies in $\mathrm{span}(S\setminus \{s\})$; and $\mathrm{span}(S)$ is already the set of linear combinations of INJECTIVE finite lists into $S$ removes the existential over lists from the statement: $S$ is dependent exactly when some $s\in S$ lies in $\mathrm{span}(S\setminus \{s\})$. Its second claim is used constantly below and is not available from $\mathrm{span}(S)$ is exactly the set of linear combinations of finite lists of elements of $S$, and $\mathrm{span}(\mathrm{\varnothing })=\{0_V\}$ alone: the span of $S$ is already the set of combinations of injective lists into $S$, so a vector of the span always comes with a list in which the coefficient of a chosen entry is meaningful. If $S\subseteq V$ is linearly independent and $w\mathrm{\notin }\mathrm{span}(S)$ then $S\cup \{w\}$ is linearly independent and $\mathrm{span}(S)⊊\mathrm{span}(S\cup \{w\})$; and if $w\in \mathrm{span}(S)$ then $\mathrm{span}(S\cup \{w\})=\mathrm{span}(S)$ is the engine of every existence argument on the page: adjoining a vector outside the span preserves independence and strictly enlarges the span, while adjoining one inside the span changes nothing. $S\subseteq V$ is linearly independent if and only if every finite subset of $S$ is; consequently the union of a nonempty chain of linearly independent subsets of $V$, ordered by inclusion, is linearly independent supplies the other half of what Zorn needs: independence is decided by finite subsets, so the union of a nonempty chain of independent sets is independent.

Bases, coordinates and the three characterisations. Basis of a vector space: a linearly independent spanning subset; and ordered basis: an injective finite list whose image is a basis defines a basis as an independent spanning subset and an ordered basis as an injective finite list whose image is a basis; it records the naming decision, that the unqualified word basis is already in use in this library for a basis of a topology, exactly as Linear subspace of a vector space reserved subspace for the topological notion. It also proves once, for the whole page, that independence and spans of subsets of a linear subspace agree with those computed in the ambient space, so "basis of $U$" is unambiguous. A finite list $v:n\to V$ is an ordered basis if and only if every $x\in V$ equals ${\sum }_{i<n}{\lambda }_i{v}_i$ for exactly one $\lambda :n\to F$; those scalars are the coordinates of $x$ in that ordered basis is the reason ordered bases are worth having: a list is an ordered basis exactly when every vector has exactly one coordinate list in it. The coordinates belong to the ordered basis and not to the underlying set, which the companion page shows by computing one vector's coordinates in three ordered bases of ${\mathbb{R}}^2$, two of which have the same image. For $B\subseteq V$ the following are equivalent: $B$ is a basis; $B$ is a maximal linearly independent subset of $V$; $B$ is a minimal spanning subset of $V$ — maximality and minimality being in the inclusion order gives the order-theoretic reading: a basis is a maximal independent subset and equally a minimal spanning subset, maximality and minimality taken in the inclusion order.

Counting, and what it is that is counted. The Steinitz exchange lemma: if $L\subseteq V$ is linearly independent and $S\subseteq V$ spans $V$ with $S$ finite of size $n$, then $L$ is finite with $\mathrm{\mid }L\mathrm{\mid }=m\le n$, and there is $T\subseteq S$ of size $n-m$ such that $L\cup T$ spans $V$ is the one hard computation of the page: an independent set cannot outnumber a finite spanning set, and vectors of the former can be exchanged one at a time for vectors of the latter without losing the spanning property. Its immediate consequence If $V$ has a spanning set with $n$ elements, then every linearly independent subset of $V$ is finite with at most $n$ elements; in particular $V$ has no linearly independent subset equinumerous with $\mathbb{N}$ is the form later items use, including the clause that a space with a finite spanning set has no independent subset equinumerous with $\mathbb{N}$. Applying that corollary in both directions gives If $V$ has a basis with $n$ elements and a basis with $m$ elements then $n=m$; and if $V$ has one finite basis then every basis of $V$ is finite, which is the well-definedness obligation for Finite-dimensional vector space, and its dimension ${\dim }_{F}V$; infinite-dimensional means having no finite basis and is listed among its prerequisites rather than left implicit. Sizes are compared through equinumerosity (Equinumerous sets, $A\approx B$ and $A⪯B$) and through claim 3 of The pigeonhole principle on $\mathbb{N}$; no cardinal number is used anywhere on this page.

What is deliberately not claimed about infinite bases. This page does not assert that any two infinite bases of a space are equinumerous. The Steinitz argument gives invariance only when one basis is finite, and the standard proof of the infinite case is cardinal arithmetic, which is not available at this point in the reading order. Accordingly Finite-dimensional vector space, and its dimension ${\dim }_{F}V$; infinite-dimensional means having no finite basis defines ${\dim }_{F}V$ only for a space with a finite basis, defines infinite-dimensional as the bare negation, and attaches no symbol such as $\mathrm{\infty }$ to such a space. The subscript on ${\dim }_F$ is not ornamental either: by A field is a vector space over itself, and over any subfield $K\subseteq F$ every $F$-vector space is a $K$-vector space by restricting the scalars the same set carries a vector space structure over any subfield, with different bases and a different dimension, so "the dimension of $V$" is incomplete language in exactly the way "the vector space $V$" is.

Existence of bases, and what it costs. Zorn's lemma gives a basis between any linearly independent set and any spanning set containing it: if $L\subseteq S\subseteq V$ with $L$ independent and $\mathrm{span}(S)=V$, there is a basis $B$ of $V$ with $L\subseteq B\subseteq S$ is the page's single Zorn argument, stated once in the form that yields both classical statements: between any independent $L$ and any spanning $S\supseteq L$ there is a basis. The poset is the independent sets between $L$ and $S$ under inclusion, and the empty chain is handled separately, its upper bound being $L$ — Zorn's lemma as proved in this library quantifies over every chain, and the union of the empty chain is $\mathrm{\varnothing }$, which need not contain $L$. The two corollaries follow by specialising: Every spanning subset of a vector space contains a basis at $L=\mathrm{\varnothing }$, and Every vector space has a basis at $L=\mathrm{\varnothing }$, $S=V$. The Axiom of Choice is declared, not hidden: it is used exactly once, inside Zorn's lemma. The converse — that the existence of bases implies the Axiom of Choice — is a theorem of Blass from 1984 which this library does not prove and does not use; it is recorded in that corollary's remarks, with its reference, because it fixes the exact strength of the statement.

The concrete side, and what finite dimension controls. The standard list $e:n\to F^n$ with $e_i(i)=1_F$ and $e_i(j)=0_F$ for $j\mathrm{\ne }i$ is an ordered basis of $F^n$; hence ${\dim }_F{F}^n=n$, and $F^0$ is the zero space with basis $\mathrm{\varnothing }$ and dimension $0$ writes down the standard basis of $F^n$ and computes ${\dim }_F{F}^n=n$, with no choice principle anywhere; it also proves, for the whole library, that a finite sum in a function space is computed pointwise. If ${\dim }_{F}V=n$ and $U$ is a linear subspace of $V$, then $U$ is finite-dimensional, ${\dim }_{F}U\le n$, and ${\dim }_{F}U=n$ if and only if $U=V$ then shows that a linear subspace of an $n$-dimensional space is finite-dimensional of dimension at most $n$, with equality only when the subspace is everything — and it too uses no choice, obtaining a basis of the subspace as an independent subset of greatest size via The well-ordering principle. Its third claim is the finite-dimensional extension statement, that a linearly independent subset of a finite-dimensional space is contained in a basis of it, again with no choice principle; that is what the dimension formula below runs on. Every linear subspace $U$ of a vector space $V$ has a complement: a linear subspace $W$ with $V=U\oplus W$ returns to Zorn and produces a complement for an arbitrary linear subspace of an arbitrary vector space, with no finiteness assumed. The dimension formula: for finite-dimensional linear subspaces $U$ and $W$ of $V$, the subspaces $U+W$ and $U\cap W$ are finite-dimensional and ${\dim }_F(U+W)+{\dim }_F(U\cap W)={\dim }_{F}U+{\dim }_{F}W$ is the page's second main computation, ${\dim }_F(U+W)+{\dim }_F(U\cap W)={\dim }_{F}U+{\dim }_{F}W$ for finite-dimensional subspaces of an arbitrary ambient space, and If $V={⨁}_{i<n}{U}_i$ with every $U_i$ finite-dimensional, then $V$ is finite-dimensional and ${\dim }_{F}V={\sum }_{i<n}{\dim }_F{U}_i$; in particular ${\dim }_F(U\oplus W)={\dim }_{F}U+{\dim }_{F}W$ iterates it along a finite direct sum, using condition (D2) of Internal direct sum $V={⨁}_{i<n}{U}_i$: the sum is everything and each summand meets the sum of the others only in $0_V$ rather than pairwise trivial intersections, which would not suffice. Neither of those two costs a choice principle: the dimension formula extends a basis of $U\cap W$ to bases of $U$ and of $W$ through claim 3 of If ${\dim }_{F}V=n$ and $U$ is a linear subspace of $V$, then $U$ is finite-dimensional, ${\dim }_{F}U\le n$, and ${\dim }_{F}U=n$ if and only if $U=V$, the finite-dimensional extension statement, which is proved from the size bound of If $V$ has a spanning set with $n$ elements, then every linearly independent subset of $V$ is finite with at most $n$ elements; in particular $V$ has no linearly independent subset equinumerous with $\mathbb{N}$, the least-element principle The well-ordering principle and If $S\subseteq V$ is linearly independent and $w\mathrm{\notin }\mathrm{span}(S)$ then $S\cup \{w\}$ is linearly independent and $\mathrm{span}(S)⊊\mathrm{span}(S\cup \{w\})$; and if $w\in \mathrm{span}(S)$ then $\mathrm{span}(S\cup \{w\})=\mathrm{span}(S)$, none of which costs a choice principle. So the whole finite-dimensional theory on this page is choice-free, and the Axiom of Choice appears only where an arbitrary vector space does: in Zorn's lemma gives a basis between any linearly independent set and any spanning set containing it: if $L\subseteq S\subseteq V$ with $L$ independent and $\mathrm{span}(S)=V$, there is a basis $B$ of $V$ with $L\subseteq B\subseteq S$, its two corollaries and Every linear subspace $U$ of a vector space $V$ has a complement: a linear subspace $W$ with $V=U\oplus W$.

What this page does not develop. There are no linear maps here, and therefore no rank, no matrix of a linear map, no change-of-basis matrix and no statement that $F^m$ and $F^n$ are isomorphic only when $m=n$; isomorphism needs a linear map, which is the subject of a later page, and what that page will need from this one is ${\dim }_F{F}^n=n$. There are no quotient spaces, no external direct sums and no infinite direct sums. Dimension is finite dimension throughout. The companion page carries the witnesses for the places where this page had to be careful: that an infinite independent set need not span, that a spanning set need not be independent, that a proper subspace can carry a basis equinumerous with a basis of the whole space, and that the dimension formula has no inclusion-exclusion analogue for three subspaces.