1 Linear maps, matrices, and fundamental definitions
1.1 Linear transformations and their matrix representations
A linear transformation is a map between vector spaces that preserves addition and scalar multiplication. When the domain and codomain are finite-dimensional, such a transformation can be represented by a matrix once bases are fixed. Under this identification, studying the transformation is equivalent to analyzing how the matrix acts on vectors in coordinates.
1.2 Nullspace (kernel) of a matrix
For a matrix \(A\) (or a linear map \(T\)), the nullspace (also called the kernel) is the set of vectors that are sent to zero: \[
| \mathrm{Null}(A)=\{x \; | \; Ax=0\}. |
|---|
\] It forms a subspace of the domain. Each nonzero vector in the nullspace describes a direction of variation that does not affect the output.
1.3 Image (range) of a matrix
The image (or range) of \(A\) is the set of all outputs the matrix can produce: \[
| \mathrm{Im}(A)=\{Ax \; | \; x \text{ in the domain}\}. |
|---|
\] As a subspace of the codomain, it describes which components of the output space are reachable by applying the transformation.
1.4 Rank of a matrix and its interpretation
The rank of \(A\) is the dimension of its image. Intuitively, it counts how many independent output directions exist. In row- and column-language, it also equals the number of pivot positions in a reduced row-echelon form and the number of linearly independent columns (or rows).
1.5 Linear systems viewpoint: Ax = 0 and Ax = b
Many properties of \(A\) are revealed by the associated linear system(s). The homogeneous system \(Ax=0\) has solutions exactly equal to the nullspace. The inhomogeneous system \(Ax=b\) is solvable precisely when \(b\) lies in the image of \(A\).
2 Rank–nullity theorem and dimension relationships
2.1 Statement of the rank–nullity theorem
If \(A\) maps an \(n\)-dimensional space to some \(m\)-dimensional space, then \[ \mathrm{rank}(A) + \mathrm{nullity}(A)=n, \] where \(\mathrm{nullity}(A)=\dim(\mathrm{Null}(A))\). This identity links the “independent constraints” encoded by \(A\) to the “free directions” in solutions.
2.2 Geometric meaning of nullspace dimension
Geometrically, the nullspace dimension counts the number of degrees of freedom that remain after imposing the equations \(Ax=0\). If the matrix eliminates many directions, the kernel is small; if many directions are untouched by the transformation, the kernel is large.
2.3 Degrees of freedom and solution structure
For \(Ax=0\), every solution is a linear combination of basis vectors for \(\mathrm{Null}(A)\). When \(A\) has rank \(r\), the solution space has dimension \(n-r\). Thus, rank deficiency (smaller than expected rank) increases the number of free parameters in the homogeneous solutions.
2.4 Nullity vs. multiplicity of constraints
A common misconception is that each equation always reduces one degree of freedom. In reality, equations may be redundant: multiple rows can encode the same information. Rank captures the number of independent constraints, while nullity captures what remains unconstrained.
3 Characterizations of nullspace
3.1 Nullspace from row-reduced echelon form (RREF)
Row-reduction to reduced row-echelon form provides a direct route to a nullspace basis. Pivot columns correspond to variables that can be expressed in terms of free variables. Setting free variables to basis choices and solving for pivot variables yields explicit vectors spanning \(\mathrm{Null}(A)\).
3.2 Using the SVD to compute the nullspace
The singular value decomposition (SVD) expresses \(A\) as \(A=U\Sigma V^T\), where \(\Sigma\) contains singular values. Right singular vectors associated with singular values equal (or numerically close) to zero span the nullspace. This method is especially valuable for stable computations in floating-point arithmetic.
3.3 Nullspace basis construction
A basis for the nullspace can be constructed by any method that identifies independent constraints. In RREF-based approaches, the basis emerges from free-variable parameterizations. In SVD-based approaches, it comes from the subspace associated with (near-)zero singular values. Either way, a basis is useful because it parameterizes all solutions compactly.
3.4 Relationship to eigenvectors (for square matrices)
For square matrices, nullspace relates to eigenvectors with eigenvalue zero. Specifically, a nonzero vector \(x\) satisfies \(Ax=0\) exactly when it is an eigenvector of \(A\) for eigenvalue \(0\). The dimension of the nullspace then equals the geometric multiplicity of the zero eigenvalue.
3.5 Orthogonality links: left nullspace and column space
| The left nullspace of \(A\), defined by \(\{y \; | \; y^TA=0\}\), is orthogonal to the column space of \(A\). Similarly, the nullspace is orthogonal to the row space (in an appropriate coordinate sense). These relationships clarify solvability and underlie many algorithms based on projections. |
|---|
4 Rank deficiency: concepts and diagnostics
4.1 What it means for a matrix to be rank-deficient
A matrix is rank-deficient when its rank is smaller than the maximum possible value (for example, smaller than \(\min(m,n)\)). Rank deficiency implies that some rows or columns are linearly dependent and that the nullspace has positive dimension.
4.2 Causes: dependent rows/columns and model redundancy
Rank deficiency can arise when the matrix encodes constraints that are not genuinely independent. Common sources include exact algebraic dependence, repeated features in data, symmetry-induced structure, or an overparameterized model where multiple parameter settings produce the same output.
4.3 Detecting rank deficiency via exact arithmetic
In settings where entries are exact (such as rational numbers or symbolic computation), rank can be determined by exact row-reduction or determinant-based reasoning. Exact arithmetic can reveal true dependencies rather than numerical approximations.
4.4 Numerical rank vs. exact rank (conditioning and tolerances)
In floating-point computations, nearly dependent rows may appear independent depending on scaling and noise. As a result, practitioners often speak of numerical rank, determined by comparing singular values to a tolerance. Small singular values indicate directions that are effectively constrained weakly, producing an estimated nullspace that may reflect both true structure and numerical artifacts.
4.5 Illustrative examples with small matrices
Consider a matrix with two identical rows. Its rank drops by at least one, and the nullspace dimension increases accordingly. Conversely, a matrix with rows that are almost identical will show one very small singular value, suggesting near rank deficiency; the computed nullspace may depend noticeably on the tolerance level.
5 Decomposition frameworks connecting nullspace and rank
5.1 Fundamental subspaces decomposition
A matrix induces several canonical subspaces: the column space, row space, nullspace, and left nullspace. These spaces are intertwined by orthogonality relations. Decompositions using these subspaces explain how rank deficiency increases the “hidden” directions (kernel-related) while shrinking the effective range.
5.2 QR decomposition and rank-revealing variants
QR factorization decomposes \(A\) into an orthonormal basis times an upper triangular factor. Rank-revealing QR (often with column pivoting) is designed to expose near dependencies by reordering columns. The diagonal entries of the triangular factor and the pivot behavior inform which columns contribute independently.
5.3 Singular value decomposition (SVD) and interpretation
SVD provides a unified interpretation: singular values measure how strongly the transformation acts along particular input directions. Zero (or tiny) singular values correspond to input directions that map to (near) zero output—precisely the nullspace (or an approximation to it). This makes SVD central for understanding both rank and nullity.
5.4 Column/row space decomposition using orthogonal bases
Given an orthonormal basis for the column space, any vector in the column space can be reconstructed via projection. When rank is deficient, the column space has lower dimension, and the orthogonal complement becomes larger. This perspective makes the jump from “few independent columns” to “larger nullspace” geometrically transparent.
5.5 Generalized inverses and their relation to nullspaces
Generalized inverses, such as the Moore–Penrose pseudoinverse, provide systematic ways to handle non-invertible matrices. The pseudoinverse produces minimum-norm solutions and naturally incorporates both the range and nullspace components. In particular, solution sets often separate into a particular solution plus arbitrary nullspace components.
6 Implications for solving linear systems
6.1 Homogeneous systems: structure of solution sets
For \(Ax=0\), the solution space is exactly \(\mathrm{Null}(A)\). If the system is rank-deficient, the nullspace has dimension greater than zero, so there are infinitely many nontrivial solutions (unless restricted by additional constraints).
6.2 Nonhomogeneous systems: consistency and solvability
For \(Ax=b\), solvability depends on whether \(b\in\mathrm{Im}(A)\). Rank deficiency does not by itself guarantee inconsistency; it mainly changes the number of solutions when consistent. If consistent, solutions form an affine space: one particular solution plus any vector from the nullspace.
6.3 Least squares with rank deficiency
| Least squares seeks \(x\) minimizing \(\|Ax-b\|\). When \(A\) is rank-deficient, the minimizer may not be unique because movement within the nullspace does not change \(Ax\) and therefore does not alter the residual. The typical resolution is to select a minimum-norm solution, often using the pseudoinverse or regularization. |
|---|
6.4 Normal equations and stability considerations
The normal equations \(A^TAx=A^Tb\) can be problematic when \(A\) is ill-conditioned or rank-deficient, since they square the condition number and can amplify numerical errors. Alternative formulations—such as QR or SVD-based least squares—often provide more reliable results.
6.5 Regularization perspective (overview)
Regularization introduces extra terms that penalize undesirable behavior, effectively addressing instability caused by near rank deficiency. Conceptually, it modifies the influence of small singular values so that the computed solution does not vary wildly under small perturbations of the data.
7 Nullspace in constrained and optimization problems
7.1 Constraint manifolds and feasible directions
In constrained optimization, constraints define a feasible set, sometimes approximated locally by a manifold. The tangent directions that do not violate the constraints to first order correspond to a nullspace of a constraint Jacobian. These feasible directions form the backbone for local search methods.
7.2 Parameterization via nullspace bases
A common technique is to reparameterize variables so that constraints are satisfied automatically. By expressing decision variables as a particular feasible point plus a linear combination of nullspace basis vectors of the constraint linearization, one reduces the constrained problem to an unconstrained one in fewer dimensions.
7.3 KKT systems and the role of degeneracy
Karush–Kuhn–Tucker (KKT) conditions introduce a system coupling variables and Lagrange multipliers. Degeneracy in constraints can lead to rank deficiency in the KKT matrix or reduced system, affecting solvability and the uniqueness of multipliers and primal variables.
7.4 Handling redundant constraints
Redundant constraints are those that do not add new information. Their presence increases nullspace dimensions associated with the constraint linearization and can create numerical issues such as slow convergence or unstable multiplier estimates. Algorithms often employ rank tests or constraint elimination to mitigate redundancy.
7.5 Subspace methods for iterative algorithms
Iterative methods can exploit nullspace structure by updating within feasible subspaces or by separating constrained and unconstrained components. Such subspace strategies can improve efficiency by avoiding directions that do not change the constraint satisfaction.
8 Sensitivity, stability, and numerical computation
8.1 Conditioning of rank-deficient problems
When \(A\) is nearly rank-deficient, small perturbations in the data can cause large changes in computed solutions, especially in components associated with small singular values. The sensitivity is closely tied to how the singular spectrum decays.
8.2 Effects of perturbations on rank
A tiny perturbation can turn an exactly dependent situation into an almost dependent one—or vice versa—depending on whether the underlying dependence is exact or approximate. Therefore, rank observed from numerical computations should be interpreted in light of perturbation magnitude and scaling.
8.3 Thresholding singular values to estimate nullity
Since floating-point arithmetic cannot reliably distinguish zeros from small numbers without context, numerical workflows typically set a tolerance and treat singular values below it as effectively zero. The count of such values estimates the numerical nullity and guides the construction of a stable nullspace basis.
8.4 Propagation of numerical errors in nullspace computation
| Algorithms that compute nullspaces may amplify error in directions corresponding to small singular values. Errors in estimated basis vectors can be substantial, though the spanned subspace may still be meaningful. Assessing residuals \(\|Ax\|\) for basis vectors and comparing subspaces at different tolerances helps quantify reliability. |
|---|
8.5 Practical guidelines for interpreting “near” rank deficiency
| A practical interpretation links computational evidence—like small singular values and unstable pivot patterns—to expected problem structure. Scaling the matrix, using SVD or rank-revealing QR, and reporting the tolerance choice are common best practices. Additionally, consistency checks such as verifying \(\|A\hat{x}\|\) and assessing sensitivity across tolerances support interpretation. |
|---|
9 Applications in applied mathematics
9.1 Inverse problems and ill-posedness
Many inverse problems can be written as \(Ax\approx b\), where \(A\) models how parameters map to observations. When \(A\) is rank-deficient or nearly so, multiple parameter values produce similar outputs, creating ambiguity that manifests as an enlarged nullspace.
9.2 Signal processing and dimensionality reduction
Signal models frequently assume that observations depend on a lower-dimensional structure. Rank deficiency indicates that only certain combinations of features are observable. Transform methods such as PCA relate directly to identifying dominant subspaces and discarding directions with little explanatory power.
9.3 Data science: PCA and low-rank structure (nullspace meaning)
In PCA, directions with small variance correspond to components that contribute minimally to the data model. While PCA is usually described via covariance eigenvectors, the same subspace logic applies: the near-null directions correspond to directions where the model is insensitive, which aligns with nullspace intuition.
9.4 System identification and overparameterized models
When models include more parameters than the data can support, parameters become non-identifiable. This non-identifiability is mathematically expressed through rank deficiency: multiple parameter vectors map to effectively the same outputs, producing a nullspace of the sensitivity matrix.
9.5 Graph theory connections (incidence matrices and kernels)
Graph incidence matrices and related operators have kernels that encode graph structure. For example, constraints imposed by flow conservation or potentials lead to nullspace descriptions that reveal connectivity properties and cycle-related degrees of freedom.
10 Common computational workflows and best practices
10.1 Choosing methods: RREF, QR, SVD
RREF is conceptually transparent and useful with exact arithmetic but is often numerically sensitive in floating-point settings. QR with pivoting is efficient for many problems and can reveal numerical rank. SVD is typically the most robust for identifying nullspaces and estimating numerical rank, especially under ill-conditioning.
10.2 Determining tolerance levels for rank decisions
Tolerance selection depends on machine precision, matrix scaling, and the expected noise level. Common practice uses relative thresholds tied to the largest singular value, rather than absolute cutoffs, to accommodate varying scales across problems.
10.3 Verifying nullspace bases and residuals
| A computed nullspace basis should satisfy \(\|A v\|\approx 0\) for each basis vector \(v\), with residual magnitude consistent with the tolerance and the scaling of \(A\). For subspaces, comparing the angle between computed bases at different tolerances helps confirm stability. |
|---|
10.4 Reporting results: rank, nullity, and basis vectors
Good reporting includes the estimated rank, the inferred nullity (dimension of the computed nullspace), and the basis representation method (e.g., RREF, QR, SVD). Including residual checks and tolerance values improves interpretability and reproducibility.
10.5 Reproducibility: numerical settings and diagnostics
Because numerical rank decisions can differ across software packages and settings, reproducibility benefits from recording solver choices, tolerance parameters, and any preprocessing steps such as normalization. Diagnostic outputs—singular value spectra, pivot patterns, and residual norms—provide context for why a particular nullspace was selected.