Showing that upper triangular matrices form a subgroup

[Mr Davis 97]

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)$

Homework Equations

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]

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))?

 

[fresh_42]

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)$

Homework Equations

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]

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.

 

[Mr Davis 97]

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]

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]

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.

 

[StoneTemplePython]

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$

 

[mathwonk]

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.

 

[Ray Vickson]

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.

 

[fresh_42]

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]

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.