4
$\begingroup$

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.

  • 0
    yes, I do allow diagonal matrices as triangular.2012-10-26

2 Answers 2

6

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.

0

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.

  • 0
    @navigetor23 I apologize, I was giving my attempt on it. Does it mean a MSE user i$f$ he is to $g$ive 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.2012-10-27