# Show that the product of upper triangular matrices is upper triangular

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.

-
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

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?
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. – Nick Peterson Jul 10 '13 at 2:50