# Showing that upper triangular matrices form a subgroup

## Homework Statement

Let ##n \in \mathbb{Z}^+## and let ##F## be a field. Prove that the set ##H = \{(A_{ij}) \in GL_n (F) ~ | ~ A_{ij} = 0 ~ \forall i > j \}## is a subgroup of ##GL_n (F)##

## The Attempt at a Solution

So clearly the set is nonempty since ##I_n## is upper triangular. Now let ##A, B \in H##. We want to show that ##(AB)_{ij} = 0 ~ \forall i > j##. So ##(AB)_{ij} = \sum_{k=1}^n A_{ik}B_{kj}##. Now here is where I'm a bit stuck. I know that the fact that ##A## and ##B## are both in ##H## means that when ##i > j## we'll have ##\sum_{k=1}^n A_{ik}B_{kj} = 0##. But I am not sure how to show this clearly...

mathwonk
Homework Helper
2020 Award
being upper triangular means that the corresponding linear transformation T has the property that T(ej) is a linear combination of those basis vectors ei with i ≤ j. You might see if you can show this property is preserved under composition. I.e. if it is true for both S and T, then what about S(T(ej))?

Last edited:
fresh_42
Mentor

## Homework Statement

Let ##n \in \mathbb{Z}^+## and let ##F## be a field. Prove that the set ##H = \{(A_{ij}) \in GL_n (F) ~ | ~ A_{ij} = 0 ~ \forall i > j \}## is a subgroup of ##GL_n (F)##

## The Attempt at a Solution

So clearly the set is nonempty since ##I_n## is upper triangular. Now let ##A, B \in H##. We want to show that ##(AB)_{ij} = 0 ~ \forall i > j##. So ##(AB)_{ij} = \sum_{k=1}^n A_{ik}B_{kj}##. Now here is where I'm a bit stuck. I know that the fact that ##A## and ##B## are both in ##H## means that when ##i > j## we'll have ##\sum_{k=1}^n A_{ik}B_{kj} = 0##. But I am not sure how to show this clearly...
Of course you can simply compute ##AB^{-1}## where you need only calculate the diagonal elements of ##B^{-1}##. This is straight forward, but boring and a mess of indices. O.k the mess is not that big, you only need 5 different indices. How about another approach? Your matrices are all of the form ##A=D+S## where ##D## is a diagonal matrix and ##S## is a strict upper triangular matrix, i.e. nilpotent. I would first eliminate ##D## such that it becomes ##I## and then see what multiplications do.

Orodruin
Staff Emeritus
Homework Helper
Gold Member
To go in the direction you were going, I would suggest removing terms that are zero from your sum. For i > j you should find that none of the terms are non-zero.

To go in the direction you were going, I would suggest removing terms that are zero from your sum. For i > j you should find that none of the terms are non-zero.
Is the following explicit enough? For ##i > j##, ##(AB)_{ij} = \sum_{k=1}^n A_{ik}B_{kj} = \sum_{k=1}^{i-1} A_{ik}B_{kj} + \sum_{k=i}^n A_{ik}B_{kj} = 0 + 0 = 0##, since for the former sum ##k \leq i-1 \implies A_{ik} =0## and for the latter sum ##k \geq i \implies B_{kj} =0 ##

fresh_42
Mentor
Is the following explicit enough? For ##i > j##, ##(AB)_{ij} = \sum_{k=1}^n A_{ik}B_{kj} = \sum_{k=1}^{i-1} A_{ik}B_{kj} + \sum_{k=i}^n A_{ik}B_{kj} = 0 + 0 = 0##, since for the former sum ##k \leq i-1 \implies A_{ik} =0## and for the latter sum ##k \geq i \implies B_{kj} =0 ##
Yes. I would have written ##k \geq i > j## to make ##B_{kj}=0## easier to see, but that's correct. But you still have the problem with the inverse.

Mr Davis 97
Yes. I would have written ##k \geq i > j## to make ##B_{kj}=0## easier to see, but that's correct. But you still have the problem with the inverse.
Right... Is there a element-wise definition of the inverse? Is there a formula for ##(A^{-1})_{ij}## that would be useful?

fresh_42
Mentor
Right... Is there a element-wise definition of the inverse? Is there a formula for ##(A^{-1})_{ij}## that would be useful?
Yes, there is. It's a bit ugly, but so are these many coordinates. You can look it up on Wikipedia under Invertible Matrix, resp. Adjugate Matrix, but I think it's easier to tell. In order to calculate ##a'_{ij} := (A^{-1})_{ij}## you proceed as follows: Multiply ##1## by the determinant of the matrix which you get by erasing the i-th row and j-th column from ##A##. Then multiply it by ##(-1)^{i+j}## and at last of course by ##\dfrac{1}{\det A}##. At the end transpose that thing.

But I think it's easier to work with the nilpotent submatrix, because this can be inverted easily. You use the trick that ##(x^n-1)=(x-1)(x^{n-1}+x^{n-2}+\ldots +x^2+x+1)## and the fact, that every multiplication shifts the triangle to the upper right until it finally disappears. I haven't worked it out, but it sounds funnier than to deal with the cofactors of a matrix.

Edit: On the other hand, you only have to do the procedure for a single ##a'_{ij}## in the lower half and should get a zero row (or column) in this minor determinant.

Last edited:
StoneTemplePython
Gold Member
There's probably a nice way to show this with graphs -- i.e. composing two feedforward graphs with no cycles (other than self loops) cannot induce a cycle (other than said self loops). edit: nevermind the graphs point as that is done.

But I think it's easier to work with the nilpotent submatrix, because this can be inverted easily. You use the trick that ##(x^n-1)=(x-1)(x^{n-1}+x^{n-2}+\ldots +x^2+x+1)## and the fact, that every multiplication shifts the triangle to the upper right until it finally disappears. I haven't worked it out, but it sounds funnier than to deal with the cofactors of a matrix.

Edit: On the other hand, you only have to do the procedure for a single ##a'_{ij}## in the lower half and should get a zero row (or column) in this minor determinant.

Sounds a bit like a recent math challenge problem to me, hmmm...

By the way, can't this unpleasantness be bypassed via Cayley Hamilton? That seems like a standard result that could be used -- i.e. consider ##\mathbf A^{-1}p\big(\mathbf A\big)##
- - - - -

edit:

even without Cayley Hamilton we'd know that an ##n## x ##n## matrix is annihilated by

##g\big(\mathbf A\big) := \sum_{k=0}^{n^2} c_k \mathbf A^{k} = \mathbf 0##

where at least one ##c_k \neq 0## (and since ##\mathbf A## is nonsingular this implies at least two ##c_k \neq 0##)

as said matrix can be interpreted as living in an ##n^2## dimensional vector space (we can tighten this of course for upper triangular ones, but it is fine as a loose bound)

then, of course, consider ##\mathbf A^{-r} g\big(\mathbf A\big)## for a well chosen natural number ##r##

Last edited:
mathwonk
Homework Helper
2020 Award
following up on post #2, recall that the entries in the jth column of the matrix of the linear transformation T, are the coefficients of T(ej). Hence if the only non zero ones occur above the diagonal, that means that T(ej) is a linear copmbination of just those ei with i≤j. Now suppose both S and T satisfy this condition and consider SoT. We want to show that (SoT)(ej) = S(T(ej)) is also a linear combination of the ei with i≤ j. But T(ej) is a linear combination of ei with i ≤ j, and when we apply T to each of these, again by the hypothesis applied to T, we get several linear combinations of the ei, all with i ≤ j. I.e. the only ei occurring in S(ej) have i ≤ j, and if i ≤ j, the only ek occurring in S(ei) have k ≤ i ≤ j. So all ek occurring have k ≤ j. I apologize if this did not seem clear. I hoped it would seem much simpler than bashing indices. of course just looking at small matrices, say 2x2 or 3x3, it is pretty obvious, but I gathered the question was how to prove it.

Mr Davis 97
Ray Vickson
Homework Helper
Dearly Missed
Right... Is there a element-wise definition of the inverse? Is there a formula for ##(A^{-1})_{ij}## that would be useful?

Since ##\det(A) = a_{11} a_{22} \cdots a_{nn},## an inverse will exist if, and only if all the diagonal elements are non-zero. In that case, the inverse matrix ##B = A^{-1}## has columns ##[b_1, b_2, \ldots, b_n]## that are the solutions of ##A b_i = e_i,## where ##e_i## is column ##i## of the identity matrix. So ##b_1## satisfies the equations
$$\begin{array}{rrrcrc} a_{11} b_{11}&+a_{12} b_{12} & + a_{13}b_{13} & \cdots & + a_{1n} b_{1n}&= 1 \\ & a_{22}b_{12} & + a_{23}b_{13} & \cdots & + a_{2n} b_{1n} & = 0 \\ & & a_{33} b_{13} & \cdots & +a_{3n} b_{1n} &=0 \\ & & & \vdots & \vdots & \vdots \\ & & & & a_{nn} b_{1n} & =0 \end{array}$$
The last equation gives ##b_{1n} = 0## (because ##a_{nn} \neq 0##). Then, the second-last equation gives ##b_{1,n-1} = 0##, then the third-last gives ##b_{1,n-2} = 0,## etc. That continues all the way down to ##b_{12}##, so the first column of ##B## has the form ##b_1 = (b_{11},0,0,\ldots, 0)^T.## In the same way you can show that the last ##n-2## components of ##b_2## are all zero, so ##b_2 = (b_{21},b_{22},0,0,\ldots, 0)^T,## that the last ##n-3## elements of ##b_3## are zero, etc, etc. That shows very explicitly that ##B## is upper-triangular. It also gives a handy way of actually computing the inverse.

Orodruin
fresh_42
Mentor
I think the shortest way is actually the adjugate. Removing a row and a column of a non-zero element in the upper triangular yields a zero in the diagonal. QED.

mathwonk
Homework Helper
2020 Award
if you want to show the inverse is also upper triangular, the determinant formula for the inverse seems nice as stated above.

if you want to try the linear map approach, it seems also easy by induction. i.e. T(e1) = ce1, since T(e1) depends only on ej with j ≤ 1. Hence applying T^-1 to both sides, e1 = T^-1(ce1), so T^-1(e1) = c^-1e1.
as desired,

Now T(e2) = ae1 + be2 by hypothesis, so again apply T^-1 to both sides and get e2 = aT^-1(e1) + bT^-1(e2), so solving for T^-1(e2) = (1/b)(e2 - aT^-1(e1)), which involves only e1 and e2.........

I.e. this inductive approach shows that T^-1(ej) is a linear combination of ej and of T^-1(ei) with i <j, hence since those latter vectors are linear combinations of ek with k ≤ i, by induction, we are done.

of course this uses the observation that an invertible upper triangular matrix has non zero entries on the diagonal.