Product of Upper Triangular MatricesDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/