Linear Algebra Theorem Map and Dependency Chart

Q: Is there a single theorem that everything else depends on?

Uniqueness of the reduced row-echelon form comes closest. It is what makes the pivot count, the pivot column set and therefore the rank well-defined properties of a matrix rather than artefacts of a particular elimination order. Almost every structural theorem in the first four layers begins by fixing the reduced form of a matrix, and each of those silently invokes uniqueness.

Q: Why does the abstraction to general vector spaces earn its keep?

Because two theorems become provable that resist direct attack on entries. That row rank equals column rank is nearly opaque as a statement about arrays, and falls out of dimension counting. That a set of the right size need only be independent or spanning to be a basis halves the work in every later basis verification. Both results reach back through dimension to a single counting theorem about spanning sets.

Q: Can eigenvalue theory be developed without determinants?

Yes. The existence proof used here shows that some polynomial in $A$ annihilates a chosen non-zero vector, factors it over $\mathbb{C}$, and extracts an eigenvalue — no determinant appears. The determinant enters afterwards as a computational device, turning eigenvalue-finding into root-finding for the characteristic polynomial. On the chart this is an alternative edge set reaching the same vertex.

Q: Where exactly does the complex field become necessary?

At the existence of eigenvalues, and nowhere below it. Row reduction, rank, the four subspaces, dimension, bases, rank-nullity and the entire theory of linear transformations are valid over any field. Algebraic closure is what guarantees that the characteristic polynomial has a root, and it is the only place where the fundamental theorem of algebra is imported from outside the subject.

Q: Why does the same rank-nullity statement appear twice?

Once for matrices, as rank plus nullity equals the number of columns, and once for transformations, as rank plus nullity equals the dimension of the domain. They are not coincidentally similar: the kernel of a transformation is isomorphic to the null space of any matrix representation, and the range is isomorphic to its column space, so choosing bases converts either statement into the other.

Q: How deep is the graph in practice?

Shallow relative to its size. Expanding the dependencies of a typical upper-layer theorem reaches definitions in four or five steps, because a small number of hub results — uniqueness of the reduced form, solutions as linear combinations, the counting theorem behind dimension, rank plus nullity and the fundamental theorem of matrix representation — absorb most of the paths.

Q: Does the chart change if invertibility is taken as the definition of nonsingular?

The vertex set is unchanged and the edges are rerouted. Taking a two-sided inverse as primitive makes the trivial null space a theorem instead of a definition, and moves several proofs earlier or later. What no reordering can change is which results genuinely need which hypotheses — squareness, finite dimension and algebraic closure remain exactly where they are.

Overview

A first pass through linear algebra can feel like an unordered inventory of results: row reduction, span, independence, bases, dimension, rank, determinants, eigenvalues, transformations. The subject is in fact tightly ordered. Each theorem is proved from a short list of earlier theorems, so the whole body of results forms a directed acyclic graph in which the edges are proof dependencies. Understanding that graph is what separates a reader who can recall a statement from an engineer who can decide, on sight, which result settles the question in front of them.

The graph has a single narrow base. Everything downstream begins with three reversible row operations, the fact that they do not disturb a solution set, and the existence and uniqueness of the reduced row-echelon form they produce. From that root emerges one integer — $r$ , the number of non-zero rows of the reduced form — and that integer propagates through the entire subject. It counts the pivot columns, it fixes the number of free variables at $n - r$ , it becomes the rank of the matrix, it gives the dimension of the column space and the row space, it decides whether a square matrix is invertible, and it reappears as the rank of a linear transformation. Most of the theorems in the middle of the subject are statements about what $r$ controls.

Above that core the graph branches. One branch abstracts from column vectors to arbitrary vector spaces and produces span, independence, bases and dimension, culminating in a counting theorem that makes set size alone decide two of the three defining properties of a basis. A second branch attaches four subspaces to every matrix and relates their dimensions. A third introduces the determinant as a single scalar certificate and then the eigenvalues as the numbers that describe how a square matrix acts on its own invariant directions. A fourth replaces matrices with linear transformations between abstract spaces, and then closes the loop by proving that every finite-dimensional transformation is a matrix once bases are chosen.

The practical value of holding this structure in mind is economy. Questions have a natural depth. Whether a truss is statically indeterminate, whether a sensor set determines a state, whether a set of predictors is redundant — these are all layer-two questions answered by $r$ alone, at cubic cost and with no eigenvalue computation. Whether a system is stable, whether a matrix can be diagonalised, whether two matrices represent the same operator — these live several layers higher and genuinely need the spectral machinery. Reaching for the wrong layer is the most common source of unnecessary work and of numerically fragile code.

Definition

Reduced Row-Echelon Form

RREF

The canonical representative of a matrix under row equivalence. A matrix is in reduced row-echelon form when every zero row lies below every non-zero row, the leftmost non-zero entry of each non-zero row equals $1$ , each such leading one lies strictly to the right of the leading one above it, and each leading one is the only non-zero entry in its column. Every matrix is row-equivalent to exactly one matrix in this form.

This is the root of the dependency graph. Existence is proved by an algorithm; uniqueness is proved separately and is what licenses the definite article in phrases such as the rank of a matrix.

Rank of a Matrix

ROM

The dimension of the column space of $A$ , written $\operatorname{rank}(A)$ or $r(A)$ . Operationally it equals $r$ , the number of non-zero rows of the reduced row-echelon form of $A$ , equivalently the number of pivot columns. The companion quantity is the nullity $\operatorname{nullity}(A)$ , the dimension of the null space, which equals $n - r$ .

Rank is the single quantity with the highest degree in the dependency graph: results in every layer above the second either compute it, constrain it or consume it.

Multiple Equivalences

A theorem whose statement is a list of assertions declared mutually equivalent — any two may be joined by if and only if. A list of $k$ statements therefore packages $\binom{k}{2}$ separate theorems. Such a theorem is normally proved as a cycle of implications $P_1 \Rightarrow P_2 \Rightarrow \cdots \Rightarrow P_k \Rightarrow P_1$ , which costs $k$ proofs rather than $k(k-1)$ .

The equivalences for nonsingular matrices are the largest such theorem in the subject and act as a vertical spine through the dependency chart, gaining a new statement in almost every layer.

Theorem Dependency Graph

The directed graph whose vertices are the definitions and theorems of the subject and whose edges run from a result to every later result whose proof invokes it. Because no proof may use a result that depends on it, the graph is acyclic and admits a topological ordering — which is precisely a valid order in which the subject can be developed. Layers in this page are levels of that ordering, and a hub is a vertex of unusually high out-degree.

The graph is not unique: an alternative development can reorder results, prove eigenvalues without determinants, or take invertibility rather than a trivial null space as the primitive notion. What is invariant is which results genuinely require which hypotheses.

Concepts

Layer 0 — row operations and the canonical form

The base of the chart contains four results and nothing else depends on anything outside them. They establish that row manipulation is safe and that it has a well-defined destination.

Equation Operations Preserve Solution Sets (EOPSS) — establishes that swapping two equations, multiplying an equation by a non-zero scalar and adding a multiple of one equation to another leave the solution set untouched. Rests on: the definition of a solution set alone. This is the only genuinely primitive theorem in the subject.
Row-Equivalent Matrices represent Equivalent Systems (REMES) — establishes that the same three operations applied to the rows of an augmented matrix preserve the solution set. Rests on: EOPSS plus the correspondence between a system and its augmented matrix.
Row-Equivalent Matrix in Echelon Form (REMEF) — establishes existence: every matrix is row-equivalent to a matrix in reduced row-echelon form. Rests on: the row-reducing algorithm, which is a constructive proof.
Reduced Row-Echelon Form is Unique (RREFU) — establishes uniqueness: if two matrices in reduced row-echelon form are both row-equivalent to $A$ , they are equal. Rests on: an induction on pivot positions and the correspondence between rows and linear combinations. It depends on nothing above it, which is why it can be quoted freely everywhere else.

Together these two halves make reduced row-echelon form a canonical form. Existence gives an algorithm; uniqueness makes the algorithm's output a function of the input rather than of the route taken. Every quantity read from a reduced form — the pivot set, the rank, a null space basis — is well defined only because of RREFU, and every later theorem that says “let $B$ be the reduced row-echelon form of $A$ ” silently cites it.

Layer 1 — the pivot count $r$ governs every linear system

One integer emerges from the base layer and organises the next. Write $r$ for the number of non-zero rows of the reduced form of an augmented matrix with $n$ variables. Every question about a single linear system is answered by $r$ , $n$ and one bit indicating whether the final column holds a pivot.

Recognising Consistency of a Linear System (RCLS) — establishes that a system is inconsistent exactly when the reduced augmented matrix has a leading one in column $n+1$ . Rests on: REMES and RREFU. This is the decision procedure the whole first chapter is built to deliver.
Consistent Systems, $r$ and $n$ (CSRN) — establishes that a consistent system has exactly $n - r$ free variables, so the solution set is a single point when $r = n$ and infinite otherwise. Rests on: RCLS.
Possible Solution Sets for Linear Systems (PSSLS) — establishes the trichotomy: no solution, exactly one, or infinitely many. Rests on: CSRN. There is no fourth possibility, and no linear system has, say, exactly seven solutions.
Consistent, More Variables than Equations (CMVEI) — establishes that a consistent system with $n > m$ has infinitely many solutions. Rests on: CSRN and the inequality $r \le m$ . Notably it needs no computation at all, only the shape of the system.
Homogeneous Systems are Consistent (HSC) and Homogeneous, More Variables than Equations (HMVEI) — establish that $A\vec{x} = \vec{0}$ always has the zero solution, and has others whenever $n > m$ . Rests on: CMVEI. This pair is the engine behind every later independence argument.

The step that makes this layer permanent is the reinterpretation of $r$ as an intrinsic quantity. Computing Rank and Nullity (CRN) establishes $r(A) = r$ and $n(A) = n - r$ , converting a count of rows in an algorithm's output into a pair of dimensions. From that point on, results can be stated about rank without any reference to row reduction, and row reduction survives only as the means of computing it.

Layer 2 — span, independence, bases and dimension

The second branch abstracts away from systems. A set of vectors, rather than a matrix, becomes the object of study, and three properties of a set — spanning, independence, and being a basis — are related to one another and eventually to a single integer.

Solutions to Linear Systems are Linear Combinations (SLSLC) — establishes that $A\vec{x} = \vec{b}$ is solvable exactly when $\vec{b}$ is a linear combination of the columns of $A$ . Rests on: the definition of the matrix-vector product. This single theorem is the bridge between the system layer and the vector layer, and almost every result above it uses it at least once.
Vector Form of Solutions to Linear Systems (VFSLS) and Particular Solution Plus Homogeneous Solutions (PSPHS) — establish that a solution set is a single particular solution translated by the null space. Rests on: SLSLC and CSRN.
Linearly Independent Vectors and Homogeneous Systems (LIVHS) — establishes that a set of column vectors is independent exactly when the homogeneous system with those columns has only the trivial solution. Rests on: SLSLC. Independence becomes a computation.
More Vectors than Size implies Linear Dependence (MVSLD) — establishes that any set of more than $m$ vectors in $\mathbb{C}^m$ is dependent. Rests on: LIVHS and HMVEI. This is the first purely numerical constraint on a set of vectors.
Basis for Null Spaces (BNS) and Basis of a Span (BS) — establish that row reduction produces an independent spanning set, not merely a spanning set. Rests on: SSNS, DLDS and the pivot structure of the reduced form.
Spanning Sets and Linear Dependence (SSLD) — establishes that if $t$ vectors span a space then any $t+1$ or more vectors in it are dependent. Rests on: MVSLD lifted to an abstract space. Almost every dimension result traces back here.
Bases have Identical Sizes (BIS) — establishes that two bases of the same space have the same number of vectors, which is what makes dimension definable at all. Rests on: SSLD applied twice, once in each direction.

The layer terminates in a counting theorem of unusual leverage. The Goldilocks theorem (G) states that in a space of dimension $t$ , a set of $m > t$ vectors is dependent, a set of $m < t$ vectors cannot span, and a set of exactly $t$ vectors is a basis as soon as either independence or spanning is verified. It rests on SSLD, BIS and the extension theorem ELIS. Its practical payoff is large: verifying independence is one homogeneous system, whereas verifying spanning directly would require solving a system for an arbitrary target vector.

Layer 3 — the four subspaces, rank and rank-nullity

The third layer attaches four subspaces to every $m \times n$ matrix and computes their dimensions. It is where the abstract vocabulary of layer two is reconnected to the concrete arithmetic of layer one.

Column Spaces and Consistent Systems (CSCS) — establishes $\vec{b} \in \mathcal{C}(A)$ if and only if $A\vec{x} = \vec{b}$ is consistent. Rests on: SLSLC. The column space is exactly the set of achievable right-hand sides.
Basis of the Column Space (BCS) — establishes that the columns of $A$ in the pivot positions of its reduced form are a basis for $\mathcal{C}(A)$ . Rests on: BS. Note the subtlety: the original columns form the basis, not the reduced ones.
Row-Equivalent Matrices have equal Row Spaces (REMRS) and Basis for the Row Space (BRS) — establish that the non-zero rows of the reduced form are a basis for the row space. Rests on: the fact that each row operation replaces a row by a linear combination of rows.
Column Space, Row Space, Transpose (CSRST) — establishes $\mathcal{C}(A) = \mathcal{R}(A^{t})$ , so the two spaces are the same object viewed twice. Rests on: the involution property of the transpose.
Properties of Extended Echelon Form (PEEF) and Four Subsets (FS) — establish that reducing $[\, A \mid I_m \,]$ yields two submatrices from which all four subspaces can be read: the null space and row space from one, the column space and left null space from the other. Rests on: BNS, BRS and the record of the transforming matrix.
Rank Plus Nullity is Columns (RPNC) — establishes $r(A) + n(A) = n$ . Rests on: CRN alone, since $r + (n - r) = n$ . The proof is trivial; the content sits entirely in CRN, which is in turn licensed by RREFU.
Rank of a Matrix is the Rank of the Transpose (RMRT) — establishes $r(A) = r(A^{t})$ , that is, row rank equals column rank. Rests on: the Goldilocks theorem and BRS. This is the least obvious result in the layer and the one that most clearly repays the abstraction of layer two: no direct manipulation of entries proves it easily.

The layer also supplies the tool used constantly to prove two subspaces equal without exhibiting a bijection: Equal Dimensions Yields Equal Subspaces (EDYES) says that if $U \subseteq V$ and $\dim(U) = \dim(V)$ then $U = V$ . It converts a statement about integers into a statement about sets, and it rests on the Goldilocks theorem.

Layer 4 — determinants and eigenvalues

The fourth layer changes the question. Instead of asking what a matrix does to arbitrary vectors, it asks which directions the matrix leaves invariant. Two independent sub-branches feed it: the determinant, a single scalar certificate, and the eigenvalue theory that the determinant makes computable.

Determinant Expansion about Rows and Columns (DERC) — establishes that cofactor expansion along any row or column gives the same value. Rests on: induction on size. It is what makes the determinant well defined rather than a choice.
Determinant Respects Matrix Multiplication (DRMM) and Determinant of the Transpose (DT) — establish $\det(AB) = \det(A)\det(B)$ and $\det(A^{t}) = \det(A)$ . Rests on: elementary matrix decompositions.
Singular Matrices have Zero Determinants (SMZD) — establishes that $A$ is singular if and only if $\det(A) = 0$ , joining the determinant branch to the main trunk. Rests on: the behaviour of the determinant under row operations.
Every Matrix Has an Eigenvalue (ESMHE) — establishes that every square matrix over $\mathbb{C}$ has at least one eigenvalue. Rests on: the fundamental theorem of algebra, imported from outside linear algebra, together with a dependence argument on the powers $\{\vec{x}, A\vec{x}, A^{2}\vec{x}, \ldots\}$ . This is where the choice of scalar field becomes load-bearing: over $\mathbb{R}$ the statement is false.
Eigenvalues are Roots of the Characteristic Polynomial (EMRCP) and Eigenspace of a Matrix is a Null Space (EMNS) — establish $p_A(\lambda) = 0 \iff \lambda$ is an eigenvalue, and $E_A(\lambda) = \mathcal{N}(A - \lambda I_n)$ . Rests on: SMZD and the equivalences for nonsingular matrices. These two theorems reduce the eigenvector problem to a null space problem — a layer-one computation — which is why the whole spectral theory is computable at all.
Multiplicities of an Eigenvalue (ME) — establishes $1 \le \gamma_A(\lambda) \le \alpha_A(\lambda) \le n$ , the geometric multiplicity never exceeding the algebraic. Rests on: similarity invariance of the characteristic polynomial.
Diagonalisation Characterisation (DC), Diagonalizable Matrices have Large Eigenspaces (DMLE) and Distinct Eigenvalues implies Diagonalizable (DED) — establish, respectively, that $A$ is diagonalisable exactly when $\mathbb{C}^n$ has a basis of eigenvectors of $A$ ; exactly when $\gamma_A(\lambda) = \alpha_A(\lambda)$ for every eigenvalue; and that $n$ distinct eigenvalues suffice. Rests on: EDELI, ME and the Goldilocks theorem.

The dependency worth noticing is that the eigenvalue branch consumes the layers below it wholesale. An eigenspace is a null space, so computing one is row reduction; deciding diagonalisability is a dimension count; and the proof that eigenvectors for distinct eigenvalues are independent is a relation-of-linear-dependence argument from layer two. Nothing in the eigenvalue layer is self-contained.

Layer 5 — transformations, isomorphism and representation

The top of the chart replaces matrices with functions between vector spaces and then proves that, in finite dimension, nothing has been gained or lost. This is the closure that makes the subject a single theory rather than two.

Matrices Build Linear Transformations (MBLT) and Matrix of a Linear Transformation (MLTCV) — establish that $T(\vec{x}) = A\vec{x}$ is always linear, and that every linear $T \colon \mathbb{C}^n \to \mathbb{C}^m$ arises this way from a unique $A$ . Rests on: the distributive properties of the matrix-vector product and the standard unit vectors.
Kernel of an Injective Linear Transformation (KILT) and Range of a Surjective Linear Transformation (RSLT) — establish that injectivity is a trivial kernel and surjectivity is a full range. Rests on: LTTZZ. These are the transformation-level analogues of a trivial null space and a full column space.
Invertible Linear Transformations are Injective and Surjective (ILTIS) — establishes the expected characterisation of invertibility. Rests on: KILT, RSLT and the definition of a two-sided inverse function.
Rank Plus Nullity is Domain Dimension (RPNDD) — establishes $r(T) + n(T) = \dim(U)$ for $T \colon U \to V$ . Rests on: a basis-extension construction and the Goldilocks theorem. It is the exact analogue of RPNC one layer up, and the two are provably the same statement once a matrix representation is chosen.
Characterisation of Finite Dimensional Vector Spaces (CFDVS) and Isomorphism of Finite Dimensional Vector Spaces (IFDVS) — establish that every space of dimension $n$ is isomorphic to $\mathbb{C}^n$ , and that two finite-dimensional spaces are isomorphic exactly when their dimensions agree. Rests on: VRILT, the proof that vector representation relative to a basis is an invertible linear transformation. Dimension is therefore a complete invariant.
Fundamental Theorem of Matrix Representation (FTMR) — establishes $\rho_C(T(\vec{u})) = M^{B}_{C}\, \rho_B(\vec{u})$ : coordinatise the input, multiply by a matrix, and the result is the coordinatisation of the output. Rests on: LTDB and VRLT. Every question about an abstract transformation becomes a question about a matrix, and the whole chart below becomes available.
Kernel and Null Space Isomorphism (KNSI), Range and Column Space Isomorphism (RCSI), Invertible Matrix Representations (IMR) and Similarity and Change of Basis (SCB) — establish the dictionary entry by entry: kernel to null space, range to column space, invertible transformation to invertible matrix, change of basis to similarity. Rests on: FTMR throughout.

Reading the chart by out-degree identifies the hubs. Uniqueness of the reduced form and the theorem converting solutions into linear combinations dominate the lower half; the Goldilocks theorem and rank plus nullity dominate the middle; the fundamental theorem of matrix representation dominates the top. The equivalences for nonsingular matrices run vertically through all of them, absorbing one new statement per layer, and are best read as a summary of the whole chart restricted to square matrices.

Locating a question on the chart

Is the object a matrix or a map between abstract spaces?If it is an abstract linear transformation on finite-dimensional spaces, choose bases and coordinatise first. The fundamental theorem of matrix representation converts the question into a matrix question, after which every layer below is available.

Does the question concern one specific right-hand side?Consistency, uniqueness and the number of free variables are settled by the reduced form of

[\, A \mid \vec{b} \,]

and the two integers

r

and

n

. Stop at layer one; nothing higher is needed.

Does it concern a set of vectors rather than a system?Independence, spanning and basis questions belong to layer two. If the ambient dimension is known and the set has exactly that many vectors, the Goldilocks theorem lets one verified property certify the other.

Does it concern a subspace attached to the matrix?Null space, column space, row space and left null space, and their dimensions, belong to layer three. One extended reduction of

[\, A \mid I_m \,]

delivers all four at once; rank plus nullity then constrains the answer.

Does it concern the matrix acting on itself?Powers, similarity, invariant directions, diagonal form and long-run behaviour are layer four. These require a square matrix and, for existence guarantees, complex scalars. Expect an iterative numerical method rather than a closed form.

Answer at the lowest layer that settles the questionA lower-layer answer is cheaper, has weaker hypotheses and is numerically better behaved. Rank questions cost

O(n^3)

and need no field extension; spectral questions cost more and carry existence caveats.

Equations

Canonical form at the root of the chart

EQ-MAP-01

A \sim B \Leftrightarrow RREF (A) = RREF (B)

Row equivalence is decided by comparing two specific matrices. Everything downstream that speaks of “the” reduced form, “the” pivot columns or “the” rank depends on the uniqueness half of this statement.

The pivot count decides the solution set

EQ-MAP-02

| S | = {\begin{cases} 0 & (n + 1) \in D \\ 1 & (n + 1) \notin D, r = n \\ \infty & (n + 1) \notin D, r < n \end{cases}

The complete classification of solution sets for a system in $n$ variables, where $D$ is the pivot column set of the reduced augmented matrix. The degrees of freedom are $n - r$ .

Rank plus nullity is columns

EQ-MAP-03

rank (A) + nullity (A) = n

The conservation law of the middle layers. Every column of $A$ either contributes a dimension to the column space or a degree of freedom to the null space, never both and never neither.

The Goldilocks theorem

EQ-MAP-04

\dim (V) = t, | S | = m \Rightarrow {\begin{cases} m > t & S dependent \\ m < t & span (S) \neq V \\ m = t & independent \Leftrightarrow spanning \end{cases}

Set size alone decides two of the three cases outright, and in the third case reduces two verifications to one. This is the highest-leverage counting result in the subject.

Row rank equals column rank

EQ-MAP-05

rank (A) = rank (A^{t})

The number of independent rows equals the number of independent columns for every matrix of every shape. Elementary to state, and reachable only after dimension theory is in place.

Characteristic polynomial and its degree

EQ-MAP-06

p_{A} (x) = \det (A - x I_{n}), \deg p_{A} = n, \sum_{i}^{=} α_{A} (λ_{i}) = n

The entry point to layer four. Its degree bounds the number of distinct eigenvalues by $n$ , and over $\mathbb{C}$ the fundamental theorem of algebra guarantees at least one root.

Fundamental theorem of matrix representation

EQ-MAP-07

ρ_{C} (T (\vec{u})) = M_{C}^{B} ρ_{B} (\vec{u})

Applying a linear transformation and then coordinatising gives the same result as coordinatising and then multiplying by a matrix. This identity closes the loop between the top and bottom of the chart.

Variable Definitions

Symbols used on this page
Symbol	Name	Meaning	Domain / type
$A$	Matrix	The $m \times n$ matrix under study, with complex entries	m x n matrix
$m$	Row count	Number of equations, or the size of the codomain $\mathbb{C}^m$	positive integer
$n$	Column count	Number of unknowns, or the size of the domain $\mathbb{C}^n$	positive integer
$r$	Pivot count and rank	Non-zero rows of the reduced form; becomes $\operatorname{rank}(A)$ and $\dim(\mathcal{C}(A))$	0 to min(m,n)
$D$	Pivot column set	Indices of the columns carrying leading ones; determines every structural reading	subset of 1..n
$t$	Dimension of a vector space	Common size of every basis of $V$ , written $\dim(V)$	non-negative integer
$λ$	Eigenvalue	Scalar with $A\vec{x} = \lambda\vec{x}$ for some non-zero $\vec{x}$	complex number
$α_{A} (λ)$	Algebraic multiplicity	Multiplicity of $\lambda$ as a root of $p_A(x)$	1 to n
$γ_{A} (λ)$	Geometric multiplicity	$\dim(E_A(\lambda)) = \operatorname{nullity}(A - \lambda I_n)$ , never larger than $\alpha_A(\lambda)$	1 to n
$M_{C}^{B}$	Matrix representation	Matrix of a linear transformation relative to a domain basis $B$ and a codomain basis $C$	matrix over C

Worked Numerical Example

Problem statement

Four instruments observe a six-state process, giving a $4 \times 6$ measurement matrix. Trace one reduction through the chart and extract, layer by layer, every conclusion the structure supports — and identify the question the chart says cannot be asked at all.

Assemble the measurement matrix
Each row is one instrument's sensitivity to the six state variables $x_1, \ldots, x_6$ . The matrix is the object; the chart is the map for interrogating it.
$M = [\begin{matrix} 1 & 2 & 0 & - 1 & 0 & 3 \\ 2 & 4 & 1 & 2 & 0 & 4 \\ 1 & 2 & 1 & 3 & 1 & 6 \\ 3 & 6 & 2 & 5 & 1 & 10 \end{matrix}]$
Layer 0: reduce to the canonical form
Gauss-Jordan elimination gives the reduced row-echelon form. Uniqueness guarantees that any other sequence of row operations reaches the same destination, so every number extracted below is a property of $M$ rather than of the route.
$Layer 0: reduce to the canonical form$
Layer 1: read $r$ , the pivot set and the free variables
Three non-zero rows give $r = 3$ , with pivot columns $D = \{1, 3, 5\}$ and free columns $F = \{2, 4, 6\}$ . For any consistent right-hand side there are $n - r = 6 - 3 = 3$ degrees of freedom, so no measurement vector can ever determine the state uniquely. That verdict required nothing above layer one.
$r = 3, D = {1, 3, 5}, n - r = 3$
Layer 2: a basis for the unobservable subspace
Setting each free variable to one in turn and reading the dependent variables off the reduced rows gives three vectors. They are independent by construction — each carries a $1$ in a position where the others carry $0$ — so they are a basis, not merely a spanning set. Any state differing by a vector in this span produces identical readings on all four instruments.
$Layer 2: a basis for the unobservable subspace$
Layer 3: column space, row space and the transpose
The pivot columns index the original columns of $M$ that form a basis for the column space, so $\dim(\mathcal{C}(M)) = 3$ . The three non-zero rows of the reduced form are a basis for the row space, so $\dim(\mathcal{R}(M)) = 3$ as well — an instance of row rank equalling column rank. Rank plus nullity checks out: $3 + 3 = 6 = n$ .
$C (M) = span ([\begin{matrix} 1 \\ 2 \\ 1 \\ 3 \end{matrix}], [\begin{matrix} 0 \\ 1 \\ 1 \\ 2 \end{matrix}], [\begin{matrix} 0 \\ 0 \\ 1 \\ 1 \end{matrix}]), rank (M) = rank (M^{t}) = 3$
Layer 3: the left null space and the consistency criterion
The left null space has dimension $m - r = 4 - 3 = 1$ . Its single basis vector records the linear dependency among the instrument rows: row four is the sum of rows two and three. Because the column space is exactly the null space of the left null space basis, this one vector is a complete consistency test — a reading vector $\vec{b}$ is achievable if and only if $-b_2 - b_3 + b_4 = 0$ .
$L (M) = span ([\begin{matrix} 0 \\ - 1 \\ - 1 \\ 1 \end{matrix}]), \vec{b} \in C (M) \Leftrightarrow - b_{2} - b_{3} + b_{4} = 0$
Layer 5: the transformation reading
Define $T \colon \mathbb{C}^6 \to \mathbb{C}^4$ by $T(\vec{x}) = M\vec{x}$ . The kernel is the null space, so $n(T) = 3 \ne 0$ and $T$ is not injective. The range is the column space, so $r(T) = 3 < 4$ and $T$ is not surjective. Rank plus nullity for transformations reproduces the matrix identity exactly.
$Layer 5: the transformation reading$
Layer 4 is unreachable, and the chart says so
There is no meaningful question here about eigenvalues, the determinant, similarity or diagonalisation. Every theorem in layer four carries the hypothesis that the matrix is square, and $M$ is $4 \times 6$ . Attempting $\det(M)$ or solving $M\vec{x} = \lambda\vec{x}$ is not a hard computation — it is a type error. Recognising that boundary is exactly what the dependency chart is for.

Result

The instrument set resolves a three-dimensional subspace of the six-dimensional state and is blind to a three-dimensional complement, so three further independent instruments would be required for full observability. One of the four existing instruments is redundant — its reading is forced by two others — which both provides a live consistency check on the hardware and identifies a sensor that could be removed without loss. All of this follows from a single row reduction and three layers of the chart; no spectral computation was performed or available.

Applications & Industry Use

Scientific computing

Library architecture mirrors the layers

The public interface of a dense linear algebra library is stratified in the same way as the dependency chart. Factorisation routines answer layer-one and layer-three questions, rank-revealing decompositions answer dimension questions, and a separate eigensolver family answers layer-four questions at higher cost and with different convergence guarantees. Choosing the correct routine for a problem is exactly the act of locating the problem on the chart.

Formal methods and verification

Machine-checked dependency graphs

Proof-assistant mathematics libraries maintain the dependency graph explicitly: each lemma records the lemmas it invokes, and the build system enforces acyclicity. Refactoring such a library — for instance, deriving the spectral theory without the determinant — is a graph-rewriting exercise whose feasibility is settled by exactly the dependency questions this chart answers.

Control systems

Rank tests versus spectral tests

Controllability and observability are decided by the rank of a block matrix — a layer-three question settled by one factorisation, with no eigenvalues involved. Stability, modal decomposition and pole placement are layer-four questions requiring the spectrum. Recognising which of the two a design review is asking prevents both unnecessary eigensolves and misplaced confidence in a rank test that says nothing about dynamics.

Structural engineering

One stiffness matrix, two different layers

The degree of static indeterminacy of a frame is a rank question about the equilibrium matrix, answered by elimination. Buckling loads and vibration modes of the same structure are eigenvalue questions about the stiffness and mass matrices. The two analyses share input data but occupy different layers, with different costs, different solvers and different sensitivity to modelling error.

Data science and statistics

Collinearity diagnostics at the right depth

Exact redundancy among predictors is a rank-layer property, detected by a pivoted factorisation that also names which columns are redundant. Near-redundancy and its effect on estimator variance are spectral properties, described by singular values and the condition number. Reporting a rank when the question was about conditioning — or the reverse — is a layer confusion that produces confidently wrong model diagnostics.

Technical education and assessment

Sequencing a curriculum along the graph

A topological ordering of the dependency graph is a valid teaching order, and the edges are the genuine prerequisites. Competency frameworks built on the graph can state precisely which earlier results a learner must hold before a given result is meaningful, and assessment items can be traced to the specific edges they exercise rather than to a chapter number.

Design Considerations

Answer at the lowest layer that settles the question

Lower layers have weaker hypotheses, lower cost and better numerical behaviour. Deciding whether a square system has a unique solution needs one elimination; it does not need a determinant, an inverse or a spectrum. Every layer climbed adds hypotheses that must be checked and arithmetic that can go wrong.

The determinant is a certificate, not a method

In the dependency chart the determinant sits between the rank layer and the eigenvalue layer, and its role is to connect them: it turns a singularity question into a polynomial root question. It is not a competitive computational tool. Cofactor expansion costs $O(n!)$ , and even computed by factorisation the determinant overflows or underflows for moderate $n$ and carries no information about conditioning.

The scalar field is load-bearing above layer three

Layers zero to three are valid over any field: row reduction, rank, dimension and the four subspaces do not care whether the scalars are rational, real, complex or drawn from a finite field. Layer four does care. The guarantee that every square matrix has an eigenvalue is a consequence of algebraic closure, and over $\mathbb{R}$ it fails — a plane rotation has no real eigenvalue at all. State the field before quoting any spectral result.

Square and finite-dimensional are hypotheses, not decoration

Determinants, eigenvalues, similarity, diagonalisation and invertibility are defined only for square matrices; rank, the four subspaces and rank-nullity apply to any shape. Above layer two, finite dimension is a standing assumption: the Goldilocks theorem, rank plus nullity for transformations and the characterisation of vector spaces by dimension all fail without it.

Watch for circularity when extending an equivalence list

The running list of conditions equivalent to nonsingularity grows by one statement per layer, each added by a bridging theorem. A bridging theorem proved using the list it is about would make the whole structure vacuous. When adding a new equivalence, check that its proof reaches back only to results strictly below it in the chart.

The chart is exact arithmetic; floating point blurs the layers

In exact arithmetic a pivot is zero or it is not, and the layer boundaries are sharp. In floating point, rank becomes a threshold decision, a determinant near zero means almost nothing, and eigenvalues of a defective matrix are computed with error proportional to a fractional power of the machine epsilon. Production code should replace the exact statements with their tolerance-bearing numerical analogues rather than pretend the distinction is absent.

Standards & Codes

Notation, interchange and numerical standards that govern how this material is written down, stored and computed in production systems.

Applicable standards, conventions and reference implementations
Reference	Title	Relevance to this topic
`ISO 80000-2`	Quantities and units — Part 2: Mathematics	Fixes the typography this chart depends on for legibility across many named objects: upright operators such as $\det$ and $\dim$ , italic scalars, arrow or bold vectors, and the distinction between a set and its cardinality.
`ISO/IEC 40314`	Mathematical Markup Language (MathML) Version 3.0	Encodes every statement on this page as structured mathematics rather than images, so a theorem statement remains searchable, quotable and machine-comparable when the chart is consumed programmatically.
`W3C SKOS`	Simple Knowledge Organization System Reference	Provides the vocabulary for expressing a dependency chart as data: `skos:broader` and `skos:related` map naturally onto prerequisite and cross-reference edges, which is how a theorem map is published as a navigable concept scheme rather than prose.
`IEEE 754-2019`	IEEE Standard for Floating-Point Arithmetic	Defines the arithmetic in which every layer of the chart is actually executed, and therefore why the sharp exact-arithmetic boundaries between layers become tolerance decisions in any implementation.
`LAPACK / BLAS reference`	Linear Algebra PACKage reference implementation	The de facto catalogue of which computations are considered routine at each layer: driver routines exist for factorisation, least squares, singular values and eigenvalues, and their documented cost and accuracy bounds are the practical cost model for the chart.

Material Selection

For a mathematical topic, "material" is the numeric representation: the scalar field, storage format and precision the computation is built from.

Representation and precision selection
Representation	Select when	Trade-off
Complex scalars, $\mathbb{C}$	Whenever eigenvalues, diagonalisation or any existence guarantee about the spectrum is required.	Algebraic closure makes layer four complete — every square matrix has $n$ eigenvalues counted with multiplicity. The cost is doubled storage, roughly four times the arithmetic per multiplication, and results that may be complex even for real input.
Real scalars, $\mathbb{R}$	Physical models where the data and the answer are both real and only layers zero to three are needed.	Everything up to and including rank-nullity is intact and cheaper. Layer four is incomplete: existence of an eigenvalue fails, and real algorithms must fall back to a real Schur form with $2 \times 2$ blocks representing complex conjugate pairs.
Exact rationals, $\mathbb{Q}$	Structural determinations — rank, pivot pattern, basis extraction, symbolic null spaces — where a wrong answer is worse than a slow one.	Removes every tolerance decision from layers zero to three. Intermediate coefficients can grow explosively, and eigenvalues are generally irrational, so layer four escapes the field entirely.
Finite field, $\mathbb{F}_p$	Coding theory, cryptography, and probabilistic certification of rank by reduction modulo a random prime.	Layers zero to three transfer without change and run in fixed-width arithmetic with no growth. Layer four requires an extension field, and an unlucky prime can lower the observed rank relative to the rational answer.
IEEE 754 binary64	Numerical solution of engineering problems where inputs already carry measurement uncertainty.	Fast and memory-efficient with about sixteen significant decimal digits. Rank becomes a tolerance decision, determinants scale as the $n$ -th power and lose meaning, and defective eigenvalues lose accuracy at a fractional-power rate.
Symbolic entries in a polynomial ring	Parametric studies where a design variable appears in the matrix and the question is how the structure changes with it.	Reveals the parameter values at which rank drops or eigenvalues collide, which no numerical sweep can locate exactly. Expression growth is severe, and the ring is not a field, so several layer-two and layer-three theorems require restatement.

Manufacturing Notes

Implementation notes — how the result is actually produced by hand, by algorithm and by library, including cost and numerical behaviour.

Cost rises sharply with layer

Row reduction of an $n \times n$ matrix costs about $n^3$ operations, and a factorisation with back-substitution about $\tfrac{2}{3}n^3$ . A determinant obtained from that factorisation is essentially free; obtained by cofactor expansion it costs $O(n!)$ and is unusable beyond about $n = 12$ . Eigenvalues have no finite algorithm at all — they are roots of a degree- $n$ polynomial — so every eigensolver is iterative, typically running at $10n^3$ to $25n^3$ operations with convergence that depends on the matrix.

Mapping library calls to layers

Layer one and three: LU and QR factorisations, numpy.linalg.solve, scipy.linalg.lu, xGETRF. Layer three dimensions: numpy.linalg.matrix_rank, pivoted QR (xGEQP3), the singular value decomposition. Layer four: numpy.linalg.eig, xGEEV, xSYEVR for the symmetric case. Layers zero and two, being about exact structure, appear only in symbolic systems such as SymPy, Maxima or Sage.

Verification technique differs by layer

A layer-one answer is verified by substituting a solution into the original equations. A layer-three answer is verified by a dimension count: the extracted bases must have sizes summing correctly under rank plus nullity, and each basis vector must satisfy its defining equation. A layer-four answer is verified by residual: $\|A\vec{x} - \lambda\vec{x}\|$ small relative to $\|A\| \|\vec{x}\|$ . Never verify a computation using the reduced object that the computation produced.

Tracing a proof's real dependencies by hand

Take the statement, list every named result its proof cites, then recurse until only definitions remain. Two things emerge. First, the effective depth is usually small — four or five levels — because a few hub theorems absorb the complexity. Second, some cited results turn out to be conveniences rather than necessities, and removing them shows the theorem holds under weaker hypotheses than stated.

Numerical stability is not uniform across the chart

Solving a well-conditioned system is backward stable and loses digits in proportion to the condition number. Determining rank is discontinuous in the entries and requires an explicit tolerance. Computing eigenvalues of a symmetric matrix is well conditioned, while eigenvalues of a highly non-normal matrix can move by $O(\sqrt{\epsilon})$ or worse under perturbations of size $\epsilon$ . Cost and stability are separate axes and both degrade upward.

Failure Modes & Common Mistakes

Failure modes, root causes and prevention
Failure mode / mistake	Impact	Root cause	Prevention & detection
Applying a square-matrix theorem to a rectangular matrix	high	Quoting determinant, eigenvalue, invertibility or similarity results for a matrix that is not $n \times n$ , usually after a shape change went unnoticed in code.	Treat squareness as a precondition to assert, not to assume. Rank, nullity and the four subspaces are the shape-agnostic tools; everything in layer four is not.
Assuming eigenvalues exist over the reals	high	Carrying the existence guarantee across from $\mathbb{C}$ to $\mathbb{R}$ , where it is false: a planar rotation matrix has no real eigenvalue.	State the field. Use the real Schur form with $2 \times 2$ blocks when a real answer is required, or accept complex conjugate pairs.
Circular citation in an equivalence chain	high	Proving a new equivalent condition using a consequence of the very list being extended, which makes the addition vacuous.	Before adding a statement to an equivalence theorem, expand its proof's dependency list and confirm every entry sits strictly lower in the chart.
Using $\det(A) \ne 0$ as a numerical singularity test	high	Transferring an exact-arithmetic equivalence into floating point, where the determinant scales as $\det(cA) = c^{n}\det(A)$ and can be enormous or vanishing for a perfectly well-conditioned matrix.	Use a reciprocal condition number estimate or the smallest singular value. Reserve the determinant for exact and symbolic work.
Cofactor expansion on a matrix of moderate size	medium	Implementing the recursive definition literally, which costs $O(n!)$ multiplications.	Compute the determinant as the product of the pivots of an LU factorisation, adjusted for the sign of the row interchanges — $O(n^3)$ and numerically far better behaved.
Dropping the finite-dimension hypothesis	medium	Applying the Goldilocks theorem, rank plus nullity for transformations, or the characterisation of spaces by dimension to a space with no finite basis, such as all polynomials or all continuous functions.	Establish a finite basis first. Where none exists, the counting arguments of layers two and three simply do not apply and different machinery is required.
Confusing algebraic and geometric multiplicity	medium	Assuming a repeated root of the characteristic polynomial supplies that many independent eigenvectors, which is the diagonalisable case only.	Compute $\gamma_A(\lambda) = \operatorname{nullity}(A - \lambda I_n)$ explicitly and compare with $\alpha_A(\lambda)$ . Equality for every eigenvalue is exactly the condition for diagonalisability.
Treating spanning and independence as interchangeable	medium	Half-remembering the Goldilocks theorem and applying its third or fourth part without checking that the set has exactly $\dim(V)$ members.	Count first. The equivalence of independence and spanning holds only at the exact size $m = t$ ; at any other size one property can hold while the other fails.
Reaching for a spectral tool to answer a rank question	low	Habitually computing a full eigendecomposition or singular value decomposition when a pivoted factorisation would settle the structural question at a fraction of the cost.	Locate the question on the chart before choosing a routine. If the answer is an integer and a set of column indices, stay at layer three.

FAQs

Is there a single theorem that everything else depends on?

Uniqueness of the reduced row-echelon form comes closest. It is what makes the pivot count, the pivot column set and therefore the rank well-defined properties of a matrix rather than artefacts of a particular elimination order. Almost every structural theorem in the first four layers begins by fixing the reduced form of a matrix, and each of those silently invokes uniqueness.

Why does the abstraction to general vector spaces earn its keep?

Because two theorems become provable that resist direct attack on entries. That row rank equals column rank is nearly opaque as a statement about arrays, and falls out of dimension counting. That a set of the right size need only be independent or spanning to be a basis halves the work in every later basis verification. Both results reach back through dimension to a single counting theorem about spanning sets.

Can eigenvalue theory be developed without determinants?

Yes. The existence proof used here shows that some polynomial in $A$ annihilates a chosen non-zero vector, factors it over $\mathbb{C}$ , and extracts an eigenvalue — no determinant appears. The determinant enters afterwards as a computational device, turning eigenvalue-finding into root-finding for the characteristic polynomial. On the chart this is an alternative edge set reaching the same vertex.

Where exactly does the complex field become necessary?

At the existence of eigenvalues, and nowhere below it. Row reduction, rank, the four subspaces, dimension, bases, rank-nullity and the entire theory of linear transformations are valid over any field. Algebraic closure is what guarantees that the characteristic polynomial has a root, and it is the only place where the fundamental theorem of algebra is imported from outside the subject.

Why does the same rank-nullity statement appear twice?

Once for matrices, as rank plus nullity equals the number of columns, and once for transformations, as rank plus nullity equals the dimension of the domain. They are not coincidentally similar: the kernel of a transformation is isomorphic to the null space of any matrix representation, and the range is isomorphic to its column space, so choosing bases converts either statement into the other.

How deep is the graph in practice?

Shallow relative to its size. Expanding the dependencies of a typical upper-layer theorem reaches definitions in four or five steps, because a small number of hub results — uniqueness of the reduced form, solutions as linear combinations, the counting theorem behind dimension, rank plus nullity and the fundamental theorem of matrix representation — absorb most of the paths.

Does the chart change if invertibility is taken as the definition of nonsingular?

The vertex set is unchanged and the edges are rerouted. Taking a two-sided inverse as primitive makes the trivial null space a theorem instead of a definition, and moves several proofs earlier or later. What no reordering can change is which results genuinely need which hypotheses — squareness, finite dimension and algebraic closure remain exactly where they are.

References

Beezer, R. A. A First Course in Linear Algebra, Version 0.70. University of Puget Sound, 2006. Sections SSLE, RREF, LI, D, PD, DM, EE, PEE, SD, LT, IVLT, VR and MR. Licensed under the GNU Free Documentation License v1.2.
Strang, G. Linear Algebra and Its Applications, 4th edition. Cengage Learning, 2006.
Axler, S. Linear Algebra Done Right, 3rd edition. Springer, 2015. The determinant-free development of eigenvalue existence.
Golub, G. H. and Van Loan, C. F. Matrix Computations, 4th edition. Johns Hopkins University Press, 2013. Cost and stability figures for each computational layer.
ISO 80000-2:2019, Quantities and units — Part 2: Mathematics. International Organization for Standardization.
W3C. SKOS Simple Knowledge Organization System Reference, W3C Recommendation, 2009.

AI Suggested Questions

Expand the full dependency tree of the statement that row rank equals column rank, stopping at definitions, and tell me how many distinct theorems it uses.
Which theorems in this chart remain true over a finite field, and which ones fail or need restatement?
Give me a topological ordering of the subject that introduces linear transformations before matrices, and say which proofs would have to change.
For a 2000x2000 sparse matrix, compare the cost of answering a rank question, a determinant question and an eigenvalue question, and say which are practical.
Show me a concrete matrix where the geometric multiplicity of an eigenvalue is strictly less than the algebraic multiplicity, and trace which layer-four theorems then fail to apply.
If I take invertibility as the definition of nonsingular instead of a trivial null space, which theorems swap places in the dependency order?

Related Calculators

RREF Calculator

Reduce any matrix to reduced row-echelon form and read off the pivot set, rank and free columns.

Matrix Rank & Nullity Calculator

Compute rank and nullity with a selectable tolerance, and verify rank plus nullity against the column count.

Four Fundamental Subspaces Calculator

Extract bases for the null space, column space, row space and left null space from a single extended reduction.

Eigenvalue & Eigenvector Calculator

Compute the characteristic polynomial, eigenvalues, eigenspaces and both multiplicities, and test for diagonalisability.