Inlinear algebra, therank of amatrixA is thedimension of thevector space generated (orspanned) by its columns.[1][2][3] This corresponds to the maximal number oflinearly independent columns ofA. 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 thesystem of linear equations andlinear transformation encoded byA. There are multiple equivalent definitions of rank. A matrix's rank is one of its most fundamental characteristics.
The rank is commonly denoted byrank(A) orrk(A);[2] sometimes the parentheses are not written, as inrankA.[i]
In this section, we give some definitions of the rank of a matrix. Many definitions are possible; seeAlternative definitions for several of these.
Thecolumn rank ofA is thedimension of thecolumn space ofA, while therow rank ofA is the dimension of therow space ofA.
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 therank ofA.
A matrix is said to havefull 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 berank-deficient if it does not have full rank. Therank deficiency of a matrix is the difference between the lesser of the number of rows and columns, and the rank.
The rank of alinear map or operator is defined as the dimension of itsimage:[5][6][7][8]where is the dimension of a vector space, and is the image of a map.
The matrixhas rank 2: the first two columns arelinearly 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 matrixhas rank 1: there are nonzero columns, so the rank is positive, but any pair of columns is linearly dependent. Similarly, thetransposeofA has rank 1. Indeed, since the column vectors ofA are the row vectors of thetranspose ofA, 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(AT).
A common approach to finding the rank of a matrix is to reduce it to a simpler form, generallyrow echelon form, byelementary 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 ofpivots (or basic columns) and also the number of non-zero rows.
For example, the matrixA given bycan be put in reduced row-echelon form by using the following elementary row operations:The final matrix (in reduced row echelon form) has two non-zero rows and thus the rank of matrixA is 2.
When applied tofloating 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 thesingular value decomposition (SVD), but there are other less computationally expensive choices, such asQR decomposition with pivoting (so-calledrank-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.
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§ 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 anelementary row operation. AsGaussian elimination proceeds by elementary row operations, thereduced 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 anidentity 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 oflinear combinations of vectors, and is valid over anyfield. The proof is based upon Wardlaw (2005).[9] The second usesorthogonality and is valid for matrices over thereal numbers; it is based upon Mackiw (1995).[4] Both proofs can be found in the book by Banerjee and Roy (2014).[10]
LetA be anm ×n matrix. Let the column rank ofA ber, and letc1, ...,cr be any basis for the column space ofA. Place these as the columns of anm ×r matrixC. Every column ofA can be expressed as a linear combination of ther columns inC. This means that there is anr ×n matrixR such thatA =CR.R is the matrix whoseith column is formed from the coefficients giving theith column ofA as a linear combination of ther columns ofC. In other words,R is the matrix which contains the multiples for the bases of the column space ofA (which isC), which are then used to formA as a whole. Now, each row ofA is given by a linear combination of ther rows ofR. Therefore, the rows ofR form a spanning set of the row space ofA and, by theSteinitz exchange lemma, the row rank ofA cannot exceedr. This proves that the row rank ofA is less than or equal to the column rank ofA. This result can be applied to any matrix, so apply the result to the transpose ofA. Since the row rank of the transpose ofA is the column rank ofA and the column rank of the transpose ofA is the row rank ofA, this establishes the reverse inequality and we obtain the equality of the row rank and the column rank ofA. (Also seeRank factorization.)
LetA be anm × n matrix with entries in thereal numbers whose row rank isr. Therefore, the dimension of the row space ofA isr. Letx1,x2, ...,xr be abasis of the row space ofA. We claim that the vectorsAx1,Ax2, ...,Axr arelinearly independent. To see why, consider a linear homogeneous relation involving these vectors with scalar coefficientsc1,c2, ...,cr:wherev =c1x1 +c2x2 + ⋯ +crxr. We make two observations: (a)v is a linear combination of vectors in the row space ofA, which implies thatv belongs to the row space ofA, and (b) sinceAv = 0, the vectorv isorthogonal to every row vector ofA and, hence, is orthogonal to every vector in the row space ofA. The facts (a) and (b) together imply thatv is orthogonal to itself, which proves thatv = 0 or, by the definition ofv,But recall that thexi were chosen as a basis of the row space ofA and so are linearly independent. This implies thatc1 =c2 = ⋯ =cr = 0. It follows thatAx1,Ax2, ...,Axr are linearly independent.
EveryAxi is in the column space ofA. So,Ax1,Ax2, ...,Axr is a set ofr linearly independent vectors in the column space ofA and, hence, the dimension of the column space ofA (i.e., the column rank ofA) must be at least as big asr. This proves that row rank ofA is no larger than the column rank ofA. Now apply this result to the transpose ofA to get the reverse inequality and conclude as in the previous proof.
In all the definitions in this section, the matrixA is taken to be anm ×n matrix over an arbitraryfieldF.
Given the matrix, there is an associatedlinear mappingdefined byThe rank of is the dimension of the image of. This definition has the advantage that it can be applied to any linear map without need for a specific matrix.
Given the same linear mappingf as above, the rank isn minus the dimension of thekernel off. Therank–nullity theorem states that this definition is equivalent to the preceding one.
The rank ofA is the maximal number of linearly independent columns ofA; this is thedimension of thecolumn space ofA (the column space being the subspace ofFm generated by the columns ofA, which is in fact just the image of the linear mapf associated toA).
The rank ofA is the maximal number of linearly independent rows ofA; this is the dimension of therow space ofA.
The rank ofA is the smallest positive integerk such thatA can be factored as, whereC is anm ×k matrix andR is ak ×n matrix. In fact, for all integersk, the following are equivalent:
Indeed, the following equivalences are obvious:.For example, to prove (3) from (2), takeC to be the matrix whose columns are from (2).To prove (2) from (3), take to be the columns ofC.
It follows from the equivalence 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 mapf :V →W is the minimal dimensionk of an intermediate spaceX such thatf can be written as the composition of a mapV →X and a mapX →W. 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). Seerank factorization for details.
The rank ofA equals the number of non-zerosingular values, which is the same as the number of non-zero diagonal elements in Σ in thesingular value decomposition.
The rank ofA is the largest order of any non-zerominor inA. (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-vanishingp-minor (p ×p 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 ofn vectors has dimensionp, thenp of those vectors span the space (equivalently, that one can choose a spanning set that is asubset 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 ofn vectors has dimensionp, thenp of these vectors span the spaceand there is a set ofp coordinates on which they are linearly independent).
The rank ofA is the smallest numberk such thatA can be written as a sum ofk rank 1 matrices, where a matrix is defined to have rank 1 if and only if it can be written as a nonzero product of a column vectorc and a row vectorr. This notion of rank is calledtensor rank; it can be generalized in theseparable models interpretation of thesingular value decomposition.
We assume thatA is anm ×n matrix, and we define the linear mapf byf(x) =Ax as above.
One useful application of calculating the rank of a matrix is the computation of the number of solutions of asystem of linear equations. According to theRouché–Capelli theorem, the system is inconsistent if the rank of theaugmented matrix is greater than the rank of thecoefficient 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 hask free parameters wherek 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.
Incontrol theory, the rank of a matrix can be used to determine whether alinear system iscontrollable, orobservable.
In the field ofcommunication 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.
There are different generalizations of the concept of rank to matrices over arbitraryrings, 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 astensors, thetensor 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 ofrank forsmooth maps betweensmooth manifolds. It is equal to the linear rank of thederivative.
Matrix rank should not be confused withtensor order, which is called tensor rank. Tensor order is the number of indices required to write atensor, 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; seeTensor (intrinsic definition) for details.
The tensor rank of a matrix can also mean the minimum number ofsimple tensors necessary to express the matrix as a linear combination, and that this definition does agree with matrix rank as here discussed.
{{cite book}}:ISBN / Date incompatibility (help)
