The number of operations appear in the multiplication of two upper triangular matrices

Question

Imagine $A$ and $B$ are both $n\times n$ upper triangular matrices. How many operations exist in the $AB$?

I know that multiplication of two upper triangular matrices is upper triangular and operations that appear in finding the main diagonal is $n$, but I can't find how many operations appear in the $j>i$ matrix elements, can someone help me?

Answer 1

The $\ i^\text{th}\ $ row or column of an $\ n\times n\ $ upper triangular matrix contains $\ n-i+1\ $ entries that could be non-zero. If all those entries in both factors are in fact non-zero, and you compute the $\ ij\ $ entry of the product (for $\ i\le j\ $) by taking the dot product of the $\ i^\text{th}\ $ row of the first factor with the $\ j^\text{th}\ $ column of the second, then that operation will require $\ n-j+1\ $ multiplications and $\ n-j\ $ additions. The total numbers, $\ M\ $, of multiplications, and, $\ A\ $, of additions, are therefore given by \begin{align} M&=\sum_{i=1}^n\sum_{j=i}^n(n-j+1)\\ &=\frac{n(n+1)(n+2)}{6}\\ A&=\sum_{i=1}^n\sum_{j=i}^n(n-j)\\ &=\frac{(n-1)n(n+1)}{6}\ . \end{align} Since multiplications are significantly more computationally expensive than additions, it doesn't make much sense to add these together to get the total number of "operations".

You should also be made aware that there are matrix multiplication algorithms that require asymptotically fewer than the $\ O(n^3)\ $ operations needed for the straightforward method of multiplication treated above, so the above results are only valid for that specific method.

Answer 2

Just a minor comment, initially, on

operations that appear in finding the main diagonal is n

I think the operations in finding the diagonal in fact is 1, because $i$th row of $A$ has zero values from column 1 up to column $i-1$, and $i$th column of $B$ has zeroes from row $i+1$ to $n$. Thus, $c_{ii} = a_{ii} \times b_{ii}$

Or maybe I'm losing something...

Now, following the same reasoning, i.e. taking into account that matrices are upper triangular, a similar comment on

taking the dot product of the $i^{th}$ row of the first factor with the $j^{th}$ column of the second, then that operation will require $n−j+1$ multiplications

I think that, since $i^{th}$ row of the first factor has zero values from column 1 to column $i-1$ and the $j^{th}$ column of the second has zero values from rows $j+1$ to $n$, then the number of multiplications will be $j-i+1$, not $n-j+1$

right?