Question

How many multiplications of entries are used by the algorithm found in Exercise 41 for multiplying two$\mathit{n}\mathbf{\times }\mathit{n}$upper triangular matrices?

Short answer

$\frac{1}{6}n(n+1)(n+2)$

Step-by-step solution

Previous Exercise

Solution previous exercise:

for i = j to n

for j := 1 to n

$c_{ij}:=0$

if $i\le j$then

for $q:=itoj$

$c_{ij}:=c_{ij}+a_{i}q{b}_{qj}$

return C

GENERAL SUMS

$\begin{array}{r}\sum _{k=1}^n a=a\cdot n\\ \sum _{k=1}^n k=\frac{n(n+1)}{2}\\ \sum _{k=1}^n k^2=\frac{n(n+1)(2n+1)}{6}\end{array}$

Solution

We note that for every iteration of the for-loop of the variable q one multiplication is made $\left(a_{iq}{b}_{qj}\right)$ , while q can take on values from i to j and thus every time the for-loop of the variable q is executed, j - i+ 1 multiplications are used.

j can take on the values from 1 to n, while ican take on the values from 1 to n as well. However, when j < i , no multiplications are made as we know that the element is and thus there are only made any multiplications for j from i to n.

Using the above general sums, we then obtain:

localid="1668664755742" $\begin{array}{r}\sum _{i=1}^n \sum _{j=i}^n (j-i+1)=\sum _{i=1}^n \left(\sum _{k=1}^{n-i+1} k\right)\\ =\sum _{i=1}^n \frac{(n-i+1)(n-i+2)}{2}\\ =\sum _{i=1}^n \frac{n^2-in+n-ni+i^2-i+2n-2i+2}{2}\\ =\sum _{i=1}^n \frac{n^2-2in+3n+i^2-3i+2}{2}\\ =\frac{1}{2}\cdot \left(n^2\cdot \sum _{i=1}^n 1-2n\cdot \sum _{i=1}^n i+3n\cdot \sum _{i=1}^n 1+\sum _{i=1}^n i^2-3\cdot \sum _{i=1}^n i+2\cdot \sum _{i=1}^n 1\right)\end{array}$

Further simplify as:

localid="1668664759736" $\begin{array}{r}\sum _{i=1}^n \sum _{j=i}^n (j-i+1)=\frac{1}{2}\cdot \left(n^2\cdot n-2n\cdot \frac{n(n+1)}{2}+3n\cdot n+\frac{n(n+1)(2n+1)}{6}-3\cdot \frac{n(n+1)}{2}+2\cdot n\right)\\ =\frac{1}{2}\cdot \left(n^3\cdot n^3+n^2+3n^2+\cdot \frac{n(n+1)(2n+1)}{6}-\frac{3}{2}{n}^2+\frac{3}{2}n(n+1)+2n\right)\\ =\frac{1}{2}\cdot \left(\frac{1}{2}{n}^2+\frac{1}{2}n+\frac{n(n+1)(2n+1)}{6}\right)\\ =\frac{1}{2}\cdot \left(\frac{1}{2}n(n+1)+\frac{n(n+1)(2n+1)}{6}\right)\end{array}$

Simplify

Further simplify as:

$\begin{array}{r}\sum _{i=1}^n \sum _{j=i}^n (j-i+1)=\frac{1}{2}n(n+1)\cdot \left(\frac{1}{2}+\frac{2\mathrm{n}+1}{6}\right)\\ =\frac{1}{2}n(n+1)\cdot \left(\frac{3}{6}+\frac{2n+1}{6}\right)\\ =\frac{1}{2}n(n+1)\cdot \left(\frac{2\mathrm{n}+4}{6}\right)\\ =n(n+1)\cdot \left(\frac{\mathrm{n}+2}{6}\right)\\ =\frac{1}{6}n(n+1)(\mathrm{n}+2)\end{array}$