Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Linear Algebra
High School Linear Algebra

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search