<p>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 <span class="math-container">$n \times n$</span> matrices <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, I can embed <span class="math-container">$A$</span> as <span class="math-container">$M_{32}^{th}$</span> block of a <span class="math-container">$3n \times 3n$</span> matrix <span class="math-container">$M$</span> with rest of the blocks all zero matrices. Similarly, I can embed <span class="math-container">$B$</span> as <span class="math-container">$N_{21}^{th}$</span> block of <span class="math-container">$3n \times 3n$</span> matrix <span class="math-container">$N$</span> with rest of the blocks all zero. Both M and N are lower triangular. An asymptotically faster algorithm for <span class="math-container">$M.N$</span> would then yield faster algorithm for <span class="math-container">$A.B$</span> too. </p>

<p><span class="math-container">$$
\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}
$$</span></p>

<p>It's amazing how this argument does not manifest when trying to embed <span class="math-container">$A$</span> and <span class="math-container">$B$</span> in <span class="math-container">$2n \times 2n$</span> matrices!</p>

CC BY-SA 4.0
2020-04-01T15:36:28.110Z
2020-04-01T15:36:28.110Z
Pranav Bisht
<p>I was wondering, if multiplication of two <span class="math-container">$n \times n$</span> lower (or upper) triangular matrices has a more efficient algorithm than multiplication of two general <span class="math-container">$n \times n$</span> matrices?
<span class="math-container">$$
\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}
$$</span>
Initially, I thought the above block decomposition yields an <span class="math-container">$O(n^2)$</span> time algorithm since there are 4 recursive instances of multiplication of <span class="math-container">$n/2 \times n/2$</span> matrices. However, I quickly realized that we cannot recurse since the lower left blocks are not triangular (<span class="math-container">$C$</span> and <span class="math-container">$R$</span> above). </p>

CC BY-SA 4.0
2020-03-31T17:20:19.363Z
This looks like homework.
Gamow
CC BY-SA 4.0
2020-03-31T17:45:44.557Z
I also don't see any easy way to reduce general matrix multiplication to lower triangular multiplication. We can decompose matrix into LUP decomposition but we still don't get product of two lower (or upper) triangular matrices
Pranav Bisht
CC BY-SA 4.0
2020-04-01T07:01:12.510Z
Hint: consider $n/3\times n/3$ submatrices.
Emil Jeřábek
CC BY-SA 4.0
2020-04-01T07:26:15.783Z
@EmilJeřábek, it has the same problem, no? Three of the submatrices are not triangular.
Pranav Bisht
CC BY-SA 4.0
2020-04-01T07:50:19.193Z
Yes. My point is that you get a reduction from general matrix multiplication if you look at the right submatrices.
Emil Jeřábek
CC BY-SA 4.0
2020-04-01T08:34:36.537Z
@EmilJeřábek Wow! So, the reduction from general multiplication is this: If I wish to multiply two $n \times n$ matrices $A$ and $B$, I can embed $A$ as $M_{32}$ block of a $3n \times 3n$ matrix $M$ with rest of the blocks all zero matrices. Similarly, I can embed $B$ as $N_{21}$ block of $3n \times 3n$ matrix $N$ with rest of the blocks all zero. Both $M$ and $N$ are lower triangular. An asymptotically faster algo for $M.N$ would then yield faster algorithm for $A.B$ too. It's amazing how this argument does not manifest when considering $n/2 \times n/2$ submatrices!
Pranav Bisht
CC BY-SA 4.0
2020-04-01T15:24:40.463Z
@Gamow It's not homework. In fact, I was creating a short question on block-wise matrix multiplication as a TA. Now understanding the solution, I can understand why you felt its a homework question.
Pranav Bisht
CC BY-SA 4.0
2020-04-01T16:09:09.503Z
It would actually manifest if you iterated the decomposition to $n/2\times n/2$ matrices twice (yielding a decomposition to $n/4\times n/4$ matrices).
Emil Jeřábek
<cc.complexity-theory><ds.algorithms><time-complexity><matrices><recursion>
Time complexity for multiplying two lower triangular matrices
Pranav Bisht
# Time complexity for multiplying two lower triangular matrices

(Asked by: username_0 on 2020-03-31)

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 & 0\\
C & D
\end{bmatrix}
\begin{bmatrix}
P & 0\\
R & S
\end{bmatrix}
=
\begin{bmatrix}
AP & 0\\
CP + DR & 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).

**Tags:** cc.complexity-theory, ds.algorithms, time-complexity, matrices, recursion

> **Comments:**
> **username_1**: This looks like homework.  
> **username_0**: I also don't see any easy way to reduce general matrix multiplication to lower triangular multiplication. We can decompose matrix into LUP decomposition but we still don't get product of two lower (or upper) triangular matrices  
> **username_2**: Hint: consider $n/3\times n/3$ submatrices.  
> **username_0**: @EmilJeřábek, it has the same problem, no? Three of the submatrices are not triangular.  
> **username_2**: Yes. My point is that you get a reduction from general matrix multiplication if you look at the right submatrices.  
> **username_0**: @EmilJeřábek Wow! So, the reduction from general multiplication is this: If I wish to multiply two $n \times n$ matrices $A$ and $B$, I can embed $A$ as $M_{32}$ block of a $3n \times 3n$ matrix $M$ with rest of the blocks all zero matrices. Similarly, I can embed $B$ as $N_{21}$ block of $3n \times 3n$ matrix $N$ with rest of the blocks all zero. Both $M$ and $N$ are lower triangular. An asymptotically faster algo for $M.N$ would then yield faster algorithm for $A.B$ too. It's amazing how this argument does not manifest when considering $n/2 \times n/2$ submatrices!  
> **username_0**: @username_1 It's not homework. In fact, I was creating a short question on block-wise matrix multiplication as a TA. Now understanding the solution, I can understand why you felt its a homework question.  
> **username_2**: It would actually manifest if you iterated the decomposition to $n/2\times n/2$ matrices twice (yielding a decomposition to $n/4\times n/4$ matrices).  

---

## 1 answers

### Answer by username_0 on 2020-04-01. Score: 3 | Accepted answer

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 & 0 & 0\\
0 & 0 & 0\\
0 & A & 0
\end{bmatrix}
\begin{bmatrix}
0 & 0 & 0\\
B & 0 & 0\\
0 & 0 & 0
\end{bmatrix}
=
\begin{bmatrix}
0 & 0 & 0\\
0 & 0 & 0\\
AB & 0 & 0
\end{bmatrix}
$$

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


---

