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
    http://en.wikipedia.org/wiki/LU_decomposition#Existence_and_uniqueness2012-10-26
  • 0
    Thanks. But the entry does not include the answer (directly, at least).2012-10-26
  • 0
    Hence a comment, and not an answer. Also, using more than two matrices only helps if we alternate upper and lower triangular.2012-10-26
  • 0
    Ok, thanks. What do you mean by "only helps"?2012-10-26
  • 0
    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.2012-10-26
  • 0
    Do you allow diagonal matrices as triangular?2012-10-26
  • 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.

  • 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.2012-10-26
  • 0
    @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.2012-10-27