Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is it true that any square matrix $A $ can be factorized as a product of only triangular matrices? That is, can we write $A $ as $\prod_{i=1}^k B_i$, where every $B_i$ is either a lower or an upper triangular matrix (for some natural $ k $)?

Note $ k $ is not assumed to be 2 above. So the question is not (directly) about the $LU$ decomposition.

Comment: We know that for any square matrix $A$ we have: $A=PLU$ where $P$ is a permutation matrix, $L$ is a lower triangular matrix and $U$ is an upper triangular matrix. So the question possibly boils down to whether any permutation matrix can be factorized to triangular matrices.

share|improve this question
    
    
Thanks. But the entry does not include the answer (directly, at least). –  Dilworth Oct 26 '12 at 8:30
    
Hence a comment, and not an answer. Also, using more than two matrices only helps if we alternate upper and lower triangular. –  ronno Oct 26 '12 at 8:31
    
Ok, thanks. What do you mean by "only helps"? –  Dilworth Oct 26 '12 at 8:34
    
As in, if it can be factored into triangular matrices, the factorization can be taken to be alternately upper and lower triangular, since two consecutive upper triangular matrices can be multiplied between themselves. –  ronno Oct 26 '12 at 8:36

2 Answers 2

up vote 5 down vote accepted

The answer to your question is yes. A permutation matrix is in fact a product of permutation matrices associated to transpositions, which means a matrix obtained from the identity matrix by interchanging two rows. Reduce the problem to this case and notice that this case can be easily deduced from the case of the $2\times 2$ matrix $$\left(\begin{array}10 & 1 \\ 1 & 0\end{array}\right).$$ This matrix can be transformed into the identity matrix by using the following elementary transformations (which correspond to triangular matrices): add the second row to the first, substract the first column from the second, substract the first row from the second, and last multiply the second row by $-1$.

Moreover, in the paper of Nagarajan et al., Products of three triangular matrices, Linear Algebra and its Applications, 292(1999), 61-71 it is proved that any matrix $n\times n$ over a field is a product of at most three triangular matrices.

share|improve this answer

Any square matrix if diagonalizable can be written as the product of as many matrices as you want. For instance, $A=SDS^{-1}$ for some invertible matrix $S$, then the decomposition $A=B^{2}$ where $B=SD^{1/2}S^{-1}$ is equally valid. For our peace of mind, if we want distinct matrices, Any $B_{i}=SD^{\theta_{i}}S^{-1}$ such that $\sum_{i=1}^{k}\theta_{i}=1$ will give you $A=\prod_{i=1}^{k}B_{i}$. Now each of this $B_{i}=L_{i}U_{i}^{T}$, Hence you get your square matrix as product of as many triangular matrices as you want.

share|improve this answer
1  
For my peace of mind, please post answers which are really answers. What you say here is far from an answer. This can be at most a comment. –  user26857 Oct 26 '12 at 19:24
    
@navigetor23 I apologize, I was giving my attempt on it. Does it mean a MSE user if he is to give an answer, it should be the absolute answer and that it couldn't be an attempt. And also since you have downvoted my answer, aren't you obligated to give a solid (mathematical) reason for it. The question was whether any given matrix can be written as product of triangular matrices. What is wrong with my answer, please explain. I would really like to know. –  dineshdileep Oct 27 '12 at 2:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.