Easy estimates of Lyapunov exponents for random products of matrices
Nadya Nabahi, Vladimir Shpilrain · 2025
Read Easy estimates of Lyapunov exponents for random products of matrices by Nadya Nabahi, Vladimir Shpilrain (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-18944.txt.
Introduction
Multiply random square matrices again and again, and how fast does the product grow? Nadya Nabahi and Vladimir Shpilrain study that growth for products built from a fixed set of real matrices. The long-run growth rate is summed up by the largest Lyapunov exponent, a number that also matters in chaos theory and random dynamics.
The authors answer a first question about the expected size of the largest entry in such a product, under mild conditions on the matrix entries. For the second question, they offer a very simple, fast method that bounds the Lyapunov exponent from above. Easy bounds of this kind are useful when exact growth rates are out of reach.
Catalog record
| CREATOR | Nadya Nabahi, Vladimir Shpilrain |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 17 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-18944
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Easy estimates of Lyapunov exponents for random products of matrices Nadya Nabahi, Vladimir Shpilrain Abstract . The problems that we consider in this paper are as follows. Let A 1 , … , A k A_{1},\ldots,A_{k} be square matrices (over reals). Let W = w ( A 1 , … , A k ) W=w(A_{1},\ldots,A_{k}) be a random product of n n matrices. What is the expected absolute value of the largest (in the absolute value) entry in such a random product? What is the (maximal) Lyapunov exponent for a random matrix product like that? We give a complete answer to the first question. For the second question, we offer a very simple and efficient method to produce an upper bound on the Lyapunov exponent. 1. Introduction The first problem that we consider in this paper is as follows. Let A_{1},\ldots,A_{k} be square matrices (over reals). Let W=w(A_{1},\ldots,A_{k}) be a random product of n matrices. What is the expected absolute value of the largest (in the absolute value) entry in such a random product? To make the exposition easier to follow, we do what some other authors do: we limit the exposition to the case of just two matrices, A and B . By a “random product” of A and B we will typically mean a product of matrices where each matrix is either A (with probability p ) or B (with probability 1-p ). In Section 2 , we show that the above problem has a surprisingly simple solution. Theorem 1 . Suppose all eigenvalues of the matrix M=pA+(1-p)B are distinct real numbers, and let \mu be the largest positive eigenvalue of M . Then the expectation of the largest (in the absolute value) entry of a random product w(A,B) of length n is \Theta(\mu^{n}) . Theorem 1 applies, in particular, to the case where the matrix M=pA+(1-p)B has only positive entries; then the existence of the largest real eigenvalue (the Perron–Frobenius eigenvalue) is guaranteed by the Perron–Frobenius theorem. The proof of Theorem 1 is given at the end of Section 2 . A more difficult problem, of interest in the theory of stochastic processes, is to estimate L=\lim_{n\to\infty}\sqrt[n]{||w(A,B)||} , where ||w(A,B)|| denotes the norm of the matrix W=w(A,B) . The natural logarithm of L is what is called the (maximal) Lyapunov exponent of a random product of A and B , see e.g. [ 8 ] . For strictly positive non-singular matrices, Pollicott [ 8 ] reported an algorithm to estimate the Lyapunov exponent \lambda=\log L with any desired precision. Pollicott mentions that “it is a fundamental problem to find both an explicit expression for \lambda and a useful method of accurate approximation”. Our contribution to this problem is a very simple and efficient method to produce an upper bound on the Lyapunov exponent based on Theorem 1 and the following Theorem 2 . Let A and B be d\times d matrices over reals. Suppose the matrix M=pA+(1-p)B has only positive entries, and let \mu be the Perron–Frobenius eigenvalue of M . Then the Lyapunov exponent \lambda of a random product of matrices A and B satisfies \lambda\leq\log\mu with probability 1. Theorem 1 and Theorem 2 generalize to an arbitrary finite collection \{A_{1},\ldots,A_{k}\} of matrices, not just for pairs. Theorem 2 , in combination with Theorem 1 , gives a very simple and efficient method for bounding the Lyapunov exponent from above. We note that altogether different (analytical) methods for bounding the Lyapunov exponent were previously used in the literature, see e.g. [ 5 ] , [ 9 ] , and [ 12 ] . We compare our bounds to theirs for some particular pairs of matrices in Section 3 . We also mention that our method applies to a larger class of matrices than methods of [ 5 ] , [ 9 ] , and [ 12 ] do. In particular, we do not require all the entries of A and B to be positive; it is sufficient that all the entries of the “expectation matrix” M=pA+(1-p)B are positive. Finally, we note that it is also an important problem to determine the maximum possible (in the absolute value) entry G(n) in a product w(A,B) of length n . The number \lim_{n\to\infty}\sqrt[n]{|G(n)|} is called the joint spectral radius of the pair (A,B) of matrices, see e.g. [ 4 ] . Computing the joint spectral radius is a difficult problem in general, although there are results in various special cases, e.g. [ 1 ] , [ 3 ] , [ 6 ] , [ 7 ] . Computing the joint spectral radius of pairs of matrices over integers has important real-life applications, see [ 10 ] for a survey. 2. Average Growth Perhaps surprisingly, computing the average growth rate of the entries in a random product of n matrices A and B (where each factor is A or B with probability p and 1-p , respectively) is easier than computing the maximum growth rate (i.e., the joint spectral radius). A straightforward method for computing the average growth rate is based on solving a system of linear recurrence relations with constant coefficients. To illustrate this method, we start with a couple of particular examples. First we determine the average growth rate of the largest entry in a random product, for p=\frac{1}{2} , of n matrices, each taken from the pair (A(k),B(m)) for a couple of values of k and m , where A(k)=\left(\begin{array}[]{cc}1&k\\ 0&1\end{array}\right),\hskip 5.69046ptB(m)=\left(\begin{array}[]{cc}1&0\\ m&1\end{array}\right) . Then we handle a pair of matrices from Pollicott’s paper [ 8 ] . 2.1. Average growth for products of A(1) and B(1) Let \left(\begin{array}[]{cc}a_{n}&b_{n}\\ c_{n}&d_{n}\end{array}\right) denote the result of multiplying n matrices where each factor is A=A(1) or B=B(1) with probability \frac{1}{2} . Denote the expectation of a_{n} by \bar{a}_{n} , etc. Then, using linearity of the expectation, we have the following recurrence relations for the expectations: \bar{a}_{n}=\frac{1}{2}\bar{a}_{n-1}+\frac{1}{2}(\bar{a}_{n-1}+\bar{b}_{n-1})=\bar{a}_{n-1}+\frac{1}{2}\bar{b}_{n-1} . \bar{b}_{n}=\frac{1}{2}(\bar{a}_{n-1}+\bar{b}_{n-1})+\frac{1}{2}\bar{b}_{n-1}=\frac{1}{2}\bar{a}_{n-1}+\bar{b}_{n-1} . The same recurrence relations hold (independently) for \bar{c}_{n} and \bar{d}_{n} , so it is sufficient to handle just \bar{a}_{n} and \bar{b}_{n} . Following the usual method of solving a “square” system of linear recurrence relations with constant coefficients, we write it in the matrix form: (\bar{a}_{n},\bar{b}_{n})=M\cdot(\bar{a}_{n-1},\bar{b}_{n-1}) , where vectors on the left and on the right should be interpreted as columns. The matrix M here is M=\left(\begin{array}[]{cc}1&\frac{1}{2}\\ \frac{1}{2}&1\end{array}\right) . The solution of the system therefore is (\bar{a}_{n},\bar{b}_{n})=M^{n}\cdot(1,0) . The largest eigenvalue of the matrix M in this case is \frac{3}{2} , so the average growth rate is \mu=\frac{3}{2} . 2.2. Average growth for products of A(2) and B(2) Here we get the following recurrence relations for the expectations \bar{a}_{n},\bar{b}_{n},\bar{c}_{n},\bar{d}_{n} of the entries in a product \left(\begin{array}[]{cc}a_{n}&b_{n}\\ c_{n}&d_{n}\end{array}\right) of n matrices: \bar{a}_{n}=\frac{1}{2}\bar{a}_{n-1}+\frac{1}{2}(\bar{a}_{n-1}+2\bar{b}_{n-1})=\bar{a}_{n-1}+\bar{b}_{n-1} . \bar{b}_{n}=\frac{1}{2}(2\bar{a}_{n-1}+\bar{b}_{n-1})+\frac{1}{2}\bar{b}_{n-1}=\bar{a}_{n-1}+\bar{b}_{n-1} . From this we see that the corresponding matrix M is \left(\begin{array}[]{cc}1&1\\ 1&1\end{array}\right) , and the largest eigenvalue of the matrix M is 2. Thus, in this case the average growth rate is \mu=2 . 2.3. Average growth for products of matrices from Pollicott’s paper In [ 8 ] , Pollicott considered the following two matrices: A=\left(\begin{array}[]{cc}2&1\\ 1&1\end{array}\right),\hskip 5.69046ptB=\left(\begin{array}[]{cc}3&1\\ 2&1\end{array}\right) . Using the same method as in the previous subsections, we have the following system of recurrence relations for the expectations: \bar{a}_{n}=\frac{1}{2}(2\bar{a}_{n-1}+\bar{b}_{n-1})+\frac{1}{2}(3\bar{a}_{n-1}+2\bar{b}_{n-1})=\frac{5}{2}\bar{a}_{n-1}+\frac{3}{2}\bar{b}_{n-1} . \bar{b}_{n}=\frac{1}{2}(\bar{a}_{n-1}+\bar{b}_{n-1})+\frac{1}{2}(\bar{a}_{n-1}+\bar{b}_{n-1})=\bar{a}_{n-1}+\bar{b}_{n-1} . Therefore, the