Question

Give a pseudocode description of the algorithm in Exercise 41 for multiplying two upper triangular matrices.

Short answer

for i = 1 to n

for j: = 1 to n

$c_{ij}:=0$

if $i\le j$then

for q := i to j

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

return C.

Step-by-step solution

Upper triangular

Upper triangular: if $a_{ij}=0$whenever i > j .

We can use algorithm described in the textbook (which gives an algorithm for regular matrix multiplication).

Upper triangular matrices are square $n\times n$-matrices and thus the matrix product is also a $n\times n$-matrix. The matrix product in algorithm 1 in the textbook is a $m\times n$matrix, thus we will have to replace m in the algorithm by 1.

The product of two upper triangular matrices, will also be an upper triangular matrix. Thus when i > j , we know that i > j . When $i\le j$, then we need to use the same method described in algorithm 1 .

Each element of the product matrix was determined as the sum of k products of two corresponding elements in the for-loop of q. However, since the terms in the sum from j + 1 to k will be zero. We can then adjust k to j in the for-loop of q. Similarly, we can adjust the lower boundary of 1 to i .

Write Algorithm

Making these adjustments will then lead to the following algorithm:

for i = 1 to n

for j: = 1 to n

$c_{ij}:0$

if $i\le j$ then

for q := i to j

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

return C

Thus each element of the product matrix is the sum of the product of the corresponding elements in the $i^{th}$ row of the first matrix A and the $j^{th}$ column in the second matrix B. However, since the matrices are upper triangular matrices, we only need to take the sum over the i to $j^{th}$ element (as all other products will be zero).