Time complexity for multiplying two lower triangular matrices I was wondering, if multiplication of two $n \times n$ lower (or upper) triangular matrices has a more efficient algorithm than multiplication of two general $n \times n$ matrices?
$$
\begin{bmatrix}
 A &amp; 0\\
 C &amp; D
\end{bmatrix}
\begin{bmatrix}
 P &amp; 0\\
 R &amp; S
\end{bmatrix}
=
\begin{bmatrix}
 AP &amp; 0\\
 CP + DR &amp; DS
\end{bmatrix}
$$
Initially, I thought the above block decomposition yields an $O(n^2)$ time algorithm since there are 4 recursive instances of multiplication of $n/2 \times n/2$ matrices. However, I quickly realized that we cannot recurse since the lower left blocks are not triangular ($C$ and $R$ above).
With the expert hints of Mr Emil, I could find a reduction of general matrix multiplication to triangular matrix multiplication. If we wish to multiply two $n \times n$ matrices $A$ and $B$, I can embed $A$ as $M_{32}^{th}$ block of a $3n \times 3n$ matrix $M$ with rest of the blocks all zero matrices. Similarly, I can embed $B$ as $N_{21}^{th}$ block of $3n \times 3n$ matrix $N$ with rest of the blocks all zero. Both M and N are lower triangular. An asymptotically faster algorithm for $M.N$ would then yield faster algorithm for $A.B$ too. 

$$
\begin{bmatrix}
0 &amp; 0 &amp; 0\\
0 &amp; 0 &amp; 0\\
0 &amp; A &amp; 0
\end{bmatrix}
\begin{bmatrix}
0 &amp; 0 &amp; 0\\
B &amp; 0 &amp; 0\\
0 &amp; 0 &amp; 0
\end{bmatrix}
=
\begin{bmatrix}
0 &amp; 0 &amp; 0\\
0 &amp; 0 &amp; 0\\
AB &amp; 0 &amp; 0
\end{bmatrix}
$$

It's amazing how this argument does not manifest when trying to embed $A$ and $B$ in $2n \times 2n$ matrices!