Product of Upper Triangular Matrices

Date: 09/23/2003 at 18:40:42
From: Francis
Subject: Matrices

Show that the product of two upper triangular matrices is an upper
triangular matrix. 

Date: 09/24/2003 at 02:34:24
From: Doctor Jacques
Subject: Re: Matrices

Hi Francis,

A matrix A = a[i,j] is upper triangular if all elements below the 
main diagonal are 0, i.e:

  i > j  --> a[i,j] = 0

In this case, we have a product C = A*B, and we must show that C is 
upper triangluar, i.e. we must show:

  i > j --> c[i,j] = 0

We compute c[i,j] as

  c[i,j] = SUM (a[i,k]*b[k,j])   (sum over k)

Let us assume that i > j. We must show that c[i,j] = 0.

The only non-zero terms in this sum are those where both factors are 
different from 0. As we know that A and B are upper triangular, we 
have:

  i > k  --> a[i,k] = 0
  k > j  --> b[k,j] = 0

For *both* factors to be different from 0, we must have:

  i <= k
  k <= j

and, together, these relations show that i <= j, contrary to the 
hypothesis.

There is a graphical way of seeing this. The element c[i,j] is the 
scalar product of the ith row of A by the jth column of B.

     [*****]     [*****]  
     [0****]     [0****]
     [00***]     [00***]
i->  [000**]     [000**]
     [0000*]     [0000*]
                    ^
                    j

The ith row of A has (i-1) 0's at the beginning, so the first (i-1) 
terms of the sum will be 0. The jth colunm of B has (n - j) 0's at 
the end, so the last (n-j) terms of the sum are also 0. This means 
that there can be at most

  n - (n - j) - (i - 1) = j - i + 1

non-zero terms in the sum, and this can only be >= 1 if i <= j, i.e 
for elements of C on or above the diagonal, which effectively says 
that C is upper triangular.

Does this help?  Write back if you'd like to talk about this 
some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/