Growth in products of matrices: fastest, average, and generic (2024)

2.1. Matrices $A(k)$ and $B(m)$

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

First we note that if $k\cdot m\geq 4$, then the semigroup generated by $A(k)$ and $B(m)$ is free. Otherwise, it is a big open problem for what values of $k$ and $m$ this (semi)group is free; see e.g. [10], [19] and references therein. We just mention here that there is no pair $(k,m)$ of rational numbers $0<k,m<2$ is known such that the group generated by $A(k)$ and $B(m)$ is free. The relevance of freeness of the semigroup to questions about products of matrices will be mentioned in Section 4.

1. In [3], it was proved that the maximum growth in products of $n$ matrices of the form $w(A(k),B(k))$ for integers $k\geq 2$ is achieved by the words $w=(A(k)B(k))^{\frac{n}{2}}$ (assuming that $n$ is even). The proof in [3] actually goes through for $k=1$ as well. The reason why the case $k=1$ was ignored in [3] is that the group generated by $A(1)$ and $B(1)$ is not free. However, what matters for us in the present paper is that the semigroup generated by $A(1)$ and $B(1)$ is free.

With these facts established, it is not hard to precisely evaluate the maximum growth rate of the matrix entries in $w(A(k),B(k))$ for various values of $k\geq 1$. This can be done either by solving a system of recurrence relations for the entries of $(A(k)B(k))^{\frac{n}{2}}$ (this is how it was done in [3]) or by computing the eigenvalues of the matrix $A(k)B(k)$.

We use the latter method here. Compute $A(k)B(k)=\left(\begin{array}[]{cc}1+k^{2}&k\\k&1\end{array}\right)$. The largest eigenvalue of this matrix is $s=\frac{1}{2}(k+\sqrt{k^{2}+4})$.

In particular, for $k=2$ the largest eigenvalue of $A(2)B(2)$ is $3+\sqrt{8}$. Then the largest entry of $(A(2)B(2))^{\frac{n}{2}}$ is $O((\sqrt{3+\sqrt{8}})^{\frac{n}{2}})=O((1+\sqrt{2})^{n})$.Note that $1+\sqrt{2}\approx 2.414$.

In fact, [3] gives a precise formula for the largest entry in $(A(2)B(2))^{\frac{n}{2}}$. It is
$(\frac{1}{2}+\frac{1}{\sqrt{8}})(1+\sqrt{2})^{n}+(\frac{1}{2}-\frac{1}{\sqrt{8$.

2. As one would expect, the maximum growth of the entries in matrices $w(A(1),B(1))$ is the slowest among all $w(A(k),B(k))$ for integers $k\geq 1$. The largest entries in the corresponding matrices $(A(1)B(1))^{\frac{n}{2}}$ are $O((\frac{3}{2}+\frac{\sqrt{5}}{2})^{n})$. Note that $\frac{3}{2}+\frac{\sqrt{5}}{2}\approx 1.618$.

3. In [6], the authors have determined the maximum growth of the entries in matrices $w(A(k),B(m))$ for all integer $k,m\geq 1$.

Now we establish the following generalization of the above mentioned results from [3] and [6]:

2.2. Other pairs of matrices

Our Theorem 1 can help handle some other pairs of matrices as well. For example, let $X=\left(\begin{array}[]{cc}1&1\\0&1\end{array}\right),\hskip 5.69046ptY=\left(\begin{array}[]{cc}1&0\\1&1\end{array}\right)$. Then, let $U=XY=\left(\begin{array}[]{cc}2&1\\1&1\end{array}\right),\hskip 5.69046ptV=YX=\left(\begin{array}[]{cc}1&1\\1&2\end{array}\right)$.

Then the fastest growth of the entries in a product of the matrices $U$ and $V$ is given by matrices $U^{n}$ or $V^{n}$ because in these products, the matrices $X$ and $Y$ alternate and this gives the fastest growth according to Theorem 1. The largest eigenvalue of either matrix ($U$ or $V$) is 2, so the largest entries of $U^{n}$ and $V^{n}$ are $O(2^{n})$.

A similar argument applies, in particular, to the pair of matrices $(XY,Y)$ as well as to pairs of matrices of the form $(A(k)B(m),B(m)A(k))$ with $k,m\geq 2$.

Another example is given by the matrices, say, $U=XYX=\left(\begin{array}[]{cc}2&3\\1&2\end{array}\right),\hskip 5.69046ptV=Y=\left(\begin{array}[]{cc}1&0\\1&1\end{array}\right)$.Again by Theorem 1, the fastest growth of the entries in a product of the matrices $U$ and $V$ is given by matrices $(UV)^{\frac{n}{2}}$ since $UV=XYXY$.

Now let us look at the pair $(XY,XY^{2})$; this pair was used as an example in Pollicott’s paper [17]. Denote $U=XY=\left(\begin{array}[]{cc}2&1\\1&1\end{array}\right),\hskip 5.69046ptV=XY^{2}=\left(\begin{array}[]{cc}3&1\\2&1\end{array}\right)$. It may seem that the fastest growth should be provided by matrices $U^{n}$ since that would give an alternating product of $X$ and $Y$. However, here $V=XY^{2}$ is just a single matrix, not a product of matrices, so it is obviously more “beneficial” for a faster growth to have powers of $V$ rather than powers of $U$ or any combination of $U$ and $V$.

The largest eigenvalue of the matrix $V$ is $2+\sqrt{3}$, so the largest entry in $V^{n}$ is $O((2+\sqrt{3})^{n})$.

2.3. Matrices $A(2)$ and $B(-2)$

This pair of matrices is rather mysterious in the sense that it is not at all clear what positive words $w(A,B)$ would give the fastest growth of the largest entry.Note that the matrix $A(2)B(-2)=\left(\begin{array}[]{cc}-3&2\\-2&1\end{array}\right)$ has the eigenvalue $\lambda=-1$ of multiplicity 2, so the entries of the matrices $(A(2)B(-2))^{\frac{n}{2}}$ grow linearly in $n$.

According to computer experiments, the largest (by the absolute value) entries among all $w(A(2),B(-2))$ of length $n$ occur in $(A^{2}B^{2})^{\frac{n}{4}}$, and these entries are $O((\sqrt{2+\sqrt{3}})^{n})$ since $(2+\sqrt{3})^{2}=7+\sqrt{48}$ is the largest (by the absolute value) eigenvalue of the matrix $A^{2}B^{2}=\left(\begin{array}[]{cc}-15&4\\-4&1\end{array}\right)$. Note that $\sqrt{2+\sqrt{3}}\approx 1.93$.

3.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(1)$ or $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{b}_{n}=\frac{1}{2}(\bar{a}_{n-1}+\bar{b}_{n-1})+\frac{1}{2}\bar{b}_{n-1}=$.

From this, $\bar{b}_{n}=2\bar{a}_{n-1}-\frac{3}{2}\bar{a}_{n}$, and then $\bar{a}_{n}=2\bar{a}_{n-1}-\frac{3}{4}\bar{a}_{n-2}$. Solving the latter recurrence relation for $\bar{a}_{n}$, we get that $\bar{a}_{n}$ is a linear combination of $(\frac{3}{2})^{n}$ and $(\frac{1}{2})^{n}$. Therefore, $\bar{a}_{n}$ is $O((\frac{3}{2})^{n})$, and so is $\bar{b}_{n}$. The recurrence relations for $\bar{c}_{n}$ and $\bar{d}_{n}$ are similar.

3.2. Average growth for products of $A(2)$ and $B(2)$

Using the same notation in this case, we get

$\bar{a}_{n}=\frac{1}{2}\bar{a}_{n-1}+\frac{1}{2}(\bar{a}_{n-1}+2\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}$.

From this we see that $\bar{b}_{n}=\bar{a}_{n}$, whence $\bar{a}_{n}=2\bar{a}_{n-1}$. Therefore, $\bar{a}_{n}=O(2^{n})$ and so is $\bar{b}_{n}$. The recurrence relations for $\bar{c}_{n}$ and $\bar{d}_{n}$ are similar.