Why Row Rank Equals Column Rank

Two Ways to Measure the Size of a Matrix

A matrix has rows and columns, and each collection generates a subspace: its row space is generated by its rows, while its column space is generated by its columns. These spaces lie in different ambient spaces when the matrix is rectangular, so there is no immediate reason their dimensions should agree. Nevertheless, they always do. The key is to use the pivot positions in an echelon form carefully: the nonzero echelon rows describe the row space, while the corresponding pivot columns of the original matrix form a basis for the column space.

Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\), with \(m,n\geq 1\). The row space \(\operatorname{Row}\mathbf{A}\) is the subspace of \(\mathbb{R}^n\) spanned by the rows of \(\mathbf{A}\), viewed as row vectors. The column space \(\operatorname{Col}\mathbf{A}\) is the subspace of \(\mathbb{R}^m\) spanned by its columns. The row rank is \(\dim(\operatorname{Row}\mathbf{A})\), and the column rank is \(\dim(\operatorname{Col}\mathbf{A})\). These dimensions exist because both spaces are finite-dimensional.

Row reduction produces a row echelon matrix \(\mathbf{U}\) from \(\mathbf{A}\) using elementary row operations. Let \(r\) be the number of pivots, and denote their column indices by \(p_1<\cdots<p_r\). In nonzero row \(i\), the pivot is in column \(p_i\). Entries in that row before \(p_i\) are zero, so the pivot-column entries in the pivot rows form an upper-triangular matrix with nonzero diagonal. They need not form a diagonal matrix. That distinction is essential when proving that the pivot columns span.

How the Pivot Positions Give Two Bases

Proof. First suppose \(r>0\), and write the nonzero rows of \(\mathbf{U}\) as \(\mathbf{u}_1,\ldots,\mathbf{u}_r\). Let the pivot in row \(i\) be \(u_{i,p_i}\), which is nonzero. The entries in the pivot columns and nonzero rows form the matrix \(\mathbf{T}\) with entries \(T_{ik}=u_{i,p_k}\). If \(k<i\), then \(p_k<p_i\), so column \(p_k\) is to the left of row \(i\)'s pivot and \(T_{ik}=0\). Thus \(\mathbf{T}\) is upper triangular, and its diagonal entries \(T_{ii}=u_{i,p_i}\) are nonzero.

We first show that the nonzero rows of \(\mathbf{U}\) are independent. Suppose \(\alpha_1\mathbf{u}_1+\cdots+\alpha_r\mathbf{u}_r=\mathbf{0}\). Inspect column \(p_1\): all rows below row 1 have zero entries there, so \(\alpha_1u_{1,p_1}=0\), giving \(\alpha_1=0\). Now, in order \(k=2,\ldots,r\), inspect column \(p_k\). Rows below row \(k\) are zero in that column, and the coefficients \(\alpha_1,\ldots,\alpha_{k-1}\) have already been shown to be zero. Therefore \(\alpha_ku_{k,p_k}=0\), so \(\alpha_k=0\). This proves independence.

Elementary row operations preserve row space: each new row is a linear combination of the old rows, and the inverse operation shows that each old row is a linear combination of the new rows. Therefore \(\operatorname{Row}\mathbf{U}=\operatorname{Row}\mathbf{A}\). The nonzero rows of \(\mathbf{U}\) span its row space because every other row is zero. Combined with their independence, this proves the first basis claim.

For the column-space claim, we first work with \(\mathbf{U}\). Consider any column \(\mathbf{u}_j\) of \(\mathbf{U}\), and let \(y_i\) be its entry in row \(i\), for \(1\leq i\leq r\). We seek coefficients \(c_1,\ldots,c_r\) such that the first \(r\) entries of \(\sum_{k=1}^r c_k\mathbf{u}_{p_k}\) match those of \(\mathbf{u}_j\). This requires \(\mathbf{T}\mathbf{c}=\mathbf{y}\), where \(\mathbf{c}=(c_1,\ldots,c_r)^{\top}\) and \(\mathbf{y}=(y_1,\ldots,y_r)^{\top}\). Since \(\mathbf{T}\) is upper triangular with nonzero diagonal, solve from the last equation upward: row \(r\) determines \(c_r\); then row \(r-1\) determines \(c_{r-1}\); continuing gives all coefficients. The difference \(\mathbf{u}_j-\sum_{k=1}^r c_k\mathbf{u}_{p_k}\) is zero in the first \(r\) rows by construction. All rows below them are zero rows of \(\mathbf{U}\), so the difference is the zero column. Thus the pivot columns of \(\mathbf{U}\) span all its columns.

Those pivot columns of \(\mathbf{U}\) are also independent. If \(\sum_{k=1}^r c_k\mathbf{u}_{p_k}=\mathbf{0}\), then \(\mathbf{T}\mathbf{c}=\mathbf{0}\). Row \(r\) gives \(T_{rr}c_r=0\), so \(c_r=0\). Working upward, row \(i\) gives \(T_{ii}c_i=0\) once \(c_{i+1},\ldots,c_r\) are zero; hence every \(c_i=0\).

Finally, the row operations giving \(\mathbf{U}\) from \(\mathbf{A}\) amount to multiplication on the left by an invertible matrix \(\mathbf{E}\): \(\mathbf{U}=\mathbf{E}\mathbf{A}\). Invertibility holds because each elementary row operation has an inverse of the same kind. For each column index \(j\), the corresponding columns satisfy \(\mathbf{u}_j=\mathbf{E}\mathbf{a}_j\). Any linear relation among columns of \(\mathbf{U}\) therefore holds among the corresponding columns of \(\mathbf{A}\) exactly when it holds among the columns of \(\mathbf{U}\), since \(\mathbf{E}\) is invertible. In particular, the original pivot columns are independent. Also, if \(\mathbf{u}_j=\sum_{k=1}^r c_k\mathbf{u}_{p_k}\), then \(\mathbf{E}\mathbf{a}_j=\sum_{k=1}^r c_k\mathbf{E}\mathbf{a}_{p_k}\); applying \(\mathbf{E}^{-1}\) gives \(\mathbf{a}_j=\sum_{k=1}^r c_k\mathbf{a}_{p_k}\). So the original pivot columns span every column of \(\mathbf{A}\), proving the second basis claim.

If \(r=0\), then \(\mathbf{U}\) is the zero matrix. Since \(\mathbf{U}=\mathbf{E}\mathbf{A}\) with \(\mathbf{E}\) invertible, \(\mathbf{A}\) is also zero. Both spaces then contain only the zero vector and have dimension \(0\); their empty bases have the required size. In all cases, each basis has \(r\) vectors, so both dimensions equal \(r\). \(\square\)

Worked Examples: Reading the Bases from Pivots

Common Pitfall: The Pivot Block Is Not Usually Diagonal

It is incorrect to read coefficients from the pivot rows as if the pivot columns formed an identity matrix. For example, consider the echelon matrix \(\mathbf{U}=\begin{bmatrix}1&2&5\\0&1&3\end{bmatrix}\). Its pivots are in columns 1 and 2. A mistaken diagonal reading treats the entries \((5,3)^{\top}\) of column 3 in the pivot rows as its coefficients on the pivot columns. But that gives \(5(1,0)^{\top}+3(2,1)^{\top}=(11,3)^{\top}\), not column 3, which is \((5,3)^{\top}\).

The correct coefficients come from solving with the triangular pivot block: \(\begin{bmatrix}1&2\\0&1\end{bmatrix}\begin{bmatrix}c_1\\c_2\end{bmatrix}=\begin{bmatrix}5\\3\end{bmatrix}\). The second equation gives \(c_2=3\), and then the first gives \(c_1+6=5\), so \(c_1=-1\). Checking, \(-1(1,0)^{\top}+3(2,1)^{\top}=(5,3)^{\top}\). The upper-triangular entries above the diagonal affect the coefficients; ignoring them can invalidate a spanning argument.

A second error is to use the columns of \(\mathbf{U}\) as a basis for the column space of \(\mathbf{A}\). Row operations preserve row space, but they need not preserve the column vectors themselves or their column space. The correct basis uses the pivot columns from \(\mathbf{A}\), with the same indices as the pivots in \(\mathbf{U}\). The proof above works because left multiplication by the invertible row-operation matrix preserves linear relations among corresponding columns, not because the column spaces of \(\mathbf{A}\) and \(\mathbf{U}\) are equal.

What the Equality Tells You

The two ranks measure the same pivot count from different directions. The nonzero echelon rows give independent generators for the row space; the original pivot columns give independent generators for the column space. This is why the dimensions agree even though the spaces consist of different kinds of vectors and can live in different ambient spaces. In practice, one row reduction supplies the count and identifies both bases, provided the row-space basis is taken from the echelon form and the column-space basis from the original matrix.