Rank (linear algebra)

In linear algebra, the rank of a matrix is the dimension of the vector space generated (or spanned) by its columns.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 13 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In linear algebra, the rank of a matrix is the dimension of the vector space generated (or spanned) by its columns. This corresponds to the maximal number of linearly independent columns of . This, in turn, is identical to the dimension of the vector space spanned by its rows.

Rank is thus a measure of the "nondegenerateness" of the system of linear equations and linear transformation encoded by . There are multiple equivalent definitions of rank. A matrix's rank is one of its most fundamental characteristics.

The rank is commonly denoted by or ; sometimes the parentheses are not written, as in . The rank can also be denoted by , from German Rang. More generally, the rank of a linear map between two vector spaces is the dimension of its image.

The rank of a linear map or operator \Phi is defined as the dimension of its image: \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. \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 has rank 1. Indeed, since the column vectors of are the row vectors of the transpose of , 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., .

Computing the rank of a matrix

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{align} \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{align} The final matrix (in reduced row echelon form) has two non-zero rows and thus the rank of matrix is 2. == Proofs that column rank = row rank

=Proof using row reduction=== The fact that the column and row ranks of any matrix are equal is fundamental in linear algebra. Many proofs have been given. One of the most elementary ones has been sketched in .

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).

The second uses orthogonality and is valid for matrices over the real numbers; it is based upon Mackiw (1995). Both proofs can be found in the book by Banerjee and Roy (2014).

Proof using linear combinations

Let be an matrix. Let the column rank of be , and let be any basis for the column space of . Place these as the columns of an matrix .

Every column of can be expressed as a linear combination of the columns in . This means that there is an matrix such that . is the matrix whose th column is formed from the coefficients giving the th column of as a linear combination of the columns of .

In other words, is the matrix which contains the multiples for the bases of the column space of (which is ), which are then used to form as a whole. Now, each row of is given by a linear combination of the rows of . Therefore, the rows of form a spanning set of the row space of and, by the Steinitz exchange lemma, the row rank of cannot exceed .

This proves that the row rank of is less than or equal to the column rank of . This result can be applied to any matrix, so apply the result to the transpose of .

Since the row rank of the transpose of is the column rank of and the column rank of the transpose of is the row rank of , this establishes the reverse inequality and we obtain the equality of the row rank and the column rank of . (Also see Rank factorization.)

Proof using orthogonality

Let be an matrix with entries in the real numbers whose row rank is . Therefore, the dimension of the row space of is . Let be a basis of the row space of .

We claim that the vectors are linearly independent. To see why, consider a linear homogeneous relation involving these vectors with scalar coefficients : 0 = c_1 A\mathbf{x}_1 + c_2 A\mathbf{x}_2 + \cdots + c_r A\mathbf{x}_r = A(c_1 \mathbf{x}_1 + c_2 \mathbf{x}_2 + \cdots + c_r \mathbf{x}_r) = A\mathbf{v}, where .

We make two observations: (a) is a linear combination of vectors in the row space of , which implies that belongs to the row space of , and (b) since , the vector is orthogonal to every row vector of and, hence, is orthogonal to every vector in the row space of . The facts (a) and (b) together imply that is orthogonal to itself, which proves that or, by the definition of , c_1\mathbf{x}_1 + c_2\mathbf{x}_2 + \cdots + c_r \mathbf{x}_r = 0.

But recall that the were chosen as a basis of the row space of and so are linearly independent. This implies that . It follows that are linearly independent.

Every is in the column space of . So, is a set of linearly independent vectors in the column space of and, hence, the dimension of the column space of (i.e., the column rank of ) must be at least as big as . This proves that row rank of is no larger than the column rank of .

Now apply this result to the transpose of to get the reverse inequality and conclude as in the previous proof. f : F^n \to F^m defined by f(x) = Ax. The rank of A is the dimension of the image of f . This definition has the advantage that it can be applied to any linear map without need for a specific matrix.

The rank of is the smallest positive integer such that can be factored as A = CR , where is an matrix and is a matrix. In fact, for all integers , the following are equivalent: the column rank of is less than or equal to , there exist columns \mathbf{c}_1,\ldots,\mathbf{c}_k of size such that every column of is a linear combination of \mathbf{c}_1,\ldots,\mathbf{c}_k , there exist an m \times k matrix and a k \times n matrix such that A = CR (when is the rank, this is a rank factorization of ), there exist rows \mathbf{r}_1,\ldots,\mathbf{r}_k of size such that every row of is a linear combination of \mathbf{r}_1,\ldots,\mathbf{r}_k , the row rank of is less than or equal to .

Indeed, the following equivalences are obvious: (1)\Leftrightarrow(2)\Leftrightarrow(3)\Leftrightarrow(4)\Leftrightarrow(5) . For example, to prove (3) from (2), take to be the matrix whose columns are \mathbf{c}_1,\ldots,\mathbf{c}_k from (2). To prove (2) from (3), take \mathbf{c}_1,\ldots,\mathbf{c}_k to be the columns of .

It follows from the equivalence (1)\Leftrightarrow(5) that the row rank is equal to the column rank. As in the case of the "dimension of image" characterization, this can be generalized to a definition of the rank of any linear map: the rank of a linear map is the minimal dimension of an intermediate space such that can be written as the composition of a map and a map .

Unfortunately, this definition does not suggest an efficient manner to compute the rank (for which it is better to use one of the alternative definitions). See rank factorization for details. The rank of an matrix is a nonnegative integer and cannot be greater than either or .

That is, \operatorname{rank}(A) \le \min(m, n). A matrix that has rank is said to have full rank; otherwise, the matrix is rank deficient. Only a zero matrix has rank zero. is injective (or "one-to-one") if and only if has rank (in this case, we say that has full column rank). is surjective (or "onto") if and only if has rank (in this case, we say that has full row rank).

If is a square matrix (i.e., ), then is invertible if and only if has rank (that is, has full rank). If is any matrix, then \operatorname{rank}(AB) \leq \min(\operatorname{rank}(A), \operatorname{rank}(B)). If is an matrix of rank , then \operatorname{rank}(AB) = \operatorname{rank}(A). If is an matrix of rank , then \operatorname{rank}(CA) = \operatorname{rank}(A). The rank of is equal to if and only if there exists an invertible matrix and an invertible matrix such that XAY = \begin{bmatrix} I_r & 0 \\ 0 & 0 \end{bmatrix}, where denotes the identity matrix and the three zero matrices have the sizes , and .

Sylvester’s rank inequality: if is an matrix and is , then \operatorname{rank}(AB)=\operatorname{rank}(B)-\dim(\operatorname{Im} B \cap \ker A) which implies \operatorname{rank}(A) + \operatorname{rank}(B) - n \leq \operatorname{rank}(A B). This is a special case of the next inequality. The inequality due to Frobenius: if , and are defined, then \operatorname{rank}(AB) + \operatorname{rank}(BC) \le \operatorname{rank}(B) + \operatorname{rank}(ABC).

Rank subadditivity: if and are matrices, then |\operatorname{rank}(A)-\operatorname{rank}(B)|\le\operatorname{rank}(A+B)\le \operatorname{rank}(A)+\operatorname{rank}(B) with equality in the second inequality if and only if the column spaces of and , and simultaneously the row spaces of and , each have only the zero vector in common. As a consequence, a rank- matrix can be written as the sum of at least rank-1 matrices.

If is a matrix over the real numbers then the rank of and the rank of its corresponding Gram matrix are equal. Thus, for real matrices \operatorname{rank}(A^\mathrm{T} A) = \operatorname{rank}(A A^\mathrm{T}) = \operatorname{rank}(A) = \operatorname{rank}(A^\mathrm{T}). This can be shown by proving equality of their null spaces.

The null space of the Gram matrix is given by vectors for which A^\mathrm{T} A \mathbf{x} = 0. If this condition is fulfilled, we also have 0 = \mathbf{x}^\mathrm{T} A^\mathrm{T} A \mathbf{x} = \left| A \mathbf{x} \right| ^2.

In fact, since (ker A)^\perp=\operatorname{Im} A^T , \mathbb R^n=ker A\oplus \operatorname{Im} A^T , which implies \operatorname{Im} A=\operatorname{Im} A A^T and likewise \operatorname{Im} A^T=\operatorname{Im} A^T A . If is a matrix over the complex numbers and \overline{A} denotes the complex conjugate of and the conjugate transpose of (i.e., the adjoint of ), then \operatorname{rank}(A) = \operatorname{rank}(\overline{A}) = \operatorname{rank}(A^\mathrm{T}) = \operatorname{rank}(A^*) = \operatorname{rank}(A^*A) = \operatorname{rank}(AA^*).

Generalization

There are different generalizations of the concept of rank to matrices over arbitrary rings, where column rank, row rank, dimension of column space, and dimension of row space of a matrix may be different from the others or may not exist. Thinking of matrices as tensors, the tensor rank generalizes to arbitrary tensors; for tensors of order greater than 2 (matrices are order 2 tensors), rank is very hard to compute, unlike for matrices.

There is a notion of rank for smooth maps between smooth manifolds. It is equal to the linear rank of the derivative.

Matrices as tensors

Matrix rank should not be confused with tensor order, which is called tensor rank. Tensor order is the number of indices required to write a tensor, and thus matrices all have tensor order 2. More precisely, matrices are tensors of type (1,1), having one row index and one column index, also called covariant order 1 and contravariant order 1; see Tensor (intrinsic definition) for details.

The tensor rank of a matrix can also mean the minimum number of simple tensors necessary to express the matrix as a linear combination, and that this definition does agree with matrix rank as here discussed.

Further reading

Kaw, Autar K. Two Chapters from the book Introduction to Matrix Algebra: 1. Vectors and System of Equations Mike Brookes: Matrix Reference Manual. [http://www.ee.ic.ac.uk/hp/staff/dmb/matrix/property.html#rank

Text derived from https://en.wikipedia.org/w/index.php?oldid=1346716366 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.