Rank (linear algebra)

In linear algebra, the rank of a matrix $A$ is the dimension of the vector space generated (or spanned) by its columns.^[1]^[2]^[3] This corresponds to the maximal number of linearly independent columns of $A$ . This, in turn, is identical to the dimension of the vector space spanned by its rows.^[4] Rank is thus a measure of the "nondegenerateness" of the system of linear equations and linear transformation encoded by $A$ . There are multiple equivalent definitions of rank. A matrix's rank is one of its most fundamental characteristics.

The rank is commonly denoted by $rank(A)$ or $rk(A)$ ;^[2] sometimes the parentheses are not written, as in $rank A$ .^[i]

Main definitions

In this section, we give some definitions of the rank of a matrix. Many definitions are possible; see Alternative definitions for several of these.

The column rank of $A$ is the dimension of the column space of $A$ , while the row rank of $A$ is the dimension of the row space of $A$ .

A fundamental result in linear algebra is that the column rank and the row rank are always equal. (Three proofs of this result are given in § Proofs that column rank = row rank, below.) This number (i.e., the number of linearly independent rows or columns) is simply called the rank of $A$ .

A matrix is said to have full rank if its rank equals the largest possible for a matrix of the same dimensions, which is the lesser of the number of rows and columns. A matrix is said to be rank-deficient if it does not have full rank. The rank deficiency of a matrix is the difference between the lesser of the number of rows and columns, and the rank.

The rank of a linear map or operator $\Phi$ is defined as the dimension of its image:^[5]^[6]^[7]^[8] $\operatorname {rank} (\Phi ):=\dim(\operatorname {img} (\Phi ))$ where $\dim$ is the dimension of a vector space, and $\operatorname {img}$ is the image of a map.

Examples

The matrix ${\begin{bmatrix}1&0&1\\0&1&1\\0&1&1\end{bmatrix}}$ has rank 2: the first two columns are linearly independent, so the rank is at least 2, but since the third is a linear combination of the first two (the first column plus the second), the three columns are linearly dependent so the rank must be less than 3.

The matrix $A={\begin{bmatrix}1&1&0&2\\-1&-1&0&-2\end{bmatrix}}$ has rank 1: there are nonzero columns, so the rank is positive, but any pair of columns is linearly dependent. Similarly, the transpose $A^{\mathrm {T} }={\begin{bmatrix}1&-1\\1&-1\\0&0\\2&-2\end{bmatrix}}$ of $A$ has rank 1. Indeed, since the column vectors of $A$ are the row vectors of the transpose of $A$ , the statement that the column rank of a matrix equals its row rank is equivalent to the statement that the rank of a matrix is equal to the rank of its transpose, i.e., $rank(A) = rank(A T)$ .

Computing the rank of a matrix

Rank from row echelon forms

A common approach to finding the rank of a matrix is to reduce it to a simpler form, generally row echelon form, by elementary row operations. Row operations do not change the row space (hence do not change the row rank), and, being invertible, map the column space to an isomorphic space (hence do not change the column rank). Once in row echelon form, the rank is clearly the same for both row rank and column rank, and equals the number of pivots (or basic columns) and also the number of non-zero rows.

For example, the matrix $A$ given by $A={\begin{bmatrix}1&2&1\\-2&-3&1\\3&5&0\end{bmatrix}}$ can be put in reduced row-echelon form by using the following elementary row operations: ${\begin{aligned}{\begin{bmatrix}1&2&1\\-2&-3&1\\3&5&0\end{bmatrix}}&\xrightarrow {2R_{1}+R_{2}\to R_{2}} {\begin{bmatrix}1&2&1\\0&1&3\\3&5&0\end{bmatrix}}\xrightarrow {-3R_{1}+R_{3}\to R_{3}} {\begin{bmatrix}1&2&1\\0&1&3\\0&-1&-3\end{bmatrix}}\\&\xrightarrow {R_{2}+R_{3}\to R_{3}} \,\,{\begin{bmatrix}1&2&1\\0&1&3\\0&0&0\end{bmatrix}}\xrightarrow {-2R_{2}+R_{1}\to R_{1}} {\begin{bmatrix}1&0&-5\\0&1&3\\0&0&0\end{bmatrix}}~.\end{aligned}}$ The final matrix (in reduced row echelon form) has two non-zero rows and thus the rank of matrix $A$ is 2.

Computation

When applied to floating point computations on computers, basic Gaussian elimination (LU decomposition) can be unreliable, and a rank-revealing decomposition should be used instead. An effective alternative is the singular value decomposition (SVD), but there are other less computationally expensive choices, such as QR decomposition with pivoting (so-called rank-revealing QR factorization), which are still more numerically robust than Gaussian elimination. Numerical determination of rank requires a criterion for deciding when a value, such as a singular value from the SVD, should be treated as zero, a practical choice which depends on both the matrix and the application.

Proofs that column rank = row rank

Proof using row reduction

The fact that the column and row ranks of any matrix are equal forms is fundamental in linear algebra. Many proofs have been given. One of the most elementary ones has been sketched in § Rank from row echelon forms. Here is a variant of this proof:

It is straightforward to show that neither the row rank nor the column rank are changed by an elementary row operation. As Gaussian elimination proceeds by elementary row operations, the reduced row echelon form of a matrix has the same row rank and the same column rank as the original matrix. Further elementary column operations allow putting the matrix in the form of an identity matrix possibly bordered by rows and columns of zeros. Again, this changes neither the row rank nor the column rank. It is immediate that both the row and column ranks of this resulting matrix is the number of its nonzero entries.

We present two other proofs of this result. The first uses only basic properties of linear combinations of vectors, and is valid over any field. The proof is based upon Wardlaw (2005).^[9] The second uses orthogonality and is valid for matrices over the real numbers; it is based upon Mackiw (1995).^[4] Both proofs can be found in the book by Banerjee and Roy (2014).^[10]

Proof using linear combinations

Let $A$ be an $m \times n$ matrix. Let the column rank of $A$ be $r$ , and let $c 1, ..., c r$ be any basis for the column space of $A$ . Place these as the columns of an $m \times r$ matrix $C$ . Every column of $A$ can be expressed as a linear combination of the $r$ columns in $C$ . This means that there is an $r \times n$ matrix $R$ such that $A = CR$ . $R$ is the matrix whose $i$ th column is formed from the coefficients giving the $i$ th column of $A$ as a linear combination of the $r$ columns of $C$ . In other words, $R$ is the matrix which contains the multiples for the bases of the column space of $A$ (which is $C$ ), which are then used to form $A$ as a whole. Now, each row of $A$ is given by a linear combination of the $r$ rows of $R$ . Therefore, the rows of $R$ form a spanning set