Rank factorization

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Given an m \times n matrix A of rank r, a rank decomposition or rank factorization of A is a product A=CF, where C is an m \times r matrix and F is an r \times n matrix.

Every finite-dimensional matrix has a rank decomposition: Let A be an m\times n matrix whose column rank is r. Therefore, there are r linearly independent columns in A; equivalently, the dimension of the column space of A is r. Let c_1,c_2,\ldots,c_r be any basis for the column space of A and place them as column vectors to form the m\times r matrix C = [c_1:c_2:\ldots:c_r]. Therefore, every column vector of A is a linear combination of the columns of C. To be precise, if A = [a_1:a_2:\ldots:a_n] is an m\times n matrix with a_j as the j-th column, then

a_j = f_{1j}c_1 + f_{2j}c_2 + \cdots + f_{rj}c_r,

where f_{ij}'s are the scalar coefficients of a_j in terms of the basis c_1,c_2,\ldots,c_r. This implies that A = CF, where f_{ij} is the (i,j)-th element of F.

rank(A) = rank(A^\text{T})[edit]

An immediate consequence of rank factorization is that the rank of A is equal to the rank of its transpose A^\text{T}. Since the columns of A are the rows of A^\text{T}, the column rank of A equals its row rank.

Proof: To see why this is true, let us first define rank to mean column rank. Since A = CF, it follows that A^\text{T} = F^\text{T}C^\text{T}. From the definition of matrix multiplication, this means that each column of A^\text{T} is a linear combination of the columns of F^\text{T}. Therefore, the column space of A^\text{T} is contained within the column space of F^\text{T} and, hence, rank(A^\text{T}) ≤ rank(F^\text{T}). Now, F^\text{T} is n×r, so there are r columns in F^\text{T} and, hence, rank(A^\text{T}) ≤ r = rank(A). This proves that rank(A^\text{T}) ≤ rank(A). Now apply the result to A^\text{T} to obtain the reverse inequality: since (A^\text{T})^\text{T} = A, we can write rank(A) = rank((A^\text{T})^\text{T}) ≤ rank(A^\text{T}). This proves rank(A) ≤ rank(A^\text{T}). We have, therefore, proved rank(A^\text{T}) ≤ rank(A) and rank(A) ≤ rank(A^\text{T}), so rank(A) = rank(A^\text{T}). (Also see the first proof of column rank = row rank under rank).

Rank Factorization from Row Echelon Forms[edit]

In practice, we can construct one specific rank factorization as follows: we can compute B, the reduced row echelon form of A. Then C is obtained by removing from A all non-pivot columns, and F by eliminating all zero rows of B.

Example[edit]

Consider the matrix

A = \begin{bmatrix} 1 & 3 & 1 & 4 \\ 2 & 7 & 3 & 9 \\ 1 & 5 & 3 & 1 \\ 1 & 2 & 0 & 8 \end{bmatrix}\sim
\begin{bmatrix} 1 & 0 & -2 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}=B\text{.}

B is in reduced echelon form. Then C is obtained by removing the third column of A, the only one which is not a pivot column, and F by getting rid of the last row of zeroes, so

C = \begin{bmatrix} 1 & 3 & 4 \\ 2 & 7 & 9 \\ 1 & 5 & 1 \\ 1 & 2 & 8 \end{bmatrix}\text{,}\qquad
F = \begin{bmatrix} 1 & 0 & -2 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\text{.}

It is straightforward to check that

A = \begin{bmatrix} 1 & 3 & 1 & 4 \\ 2 & 7 & 3 & 9 \\ 1 & 5 & 3 & 1 \\ 1 & 2 & 0 & 8 \end{bmatrix} = \begin{bmatrix} 1 & 3 & 4 \\ 2 & 7 & 9 \\ 1 & 5 & 1 \\ 1 & 2 & 8 \end{bmatrix}\begin{bmatrix} 1 & 0 & -2 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} = CF\text{.}

Proof[edit]

Let P be an n\times n permutation matrix such that AP=(C,D) in block partitioned form, where the columns of C are the r pivot columns of A. Every column of D is a linear combination of the columns of C, so there is a matrix G such that D=CG, where the columns of G contain the coefficients of each of those linear combinations. So AP=(C,CG)=C(I_r,G), I_r being the r\times r identity matrix. We will show now that (I_r,G)=FP.

Transforming AP into its reduced row echelon form amounts to left-multiplying by a matrix E which is a product of elementary matrices, so EAP=BP=EC(I_r,G), where EC=\begin{pmatrix} I_r \\ 0 \end{pmatrix}. We then can write BP=\begin{pmatrix} I_r & G \\ 0 & 0 \end{pmatrix}, which allows us to identify (I_r,G)=FP, i.e. the nonzero r rows of the reduced echelon form, with the same permutation on the columns as we did for A. We thus have AP=CFP, and since P is invertible this implies A=CF, and the proof is complete.

References[edit]

  • Lay, David C. (2005), Linear Algebra and its Applications (3rd ed.), Addison Wesley, ISBN 978-0-201-70970-4 
  • Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations, Johns Hopkins Studies in Mathematical Sciences (3rd ed.), The Johns Hopkins University Press, ISBN 978-0-8018-5414-9 
  • Stewart, Gilbert W. (1998), Matrix Algorithms. I. Basic Decompositions, SIAM, ISBN 978-0-89871-414-2