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 
.
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
, 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
).
, the reduced row echelon form
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
be an 
permutation matrix such that 
in block partitioned
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.
matrixMatrix (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 rankRank (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 dimensionDimension
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 basisBasis (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 combinationLinear 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, thenwhere
'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 multiplicationMatrix 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 combinationLinear 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 rankRank (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 columnsGaussian 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 matrix 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, soIt 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.