From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci)
Subject: Re: Factor a square matrix (more detail)
Date: 1 Oct 1999 13:17:59 GMT
Newsgroups: sci.math,sci.math.num-analysis,sci.math.iams
Keywords: Factorization into rectangular matrices of size equal to rank

In article <7t083e$if9$1@news.uky.edu>,
 jzhang@cs.engr.uky.edu (Jun Zhang) writes:
|> Sorry I forgot to specify an assumption on my early
|> posting about factoring a square matrix. The matrix
|> A is of order n, but has a rank m, where m<n. It
|> can be factored as the product of two rectangular
|> matrices B of order n*m, and C of order m*n, such
|> that
|> 
|> A = B*C,
|> 
|> my question is whether or not there is a good
|> method to compute B and C.
there are several such methods.
first of all : svd, the singular values decomposition.
It delivers in its standard form 

   U n*n  unitary  V n*n unitary  S n*n diagonal, 
 
w.l.o.g  S11>= S22>= .. >= Snn (>=0)
such that  
   A = U*S*V'  
removing the last n-m columns of U, the last n-m rows and columns of S 
and the last n-m rows of V' gives the same decomposition, since 
they are zeroed anyway in the multiplication process. multiplying the reduced
S with the reduced V' gives C, the reduced U is B. 
But this is a bit expensive. 
If you know the rank beforehand, then the modified gram-schmidt decomposition 
with column pivoting on A gives also such a reduction (delete, after 
m steps, the remainig n-m columns (which should be zero theoretically)
and the last n-m rows of the (permuted R-factor), which of course is then 
no longer triangular.
hope that helps
peter