Techniques to bound products of upper triangular matrices and their inverses - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T23:42:22Z http://mathoverflow.net/feeds/question/32231 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/32231/techniques-to-bound-products-of-upper-triangular-matrices-and-their-inverses Techniques to bound products of upper triangular matrices and their inverses Akhil Mathew 2010-07-16T21:42:45Z 2010-07-23T09:47:10Z <p>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.<br> 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$).</p> <p>In general, this will probably not be possible, but there may be conditions when there are interesting bounds.</p> <p>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.</p> <p>Hence:</p> <p><strong>Question:</strong> What techniques/tricks are there for bounding these kinds of products of matrices?</p> <p>Unfortunately I don't know exactly which techniques would be useful, so I'd appreciate any pointers to relevant papers or books. </p> <p>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.<br> 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.</p> http://mathoverflow.net/questions/32231/techniques-to-bound-products-of-upper-triangular-matrices-and-their-inverses/32233#32233 Answer by Terry Tao for Techniques to bound products of upper triangular matrices and their inverses Terry Tao 2010-07-16T22:04:49Z 2010-07-16T22:13:44Z <p>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</p> <p>$$A_1 \ldots A_k - B_1 \ldots B_k$$</p> <p>as the telescoping sum of $k$ expressions of the form</p> <p>$$A_1 \ldots A_{i-1} (A_i - B_i) B_{i+1} \ldots B_k$$</p> <p>and then estimate each term of the latter separately by various standard inequalities, e.g.</p> <p><code>$$\|AB\|_{op} \leq \|A\|_{op} \|B\|_{op}.$$</code></p> <p>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$.</p> <p>A similar device will also control $A_1 \ldots A_{n-1} B_{n-1}^{-1} \ldots B_1^{-1} - I$.</p> http://mathoverflow.net/questions/32231/techniques-to-bound-products-of-upper-triangular-matrices-and-their-inverses/32235#32235 Answer by Andrew L for Techniques to bound products of upper triangular matrices and their inverses Andrew L 2010-07-16T22:15:58Z 2010-07-16T22:15:58Z <p>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 <em>Introduction to Matrix Analysis</em>,as well as Roger A.Horn and Charles R.Johnson's 2 more recent books, <em>Matrix Analysis</em> and <em>Topics in Matrix Analysis</em>. </p> <p>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. </p> http://mathoverflow.net/questions/32231/techniques-to-bound-products-of-upper-triangular-matrices-and-their-inverses/33072#33072 Answer by Marius Buliga for Techniques to bound products of upper triangular matrices and their inverses Marius Buliga 2010-07-23T09:47:10Z 2010-07-23T09:47:10Z <p>A variant of the previous answer which uses the particular form of the matrices. </p> <p>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. </p> <p>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. </p> <p>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: </p> <ol> <li><p>$\| AB \|<em>{CC} \leq \| A \|</em>{CC} + \|B\|_{CC}$, </p></li> <li><p>$\|A\|_{CC}$ grows like (is comparable with) $\|A \|^{1/Q}$. </p></li> </ol> <p>Now, suppose we want to estimate $\|A_{1} A_{2} B_{2}^{-1} B_{1}^{-1}\|_{CC}$, then we do like this: </p> <p>$\|A_{1} A_{2} B_{2}^{-1} B_{1}^{-1}\|<em>{CC} = \|A</em>{1} A_{2} B_{2}^{-1} A_{1}^{-1} A_{1}B_{1}^{-1}\|<em>{CC} \leq \|A</em>{1} A_{2} B_{2}^{-1} A_{1}^{-1} \|<em>{CC} + \|A</em>{1}B_{1}^{-1}\|_{CC}$</p> <p>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 </p> <p>$\|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}$ </p> <p>And that is it, you may iterate the procedure if you have more matrices!</p>