Rank (linear algebra)

Template:Short description In linear algebra, the rank of a matrix Template:Mvar is the dimension of the vector space generated (or spanned) by its columns.<ref>Template:Harvard citation text pp. 111-112, §§ 3.115, 3.119</ref><ref name=":0">Template:Harvard citation text p. 48, § 1.16</ref><ref>Bourbaki, Algebra, ch. II, §10.12, p. 359</ref> This corresponds to the maximal number of linearly independent columns of Template:Mvar. This, in turn, is identical to the dimension of the vector space spanned by its rows.<ref name="mackiw">Template:Citation</ref> Rank is thus a measure of the "nondegenerateness" of the system of linear equations and linear transformation encoded by Template:Mvar. There are multiple equivalent definitions of rank. A matrix's rank is one of its most fundamental characteristics.

The rank is commonly denoted by Template:Math or Template:Math;<ref name=":0" /> sometimes the parentheses are not written, as in Template:Math.<ref group="lower-roman">Alternative notation includes <math>\rho (\Phi)</math> from Template:Harvard citation text and Template:Harvard citation text.</ref>

Main definitionsEdit

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 Template:Mvar is the dimension of the column space of Template:Mvar, while the row rank of Template:Mvar is the dimension of the row space of Template:Mvar.

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 Template:Slink, below.) This number (i.e., the number of linearly independent rows or columns) is simply called the rank of Template:Mvar.

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 <math>\Phi</math> is defined as the dimension of its image:<ref>Template:Harvard citation text p. 200, ch. 3, Definition 2.1</ref><ref>Template:Harvard citation text p. 52, § 2.5.1</ref><ref>Template:Harvard citation text p. 71, § 4.3</ref><ref>Template:Harvard citation text p. 90, § 50</ref><math display="block">\operatorname{rank} (\Phi) := \dim (\operatorname{img} (\Phi))</math>where <math>\dim</math> is the dimension of a vector space, and <math>\operatorname{img}</math> is the image of a map.

ExamplesEdit

The matrix <math display="block">\begin{bmatrix} 1 & 0 & 1\\ 0 & 1 & 1\\ 0 & 1 & 1 \end{bmatrix}</math> 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 <math display="block">A=\begin{bmatrix}1&1&0&2\\-1&-1&0&-2\end{bmatrix}</math> has rank 1: there are nonzero columns, so the rank is positive, but any pair of columns is linearly dependent. Similarly, the transpose <math display="block">A^{\mathrm T} = \begin{bmatrix}1&-1\\1&-1\\0&0\\2&-2\end{bmatrix}</math> of Template:Mvar has rank 1. Indeed, since the column vectors of Template:Mvar are the row vectors of the transpose of Template:Mvar, 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., Template:Math.

Computing the rank of a matrixEdit

Rank from row echelon formsEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} 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 Template:Mvar given by <math display="block">A=\begin{bmatrix}1&2&1\\-2&-3&1\\3&5&0\end{bmatrix}</math> can be put in reduced row-echelon form by using the following elementary row operations: <math display="block">\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}</math> The final matrix (in reduced row echelon form) has two non-zero rows and thus the rank of matrix Template:Mvar is 2.

ComputationEdit

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 rankEdit

Proof using row reductionEdit

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 Template:Slink. 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).<ref name="wardlaw"> Template:Citation</ref> The second uses orthogonality and is valid for matrices over the real numbers; it is based upon Mackiw (1995).<ref name="mackiw" /> Both proofs can be found in the book by Banerjee and Roy (2014).<ref name="banerjee-roy">Template:Citation</ref>

Proof using linear combinationsEdit

Let Template:Mvar be an Template:Math matrix. Let the column rank of Template:Mvar be Template:Mvar, and let Template:Math be any basis for the column space of Template:Mvar. Place these as the columns of an Template:Math matrix Template:Mvar. Every column of Template:Mvar can be expressed as a linear combination of the Template:Mvar columns in Template:Mvar. This means that there is an Template:Math matrix Template:Mvar such that Template:Math. Template:Mvar is the matrix whose Template:Mvarth column is formed from the coefficients giving the Template:Mvarth column of Template:Mvar as a linear combination of the Template:Mvar columns of Template:Mvar. In other words, Template:Mvar is the matrix which contains the multiples for the bases of the column space of Template:Mvar (which is Template:Mvar), which are then used to form Template:Mvar as a whole. Now, each row of Template:Mvar is given by a linear combination of the Template:Mvar rows of Template:Mvar. Therefore, the rows of Template:Mvar form a spanning set of the row space of Template:Mvar and, by the Steinitz exchange lemma, the row rank of Template:Mvar cannot exceed Template:Mvar. This proves that the row rank of Template:Mvar is less than or equal to the column rank of Template:Mvar. This result can be applied to any matrix, so apply the result to the transpose of Template:Mvar. Since the row rank of the transpose of Template:Mvar is the column rank of Template:Mvar and the column rank of the transpose of Template:Mvar is the row rank of Template:Mvar, this establishes the reverse inequality and we obtain the equality of the row rank and the column rank of Template:Mvar. (Also see Rank factorization.)

Proof using orthogonalityEdit

Let Template:Mvar be an Template:Math matrix with entries in the real numbers whose row rank is Template:Mvar. Therefore, the dimension of the row space of Template:Mvar is Template:Mvar. Let Template:Math be a basis of the row space of Template:Mvar. We claim that the vectors Template:Math are linearly independent. To see why, consider a linear homogeneous relation involving these vectors with scalar coefficients Template:Math: <math display="block">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}, </math> where Template:Math. We make two observations: (a) Template:Math is a linear combination of vectors in the row space of Template:Mvar, which implies that Template:Math belongs to the row space of Template:Mvar, and (b) since Template:Math, the vector Template:Math is orthogonal to every row vector of Template:Mvar and, hence, is orthogonal to every vector in the row space of Template:Mvar. The facts (a) and (b) together imply that Template:Math is orthogonal to itself, which proves that Template:Math or, by the definition of Template:Math, <math display="block">c_1\mathbf{x}_1 + c_2\mathbf{x}_2 + \cdots + c_r \mathbf{x}_r = 0.</math> But recall that the Template:Math were chosen as a basis of the row space of Template:Mvar and so are linearly independent. This implies that Template:Math. It follows that Template:Math are linearly independent.

Now, each Template:Math is obviously a vector in the column space of Template:Mvar. So, Template:Math is a set of Template:Mvar linearly independent vectors in the column space of Template:Mvar and, hence, the dimension of the column space of Template:Mvar (i.e., the column rank of Template:Mvar) must be at least as big as Template:Mvar. This proves that row rank of Template:Mvar is no larger than the column rank of Template:Mvar. Now apply this result to the transpose of Template:Mvar to get the reverse inequality and conclude as in the previous proof.

Alternative definitionsEdit

In all the definitions in this section, the matrix Template:Mvar is taken to be an Template:Math matrix over an arbitrary field Template:Mvar.

Dimension of imageEdit

Given the matrix <math>A</math>, there is an associated linear mapping <math display="block">f : F^n \to F^m</math> defined by <math display="block">f(x) = Ax.</math> The rank of <math>A</math> is the dimension of the image of <math>f</math>. This definition has the advantage that it can be applied to any linear map without need for a specific matrix.

Rank in terms of nullityEdit

Given the same linear mapping Template:Mvar as above, the rank is Template:Mvar minus the dimension of the kernel of Template:Mvar. The rank–nullity theorem states that this definition is equivalent to the preceding one.

Column rank – dimension of column spaceEdit

The rank of Template:Mvar is the maximal number of linearly independent columns <math>\mathbf{c}_1,\mathbf{c}_2,\dots,\mathbf{c}_k</math> of Template:Mvar; this is the dimension of the column space of Template:Mvar (the column space being the subspace of Template:Math generated by the columns of Template:Mvar, which is in fact just the image of the linear map Template:Mvar associated to Template:Mvar).

Row rank – dimension of row spaceEdit

The rank of Template:Mvar is the maximal number of linearly independent rows of Template:Mvar; this is the dimension of the row space of Template:Mvar.

Decomposition rankEdit

The rank of Template:Mvar is the smallest positive integer Template:Mvar such that Template:Mvar can be factored as <math>A = CR</math>, where Template:Mvar is an Template:Math matrix and Template:Mvar is a Template:Math matrix. In fact, for all integers Template:Mvar, the following are equivalent:

the column rank of Template:Mvar is less than or equal to Template:Mvar,
there exist Template:Mvar columns <math>\mathbf{c}_1,\ldots,\mathbf{c}_k</math> of size Template:Mvar such that every column of Template:Mvar is a linear combination of <math>\mathbf{c}_1,\ldots,\mathbf{c}_k</math>,
there exist an <math>m \times k</math> matrix Template:Mvar and a <math>k \times n</math> matrix Template:Mvar such that <math>A = CR</math> (when Template:Mvar is the rank, this is a rank factorization of Template:Mvar),
there exist Template:Mvar rows <math>\mathbf{r}_1,\ldots,\mathbf{r}_k</math> of size Template:Mvar such that every row of Template:Mvar is a linear combination of <math>\mathbf{r}_1,\ldots,\mathbf{r}_k</math>,
the row rank of Template:Mvar is less than or equal to Template:Mvar.

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

It follows from the equivalence <math>(1)\Leftrightarrow(5)</math> 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 Template:Math is the minimal dimension Template:Mvar of an intermediate space Template:Mvar such that Template:Mvar can be written as the composition of a map Template:Math and a map Template:Math. 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.

Rank in terms of singular valuesEdit

The rank of Template:Mvar equals the number of non-zero singular values, which is the same as the number of non-zero diagonal elements in Σ in the singular value decomposition Template:Nowrap

Determinantal rank – size of largest non-vanishing minorEdit

The rank of Template:Mvar is the largest order of any non-zero minor in Template:Mvar. (The order of a minor is the side-length of the square sub-matrix of which it is the determinant.) Like the decomposition rank characterization, this does not give an efficient way of computing the rank, but it is useful theoretically: a single non-zero minor witnesses a lower bound (namely its order) for the rank of the matrix, which can be useful (for example) to prove that certain operations do not lower the rank of a matrix.

A non-vanishing Template:Mvar-minor (Template:Math submatrix with non-zero determinant) shows that the rows and columns of that submatrix are linearly independent, and thus those rows and columns of the full matrix are linearly independent (in the full matrix), so the row and column rank are at least as large as the determinantal rank; however, the converse is less straightforward. The equivalence of determinantal rank and column rank is a strengthening of the statement that if the span of Template:Mvar vectors has dimension Template:Mvar, then Template:Mvar of those vectors span the space (equivalently, that one can choose a spanning set that is a subset of the vectors): the equivalence implies that a subset of the rows and a subset of the columns simultaneously define an invertible submatrix (equivalently, if the span of Template:Mvar vectors has dimension Template:Mvar, then Template:Mvar of these vectors span the space and there is a set of Template:Mvar coordinates on which they are linearly independent).

Tensor rank – minimum number of simple tensorsEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}}

The rank of Template:Mvar is the smallest number Template:Mvar such that Template:Mvar can be written as a sum of Template:Mvar rank 1 matrices, where a matrix is defined to have rank 1 if and only if it can be written as a nonzero product <math>c \cdot r</math> of a column vector Template:Mvar and a row vector Template:Mvar. This notion of rank is called tensor rank; it can be generalized in the separable models interpretation of the singular value decomposition.

PropertiesEdit

We assume that Template:Mvar is an Template:Math matrix, and we define the linear map Template:Mvar by Template:Math as above.

The rank of an Template:Math matrix is a nonnegative integer and cannot be greater than either Template:Mvar or Template:Mvar. That is, <math display="block">\operatorname{rank}(A) \le \min(m, n).</math> A matrix that has rank Template:Math is said to have full rank; otherwise, the matrix is rank deficient.
Only a zero matrix has rank zero.
Template:Mvar is injective (or "one-to-one") if and only if Template:Mvar has rank Template:Mvar (in this case, we say that Template:Mvar has full column rank).
Template:Mvar is surjective (or "onto") if and only if Template:Mvar has rank Template:Mvar (in this case, we say that Template:Mvar has full row rank).
If Template:Mvar is a square matrix (i.e., Template:Math), then Template:Mvar is invertible if and only if Template:Mvar has rank Template:Mvar (that is, Template:Mvar has full rank).
If Template:Mvar is any Template:Math matrix, then <math display="block">\operatorname{rank}(AB) \leq \min(\operatorname{rank}(A), \operatorname{rank}(B)).</math>
If Template:Mvar is an Template:Math matrix of rank Template:Mvar, then <math display="block">\operatorname{rank}(AB) = \operatorname{rank}(A).</math>
If Template:Mvar is an Template:Math matrix of rank Template:Mvar, then <math display="block">\operatorname{rank}(CA) = \operatorname{rank}(A).</math>
The rank of Template:Mvar is equal to Template:Mvar if and only if there exists an invertible Template:Math matrix Template:Mvar and an invertible Template:Math matrix Template:Mvar such that <math display="block"> XAY =

\begin{bmatrix}

 I_r & 0 \\
 0 & 0

\end{bmatrix},</math> where Template:Math denotes the Template:Math identity matrix and the three zero matrices have the sizes Template:Math, Template:Math and Template:Math.

Sylvester’s rank inequality: if Template:Mvar is an Template:Math matrix and Template:Mvar is Template:Math, then<ref group="lower-roman">Proof: Apply the rank–nullity theorem to the inequality <math display="block">\dim \ker(AB) \le \dim \ker(A) + \dim \ker(B).</math></ref> <math display="block">\operatorname{rank}(A) + \operatorname{rank}(B) - n \leq \operatorname{rank}(A B).</math> This is a special case of the next inequality.
The inequality due to Frobenius: if Template:Math, Template:Math and Template:Math are defined, then<ref group="lower-roman">Proof. The map<math display="block">C: \ker(ABC) / \ker(BC) \to \ker(AB) / \ker(B)</math>is well-defined and injective. We thus obtain the inequality in terms of dimensions of kernel, which can then be converted to the inequality in terms of ranks by the rank–nullity theorem.

Alternatively, if <math>M</math> is a linear subspace then <math>\dim (AM) \leq \dim (M)</math>; apply this inequality to the subspace defined by the orthogonal complement of the image of <math>BC</math> in the image of <math>B</math>, whose dimension is <math>\operatorname{rank} (B) - \operatorname{rank} (BC)</math>; its image under <math>A</math> has dimension <math>\operatorname{rank} (AB) - \operatorname{rank} (ABC)</math>.</ref> <math display="block">\operatorname{rank}(AB) + \operatorname{rank}(BC) \le \operatorname{rank}(B) + \operatorname{rank}(ABC).</math>

Subadditivity: <math display="block">\operatorname{rank}(A+ B) \le \operatorname{rank}(A) + \operatorname{rank}(B) </math> when Template:Mvar and Template:Mvar are of the same dimension. As a consequence, a rank-Template:Mvar matrix can be written as the sum of Template:Mvar rank-1 matrices, but not fewer.
The rank of a matrix plus the nullity of the matrix equals the number of columns of the matrix. (This is the rank–nullity theorem.)
If Template:Mvar is a matrix over the real numbers then the rank of Template:Mvar and the rank of its corresponding Gram matrix are equal. Thus, for real matrices <math display="block">\operatorname{rank}(A^\mathrm{T} A) = \operatorname{rank}(A A^\mathrm{T}) = \operatorname{rank}(A) = \operatorname{rank}(A^\mathrm{T}).</math> This can be shown by proving equality of their null spaces. The null space of the Gram matrix is given by vectors Template:Math for which <math>A^\mathrm{T} A \mathbf{x} = 0.</math> If this condition is fulfilled, we also have <math>0 = \mathbf{x}^\mathrm{T} A^\mathrm{T} A \mathbf{x} = \left| A \mathbf{x} \right| ^2.</math><ref>Template:Cite book</ref>
If Template:Mvar is a matrix over the complex numbers and <math>\overline{A}</math> denotes the complex conjugate of Template:Mvar and Template:Math the conjugate transpose of Template:Mvar (i.e., the adjoint of Template:Mvar), then <math display="block">\operatorname{rank}(A) = \operatorname{rank}(\overline{A}) = \operatorname{rank}(A^\mathrm{T}) = \operatorname{rank}(A^*) = \operatorname{rank}(A^*A) = \operatorname{rank}(AA^*).</math>

ApplicationsEdit

One useful application of calculating the rank of a matrix is the computation of the number of solutions of a system of linear equations. According to the Rouché–Capelli theorem, the system is inconsistent if the rank of the augmented matrix is greater than the rank of the coefficient matrix. If on the other hand, the ranks of these two matrices are equal, then the system must have at least one solution. The solution is unique if and only if the rank equals the number of variables. Otherwise the general solution has Template:Mvar free parameters where Template:Mvar is the difference between the number of variables and the rank. In this case (and assuming the system of equations is in the real or complex numbers) the system of equations has infinitely many solutions.

In control theory, the rank of a matrix can be used to determine whether a linear system is controllable, or observable.

In the field of communication complexity, the rank of the communication matrix of a function gives bounds on the amount of communication needed for two parties to compute the function.

GeneralizationEdit

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 tensorsEdit

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.