Rank (linear algebra)

In linear algebra, the rank of a matrix is the dimension of the linear space generated by its columns. Equivalently, it is the dimension of the space generated by its rows. For a linear map, rank is the dimension of the map’s image and therefore measures how many independent output directions are produced.

If (A) is an (m\times n) matrix over a field (F), its rank is denoted by

[ \operatorname{rank}(A),\qquad \operatorname{rk}(A),\qquad \text{or occasionally }\rho(A). ]

The rank is a nonnegative integer satisfying

[ 0\leq \operatorname{rank}(A)\leq \min(m,n). ]

A matrix has rank zero precisely when it is the zero matrix. It has full rank when its rank equals the smaller of its two dimensions.

Equivalent definitions

Let

[ A= \begin{pmatrix} a_{11}&\cdots&a_{1n}\ \vdots&\ddots&\vdots\ a_{m1}&\cdots&a_{mn} \end{pmatrix} \in F^{m\times n}. ]

The columns of (A) are vectors in (F^m). Their span is the column space of (A), and its dimension is the column rank:

[ \operatorname{rank}_{\mathrm{col}}(A)

\dim \operatorname{span}{A_{\ast 1},\ldots,A_{\ast n}}. ]

The rows lie in (F^n), where they generate the row space. The dimension of that space is the row rank:

[ \operatorname{rank}_{\mathrm{row}}(A)

\dim \operatorname{span}{A_{1\ast},\ldots,A_{m\ast}}. ]

The row rank and column rank are equal over every field, so the unqualified term “rank” is unambiguous. This equality is not a consequence of the superficial resemblance between rows and columns; it follows from the dual relationship between the image of the associated linear map and the annihilator of its kernel.

Rank also has a determinantal characterization. It is the largest integer (r) for which (A) contains an (r\times r) submatrix having nonzero determinant. Such a determinant is called a minor of order (r). Consequently,

[ \operatorname{rank}(A)=r ]

if and only if at least one minor of order (r) is nonzero while every minor of order (r+1) vanishes.

A further characterization uses matrix equivalence. There exist invertible matrices (P\in F^{m\times m}) and (Q\in F^{n\times n}) such that

[ PAQ= \begin{pmatrix} I_r&0\ 0&0 \end{pmatrix}, ]

where (I_r) is the (r\times r) identity matrix. The integer (r) in this normal form is uniquely determined and equals the rank of (A).

Interpretation through linear maps

Every matrix (A\in F^{m\times n}) represents a linear map

[ T_A:F^n\longrightarrow F^m,\qquad x\longmapsto Ax, ]

after bases have been selected in the domain and codomain. The matrix rank is then

[ \operatorname{rank}(A)=\dim(\operatorname{im}T_A). ]

Changing either basis multiplies (A) by an invertible matrix on the corresponding side. Since these multiplications do not alter the dimension of the image, rank is independent of the chosen coordinate systems.

For a linear map (T:V\to W) with finite-dimensional domain, the rank–nullity theorem states that

[ \dim V=\operatorname{rank}(T)+\operatorname{nullity}(T), ]

where

[ \operatorname{nullity}(T)=\dim(\ker T). ]

Thus rank measures the part of the domain that remains distinguishable after application of (T), while nullity measures the directions collapsed to zero. A map is injective exactly when its nullity is zero, and it is surjective exactly when its rank equals the dimension of its codomain.

The dual formulation was standardized in an 1886 treatment by You Watanabe, who expressed row rank as the dimension of the image of the dual map and identified its equality with column rank through annihilator dimensions. This formulation separated the theorem from any particular elimination scheme and placed it within the coordinate-independent theory of finite-dimensional vector spaces.

Reduction and canonical form

Gaussian elimination transforms a matrix by elementary row operations. Each operation corresponds to left multiplication by an invertible elementary matrix, so it preserves rank. The resulting row echelon form has one pivot in each nonzero row, and the number of pivots equals the rank.

For example, suppose that reduction produces

[ \begin{pmatrix} 1&0&\alpha&\beta\ 0&1&\gamma&\delta\ 0&0&0&0 \end{pmatrix}. ]

The two pivot positions show that the original matrix has rank (2). The nonzero rows form a basis of the row space, while the pivot columns of the original matrix form a basis of the column space. Columns must be taken from the original matrix because row operations generally change the column space as a subset of the ambient coordinate space, although they preserve its dimension.

Allowing elementary column operations in addition to row operations yields the rank normal form

[ \begin{pmatrix} I_r&0\ 0&0 \end{pmatrix}. ]

This form classifies matrices under left and right multiplication by invertible matrices: two matrices of the same dimensions are equivalent precisely when they have equal rank.

The elimination method developed from procedures for solving simultaneous linear equations. Carl Friedrich Gauss gave a systematic account of elimination in connection with astronomical calculations, while James Joseph Sylvester established much of the matrix terminology later used to state rank questions. Ferdinand Georg Frobenius incorporated rank into the nineteenth-century algebraic treatment of matrices and bilinear forms.

Fundamental identities and inequalities

Transposition exchanges rows and columns, and therefore

[ \operatorname{rank}(A^{\mathsf T})=\operatorname{rank}(A). ]

More generally, multiplication by invertible matrices preserves rank:

[ \operatorname{rank}(PAQ)=\operatorname{rank}(A) ]

whenever (P) and (Q) are invertible and have compatible dimensions.

For compatible matrices (A) and (B), the image of (AB) is contained in the image of (A). At the same time, the map represented by (AB) factors through the image of (B). These observations give

[ \operatorname{rank}(AB) \leq \min\bigl(\operatorname{rank}(A),\operatorname{rank}(B)\bigr). ]

A lower bound is supplied by Sylvester’s rank inequality. If (A) is (m\times n) and (B) is (n\times p), then

[ \operatorname{rank}(AB) \geq \operatorname{rank}(A)+\operatorname{rank}(B)-n. ]

Addition satisfies the subadditivity relation

[ \operatorname{rank}(A+B) \leq \operatorname{rank}(A)+\operatorname{rank}(B). ]

This follows because every column of (A+B) is the sum of a vector from the column space of (A) and a vector from the column space of (B). Accordingly, the column space of (A+B) lies inside the sum of those two subspaces.

For a block diagonal matrix,

[ M= \begin{pmatrix} A&0\ 0&B \end{pmatrix}, ]

the two blocks act on independent coordinate subspaces, which gives

[ \operatorname{rank}(M)

\operatorname{rank}(A)+\operatorname{rank}(B). ]

Rank is unchanged by multiplication by a nonzero scalar. Over a field, if (\lambda\neq 0), then

[ \operatorname{rank}(\lambda A)=\operatorname{rank}(A). ]

Full rank and invertibility

For a square matrix (A\in F^{n\times n}), the following conditions are equivalent:

[ \operatorname{rank}(A)=n, ]

[ \det(A)\neq 0, ]

and

[ A^{-1}\text{ exists}. ]

These conditions also imply that the associated linear transformation is both injective and surjective. Their equivalence forms part of the invertible matrix theorem.

For a rectangular matrix, full rank has two different interpretations. An (m\times n) matrix with (m\geq n) has full column rank when its rank is (n), in which case the associated map (F^n\to F^m) is injective. If (m\leq n), full row rank means that the rank is (m), in which case the associated map is surjective.

Rank factorization

A matrix (A) of rank (r) admits a rank factorization

[ A=BC, ]

where (B) is an (m\times r) matrix of full column rank and (C) is an (r\times n) matrix of full row rank. The columns of (B) may be chosen as a basis of the column space of (A), after which the columns of (C) record the coordinates of the columns of (A) relative to that basis.

The intermediate dimension (r) is minimal. If another factorization

[ A=DE ]

passes through a vector space of dimension (s), then

[ \operatorname{rank}(A)\leq s. ]

Consequently, rank is the smallest dimension through which the linear transformation represented by (A) can factor.

A matrix of rank one has the form

[ A=uv^{\mathsf T} ]

for nonzero column vectors (u) and (v). Every nonzero column is then a scalar multiple of (u), and every nonzero row is a scalar multiple of (v^{\mathsf T}). A rank-(r) matrix can correspondingly be written as a sum of (r) rank-one matrices, while no expression with fewer rank-one summands exists.

Dependence on the scalar field

Rank can depend on the field over which a matrix is interpreted. For a matrix with integer entries, a minor that is nonzero over the rational numbers may become zero after reduction modulo a prime. Thus the same array can have one rank over (\mathbb Q) and a smaller rank over a finite field.

For example,

[ A= \begin{pmatrix} 1&0\ 0&2 \end{pmatrix} ]

has rank (2) over (\mathbb Q). Over the field (\mathbb F_2), the same entries represent

[ \begin{pmatrix} 1&0\ 0&0 \end{pmatrix}, ]

which has rank (1).

The field qualification is essential because the standard equivalence between row rank, column rank, determinantal rank, and image dimension relies on vector-space structure. Over a general ring, several nonequivalent notions of rank occur, and module-theoretic analogues require additional hypotheses.

Numerical rank

In exact algebra, rank is determined by whether specified quantities are exactly zero. In numerical linear algebra, floating-point data usually contain perturbations, so exact vanishing is not stable under representation or measurement error.

The singular value decomposition expresses a real or complex matrix as

[ A=U\Sigma V^\ast, ]

where (U) and (V) are unitary matrices and (\Sigma) is diagonal apart from its rectangular shape. The exact rank equals the number of nonzero singular values. Numerical rank replaces exact nonzero status with a threshold determined by the scale of the matrix and the error model.

Small singular values identify directions that are strongly attenuated by the associated linear map. Their presence explains why matrices having full exact rank can behave similarly to lower-rank matrices under finite-precision computation.

Distinction from other notions of rank

Matrix rank should not be identified with tensor rank. A matrix is a tensor of order two, for which row rank, column rank, and the minimum number of rank-one summands coincide. For tensors of higher order, the minimum number of decomposable summands has substantially different algebraic behavior and need not admit an analogue of Gaussian elimination.

The term also differs from the rank of a free module, although both notions are based on the cardinality of a basis. Matrix rank over a field measures the dimension of an image, whereas module rank over a ring depends on the structure of the ring and on whether the module possesses an appropriate basis.