# Matrix factorization as a product of triangular matrices

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.

-
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

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.
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.