Target Audience: Anyone who has met vectors and matrices computationally and wants the structure underneath.
Prerequisites: Tier 0 — especially Proof Techniques and Sets, Relations and Functions, since linear maps are functions and almost everything here is proved by induction or contradiction.
This page has one destination. It starts with the axioms of a vector space and ends at the Rank–Nullity Theorem, which says that for a linear map the dimensions of its kernel and its image always total the dimension of the domain. Nothing is lost and nothing is gained; it is pure bookkeeping, and it is the single most used counting fact in the subject.
The pivot is Section 4. That dimension is well defined at all — that any two bases of the same space have the same size — is a genuine theorem, not a definition. The row reduction explorer in Section 10 makes the whole chain concrete: it reduces a matrix step by step, reads both bases off the result, and checks the rank–nullity identity on what it just computed.
Third unit of Tier 2, and the first of three on linear algebra — the site's largest proof category, with seventeen pages and, until now, no tutorial leading to any of them.
A vector space over a field \(F\) is a set \(V\) with an addition and a scalar multiplication satisfying eight axioms: addition is associative and commutative, has an identity \(\mathbf{0}\) and inverses; and scalar multiplication distributes over both kinds of addition, is associative with field multiplication, and has \(1\) acting as the identity.
There is no mention of length, angle, or coordinates. Those come later and separately — length and angle need an inner product, coordinates need a choice of basis. A vector space on its own supports exactly two operations, and every theorem in this page uses only those.
So “vector” means element of a vector space, not “arrow”. Polynomials, matrices, and real-valued functions are all vectors under the obvious operations, and the theorems below apply to them unchanged.
A subspace is a subset that is itself a vector space under the inherited operations. Checking all eight axioms again is unnecessary: a non-empty subset \(W \subseteq V\) is a subspace exactly when it is closed under addition and scalar multiplication.
The first is the quickest disqualifier: any set missing the origin — a line not through it, for instance — is not a subspace, and you need go no further.
The span of a list of vectors is the set of all their linear combinations \(c_1 v_1 + \cdots + c_k v_k\). It is always a subspace — the smallest one containing the list.
A list is linearly independent when the only solution of \(c_1 v_1 + \cdots + c_k v_k = \mathbf{0}\) is \(c_1 = \cdots = c_k = 0\). Otherwise it is dependent, and some vector is a combination of the others.
Read it as a statement about uniqueness: independence says the zero vector has only the obvious representation, and Section 5 shows that this is exactly what makes coordinates well defined.
Any list containing \(\mathbf{0}\) is dependent, and a list with a repeat is dependent however unrelated the other entries are. The question is never “is this vector independent?” — only whether the whole list is.
A basis is a list that is both independent and spanning. It is therefore as small as a spanning list can be, and as large as an independent list can be — the two conditions pull in opposite directions and a basis is where they meet.
Any two bases of the same vector space have the same number of elements. Only because of this can “the dimension” be spoken of at all.
It follows from the Steinitz exchange comparison: an independent list is never longer than a spanning list. Apply that twice, once in each direction, and the two bases bound each other's length.
The Invariance of Dimension proves it in full, via a lemma that a homogeneous system with more unknowns than equations always has a non-zero solution — Gaussian elimination in miniature, and the same fact the explorer demonstrates on every wide matrix.
Fix a basis \(B = (v_1, \ldots, v_n)\). Every \(v \in V\) is then \(c_1 v_1 + \cdots + c_n v_n\) for exactly one choice of scalars, and those scalars are the coordinates of \(v\) relative to \(B\).
Spanning gives at least one representation. If there were two, subtracting them would express \(\mathbf{0}\) as a non-trivial combination, contradicting independence. So the two halves of the definition of a basis deliver existence and uniqueness respectively — neither is decorative.
The consequence is that every \(n\)-dimensional space over \(F\) behaves exactly like \(F^n\) once a basis is chosen. Different bases give different coordinates for the same vector, which is why a change of basis is a genuine operation and not a relabelling.
A map \(T : V \to W\) is linear when \(T(u + v) = T(u) + T(v)\) and \(T(cv) = cT(v)\). Equivalently, it respects linear combinations — which is the only structure a vector space has, so linear maps are exactly the structure-preserving maps.
Choose any images for \(v_1, \ldots, v_n\) and there is exactly one linear map taking those values — extend by linearity. This is why a matrix suffices to describe a map, and it is the reason the next section works.
\(f(x) = mx + b\) is linear in the calculus sense but not a linear map unless \(b = 0\): linearity forces \(T(\mathbf{0}) = \mathbf{0}\). Maps of that form are affine.
Given bases for \(V\) and \(W\), a linear map becomes a matrix: its \(j\)th column is the coordinate vector of \(T(v_j)\). Then \(T(v)\) is computed as the matrix times the coordinate vector of \(v\).
Reading \(A\mathbf{x}\) this way — as a linear combination of the columns of \(A\), weighted by the entries of \(\mathbf{x}\) — makes the whole of the next section immediate, and is worth preferring to the row-by-row dot-product recipe.
Matrix multiplication is defined so that it matches composition of maps, which is why it is associative but not commutative: composing functions is associative, and doing two things in the other order is generally a different thing.
Every linear map carries two subspaces with it, and both are subspaces by a one-line check.
\(T\) is injective exactly when the null space is \(\{\mathbf{0}\}\): if \(T(u) = T(v)\) then \(T(u - v) = \mathbf{0}\), so a trivial kernel forces \(u = v\). And \(T\) is surjective exactly when the column space is all of the codomain. So the two spaces measure the two ways a map can fail to be a bijection.
For a linear map \(T : V \to W\) with \(V\) finite-dimensional:
The proof is the reason to have built bases carefully. Take a basis of the null space and extend it to a basis of \(V\); the images of the vectors you added form a basis of the column space. Counting the two pieces gives the theorem, and the work is entirely in showing those images are independent and spanning.
The Rank–Nullity Theorem, with the corollaries that follow at once: a square map is injective if and only if it is surjective, and a wide matrix always has a non-zero null space — which recovers the lemma that Invariance of Dimension was built on. The theory catches its own tail.
It converts a hard question into an easy one. To show a map is surjective it is often simplest to compute its kernel: for a square matrix, a trivial kernel gives surjectivity for free. The explorer below reports both numbers for every matrix it reduces.
The three elementary row operations — swapping two rows, scaling a row by a non-zero constant, and adding a multiple of one row to another — are all reversible, and each leaves the null space unchanged. That single invariant is what makes row reduction a legitimate way to answer questions about the original matrix.
Every matrix reduces to such a form, and — the substantial part — only one such form, reached by whatever route.
Choose a matrix. The explorer reduces it with exact fractions, listing every row operation, tints the pivot columns, then reads both bases off the result and checks rank–nullity on what it computed.
Every entry is computed live in exact rational arithmetic — nothing is tabulated in advance, and no value is rounded.
Row operations preserve the null space but change the column space. The pivot positions are what transfer: use them to select columns of the original matrix. Reading the columns straight out of the reduced form is the most common error in the whole topic.
The Uniqueness of the Reduced Row Echelon Form proves existence by induction on columns, then uniqueness by the null space invariant: the null space encodes the dependence relations among columns, those relations pin down which columns are pivots, and that in turn forces every entry.
Determinants, then eigenvalues and canonical forms — the other two thirds of the site's seventeen linear algebra proofs. Both rest on this page: a determinant is defined on square matrices and detects invertibility, which is a statement about rank; and an eigenvector is a non-zero element of the null space of \(A - \lambda I\), so finding eigenvalues means asking when that null space is non-trivial.
| Idea | Statement | Proof page |
|---|---|---|
| Subspace test | Contains \(\mathbf{0}\), closed under \(+\) and scalars | Section 2 above |
| Independence | \(\sum c_i v_i = \mathbf{0}\) only when every \(c_i = 0\) | Section 3 above |
| Invariance of dimension | Any two bases have the same size | Invariance of Dimension |
| Steinitz exchange | An independent list never outnumbers a spanning list | same page, Lemma 2 |
| Coordinates | Unique relative to a fixed basis | Section 5 above |
| Injective | Null space is \(\{\mathbf{0}\}\) | Section 8 above |
| Rank–Nullity | \(\operatorname{rank} + \operatorname{nullity} = \dim V\) | Rank–Nullity |
| Wide matrices | More unknowns than equations forces a non-zero solution | corollary |
| RREF uniqueness | One reduced form per matrix, by any route | Uniqueness of the RREF |
| Column space basis | Pivot columns of the original matrix | Explorer, Section 10 |