HOME

TheInfoList



OR:

In
linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrice ...
, the rank of a
matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** '' The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchi ...
is the
dimension In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coord ...
of the
vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
generated (or spanned) by its columns. p. 48, § 1.16 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 In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variables. For example, :\begin 3x+2y-z=1\\ 2x-2y+4z=-2\\ -x+\fracy-z=0 \end is a system of three equations in t ...
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 .Alternative notation includes \rho (\Phi) from and .


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 is the
dimension In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coord ...
of the
column space In linear algebra, the column space (also called the range or image) of a matrix ''A'' is the span (set of all possible linear combinations) of its column vectors. The column space of a matrix is the image or range of the corresponding mat ...
of , while the row rank of is the dimension of the row space of . A fundamental result in linear algebra is that the column rank and the row rank are always equal. (Two proofs of this result are given in , below.) This number (i.e., the number of linearly independent rows or columns) is simply called the rank of . 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 In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a mapping V \to W between two vector spaces that ...
or operator \Phi is defined as the dimension of its
image An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensio ...
:\operatorname (\Phi) := \dim (\operatorname (\Phi))where \dim is the dimension of a vector space, and \operatorname is the image of a map.


Examples

The matrix \begin1&0&1\\-2&-3&1\\3&3&0\end 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 minus the second), the three columns are linearly dependent so the rank must be less than 3. The matrix A=\begin1&1&0&2\\-1&-1&0&-2\end has rank 1: there are nonzero columns, so the rank is positive, but any pair of columns is linearly dependent. Similarly, the transpose A^ = \begin1&-1\\1&-1\\0&0\\2&-2\end 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


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 In linear algebra, a matrix is in echelon form if it has the shape resulting from a Gaussian elimination. A matrix being in row echelon form means that Gaussian elimination has operated on the rows, and column echelon form means that Gaussian ...
, by
elementary row operations In mathematics, an elementary matrix is a matrix which differs from the identity matrix by one single elementary row operation. The elementary matrices generate the general linear group GL''n''(F) when F is a field. Left multiplication (pre-multi ...
. 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 given by A=\begin1&2&1\\-2&-3&1\\3&5&0\end can be put in reduced row-echelon form by using the following elementary row operations: \begin \begin1&2&1\\-2&-3&1\\3&5&0\end &\xrightarrow \begin1&2&1\\0&1&3\\3&5&0\end \xrightarrow \begin1&2&1\\0&1&3\\0&-1&-3\end \\ &\xrightarrow \,\, \begin1&2&1\\0&1&3\\0&0&0\end \xrightarrow \begin1&0&-5\\0&1&3\\0&0&0\end~. \end The final matrix (in row echelon form) has two non-zero rows and thus the rank of matrix is 2.


Computation

When applied to
floating point In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can ...
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 In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any \ m \times n\ matrix. It is re ...
(SVD), but there are other less 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 . 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 In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used ...
proceeds by elementary row operations, the
reduced row echelon form In linear algebra, a matrix is in echelon form if it has the shape resulting from a Gaussian elimination. A matrix being in row echelon form means that Gaussian elimination has operated on the rows, and column echelon form means that Gaussian e ...
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 In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere. Terminology and notation The identity matrix is often denoted by I_n, or simply by I if the size is immaterial or ...
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 In mathematics, orthogonality is the generalization of the geometric notion of '' perpendicularity''. By extension, orthogonality is also used to refer to the separation of specific features of a system. The term also has specialized meanings in ...
and is valid for matrices over the
real numbers In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every re ...
; 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 In mathematics, given a field \mathbb F, nonnegative integers m,n, and a matrix A\in\mathbb F^, a rank decomposition or rank factorization of is a factorization of of the form , where C\in\mathbb F^ and F\in\mathbb F^, where r=\operatorname A is ...
.)


Proof using orthogonality

Let be an matrix with entries in the
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s 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_1 + c_2 A\mathbf_2 + \cdots + c_r A\mathbf_r = A(c_1 \mathbf_1 + c_2 \mathbf_2 + \cdots + c_r \mathbf_r) = A\mathbf, 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 In mathematics, orthogonality is the generalization of the geometric notion of '' perpendicularity''. By extension, orthogonality is also used to refer to the separation of specific features of a system. The term also has specialized meanings in ...
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_1 + c_2\mathbf_2 + \cdots + c_r \mathbf_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. Now, each is obviously a vector 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.


Alternative definitions

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


Dimension of image

Given the matrix A, there is an associated linear mapping f : F^n \mapsto 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.


Rank in terms of nullity

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


Column rank – dimension of column space

The rank of is the maximal number of linearly independent columns \mathbf_1,\mathbf_2,\dots,\mathbf_k of ; this is the
dimension In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coord ...
of the
column space In linear algebra, the column space (also called the range or image) of a matrix ''A'' is the span (set of all possible linear combinations) of its column vectors. The column space of a matrix is the image or range of the corresponding mat ...
of (the column space being the subspace of generated by the columns of , which is in fact just the image of the linear map associated to ).


Row rank – dimension of row space

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


Decomposition rank

The rank of is the smallest 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_1,\ldots,\mathbf_k of size such that every column of is a linear combination of \mathbf_1,\ldots,\mathbf_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 In mathematics, given a field \mathbb F, nonnegative integers m,n, and a matrix A\in\mathbb F^, a rank decomposition or rank factorization of is a factorization of of the form , where C\in\mathbb F^ and F\in\mathbb F^, where r=\operatorname A is ...
of ), # there exist rows \mathbf_1,\ldots,\mathbf_k of size such that every row of is a linear combination of \mathbf_1,\ldots,\mathbf_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_1,\ldots,\mathbf_k from (2). To prove (2) from (3), take \mathbf_1,\ldots,\mathbf_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 In mathematics, given a field \mathbb F, nonnegative integers m,n, and a matrix A\in\mathbb F^, a rank decomposition or rank factorization of is a factorization of of the form , where C\in\mathbb F^ and F\in\mathbb F^, where r=\operatorname A is ...
for details.


Rank in terms of singular values

The rank of equals the number of non-zero
singular values In mathematics, in particular functional analysis, the singular values, or ''s''-numbers of a compact operator T: X \rightarrow Y acting between Hilbert spaces X and Y, are the square roots of the (necessarily non-negative) eigenvalues of the self ...
, which is the same as the number of non-zero diagonal elements in Σ in the
singular value decomposition In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any \ m \times n\ matrix. It is re ...


Determinantal rank – size of largest non-vanishing minor

The rank of is the largest order of any non-zero minor in . (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 -minor ( 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 vectors has dimension , then 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 vectors has dimension , then of these vectors span the space ''and'' there is a set of coordinates on which they are linearly independent).


Tensor rank – minimum number of simple tensors

The rank of is the smallest number such that can be written as a sum of rank 1 matrices, where a matrix is defined to have rank 1 if and only if it can be written as a nonzero product c \cdot r of a column vector and a row vector . This notion of rank is called tensor rank; it can be generalized in the separable models interpretation of the
singular value decomposition In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any \ m \times n\ matrix. It is re ...
.


Properties

We assume that is an matrix, and we define the linear map by as above. * The rank of an matrix is a nonnegative
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
and cannot be greater than either or . That is, \operatorname(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 In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositi ...
(or "one-to-one") if and only if has rank (in this case, we say that has ''full column rank''). * is
surjective In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element o ...
(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(AB) \leq \min(\operatorname(A), \operatorname(B)). * If is an matrix of rank , then \operatorname(AB) = \operatorname(A). * If is an matrix of rank , then \operatorname(CA) = \operatorname(A). * The rank of is equal to if and only if there exists an invertible matrix and an invertible matrix such that XAY = \begin I_r & 0 \\ 0 & 0 \\ \end, where denotes the
identity matrix In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere. Terminology and notation The identity matrix is often denoted by I_n, or simply by I if the size is immaterial or ...
. *
Sylvester Sylvester or Silvester is a name derived from the Latin adjective ''silvestris'' meaning "wooded" or "wild", which derives from the noun ''silva'' meaning "woodland". Classical Latin spells this with ''i''. In Classical Latin, ''y'' represented ...
’s rank inequality: if is an matrix and is , thenProof: Apply the rank–nullity theorem to the inequality \dim \ker(AB) \le \dim \ker(A) + \dim \ker(B). \operatorname(A) + \operatorname(B) - n \leq \operatorname(A B). This is a special case of the next inequality. * The inequality due to Frobenius: if , and are defined, thenProof. The mapC: \ker(ABC) / \ker(BC) \to \ker(AB) / \ker(B)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 M is a linear subspace then \dim (AM) \leq \dim (M); apply this inequality to the subspace defined by the orthogonal complement of the image of BC in the image of B, whose dimension is \operatorname (B) - \operatorname (BC); its image under A has dimension \operatorname (AB) - \operatorname (ABC). \operatorname(AB) + \operatorname(BC) \le \operatorname(B) + \operatorname(ABC). * Subadditivity: \operatorname(A+ B) \le \operatorname(A) + \operatorname(B) when and are of the same dimension. As a consequence, a rank- matrix can be written as the sum of 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 is a matrix over the
real numbers In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every re ...
then the rank of and the rank of its corresponding Gram matrix are equal. Thus, for real matrices \operatorname(A^\mathrm A) = \operatorname(A A^\mathrm) = \operatorname(A) = \operatorname(A^\mathrm). 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 A \mathbf = 0. If this condition is fulfilled, we also have 0 = \mathbf^\mathrm A^\mathrm A x = \left, A \mathbf \ ^2. * If is a matrix over the complex numbers and \overline denotes the complex conjugate of and the conjugate transpose of (i.e., the adjoint of ), then \operatorname(A) = \operatorname(\overline) = \operatorname(A^\mathrm) = \operatorname(A^*) = \operatorname(A^*A) = \operatorname(AA^*).


Applications

One useful application of calculating the rank of a matrix is the computation of the number of solutions of a
system of linear equations In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variables. For example, :\begin 3x+2y-z=1\\ 2x-2y+4z=-2\\ -x+\fracy-z=0 \end is a system of three equations in t ...
. According to the
Rouché–Capelli theorem In linear algebra, the Rouché–Capelli theorem determines the number of solutions for a system of linear equations, given the rank of its augmented matrix and coefficient matrix. The theorem is variously known as the: * Rouché–Capelli theor ...
, 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 free parameters where 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 Control theory is a field of mathematics that deals with the control system, control of dynamical systems in engineered processes and machines. The objective is to develop a model or algorithm governing the application of system inputs to drive ...
, the rank of a matrix can be used to determine whether a
linear system In systems theory, a linear system is a mathematical model of a system based on the use of a linear operator. Linear systems typically exhibit features and properties that are much simpler than the nonlinear case. As a mathematical abstraction ...
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.


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 In mathematics, the derivative of a function of a real variable measures the sensitivity to change of the function value (output value) with respect to a change in its argument (input value). Derivatives are a fundamental tool of calculus. ...
.


Matrices as tensors

Matrix rank should not be confused with
tensor order In mathematics, a tensor is an algebraic object that describes a multilinear relationship between sets of algebraic objects related to a vector space. Tensors may map between different objects such as vectors, scalars, and even other tensor ...
, which is called tensor rank. Tensor order is the number of indices required to write a
tensor In mathematics, a tensor is an algebraic object that describes a multilinear relationship between sets of algebraic objects related to a vector space. Tensors may map between different objects such as vectors, scalars, and even other 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) In mathematics, the modern component-free approach to the theory of a tensor views a tensor as an abstract object, expressing some definite type of multilinear concept. Their properties can be derived from their definitions, as linear maps or ...
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.


See also

* Matroid rank * Nonnegative rank (linear algebra) * Rank (differential topology) * Multicollinearity *
Linear dependence In the theory of vector spaces, a set of vectors is said to be if there is a nontrivial linear combination of the vectors that equals the zero vector. If no such linear combination exists, then the vectors are said to be . These concepts ar ...


Notes


References


Sources

* * * * * *


Further reading

* * Kaw, Autar K. Two Chapters from the book Introduction to Matrix Algebra: 1. Vector

and System of Equation

* Mike Brookes: Matrix Reference Manual

{{DEFAULTSORT:Rank (Linear Algebra) Linear algebra