Rank (linear algebra)

Last updated

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.

Contents

The rank is commonly denoted by rank(A) or rk(A); [2] sometimes the parentheses are not written, as in rank A. [lower-roman 1]

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. (Two 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 between the number of rows and columns, and the rank.

The rank of a linear map or operator is defined as the dimension of its image: [5] [6] [7] [8]

where is the dimension of a vector space, and is the image of a map.

Examples

The matrix

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 second subtracted from the first), the three columns are linearly dependent so the rank must be less than 3.

The matrix

has rank 1: there are nonzero columns, so the rank is positive, but any pair of columns is linearly dependent. Similarly, the transpose

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

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

can be put in reduced row-echelon form by using the following elementary row operations:

The final matrix (in 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 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

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 × n matrix. Let the column rank of A be r, and let c1, ..., cr be any basis for the column space of A. Place these as the columns of an m × 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 × n matrix R such that A = CR. R is the matrix whose ith column is formed from the coefficients giving the ith 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 of the row space of A and, by the Steinitz exchange lemma, the row rank of A cannot exceed r. This proves that the row rank of A is less than or equal to the column rank of A. This result can be applied to any matrix, so apply the result to the transpose of A. Since the row rank of the transpose of A is the column rank of A and the column rank of the transpose of A is the row rank of A, this establishes the reverse inequality and we obtain the equality of the row rank and the column rank of A. (Also see Rank factorization.)

Proof using orthogonality

Let A be an m×n matrix with entries in the real numbers whose row rank is r. Therefore, the dimension of the row space of A is r. Let x1, x2, …, xr be a basis of the row space of A. We claim that the vectors Ax1, Ax2, …, Axr are linearly independent. To see why, consider a linear homogeneous relation involving these vectors with scalar coefficients c1, c2, …, cr:

where v = c1x1 + c2x2 + ⋯ + crxr. We make two observations: (a) v is a linear combination of vectors in the row space of A, which implies that v belongs to the row space of A, and (b) since Av = 0, the vector v is orthogonal to every row vector of A and, hence, is orthogonal to every vector in the row space of A. The facts (a) and (b) together imply that v is orthogonal to itself, which proves that v = 0 or, by the definition of v,

But recall that the xi were chosen as a basis of the row space of A and so are linearly independent. This implies that c1 = c2 = ⋯ = cr = 0. It follows that Ax1, Ax2, …, Axr are linearly independent.

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

Alternative definitions

In all the definitions in this section, the matrix A is taken to be an m × n matrix over an arbitrary field F.

Dimension of image

Given the matrix , there is an associated linear mapping

defined by

.

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

Rank in terms of nullity

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

Column rank – dimension of column space

The rank of A is the maximal number of linearly independent columns of A; this is the dimension of the column space of A (the column space being the subspace of Fm generated by the columns of A, which is in fact just the image of the linear map f associated to A).

Row rank – dimension of row space

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

Decomposition rank

The rank of A is the smallest integer k such that A can be factored as , where C is an m × k matrix and R is a k × n matrix. In fact, for all integers k, the following are equivalent:

  1. the column rank of A is less than or equal to k,
  2. there exist k columns of size m such that every column of A is a linear combination of ,
  3. there exist an matrix C and a matrix R such that (when k is the rank, this is a rank factorization of A),
  4. there exist k rows of size n such that every row of A is a linear combination of ,
  5. the row rank of A is less than or equal to k.

Indeed, the following equivalences are obvious: . For example, to prove (3) from (2), take C to be the matrix whose columns are from (2). To prove (2) from (3), take to be the columns of C.

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 map f : VW is the minimal dimension k of an intermediate space X such that f can be written as the composition of a map VX and a map XW. 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 values

The rank of A 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 .

Determinantal rank – size of largest non-vanishing minor

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

Tensor rank – minimum number of simple tensors

The rank of A is the smallest number k such that A can be written as a sum of k 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 vector c and a row vector r. This notion of rank is called tensor rank; it can be generalized in the separable models interpretation of the singular value decomposition.

Properties

We assume that A is an m × n matrix, and we define the linear map f by f(x) = Ax as above.

A matrix that has rank min(m, n) is said to have full rank; otherwise, the matrix is rank deficient.
where Ir denotes the r × r identity matrix.
[lower-roman 2]
This is a special case of the next inequality.
[lower-roman 3]
when A and B are of the same dimension. As a consequence, a rank-k matrix can be written as the sum of k rank-1 matrices, but not fewer.
This can be shown by proving equality of their null spaces. The null space of the Gram matrix is given by vectors x for which If this condition is fulfilled, we also have [11]

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. 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 k free parameters where k 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.

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.

See also

Notes

  1. Alternative notation includes from Katznelson & Katznelson (2008 , p. 52, §2.5.1) and Halmos (1974 , p. 90, § 50).
  2. Proof. Apply the rank–nullity theorem to the inequality
  3. Proof. The map
    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 is a linear subspace then ; apply this inequality to the subspace defined by the orthogonal complement of the image of in the image of , whose dimension is ; its image under has dimension .

Related Research Articles

In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It allows characterizing some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and only if the matrix is invertible, and the linear map represented by the matrix is an isomorphism. The determinant of a product of matrices is the product of their determinants . The determinant of a matrix A is denoted det(A), det A, or |A|.

In mathematics, a linear map is a mapping between two vector spaces that preserves the operations of vector addition and scalar multiplication. The same names and the same definition are also used for the more general case of modules over a ring; see Module homomorphism.

Linear algebra Branch of mathematics

Linear algebra is the branch of mathematics concerning linear equations such as:

In mathematics, the tensor product of two vector spaces V and W is a vector space which can be thought of as the space of all tensors that can be built from vectors from its constituent spaces using an additional operation which can be considered as a generalization and abstraction of the outer product. Because of the connection with tensors, which are the elements of a tensor product, tensor products find uses in many areas of application including in physics and engineering, though the full theoretical mechanics of them described below may not be commonly cited there. For example, in general relativity, the gravitational field is described through the metric tensor, which is a field of tensors, one at each point in the space-time manifold, and each of which lives in the tensor self-product of tangent spaces at its point of residence on the manifold.

In linear algebra, the trace of a square matrix A, denoted tr(A), is defined to be the sum of elements on the main diagonal of A.

Linear subspace

In mathematics, and more specifically in linear algebra, a linear subspace, also known as a vector subspace is a vector space that is a subset of some larger vector space. A linear subspace is usually simply called a subspace when the context serves to distinguish it from other types of subspaces.

Row and column spaces

In linear algebra, the column space of a matrix A is the span of its column vectors. The column space of a matrix is the image or range of the corresponding matrix transformation.

Controllability is an important property of a control system, and the controllability property plays a crucial role in many control problems, such as stabilization of unstable systems by feedback, or optimal control.

In linear algebra, the outer product of two coordinate vectors is a matrix. If the two vectors have dimensions n and m, then their outer product is an n × m matrix. More generally, given two tensors, their outer product is a tensor. The outer product of tensors is also referred to as their tensor product, and can be used to define the tensor algebra.

Singular value decomposition Matrix decomposition

In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix that generalizes the eigendecomposition, which only exists for square normal matrices, to any matrix via an extension of the polar decomposition.

In linear algebra, a column vector is a column of entries, for example,

Transpose Matrix operation which flips a matrix over its diagonal

In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal; that is, it switches the row and column indices of the matrix A by producing another matrix, often denoted by AT.

In mathematics, especially in applications of linear algebra to physics, the Einstein notation or Einstein summation convention is a notational convention that implies summation over a set of indexed terms in a formula, thus achieving notational brevity. As part of mathematics it is a notational subset of Ricci calculus; however, it is often used in applications in physics that do not distinguish between tangent and cotangent spaces. It was introduced to physics by Albert Einstein in 1916.

In linear algebra, an n-by-n square matrix A is called invertible, if there exists an n-by-n square matrix B such that

Exterior algebra Algebraic construction used in multilinear algebra and geometry

In mathematics, the exterior product or wedge product of vectors is an algebraic construction used in geometry to study areas, volumes, and their higher-dimensional analogues. The exterior product of two vectors and , denoted by , is called a bivector and lives in a space called the exterior square, a vector space that is distinct from the original space of vectors. The magnitude of can be interpreted as the area of the parallelogram with sides and , which in three dimensions can also be computed using the cross product of the two vectors. More generally, all parallel plane surfaces with the same orientation and area have the same bivector as a measure of their oriented area. Like the cross product, the exterior product is anticommutative, meaning that for all vectors and , but, unlike the cross product, the exterior product is associative.

Rank–nullity theorem The dimension of the domain of a linear map is the sum of the dimensions of its kernel and its image

The rank–nullity theorem is a theorem in linear algebra, which asserts that the dimension of the domain of a linear map is the sum of its rank and its nullity.

Projection (linear algebra)

In linear algebra and functional analysis, a projection is a linear transformation from a vector space to itself such that . That is, whenever is applied twice to any value, it gives the same result as if it were applied once (idempotent). It leaves its image unchanged. Though abstract, this definition of "projection" formalizes and generalizes the idea of graphical projection. One can also consider the effect of a projection on a geometrical object by examining the effect of the projection on points in the object.

In mathematics, the kernel of a linear map, also known as the null space or nullspace, is the linear subspace of the domain of the map which is mapped to the zero vector. That is, given a linear map L : VW between two vector spaces V and W, the kernel of L is the vector space of all elements v of V such that L(v) = 0, where 0 denotes the zero vector in W, or more symbolically:

In mathematics, especially in linear algebra and matrix theory, the commutation matrix is used for transforming the vectorized form of a matrix into the vectorized form of its transpose. Specifically, the commutation matrix K(m,n) is the nm × mn matrix which, for any m × n matrix A, transforms vec(A) into vec(AT):

In mathematics, especially in linear algebra and matrix theory, the vectorization of a matrix is a linear transformation which converts the matrix into a column vector. Specifically, the vectorization of a m × n matrix A, denoted vec(A), is the mn × 1 column vector obtained by stacking the columns of the matrix A on top of one another:

References

  1. Axler (2015) pp. 111-112, §§ 3.115, 3.119
  2. 1 2 Roman (2005) p. 48, § 1.16
  3. Bourbaki, Algebra, ch. II, §10.12, p. 359
  4. 1 2 Mackiw, G. (1995), "A Note on the Equality of the Column and Row Rank of a Matrix", Mathematics Magazine , 68 (4): 285–286, doi:10.1080/0025570X.1995.11996337
  5. Hefferon (2020) p. 200, ch. 3, Definition 2.1
  6. Katznelson & Katznelson (2008) p. 52, § 2.5.1
  7. Valenza (1993) p. 71, § 4.3
  8. Halmos (1974) p. 90, § 50
  9. Wardlaw, William P. (2005), "Row Rank Equals Column Rank", Mathematics Magazine , 78 (4): 316–318, doi:10.1080/0025570X.2005.11953349, S2CID   218542661
  10. Banerjee, Sudipto; Roy, Anindya (2014), Linear Algebra and Matrix Analysis for Statistics, Texts in Statistical Science (1st ed.), Chapman and Hall/CRC, ISBN   978-1420095388
  11. Mirsky, Leonid (1955). An introduction to linear algebra. Dover Publications. ISBN   978-0-486-66434-7.

Sources

Further reading