Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a question. Prove that the product of an [arbitrary] number of upper triangular matrices of [arbitrary] size with [undetermined] upper triangular entries is upper triangular using induction? Should I use transfinite induction? I don't even know where to start!

How do you even prove the statement: "prove that the product of n upper triangular matrices with undetermined upper triangular entries is upper triangular"?

I know that the product of n upper triangular matrices with all upper triangular entries = 1 is

[1 3 6 ... n(n+1)/2
 0 1 3 ... (n-1)n/2
 0 0 1 ... (n-2)(n-1)/2
 . .
 . .
 . .

with the pattern continuing such that a_(nn) = [n-(n-1)][n-(n-2)]/2.

Thanks.

share|improve this question
    
Why do you mention transfinite induction? Are you considering infinite matrices? Infinite products? In the latter case how would you define them? –  Marc van Leeuwen Jul 10 '13 at 2:10
    
If you are new to matrices, I would suggest studying finite ones a bit first. Infinite matrices have extra complications, such as that products of them aren't defined in general, although a definition for upper triangular matrices (or more generally matrices all of whose columns are effectively finite) is possible. As for infinite products, these are even more delicate (and frankly, I've never seen them used), you'd better not consider that. And no, there is no direct relation with Markov chains (though I can imagine consideration of the latter using limits of increasing powers of matrices). –  Marc van Leeuwen Jul 10 '13 at 13:50
add comment

1 Answer 1

up vote 4 down vote accepted

HINTS:

First and foremost: note that it is enough to prove that the product of two upper-triangular matrices is upper-triangular. Why? This is a direct consequence of the associativity of matrix multiplication. For instance, you can write $A_1A_2A_3=(A_1A_2)A_3$; if we know $A_1A_2$ is upper triangular, then this association gives us the product of two upper triangular matrices, etc. You could also use induction for this, using precisely this sort of argument.

So, all that remains is to show that the product of two upper triangular matrices is again upper triangular. You can do this by induction too; think about the following: an upper triangular matrix can be broken up as an upper block-diagonal matrix $$ \begin{bmatrix}a_{1,1} & a_{,12} & \cdots & a_{1,n+1}\\0 & a_{2,2}& \cdots & a_{2,n+1}\\ 0 & 0 & \ddots & \cdots \\0 & 0 & \cdots & a_{n+1,n+1}\end{bmatrix}=\left[\begin{array}{c|c}A_n & \begin{array}{c}a_{1,n+1}\\a_{2,n+1}\\\vdots\\a_{n,n+1}\end{array}\\\hline 0\ 0\ \cdots\ 0\ & a_{n+1,n+1}\end{array}\right], $$ where $A_n$ is the first $n$ rows/columns of your original matrix, and is itself upper triangular. Can you use this to prove the inductive step?

share|improve this answer
    
It's sort of a "collapsed" form of induction: there are a number of arguments which involve a combination, using some operation, of two mathematical objects having a particular property which produces a third one with the same property. From there, it immediately follows that since "the two become one" and preserve the property, the same thing will happen for any number of repetitions of the operation on further such objects. –  RecklessReckoner Jul 10 '13 at 2:06
    
@AbhishekMallela What about it? –  Nicholas R. Peterson Jul 10 '13 at 2:21
    
If you multiply two block matrices of the form in my answer, the result will be another block matrix of the same form; if you think about how block matrix multiplication works, you should be able to show that the upper left block is $A_nB_n$ (where $B_n$ is defined similarly for a second block-diagonal matrix of size $(n+1)\times(n+1)$), and the bottom block ends up being all 0's. –  Nicholas R. Peterson Jul 10 '13 at 2:50
    
@AbhishekMallela No problem! Glad to help. And please, if you found this helpful, consider accepting my answer. –  Nicholas R. Peterson Jul 10 '13 at 2:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.