Rank factorization
Encyclopedia
Given an matrix
of rank
, a rank decomposition or rank factorization of is a product , where is an matrix and is an matrix.
Every finite dimensional matrix has a rank decomposition: Let be an matrix whose column rank is . Therefore, there are linearly independent columns in ; equivalently, the dimension
of the column space
of is . Let be any basis
for the column space of and place them as column vectors to form the matrix . Therefore, every column vector of is a linear combination
of the columns of . To be precise, if is an matrix with as the -th column, then
where 's are the scalar coefficients of in terms of the basis . This implies that , where is the -th element of .
Proof: To see why this is true, let us first define rank to mean column rank. Since , it follows that . From the definition of matrix multiplication
, this means that each column of is a linear combination
of the columns of . Therefore, the column space of is contained within the column space of and, hence, rank() ≤ rank(). Now, is ×, so there are columns in and, hence, rank() ≤ = rank(). This proves that rank( ≤ rank(). Now apply the result to to obtain the reverse inequality: since = , we can write rank() = rank( ≤ rank(). This proves rank( ≤ rank(). We have, therefore, proved rank( ≤ rank() and rank() ≤ rank(), so rank() = rank(). (Also see the first proof of column rank = row rank under rank
).
of . Then is obtained by removing from all non-pivot columns
, and by eliminating all zero rows of .
is in reduced echelon form.
Then is obtained by removing the third column of , the only one which is not a pivot column, and by getting rid of the last row of zeroes, so
It is straightforward to check that
form, where the columns of are the pivot columns of . Every column of is a linear combination of the columns of , so there is a matrix such that , where the columns of contain the coefficients of each of those linear combinations. So , being the identity matrix. We will show now that .
Transforming into its reduced row echelon form amounts to left-multiplying by a matrix which is a product of elementary matrices, so , where . We then can write , which allows us to identify , i.e. the nonzero rows of the reduced echelon form, with the same permutation on the columns as we did for . We thus have , and since is invertible this implies , and the proof is complete.
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
of rank
Rank (linear algebra)
The column rank of a matrix A is the maximum number of linearly independent column vectors of A. The row rank of a matrix A is the maximum number of linearly independent row vectors of A...
, a rank decomposition or rank factorization of is a product , where is an matrix and is an matrix.
Every finite dimensional matrix has a rank decomposition: Let be an matrix whose column rank is . Therefore, there are linearly independent columns in ; equivalently, the dimension
Dimension
In physics and mathematics, the dimension of a 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 because only one coordinate is needed to specify a point on it...
of the column space
Column space
In linear algebra, the column space of a matrix is the set of all possible linear combinations of its column vectors. The column space of an m × n matrix is a subspace of m-dimensional Euclidean space...
of is . Let be any basis
Basis (linear algebra)
In linear algebra, a basis is a set of linearly independent vectors that, in a linear combination, can represent every vector in a given vector space or free module, or, more simply put, which define a "coordinate system"...
for the column space of and place them as column vectors to form the matrix . Therefore, every column vector of is a linear combination
Linear combination
In mathematics, a linear combination is an expression constructed from a set of terms by multiplying each term by a constant and adding the results...
of the columns of . To be precise, if is an matrix with as the -th column, then
where 's are the scalar coefficients of in terms of the basis . This implies that , where is the -th element of .
rank() = rank()
An immediate consequence of rank factorization is that the rank of is equal to the rank of its transpose . Since the columns of are the rows of , the column rank of equals its row rank.Proof: To see why this is true, let us first define rank to mean column rank. Since , it follows that . From the definition of matrix multiplication
Matrix multiplication
In mathematics, matrix multiplication is a binary operation that takes a pair of matrices, and produces another matrix. If A is an n-by-m matrix and B is an m-by-p matrix, the result AB of their multiplication is an n-by-p matrix defined only if the number of columns m of the left matrix A is the...
, this means that each column of is a linear combination
Linear combination
In mathematics, a linear combination is an expression constructed from a set of terms by multiplying each term by a constant and adding the results...
of the columns of . Therefore, the column space of is contained within the column space of and, hence, rank() ≤ rank(). Now, is ×, so there are columns in and, hence, rank() ≤ = rank(). This proves that rank( ≤ rank(). Now apply the result to to obtain the reverse inequality: since = , we can write rank() = rank( ≤ rank(). This proves rank( ≤ rank(). We have, therefore, proved rank( ≤ rank() and rank() ≤ rank(), so rank() = rank(). (Also see the first proof of column rank = row rank under rank
Rank (linear algebra)
The column rank of a matrix A is the maximum number of linearly independent column vectors of A. The row rank of a matrix A is the maximum number of linearly independent row vectors of A...
).
Rank Factorization from Row Echelon Forms
In practice, we can construct one specific rank factorization as follows: we can compute , the reduced row echelon formRow echelon form
In linear algebra a matrix is in row echelon form if* All nonzero rows are above any rows of all zeroes, and...
of . Then is obtained by removing from all non-pivot columns
Gaussian elimination
In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations. It can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix...
, and by eliminating all zero rows of .
Example
Consider the matrixis in reduced echelon form.
Then is obtained by removing the third column of , the only one which is not a pivot column, and by getting rid of the last row of zeroes, so
It is straightforward to check that
Proof
Let be an permutation matrix such that in block partitionedBlock matrix
In the mathematical discipline of matrix theory, a block matrix or a partitioned matrix is a matrix broken into sections called blocks. Looking at it another way, the matrix is written in terms of smaller matrices. We group the rows and columns into adjacent 'bunches'. A partition is the rectangle...
form, where the columns of are the pivot columns of . Every column of is a linear combination of the columns of , so there is a matrix such that , where the columns of contain the coefficients of each of those linear combinations. So , being the identity matrix. We will show now that .
Transforming into its reduced row echelon form amounts to left-multiplying by a matrix which is a product of elementary matrices, so , where . We then can write , which allows us to identify , i.e. the nonzero rows of the reduced echelon form, with the same permutation on the columns as we did for . We thus have , and since is invertible this implies , and the proof is complete.