The number of operations to multiply L by U?

Question

I have the following $A=LU$ while $L$ is is lower triangular matrix and $U$ is an upper triangular matrix, the size of both $L$ and $U$ is $N\times N$.

The question is how many operations are required to multiply both matrices to get $A$?

I got that the result is $\sum_{i=1}^N \sum_{j=1}^N \min(i,j)$ but how to calculate that?

Answer 1

Hint:

$$\sum_{i=1}^n\sum_{j=1}^n\min(i,j) =\sum_{i=1}^n\left(\sum_{j=1}^i\min(i,j)+\sum_{j=i+1}^n\min(i,j)\right) =\sum_{i=1}^n\left(\sum_{j=1}^ij+\sum_{j=i+1}^ni\right) \\=\sum_{i=1}^n\frac{i(i+1)}2+\sum_{i=1}^n(n-i)i =\frac12\sum_{i=1}^n((2n+1)i-i^2).$$

Answer 2

Note that:

$$\begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 2 \\ 1 & 2 & 3\end{bmatrix}=\begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1\end{bmatrix}+\begin{bmatrix} 0 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1\end{bmatrix}+\begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix}$$

In general we can decompose the minimum as sum of indicator of whether an entries is bigger than $i$.

We have

$$\sum_{i=1}^N \sum_{j=1}^N\min(i,j) = \sum_{i=1}^N i^2=\frac{N(N+1)(2N+1)}{6}$$