Row rank equals column rank

Theorem

Row rank equals column rank

T-140Home MU-103Threads structure

Statement

Let \( F \) be a field, let \( m, n \ge 1 \) be integers, and let \( A = (a_{ij}) \in F^{m \times n} \) be a matrix with \( m \) rows \( \rho_1, \dots, \rho_m \in F^n \) and \( n \) columns \( \alpha_1, \dots, \alpha_n \in F^m \). Write \( \operatorname{Row}(A) = \operatorname{span}_F(\rho_1, \dots, \rho_m) \subseteq F^n \) for the row space and \( \operatorname{Col}(A) = \operatorname{span}_F(\alpha_1, \dots, \alpha_n) \subseteq F^m \) for the column space. Then these two subspaces — which live in different vector spaces and generally have different ambient dimensions — have the same dimension: \[ \dim_F \operatorname{Row}(A) \;=\; \dim_F \operatorname{Col}(A). \] The common value is called the rank of \( A \), written \( \operatorname{rank} A \), and consequently \( \operatorname{rank} A = \operatorname{rank} A^{\mathsf{T}} \). No hypothesis whatever is placed on \( F \) (it may be finite, of any characteristic, unordered, with no inner product available) and none on the shape of \( A \).

Why it matters

Rank is the single most-used number attached to a matrix, and this theorem is what makes it one number rather than two. Every practical computation of rank is a row computation: Gaussian elimination sweeps rows, and the count of pivots is by construction the dimension of the row space. Almost every application, however, is a column statement: \( Ax = b \) is solvable exactly when \( b \) lies in the column space; the image of the linear map \( x \mapsto Ax \) is the column space; the free-parameter count in the general solution is \( n - \dim \operatorname{Col}(A) \) by the rank–nullity theorem. Without the identity proved here, the number produced by elimination would have no right to be substituted into any of those statements.

The identity is also the first appearance of a deep structural symmetry: a matrix and its transpose carry the same amount of linear information. That symmetry propagates upward into the duality between a linear map and its adjoint, into the equality of the ranks of the two flattenings of a bilinear form, into the fact that \( \operatorname{rank}(AB) \le \min(\operatorname{rank} A, \operatorname{rank} B) \) (one bound comes from columns, the other from rows, and only this theorem lets them be compared), and into the definition of rank as the minimal inner dimension of a factorisation \( A = CB \) — the object that low-rank approximation, matrix completion and principal component analysis all manipulate.

Hypotheses

The entries lie in a field (or a division ring).The proof chooses a basis of the column space and solves for coordinates, which needs division by nonzero scalars, and it needs dimension to be a well-defined invariant (see invariance of dimension). Over a ring lacking the invariant basis number property — for instance \( R = \operatorname{End}_{\mathbb{Q}}(V) \) with \( V \) of countably infinite dimension, where \( R \cong R \oplus R \) as left \( R \)-modules — a free module has bases of size \( 1 \) and of size \( 2 \), so “the number of independent rows” is not a number at all.

\( A \) has finitely many rows and finitely many columns.Both ranks are then finite and bounded by \( \min(m,n) \). For matrices indexed by infinite sets the two cardinals genuinely differ: see “Fails without” for a matrix whose row rank is \( 2^{\aleph_0} \) and whose column rank is at most \( \aleph_0 \).

Both dimensions are taken over the same field \( F \), with finite linear combinations.Rank is field-relative. The \( 1 \times 1 \) complex matrix \( (\,i\,) \) has rank \( 1 \) over \( \mathbb{C} \); its realification \( \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} \) has rank \( 2 \) over \( \mathbb{R} \). Both counts are correct for their own field, and comparing one with the other proves nothing. (Rank is, however, unchanged by enlarging the field: see the corollaries.)

Proof

Write \( r = \dim \operatorname{Col}(A) \) and \( s = \dim \operatorname{Row}(A) \). The whole argument is one inequality — row rank \( \le \) column rank, for every matrix over every field — applied twice: once to \( A \) and once to \( A^{\mathsf{T}} \). The mechanism is a factorisation \( A = CB \) through a space of dimension \( r \): read columnwise it is the definition of \( r \), and read rowwise it bounds \( s \).

\( \operatorname{Col}(A) \) is a subspace of \( F^m \) spanned by the \( n \) columns, so it is finite-dimensional with \[ r \;=\; \dim \operatorname{Col}(A) \;\le\; \min(m, n). \] Fix a basis \( c_1, \dots, c_r \in F^m \) of \( \operatorname{Col}(A) \).

A span of finitely many vectors is a subspace, and a spanning set of size \( n \) contains a basis, giving \( r \le n \); the subspace sits inside \( F^m \), giving \( r \le m \). Every finite-dimensional space has a basis. If \( A = 0 \) then \( r = 0 \) and the basis is empty; the argument below reads correctly with empty sums. A

Each column \( \alpha_j \) lies in \( \operatorname{Col}(A) \), so there are unique scalars \( b_{1j}, \dots, b_{rj} \in F \) with \[ \alpha_j \;=\; \sum_{i=1}^{r} b_{ij}\, c_i, \qquad j = 1, \dots, n. \] Collect them: \( C = \big(\, c_1 \mid c_2 \mid \cdots \mid c_r \,\big) \in F^{m \times r} \) and \( B = (b_{ij}) \in F^{r \times n} \).

Existence of the coefficients is the spanning property of a basis; uniqueness is its linear independence. This is where the field is used: coordinates relative to a basis exist because nonzero scalars are invertible. A

\[ A \;=\; C B. \] Indeed, comparing the \( k \)-th entry of the \( j \)-th column, \[ a_{kj} \;=\; (\alpha_j)_k \;=\; \sum_{i=1}^{r} b_{ij} \, (c_i)_k \;=\; \sum_{i=1}^{r} C_{ki} B_{ij} \;=\; (CB)_{kj}. \]

Step 2 read one coordinate at a time, together with the definition of the matrix product. Note the inner dimension is exactly \( r \): the factorisation routes every column of \( A \) through an \( r \)-dimensional space. A

Now read \( A = CB \) one row at a time. Let \( \beta_1, \dots, \beta_r \in F^n \) be the rows of \( B \). For each \( k \), \[ \rho_k \;=\; \sum_{i=1}^{r} C_{ki}\, \beta_i, \] so \( \operatorname{Row}(A) \subseteq \operatorname{span}_F(\beta_1, \dots, \beta_r) \) and therefore \[ s \;=\; \dim \operatorname{Row}(A) \;\le\; r \;=\; \dim \operatorname{Col}(A). \]

The \( j \)-th entry of the \( k \)-th row of \( CB \) is \( \sum_i C_{ki} B_{ij} \), which is the \( j \)-th entry of \( \sum_i C_{ki} \beta_i \); the identity therefore holds coordinatewise. A subspace contained in a span of \( r \) vectors has dimension at most \( r \). This is the whole idea: one factorisation, two readings. B

Steps 1–4 used nothing about \( A \) beyond its being a matrix over a field, so they apply verbatim to \( A^{\mathsf{T}} \in F^{n \times m} \). Transposition exchanges rows with columns, \[ \operatorname{Row}(A^{\mathsf{T}}) = \operatorname{Col}(A), \qquad \operatorname{Col}(A^{\mathsf{T}}) = \operatorname{Row}(A), \] so the inequality for \( A^{\mathsf{T}} \) reads \( r \le s \).

The \( i \)-th row of \( A^{\mathsf{T}} \) is the \( i \)-th column of \( A \) written horizontally, and the linear-independence relations among a list of tuples do not depend on whether the tuples are written as rows or columns; so the two spans have equal dimension. Applying a proved general statement to a second matrix is legitimate precisely because no hypothesis in Steps 1–4 mentioned the shape of \( A \). B

\[ s \le r \quad \text{and} \quad r \le s \qquad \Longrightarrow \qquad \dim \operatorname{Row}(A) = \dim \operatorname{Col}(A). \qquad \blacksquare \]

Antisymmetry of \( \le \) on the natural numbers. A

The symmetry can be made structural rather than accidental. Define \( \operatorname{rk}(A) \) to be the least \( r \) for which some factorisation \( A = CB \) with \( C \in F^{m\times r} \), \( B \in F^{r \times n} \) exists. Step 3 gives \( \operatorname{rk}(A) \le \dim \operatorname{Col}(A) \); conversely any factorisation \( A = CB \) forces \( \operatorname{Col}(A) \subseteq \operatorname{Col}(C) \), so \( \dim \operatorname{Col}(A) \le r \). Hence \( \operatorname{rk}(A) = \dim \operatorname{Col}(A) \), and Step 4 identically gives \( \operatorname{rk}(A) = \dim \operatorname{Row}(A) \). Since \[ A = CB \iff A^{\mathsf{T}} = B^{\mathsf{T}} C^{\mathsf{T}}, \] the quantity \( \operatorname{rk} \) is visibly transpose-invariant.

The two inclusions bracket the minimal inner dimension between the same pair of numbers from both sides; the displayed equivalence is the anti-multiplicativity of transposition, \( (CB)^{\mathsf{T}} = B^{\mathsf{T}} C^{\mathsf{T}} \), which is checked entrywise. This reformulation explains why the theorem is true: rank is a property of the factorisations of \( A \), and the set of factorisations is symmetric under transposition, while “row space” and “column space” individually are not. C

Result

\[ \dim_F \operatorname{Row}(A) \;=\; \dim_F \operatorname{Col}(A) \;=:\; \operatorname{rank} A \;=\; \operatorname{rank} A^{\mathsf{T}} \;\le\; \min(m,n) \]

Reading. The number of independent rows of a matrix equals the number of independent columns, even though the rows are vectors of length \( n \) and the columns are vectors of length \( m \). Equivalently: rank is the smallest \( r \) for which \( A \) factors through \( F^r \), and factorisations survive transposition.

Scope. Any finite matrix over any field or division ring; no positivity, ordering, inner product or characteristic assumption is used, so the proof runs unchanged over \( \mathbb{Q} \), \( \mathbb{R} \), \( \mathbb{C} \), \( \mathbb{F}_p \) and \( \mathbb{F}_p(t) \). It extends to matrices over an integral domain by passing to the field of fractions. It fails for matrices indexed by infinite sets and is meaningless over rings without invariant basis number.

Corollaries & converses

Transpose invariance. \( \operatorname{rank} A = \operatorname{rank} A^{\mathsf{T}} \), and over \( \mathbb{C} \) also \( \operatorname{rank} A = \operatorname{rank} \overline{A} = \operatorname{rank} A^{\dagger} \), since conjugation is a field automorphism and preserves independence.
Rank factorisation. Every \( A \) of rank \( r \ge 1 \) factors as \( A = CB \) with \( C \in F^{m\times r} \) of rank \( r \) and \( B \in F^{r\times n} \) of rank \( r \), and \( r \) is the least possible inner dimension. Equivalently \( A = \sum_{i=1}^{r} c_i \beta_i \) is a sum of \( r \) rank-one matrices, and no shorter such sum exists.
What elimination computes. Row operations preserve \( \operatorname{Row}(A) \) and \( \{x : Ax = 0\} \), so the pivot count of any echelon form equals \( \operatorname{rank} A \). Moreover the columns of the original \( A \) in the pivot positions form a basis of \( \operatorname{Col}(A) \).
The four fundamental subspaces. With \( r = \operatorname{rank} A \): \( \dim \operatorname{Col}(A) = r \), \( \dim \operatorname{Row}(A) = r \), \( \dim \ker A = n - r \) and \( \dim \ker A^{\mathsf{T}} = m - r \), by rank–nullity applied to \( A \) and to \( A^{\mathsf{T}} \).
Products. \( \operatorname{rank}(AB) \le \min(\operatorname{rank} A, \operatorname{rank} B) \): the bound by \( \operatorname{rank} A \) comes from \( \operatorname{Col}(AB) \subseteq \operatorname{Col}(A) \), the bound by \( \operatorname{rank} B \) from \( \operatorname{Row}(AB) \subseteq \operatorname{Row}(B) \). The two bounds are statements about different spaces and can only be combined because this theorem identifies the two counts.
Determinantal rank. \( \operatorname{rank} A \) equals the largest \( k \) for which some \( k \times k \) submatrix of \( A \) is invertible (equivalently, has nonzero determinant). See Problem 5.
Invariance under field extension. If \( F \subseteq K \) is a field extension and \( A \in F^{m\times n} \), then \( \operatorname{rank}_F A = \operatorname{rank}_K A \): the determinantal characterisation involves the same finitely many determinants in either field. Note this is not a statement about reduction modulo a prime, which can drop the rank.
Sharpness (converse direction). For every \( r \) with \( 0 \le r \le \min(m,n) \) there is an \( A \in F^{m\times n} \) of rank exactly \( r \) — take \( r \) ones on the diagonal and zeros elsewhere — so no relation beyond \( \operatorname{rank} A \le \min(m,n) \) constrains the common value.
Canonical form. Consequently \( A = P \begin{pmatrix} I_r & 0 \\ 0 & 0 \end{pmatrix} Q \) for invertible \( P \in F^{m\times m} \), \( Q \in F^{n\times n} \); rank is the unique invariant of a matrix under \( A \mapsto PAQ \).

Fails without

Finitely many rows and columns dropped: let \( F = \mathbb{Q} \) and let \( H \) be a Hamel basis of the \( \mathbb{Q} \)-vector space \( \mathbb{Q}^{\mathbb{N}} \) of all rational sequences, so \( |H| = 2^{\aleph_0} \). Build a matrix with rows indexed by \( H \) and columns indexed by \( \mathbb{N} \), the row labelled \( h \) being the sequence \( h \) itself. Its row space is all of \( \mathbb{Q}^{\mathbb{N}} \), of dimension \( 2^{\aleph_0} \), while its column space is spanned by only \( \aleph_0 \) columns and so has dimension at most \( \aleph_0 \). Row rank and column rank are then different cardinals. (The finite-rank case survives: if either rank is finite the factorisation argument of Steps 1–4 still applies and the two agree.)
The field dropped for a ring without invariant basis number: over \( R = \operatorname{End}_{\mathbb{Q}}(V) \) with \( \dim_{\mathbb{Q}} V = \aleph_0 \), the left module \( R \) has a basis of one element, \( \{\mathrm{id}\} \), and also a basis of two elements (split \( V \cong V \oplus V \) and take the two induced projections). The \( 1\times 1 \) matrix \( (\mathrm{id}) \) therefore has “one independent row” and “two independent rows” simultaneously; no count on either side is well defined, so there is nothing left for the theorem to assert.
A popular proof fails without an ordered field, even though the theorem does not: the argument “\( x \mapsto Ax \) maps \( \operatorname{Row}(A) \) isomorphically onto \( \operatorname{Col}(A) \)” needs \( \operatorname{Row}(A) \cap \ker A = \{0\} \), which is proved by writing such an \( x \) as \( x = A^{\mathsf{T}} y \) and computing \( \lVert x \rVert^{2} = x^{\mathsf{T}} x = y^{\mathsf{T}} A x = 0 \); the conclusion \( x = 0 \) then needs \( \lVert x \rVert^{2} = 0 \Rightarrow x = 0 \), which is available only over \( \mathbb{R} \) (or a formally real field). Over \( \mathbb{F}_2 \) take \( A = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} \): then \( \operatorname{Row}(A) = \ker A = \operatorname{span}\{(1,1)\} \), the restriction of \( A \) to the row space is the zero map, and the proof collapses. The theorem itself is still true here (both ranks are \( 1 \)) — which is exactly why the factorisation proof above, which never mentions a norm, is the one to learn.

Common errors

“Elimination preserves the column space, so the pivot columns of the echelon form are a basis of \( \operatorname{Col}(A) \).” Row operations change the column space. For \( A = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} \) over \( \mathbb{Q} \) the echelon form is \( \begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix} \), whose column space is \( \operatorname{span}\{(1,0)^{\mathsf{T}}\} \) — not \( \operatorname{span}\{(1,1)^{\mathsf{T}}\} = \operatorname{Col}(A) \). Elimination locates the pivot positions; the basis must then be read off the original columns.
“For an \( m \times n \) matrix, \( \operatorname{rank} A + \dim \ker A = m \).” Rank–nullity counts the domain, so the total is \( n \), the number of columns. The number \( m - \operatorname{rank} A \) is the count of zero rows in an echelon form, which is \( \dim \ker A^{\mathsf{T}} \), a different subspace of a different space.
“Rank is the same over \( \mathbb{Q} \) and over \( \mathbb{F}_p \).” Rank is invariant under enlarging the field, not under reducing the entries. \( \begin{pmatrix} 1 & 0 \\ 0 & 3 \end{pmatrix} \) has rank \( 2 \) over \( \mathbb{Q} \) and rank \( 1 \) over \( \mathbb{F}_3 \).
“The row space and the column space are equal, or at least isomorphic in a canonical way.” They are subspaces of \( F^n \) and \( F^m \) respectively; for \( m \ne n \) they cannot even be compared as sets. Equal dimension is all that is claimed, and no basis-free isomorphism between them exists over a general field.
“\( \operatorname{rank}(A+B) = \operatorname{rank} A + \operatorname{rank} B \).” Only \( \le \) holds. With \( A = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} \) and \( B = -A \), the left side is \( 0 \) and the right side is \( 2 \); with \( B = \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix} \) the left side is \( 2 \) and equality does hold, so no fixed relation is available.
“A matrix of rank \( r \) has an invertible \( r \times r \) submatrix in its top-left corner.” The rows and columns must be chosen. \( \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix} \) has rank \( 1 \), yet its top-left \( 1 \times 1 \) submatrix is \( (0) \).

Discussion

The statement looks harmless and is not. The row space lives in \( F^n \), the column space in \( F^m \); there is no map between them supplied by the data, and for \( m \ne n \) they are not even subspaces of the same space. What the proof exhibits is not an isomorphism but a common measurement: the least \( r \) such that \( A \) can be routed through \( F^r \). Once rank is defined that way — \( \operatorname{rank} A = \min \{ r : A = CB, \ C \in F^{m\times r}, B \in F^{r\times n} \} \) — the theorem is nearly a tautology, because \( A = CB \) if and only if \( A^{\mathsf{T}} = B^{\mathsf{T}} C^{\mathsf{T}} \), so the set of admissible inner dimensions is identical for \( A \) and \( A^{\mathsf{T}} \). Step 7 above is exactly this observation, and it is the version worth remembering.

Many textbooks instead prove the theorem over \( \mathbb{R} \) by showing that \( x \mapsto Ax \) restricts to an isomorphism \( \operatorname{Row}(A) \to \operatorname{Col}(A) \). That proof is geometrically appealing and genuinely useful — it is the germ of the singular value decomposition, in which \( A = U \Sigma V^{\mathsf{T}} \) exhibits orthonormal bases of \( \operatorname{Row}(A) \) and \( \operatorname{Col}(A) \) paired by the singular values \( \sigma_1 \ge \dots \ge \sigma_r \gt 0 \), whose number is the rank. But it uses positive-definiteness of the dot product to conclude \( \operatorname{Row}(A) \cap \ker A = \{0\} \), and over \( \mathbb{F}_2 \) that intersection can be everything (see “Fails without”). A theorem that holds over every field deserves a proof that uses no field-specific structure, and the factorisation proof uses only the existence of coordinates.

The transpose symmetry has a coordinate-free reading. If \( T : V \to W \) is linear between finite-dimensional spaces, its dual \( T^{*} : W^{*} \to V^{*} \) is defined by \( T^{*}(f) = f \circ T \), and a matrix of \( T^{*} \) in dual bases is the transpose of a matrix of \( T \). The theorem then says \( \dim \operatorname{im} T = \dim \operatorname{im} T^{*} \). In this language the row space of \( A \) is precisely the annihilator of \( \ker A \) inside \( (F^n)^{*} \cong F^n \) — the set of linear functionals vanishing on every solution of \( Ax = 0 \) — which is the real reason elimination, a procedure that manipulates only equations, computes a number about images. It is also the reason the theorem is stable under enlarging the field: annihilators and images are defined by finitely many linear conditions with coefficients in \( F \).

Two boundaries are worth marking. First, the result is a genuine feature of order-two tensors: a matrix has one rank, whereas a three-way array \( T \in F^{n_1 \times n_2 \times n_3} \) has three flattening ranks that need not agree, and its tensor rank (least number of rank-one summands) can exceed all of them — the tidy identity of this page has no order-three analogue. Second, the passage from a field to a commutative ring is subtle but not hopeless: over an integral domain \( D \) one embeds \( D \) in its field of fractions and the theorem survives verbatim, which is why an integer matrix has a single well-defined rank; over a general commutative ring one abandons dimension for determinantal rank and works with the ideals generated by the \( k \times k \) minors (the Fitting ideals), which is the correct home for the statement in commutative algebra. Numerically, meanwhile, rank is discontinuous — \( \begin{pmatrix} 1 & 0 \\ 0 & \varepsilon \end{pmatrix} \) has rank \( 2 \) for every \( \varepsilon \neq 0 \) and rank \( 1 \) at \( \varepsilon = 0 \) — so floating-point work replaces the exact count by the number of singular values above a tolerance, and the Eckart–Young theorem guarantees that truncating the singular value decomposition gives the best approximation of each lower rank.

Common misconceptions. The theorem does not say the row space and column space coincide (they generally live in different spaces); it does not say elimination preserves the column space (it does not); it does not make rank independent of the field of entries (only independent of enlarging that field); and it does not assert any canonical pairing of a basis of \( \operatorname{Row}(A) \) with a basis of \( \operatorname{Col}(A) \) — such a pairing exists over \( \mathbb{R} \) via the singular value decomposition, but it is extra structure, not part of this statement.

Worked examples

Example 1 (both ranks computed independently, and the factorisation exhibited). Over \( \mathbb{Q} \) let \[ A = \begin{pmatrix} 1 & 2 & -1 & 3 \\ 2 & 4 & 1 & 0 \\ 3 & 6 & 0 & 3 \end{pmatrix} \in \mathbb{Q}^{3\times 4}. \] Compute \( \dim \operatorname{Row}(A) \) by elimination and \( \dim \operatorname{Col}(A) \) directly, then write down the rank factorisation \( A = CB \) predicted by the proof.

Row-reduce with \( R_2 \mapsto R_2 - 2R_1 \) and \( R_3 \mapsto R_3 - 3R_1 \), then \( R_3 \mapsto R_3 - R_2 \): \[ \begin{pmatrix} 1 & 2 & -1 & 3 \\ 0 & 0 & 3 & -6 \\ 0 & 0 & 3 & -6 \end{pmatrix} \longrightarrow \begin{pmatrix} 1 & 2 & -1 & 3 \\ 0 & 0 & 3 & -6 \\ 0 & 0 & 0 & 0 \end{pmatrix}. \] Two nonzero rows, pivots in columns \( 1 \) and \( 3 \), so \( \dim \operatorname{Row}(A) = 2 \).

Elementary row operations are invertible and replace each row by a combination of rows, so they preserve the row space; the nonzero rows of an echelon form are independent because each has a leading entry in a column where the later rows vanish. A

Now work with the columns of the original matrix. Write \( \alpha_1 = (1,2,3)^{\mathsf{T}} \), \( \alpha_2 = (2,4,6)^{\mathsf{T}} \), \( \alpha_3 = (-1,1,0)^{\mathsf{T}} \), \( \alpha_4 = (3,0,3)^{\mathsf{T}} \). Then \[ \alpha_2 = 2\alpha_1, \qquad \alpha_4 = 1\cdot\alpha_1 + (-2)\cdot\alpha_3, \] as the coordinates confirm: \( 2(1,2,3) = (2,4,6) \) and \( (1,2,3) - 2(-1,1,0) = (3,0,3) \).

Direct verification, coordinate by coordinate. These two relations show \( \operatorname{Col}(A) = \operatorname{span}(\alpha_1, \alpha_3) \), so \( \dim \operatorname{Col}(A) \le 2 \). A

\( \alpha_1, \alpha_3 \) are independent: \( x\,(1,2,3)^{\mathsf{T}} + y\,(-1,1,0)^{\mathsf{T}} = 0 \) gives \( 3x = 0 \) from the third coordinate, hence \( x = 0 \), and then \( y = 0 \) from the first. So \( \dim \operatorname{Col}(A) = 2 \), matching Step 1.

Definition of linear independence, solved from the coordinate that involves only one unknown. The two computations — one on rows, one on columns — were carried out with no reference to each other, and agree, as the theorem requires. B

Take \( c_1 = \alpha_1 \), \( c_2 = \alpha_3 \) as the basis of the column space. Reading off the coordinates of \( \alpha_1, \alpha_2, \alpha_3, \alpha_4 \) in that basis gives \[ C = \begin{pmatrix} 1 & -1 \\ 2 & 1 \\ 3 & 0 \end{pmatrix}, \qquad B = \begin{pmatrix} 1 & 2 & 0 & 1 \\ 0 & 0 & 1 & -2 \end{pmatrix}, \qquad A = CB. \]

Column \( j \) of \( B \) is the coordinate vector of \( \alpha_j \): \( \alpha_1 = c_1 \), \( \alpha_2 = 2c_1 \), \( \alpha_3 = c_2 \), \( \alpha_4 = c_1 - 2c_2 \). Multiplying out reproduces \( A \). B

Read the same factorisation by rows: with \( \beta_1 = (1,2,0,1) \) and \( \beta_2 = (0,0,1,-2) \), \[ \rho_1 = \beta_1 - \beta_2 = (1,2,-1,3), \quad \rho_2 = 2\beta_1 + \beta_2 = (2,4,1,0), \quad \rho_3 = 3\beta_1 = (3,6,0,3), \] the coefficients being exactly the rows of \( C \).

This is Step 4 of the proof made explicit: two vectors \( \beta_1, \beta_2 \) span all three rows, which is why the row rank cannot exceed \( 2 \). Note that \( \beta_1, \beta_2 \) are not rows of \( A \); they are rows of the echelon form, and they span the same row space. B

\[ \dim \operatorname{Row}(A) = \dim \operatorname{Col}(A) = \operatorname{rank} A = 2, \qquad A = \begin{pmatrix} 1 & -1 \\ 2 & 1 \\ 3 & 0 \end{pmatrix} \begin{pmatrix} 1 & 2 & 0 & 1 \\ 0 & 0 & 1 & -2 \end{pmatrix} \]

Reading. Three rows of length four and four columns of length three; both lists carry exactly two independent directions, and the single \( 3\times 2 \) by \( 2\times 4 \) factorisation certifies both counts at once.

Scope. The recipe is general: row-reduce to find the pivot columns, take those columns of the original matrix as \( C \), and take the nonzero rows of the reduced row echelon form as \( B \).

Example 2 (rank of a dimension matrix, and the count of dimensionless groups). A fluid-mechanics problem involves the density \( \rho \), a flow speed \( v \), a length \( L \) and the dynamic viscosity \( \mu \). In the base units mass (kg), length (m), time (s), their dimensions are \( \rho : \mathrm{kg}\,\mathrm{m}^{-3} \), \( v : \mathrm{m}\,\mathrm{s}^{-1} \), \( L : \mathrm{m} \), \( \mu : \mathrm{kg}\,\mathrm{m}^{-1}\mathrm{s}^{-1} \). Form the \( 3\times 4 \) exponent matrix \( D \), find its rank both ways, and use \( n - \operatorname{rank} D \) to count the independent dimensionless groups. Then evaluate the group for water at \( 20\,{}^{\circ}\mathrm{C} \) flowing at \( v = 0.50\ \mathrm{m}\,\mathrm{s}^{-1} \) through a pipe of diameter \( L = 0.10\ \mathrm{m} \), using the standard tabulated values \( \rho = 998\ \mathrm{kg}\,\mathrm{m}^{-3} \) and \( \mu = 1.002\times 10^{-3}\ \mathrm{Pa}\,\mathrm{s} \).

Rows indexed by \( (\mathrm{kg}, \mathrm{m}, \mathrm{s}) \), columns by \( (\rho, v, L, \mu) \): \[ D = \begin{pmatrix} 1 & 0 & 0 & 1 \\ -3 & 1 & 1 & -1 \\ 0 & -1 & 0 & -1 \end{pmatrix}. \]

Each column records the exponents of kg, m, s in that quantity's dimension; e.g. \( \mu \) has dimensions \( \mathrm{kg}\,\mathrm{m}^{-1}\mathrm{s}^{-1} \), giving the column \( (1,-1,-1)^{\mathsf{T}} \). A product \( \rho^{p} v^{q} L^{t} \mu^{u} \) is dimensionless exactly when \( D\,(p,q,t,u)^{\mathsf{T}} = 0 \). A

Row rank: \( R_2 \mapsto R_2 + 3R_1 \) then \( R_3 \mapsto R_3 + R_2 \) give \[ \begin{pmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & 1 & 1 \end{pmatrix}, \] three nonzero rows, so \( \dim \operatorname{Row}(D) = 3 \).

Elimination with pivots in columns \( 1, 2, 3 \); the echelon rows are independent by their leading entries. A

Column rank, computed independently: the three columns \( \alpha_1 = (1,-3,0)^{\mathsf{T}} \), \( \alpha_2 = (0,1,-1)^{\mathsf{T}} \), \( \alpha_3 = (0,1,0)^{\mathsf{T}} \) satisfy \[ \det \begin{pmatrix} 1 & 0 & 0 \\ -3 & 1 & 1 \\ 0 & -1 & 0 \end{pmatrix} = 1\cdot\big(1\cdot 0 - 1\cdot(-1)\big) = 1 \neq 0, \] so they are independent and span \( \mathbb{R}^3 \); hence \( \dim \operatorname{Col}(D) = 3 \), agreeing with Step 2.

A square matrix with nonzero determinant has independent columns; three independent vectors in \( \mathbb{R}^3 \) span it, and no more than \( 3 \) columns can be independent there. B

By rank–nullity applied to \( D \) with \( n = 4 \) columns, \[ \dim \ker D = 4 - \operatorname{rank} D = 4 - 3 = 1. \] Solving \( D\,(p,q,t,u)^{\mathsf{T}} = 0 \) from the echelon form with \( u \) free gives \( t = -u \), \( q = -u \), \( p = -u \), so the kernel is spanned by \( (p,q,t,u) = (1,1,1,-1) \).

From the echelon form: row 3 gives \( t + u = 0 \), row 2 gives \( q + t + 2u = 0 \), hence \( q = -u \), and row 1 gives \( p + u = 0 \). Setting \( u = -1 \) clears signs. Check directly in \( D \): kg: \( 1 - 1 = 0 \); m: \( -3 + 1 + 1 + 1 = 0 \); s: \( -1 + 1 = 0 \). B

The unique (up to powers) dimensionless group is therefore the Reynolds number \[ \Pi = \rho^{1} v^{1} L^{1} \mu^{-1} = \frac{\rho v L}{\mu}. \] With the stated values, \[ \Pi = \frac{(998\ \mathrm{kg}\,\mathrm{m}^{-3})(0.50\ \mathrm{m}\,\mathrm{s}^{-1})(0.10\ \mathrm{m})}{1.002\times 10^{-3}\ \mathrm{Pa}\,\mathrm{s}} = \frac{49.9\ \mathrm{kg}\,\mathrm{m}^{-1}\mathrm{s}^{-1}}{1.002\times 10^{-3}\ \mathrm{kg}\,\mathrm{m}^{-1}\mathrm{s}^{-1}} \approx 4.98\times 10^{4}. \]

Symbols first: the kernel vector gives the exponents, and only then are numbers substituted. The unit check is the content of Step 4: \( 1\ \mathrm{Pa}\,\mathrm{s} = 1\ \mathrm{kg}\,\mathrm{m}^{-1}\mathrm{s}^{-1} \), so numerator and denominator carry identical units and \( \Pi \) is a pure number, as the kernel computation promised. B

\[ \operatorname{rank} D = 3, \qquad \dim \ker D = 1, \qquad \Pi = \frac{\rho v L}{\mu} \approx 4.98 \times 10^{4} \]

Reading. The row computation counts independent base units actually used (three: kg, m, s); the column computation counts independent dimensions among the four quantities. The theorem says these are the same number, and only then does “\( 4 - 3 = 1 \) dimensionless group” make sense: the count subtracts a row-derived rank from a column count.

Scope. This is the linear-algebra half of the Buckingham \( \pi \) theorem for any list of quantities in any system of base units; the values quoted are the standard ones for liquid water at \( 20\,{}^{\circ}\mathrm{C} \) and \( 1\ \mathrm{atm} \). \( \Pi \approx 5\times 10^{4} \) is well above the pipe-flow transition near \( 2300 \), so the flow is turbulent.

Problems

For \( A = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \\ 1 & 0 & 1 \end{pmatrix} \) over \( \mathbb{Q} \), compute the row rank and the column rank separately, exhibiting one explicit dependency on each side.
Solution

Rows: \( \rho_2 = 2\rho_1 \), an explicit dependency, so \( \dim \operatorname{Row}(A) \le 2 \). The remaining rows \( \rho_1 = (1,2,3) \) and \( \rho_3 = (1,0,1) \) are independent: \( x(1,2,3) + y(1,0,1) = 0 \) gives \( 2x = 0 \) from the second coordinate, so \( x = 0 \), then \( y = 0 \). Hence \( \dim \operatorname{Row}(A) = 2 \).

Columns: \( \alpha_1 = (1,2,1)^{\mathsf{T}} \), \( \alpha_2 = (2,4,0)^{\mathsf{T}} \), \( \alpha_3 = (3,6,1)^{\mathsf{T}} \). Here \( \alpha_1 + \alpha_2 = (3,6,1)^{\mathsf{T}} = \alpha_3 \), an explicit dependency, so \( \dim \operatorname{Col}(A) \le 2 \). And \( \alpha_1, \alpha_2 \) are independent: \( x(1,2,1) + y(2,4,0) = 0 \) gives \( x = 0 \) from the third coordinate and then \( 2y = 0 \). Hence \( \dim \operatorname{Col}(A) = 2 \).

Both counts are \( 2 \), as the theorem requires; note the dependencies are quite different in shape (\( \rho_2 = 2\rho_1 \) versus \( \alpha_3 = \alpha_1 + \alpha_2 \)), which is why the equality of the two counts is a theorem and not an observation.
Let \( A \in F^{m\times n} \) and \( B \in F^{n\times p} \). Prove \( \operatorname{rank}(AB) \le \min(\operatorname{rank} A, \operatorname{rank} B) \), stating where row rank equals column rank is used. Then give matrices for which the inequality is strict against both bounds simultaneously.
Solution

Each column of \( AB \) is \( A \) times the corresponding column of \( B \), hence lies in \( \operatorname{Col}(A) \); so \( \operatorname{Col}(AB) \subseteq \operatorname{Col}(A) \) and \( \dim \operatorname{Col}(AB) \le \dim \operatorname{Col}(A) \). Each row of \( AB \) is the corresponding row of \( A \) times \( B \), hence a linear combination of the rows of \( B \); so \( \operatorname{Row}(AB) \subseteq \operatorname{Row}(B) \) and \( \dim \operatorname{Row}(AB) \le \dim \operatorname{Row}(B) \).

The theorem enters twice: it lets the first inequality be written as \( \operatorname{rank}(AB) \le \operatorname{rank} A \) and the second as \( \operatorname{rank}(AB) \le \operatorname{rank} B \), i.e. it identifies the column-dimension bound and the row-dimension bound as bounds on the same quantity, which may then be combined into a minimum. Without it one would only have two incomparable statements about two different subspaces.

Strictness: take \( A = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} \) and \( B = \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix} \). Then \( \operatorname{rank} A = \operatorname{rank} B = 1 \), while \( AB = 0 \) has rank \( 0 \lt 1 \).
Let \( A \in \mathbb{R}^{m\times n} \). Prove \( \operatorname{rank}(A^{\mathsf{T}}A) = \operatorname{rank} A \). Then show the statement fails over \( \mathbb{F}_2 \) and over \( \mathbb{C} \) (with the plain, unconjugated transpose), and explain which hypothesis of your proof was lost.
Solution

Over \( \mathbb{R} \) it suffices to prove \( \ker(A^{\mathsf{T}}A) = \ker A \), since both matrices have \( n \) columns and rank–nullity then gives \( \operatorname{rank}(A^{\mathsf{T}}A) = n - \dim\ker(A^{\mathsf{T}}A) = n - \dim \ker A = \operatorname{rank} A \). One inclusion is immediate: \( Ax = 0 \Rightarrow A^{\mathsf{T}}Ax = 0 \). Conversely, if \( A^{\mathsf{T}}Ax = 0 \) then \[ 0 = x^{\mathsf{T}}A^{\mathsf{T}}Ax = (Ax)^{\mathsf{T}}(Ax) = \lVert Ax \rVert^{2} = \sum_{k=1}^{m} (Ax)_k^{2}, \] and a sum of real squares vanishes only if every term does, so \( Ax = 0 \).

Over \( \mathbb{F}_2 \) take \( A = \begin{pmatrix} 1 \\ 1 \end{pmatrix} \), a \( 2\times 1 \) matrix of rank \( 1 \). Then \( A^{\mathsf{T}}A = (1 + 1) = (0) \), of rank \( 0 \). Over \( \mathbb{C} \) take \( A = \begin{pmatrix} 1 \\ i \end{pmatrix} \), again of rank \( 1 \); then \( A^{\mathsf{T}}A = (1 + i^{2}) = (0) \), of rank \( 0 \).

The lost hypothesis is positive-definiteness of the bilinear form \( \langle u, v\rangle = u^{\mathsf{T}}v \): over \( \mathbb{R} \) a sum of squares vanishes only when each term does, whereas over \( \mathbb{F}_2 \) and \( \mathbb{C} \) there are nonzero isotropic vectors with \( u^{\mathsf{T}}u = 0 \). Note that \( \operatorname{rank} A = \operatorname{rank} A^{\mathsf{T}} \) itself, the theorem of this page, remains true in all three cases — it is the extra identity involving the product that needs the real field. (Over \( \mathbb{C} \) the conjugate transpose repairs it: \( \operatorname{rank}(A^{\dagger}A) = \operatorname{rank} A \).)
Prove that for \( A \neq 0 \), \( \operatorname{rank} A \) equals the least \( r \) such that \( A = CB \) with \( C \in F^{m\times r} \) and \( B \in F^{r\times n} \), and equally the least \( r \) such that \( A \) is a sum of \( r \) matrices of rank \( 1 \). Deduce \( \operatorname{rank} A = \operatorname{rank} A^{\mathsf{T}} \) in one line.
Solution

Write \( r_0 = \dim \operatorname{Col}(A) \). Steps 1–3 of the proof construct a factorisation with inner dimension \( r_0 \), so the least admissible inner dimension is at most \( r_0 \). Conversely, if \( A = CB \) with \( C \in F^{m\times r} \), then every column of \( A \) is \( C \) times a column of \( B \), hence lies in \( \operatorname{Col}(C) \), a space of dimension at most \( r \); so \( r_0 \le r \). Therefore the least inner dimension is exactly \( r_0 = \operatorname{rank} A \).

For the rank-one form, write \( C = (c_1 \mid \dots \mid c_r) \) and let \( \beta_1, \dots, \beta_r \) be the rows of \( B \). Multiplying out, \( CB = \sum_{i=1}^{r} c_i \beta_i \), a sum of \( r \) matrices each of rank at most \( 1 \) (the columns of \( c_i\beta_i \) are all multiples of \( c_i \)). Conversely a sum of \( r \) rank-one matrices \( u_i v_i \) is \( UV \) with \( U = (u_1 \mid \dots \mid u_r) \) and \( V \) having rows \( v_i \), an inner dimension \( r \) factorisation. So the two minima coincide.

One-line deduction: \( A = CB \iff A^{\mathsf{T}} = B^{\mathsf{T}}C^{\mathsf{T}} \), and \( B^{\mathsf{T}} \in F^{n\times r} \), \( C^{\mathsf{T}} \in F^{r\times m} \); so \( A \) and \( A^{\mathsf{T}} \) admit factorisations of exactly the same inner dimensions, and their minima agree.
(Determinantal rank.) Let \( A \in F^{m\times n} \). Prove that \( \operatorname{rank} A \) equals the largest \( k \) for which some \( k\times k \) submatrix of \( A \) (choose any \( k \) rows and any \( k \) columns) is invertible. Verify the result on the matrix \( A \) of Example 1.
Solution

Let \( r = \operatorname{rank} A \) and let \( d \) be the largest size of an invertible square submatrix (with \( d = 0 \) if \( A = 0 \)).

\( d \ge r \). Choose \( r \) independent rows of \( A \) and let \( A' \in F^{r\times n} \) be the submatrix they form. Its rows are independent, so \( \dim\operatorname{Row}(A') = r \), and by the theorem \( \dim \operatorname{Col}(A') = r \) as well. Hence \( A' \) has \( r \) independent columns; the \( r\times r \) submatrix \( A'' \) they form has \( r \) independent columns in \( F^{r} \), so it is invertible. Thus \( d \ge r \). (The theorem is essential here: independence was arranged among rows and had to be harvested among columns.)

\( d \le r \). Suppose some \( k\times k \) submatrix \( M \), on rows \( i_1 \lt \dots \lt i_k \) and columns \( j_1 \lt \dots \lt j_k \), is invertible. Its rows are independent. If the corresponding full rows \( \rho_{i_1}, \dots, \rho_{i_k} \) of \( A \) satisfied a relation \( \sum_t \lambda_t \rho_{i_t} = 0 \), then restricting that relation to the coordinates \( j_1, \dots, j_k \) would give a relation among the rows of \( M \), forcing all \( \lambda_t = 0 \). So \( \rho_{i_1}, \dots, \rho_{i_k} \) are independent and \( k \le \dim \operatorname{Row}(A) = r \). Thus \( d \le r \), and \( d = r \).

Verification. For \( A = \begin{pmatrix} 1 & 2 & -1 & 3 \\ 2 & 4 & 1 & 0 \\ 3 & 6 & 0 & 3 \end{pmatrix} \) of Example 1, rank \( 2 \): rows \( \{1,2\} \) and columns \( \{1,3\} \) give \( \begin{pmatrix} 1 & -1 \\ 2 & 1 \end{pmatrix} \) with determinant \( 1\cdot 1 - (-1)\cdot 2 = 3 \neq 0 \), so \( d \ge 2 \). No \( 3\times 3 \) submatrix is invertible: every such submatrix has \( \rho_3 = \rho_1 + \rho_2 \) inherited from \( A \) (since \( (1,2,-1,3) + (2,4,1,0) = (3,6,0,3) \)), so its rows are dependent and its determinant is \( 0 \). Hence \( d = 2 = \operatorname{rank} A \).