# Techniques to bound products of upper triangular matrices and their inverses

Let $A_0, \dots, A_{n-1}$ be upper triangular matrices with ones on the diagonal. Let $B_{n-1}, \dots, B_0$ be of the same form.
I am interested in bounding $$|| A_0 \dots A_{n-1} B_{n-1}^{-1} \dots B_0^{-1}||$$ and in particular showing that this product is close to the identity when $A_i$ and $B_i$ are close (specifically, $||A_i - B_i|| \leq \delta \lambda^{- \min(i, n-i)}$ where $\lambda>1$).

In general, this will probably not be possible, but there may be conditions when there are interesting bounds.

The problem is, I don't really know anything about techniques for bounding products of matrices. There is the obvious multiplicativity of the matrix (i.e., operator) norm, but it is far from best possible in this case. For instance, it is easy to check that the norm can grow at most polynomially in $n$ if the norms of the $A_i, B_i$ are bounded above by some constant.

Hence:

Question: What techniques/tricks are there for bounding these kinds of products of matrices?

Unfortunately I don't know exactly which techniques would be useful, so I'd appreciate any pointers to relevant papers or books.

I can at least explain how the problem is motivated. Namely, we have a Holder-continuous matrix-valued function $A: X \to GL_m(\mathbb{R})$ for $X$ a compact metric space.
Then the $A_i$ will be the values $A(T^ix)$ and the $B_i$ will be $A(T^ip)$ for $p$ close to $x$. The multiplicative ergodic theorem states that the norm products $||A_0 \dots A_{n-1}||$ grow like $e^{\lambda n}$ almost everywhere (in $x$) with respect to any invariant measure (where $\lambda$ is the maximal Lyapunov exponent), but in the case of upper triangular matrices, this is actually immediate---we even have polynomial growth if ones are on the diagonal (a corollary of the nilpotence of strictly upper triangular matrices). The multiplicative ergodic theorem and its variants were used in a paper that motivated the problem I'm working on, but it doesn't quite seem to help here (because we make slightly different assumptions), which is why I was curious about other techniques.

-

The standard trick to quantify the joint continuity of a product operation such as $(A_1,\ldots,A_k) \to A_1 \ldots A_k$ (which is essentially what you are trying to do here) is to split a difference such as

$$A_1 \ldots A_k - B_1 \ldots B_k$$

as the telescoping sum of $k$ expressions of the form

$$A_1 \ldots A_{i-1} (A_i - B_i) B_{i+1} \ldots B_k$$

and then estimate each term of the latter separately by various standard inequalities, e.g.

$$\|AB\|_{op} \leq \|A\|_{op} \|B\|_{op}.$$

This will give some bound on the norm of the difference of the product in terms of the norms of the individual differences $A_i - B_i$.

A similar device will also control $A_1 \ldots A_{n-1} B_{n-1}^{-1} \ldots B_1^{-1} - I$.

-
I fixed your math display involving norms: since you had underscores in it, the MarkDown/jsmath combination chokes on it, and wrapping it with backticks ` usually does the trick. – Mariano Suárez-Alvarez Jul 16 '10 at 22:15
Thanks! This is useful. – Akhil Mathew Jul 16 '10 at 23:34

A variant of the previous answer which uses the particular form of the matrices.

I shall just take four matrices $A_{1}, A_{2}, B_{2}, B_{1}$, upper triangular with 1's on the diagonal, because the general case reduces to this one.

Consider the group of $n \times n$ real upper triangular matrices with 1's on the diagonal. That is a Carnot group! Identify it with its Lie algebra because the exponential is bijective. Let $Q= \sum_{i=1}^{n-1} (n-i) i$, that is called the homogeneous dimension.

Then you have two norms on this group: the first one is a Carnot-Caratheodory norm, call it '$\| A\|_{CC}$' , the other one is just an euclidean norm, call it $\|A \|$ . These norms have the properties:

1. $\| AB \|_{CC} \leq \| A \|_{CC} + \|B\|_{CC}$,

2. $\|A\|_{CC}$ grows like (is comparable with) $\|A \|^{1/Q}$.

Now, suppose we want to estimate $\|A_{1} A_{2} B_{2}^{-1} B_{1}^{-1}\|_{CC}$, then we do like this:

$\|A_{1} A_{2} B_{2}^{-1} B_{1}^{-1}\|_{CC} = \|A_{1} A_{2} B_{2}^{-1} A_{1}^{-1} A_{1}B_{1}^{-1}\|_{CC} \leq \|A_{1} A_{2} B_{2}^{-1} A_{1}^{-1} \|_{CC} + \|A_{1}B_{1}^{-1}\|_{CC}$

You only need to estimate now the first term from the right. Remember that because the group is nilpotent the Baker-Campbell-Hausdorff formula (i e the multiplication law when you identify the Lie algebra with the Lie group) is polynomial. Then you get, by simply taking the Euclidean norm of the multiplication, that

$\|A_{1} A_{2} B_{2}^{-1} A_{1}^{-1} A_{1}B_{1}^{-1}\| \leq \mathcal{O}(\|A_{1}\|) \|B_{2}^{-1} A_{1}^{-1}\|_{CC}^{Q}$

And that is it, you may iterate the procedure if you have more matrices!

-

The definitive texts that I know of for matrix analysis (as distinguished from it's more general sibling,linear algebra) are Richard Bellman's classic Introduction to Matrix Analysis,as well as Roger A.Horn and Charles R.Johnson's 2 more recent books, Matrix Analysis and Topics in Matrix Analysis.

I used all 3 in my advanced differential equations course and found all of them fascinating and very useful. I'm certain you'll find all the basic results in thier union along with references to more specialized related results.

-
It's almost as if you didn't read the question at all.. – Harry Gindi Jul 16 '10 at 22:19
Andrew, unless you have reason to think that those texts contain things specifically relevant to this question, I don't think this is a very helpful answer. Matrix analysis is a vast topic, the nilpotent case that Akhil is asking about has its own peculiarities and distinguished features, and your answer comes across as a bit of a stab in the dark. – Yemon Choi Jul 16 '10 at 22:27
To comment further, not every question on MO is a book/reference request... – Harry Gindi Jul 16 '10 at 22:30
@Harry Quoting from the above post: "Unfortunately I don't know exactly which techniques would be useful, so I'd appreciate any pointers to relevant papers or books."@Yemon Yes,it is a stab in the dark since my knowledge of this area is rather limited. But these are very useful and standard references and he may indeed find what he needs in there.So how can it hurt? – The Mathemagician Jul 16 '10 at 22:45
I actually knew nothing about this sort of things, and was not familiar with the term "matrix analysis" so +1 - thanks! My question was itself something of a stab in the dark, so such an answer is helpful. – Akhil Mathew Jul 16 '10 at 23:32