how do I prove this matrix result?

Question

How do I prove that if A and B are lower triangular matrices, then AB is also a lower triangular?

Answer 1

For a lower triangular matrix $A = (a_{ij})$ we have the property $a_{ij} = 0$ for $i < j$.

E.g. $$ \left( \begin{matrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{matrix} \right) = \left( \begin{matrix} a_{11} & 0 & 0 \\ a_{21} & a_{22} & 0 \\ a_{31} & a_{32} & a_{33} \\ \end{matrix} \right) $$

If we matrix multiply two lower triangular matrices $A B=C$ then by definition of the matrix product we have $$ c_{ij} = \sum_{k=1}^n a_{ik} b_{kj} $$ If $i < j$ $(*)$ then we split the sum into two sums and observe $$ c_{ij} = \sum_{k=1}^i a_{ik} \underbrace{b_{kj}}_{k\le i <j} + \sum_{k=i+1}^n \underbrace{a_{ik}}_{i<k} b_{kj} = 0 \quad (**) $$ During the first summation the summation index $k$ takes values between $1$ and $i$, thus $k$ stays less equal $i$ which is less than $j$ by assumption $(*)$ thus $k < j$ and $b_{kj}$ vanishes because $B$ is lower triangular having zero components if the first index is smaller than the second index, which is true in the upper triangular area above the matrix diagonal.

During the second sum the summation index $k$ takes values from $i+1$ to $n$. So $k$ being the second index for the $a_{ik}$ is larger than the first index $i$. Because $A$ is lower triangular, such an $a_{ik}$ is zero.

$(**)$ means $C$ is lower triangular too.

Note: Such a split into two sums is always possible because $1 \le i < j \le n$, so each sum has at least one summand.

Example: $$ \left( \begin{matrix} c_{11} & \fbox{$c_{12}$} & c_{13} \\ c_{21} & c_{22} & c_{23} \\ c_{31} & c_{32} & c_{33} \\ \end{matrix} \right) = \left( \begin{array}{ccc} \hline a_{11} & 0 & 0 \\ \hline a_{21} & a_{22} & 0 \\ a_{31} & a_{32} & a_{33} \\ \end{array} \right) \left( \begin{array}{c|c|c} b_{11} & 0 & 0 \\ b_{21} & b_{22} & 0 \\ b_{31} & b_{32} & b_{33} \\ \end{array} \right) $$

Answer 2

If $A$ and $B$ are lower triangular, then:

$$A = \begin{bmatrix} C & 0 \\ X & D \end{bmatrix}$$ $$B = \begin{bmatrix} E & 0 \\ Y & F \end{bmatrix}$$

Where $C$, $D$, $E$, and $F$ are lower triangular matrices. What does $AB$ look like in terms of $C$, $D$, $E$, $F$, $X$, and $Y$?

Hint:

You can make the inductive assumption that $CE$ and $DF$ are lower triangular because they are smaller than $A$ and $B$