Lyapunov Exponents for Sparsely Coupled Linear Cocycles Reza Rastegar Abstract This paper studies structured products of real matrices for which the top Lyapunov exponent can be accessed by reducing the dynamics to an amenable generalization of upper triangular matrices. Exploiting prescribed zero patterns (including block-triangularity and sparse decompositions, conveniently encoded by a directed sparsity graph), we obtain explicit, computable bounds and, in favorable cases, formulas for γ 1 \gamma_{1} by combining deterministic triangular controls with a suitable refinement of the Furstenberg–Kifer lemma [ 17 ] for block-triangular products. The estimates apply both to tempered (possibly deterministic) sequences and to stationary ergodic random cocycles under standard integrability. We also discuss applications to perturbation models for linear systems, including low-rank updates, where the reduction converts the problem to lower-dimensional or scalar cocycles. MSC2010: 37H15, 37M25. Keywords : Lyapunov exponents, random triangular matrices, random block matrices, zero entry pattern, graph decomposition, matrix perturbations. 1 Introduction Lyapunov exponents play a central role in the analysis of random and chaotic dynamical systems: they quantify sensitivity to initial conditions and, in the linear-cocycle setting, encode long-time growth rates of matrix products; see, e.g., [ 5 , 6 , 8 , 16 , 37 ] . Despite their importance, explicit formulas are available only for a comparatively small collection of solvable ensembles—classically, many computations focus on 2\times 2 products or on highly symmetric distributions (including several Gaussian-type models); see, for instance, [ 4 , 10 , 11 , 13 , 21 , 23 , 24 , 26 , 27 , 28 , 29 , 30 , 34 ] and [ 1 , 2 , 3 , 9 , 14 , 15 , 22 , 32 ] . The purpose of this paper is to extend and reorganize a few ideas from [ 4 , 17 , 24 , 34 ] into a small toolkit for obtaining computable bounds (and, in favorable cases, explicit values) for Lyapunov exponents of structured matrix products. From a matrix-analysis viewpoint, the guiding principle is that triangular or block-triangular structure—and more generally prescribed sparsity/zero patterns with limited feedback—localize exponential growth to lower-dimensional diagonal dynamics, while the remaining entries contribute at most an explicitly controlled combinatorial factor. Concretely, our bounds are expressed in terms of diagonal-block products together with a directed graph encoding admissible off-diagonal couplings, and are therefore readily computable from a small collection of lower-dimensional norm estimates. The framework covers both stationary/ergodic matrix sequences and deterministic sequences satisfying the temperedness condition ( 1 ), so it can be read as a matrix-analytic toolkit for growth-rate bounds in structured or sparsely coupled linear systems. For an integer d\geq 2 , let {\mathcal{M}}_{d} denote the space of d\times d matrices with real-valued entries. Throughout, we write \|\cdot\| both for a generic norm on {\mathbb{R}}^{d} (when the particular choice is immaterial) and for the induced operator norm on {\mathcal{M}}_{d} . Let {\mathcal{A}}:=(A_{n})_{n\in{\mathbb{N}}} be a sequence in {\mathcal{M}}_{d} such that \displaystyle\limsup_{n\to\infty}\frac{1}{n}\log\|X_{n}\|<\infty\qquad\mbox{\rm where}\qquad X_{n}:=A_{n}\cdots A_{1}. (1) We associate to {\mathcal{A}} the (upper) Lyapunov exponent function \gamma:{\mathbb{R}}^{d}\to{\mathbb{R}}\cup\{-\infty\} defined by \displaystyle\gamma(v):=\limsup_{n\to\infty}\frac{1}{n}\log\|X_{n}v\|. (2) In particular, we define the top (upper) Lyapunov exponent of the sequence {\mathcal{A}} by \displaystyle\gamma_{1}({\mathcal{A}}):=\limsup_{n\to\infty}\frac{1}{n}\log\|X_{n}\|=\sup_{\|v\|=1}\gamma(v). (3) This directional growth rate is the basic object we aim to control in the structured regimes considered below. A particularly clean structure emerges when {\mathcal{A}} is random, stationary, and ergodic and satisfies the standard integrability condition \displaystyle{\mathbb{E}}\left(\log^{+}\|A_{1}\|\right)<\infty, (4) where, for x>0 , \log^{+}x:=\max(0,\log x) , with the convention \log^{+}0:=0 . Oseledets’ multiplicative ergodic theorem then yields deterministically constant Lyapunov exponents \gamma_{1}>\cdots>\gamma_{\ell},\qquad\ell\leq d, together with a corresponding filtration of subspaces {\mathbb{R}}^{d}=E_{1}\supset E_{2}\supset\cdots\supset E_{\ell}\supset E_{\ell+1}:=\{0\}, such that the limsup in ( 2 ) is in fact a limit and \gamma(v)\in\{\gamma_{1},\dots,\gamma_{\ell}\} almost surely, with the value determined by the position of v in the filtration; see [ 7 , Section 2.1] and [ 5 , 6 , 37 ] . In particular, the exponents and subspaces are independent of the realization with probability one. Even in this ergodic framework, however, the exponents \gamma_{k} are rarely available in closed form. A notable exception occurs for triangular cocycles, where the diagonal entries dictate the asymptotic growth. In particular, for upper triangular matrices we have: Proposition 1.1 . [ 34 ] Let {\mathcal{A}}=(A_{k})_{k\in{\mathbb{N}}}\in{\mathcal{M}}_{d}^{\mathbb{N}} be a random, stationary, and ergodic sequence of d\times d invertible matrices with A_{k}(i,j)=0 for i>j and such that ( 4 ) holds. Then, \displaystyle\gamma_{1}=\max_{i\in[d]}{\mathbb{E}}\left(\log|A_{1}(i,i)|\right), where [d]:=\{1,\ldots,d\}. In fact, under the conditions of the proposition, all Lyapunov exponents of {\mathcal{A}} can be identified as distinct elements of the multi-set \{{\mathbb{E}}\left(\log|A_{1}(i,i)|\right)\}_{i=1}^{d} (see Corollary 1 in [ 19 ] and item (iv) on p. 130 of [ 5 , Section 3.2] ). A conceptual explanation for Proposition 1.1 is provided by a lemma of Furstenberg and Kifer [ 17 ] (quoted here as Lemma 2.3 ), which reduces the computation of the top Lyapunov exponent for block-triangular products to that of the diagonal blocks; see, for example, [ 17 , 25 , 12 , 18 , 31 ] . Extensions appear in several directions, including switched systems [ 33 , 35 , 36 ] and linear cocycles in bundles [ 25 , Lemma 3.6] ; see also [ 12 , Proposition 1] , [ 18 , Theorem 1.1] and [ 31 , Lemma 4.9] . The starting point of this paper is that the same block-triangular viewpoint can be packaged into a practical toolkit that continues to be useful beyond the classical stationary-random setting. In particular, the resulting bounds are explicit in terms of diagonal-block growth rates and simple combinatorial parameters of the zero pattern, which makes them amenable to computation in matrix-analytic applications. Our contributions are organized around four structured regimes. Section 2 begins with deterministic control of upper triangular products: for general tempered sequences (not necessarily random), Proposition 2.1 gives a two-sided estimate for \gamma_{1} in terms of diagonal growth rates \alpha_{i}^{\pm} , and Corollary 2.2 recovers the familiar “maximum of diagonal exponents” identity when the relevant diagonal averages converge. In the same section we develop a deterministic Furstenberg–Kifer-type reduction for block-triangular products under Lyapunov-regularity hypotheses on the diagonal blocks (Proposition 2.4 ), providing a modular step that reduces \gamma_{1} to diagonal-block data plus an explicit error term. Section 3 illustrates how these reductions turn concrete perturbation models (including rank-one updates) into lower-dimensional or scalar cocycles with computable Lyapunov exponents, and it clarifies when a perturbation changes only the top exponent. Finally, Section 4 introduces shape graphs for sparse decompositions with disjoint supports and limited feedback, proves an energy–entropy bound (Theorem 4.4 ) of the form \gamma_{1}({\mathcal{A}})\leq\beta+\log k (or \beta+\log k_{*} when O_{d}\in{\mathcal{V}} ), and provides a short “how-to” guide with worked examples in Section 4.1 , including a transfer-matrix/DAG model that makes the mechanism transparent. 2 Block-triangular matrices We begin with the following inequality concerning the top Lyapunov exponent of a given sequence of upper triangular matrices (cf. [ 6 , Lemma 3.1.4] ). Proposition 2.1 . Let {\mathcal{A}}:=(A_{n})_{n\in{\mathbb{N}}} be a sequence of real, invertible upper triangular d\times d matrices (that is A_{n}(j,k)=0 for j>k and A_{n}(j,j)\neq 0, j,k\in[d] ) such that \displaystyle\limsup_{n\to\infty}\frac{1}{n}\log\|A_{n}\|=0. (5) Then, \displaystyle\max_{j\in[d]}\alpha_{j}^{+}\leq\gamma_{1}\leq\max_{j\in[d]}\Big(\alpha_{j}^{+}+\sum_{r=1}^{j-1}\big(\alpha_{r}^{+}-\alpha_{r}^{-}\big)\Big), (6) where \alpha_{i}^{-}:=\liminf_{n\to\infty}\frac{1}{n}\sum_{k=1}^{n}\log|A_{k}(i,i)| and \alpha_{i}^{+}:=\limsup_{n\to\infty}\frac{1}{n}\sum_{k=1}^{n}\log|A_{k}(i,i)|. Proof. The upper bound is an immediate consequence of Lemma 3.1.4 in [ 6 ] which shows that under the conditions of the proposition, \displaystyle\limsup_{n\to\infty}\frac{1}{n}\log|X_{n}(i,j)|\leq\alpha_{j}^{+}+\sum_{r=1}^{j-1}\big(\alpha_{r}^{+}-\alpha_{r}^{-}\big),\qquad\forall i,j\in[d]. The proof of the lower bound given in the following uses a connection between the growth rates of singular values and the Lyapunov exponents of X_{n} . For A\in{\mathcal{M}}_{d}, let \sigma_{1}(A)\geq\cdots\geq\sigma_{d}(A) be singular values of A, that is, eigenvalues of (A^{T}A)^{1/2}, where A^{T} is the transpose of A . Since all norms on {\mathbb{R}}^{d} are equivalent, the top Lyapunov exponent \gamma_{1}({\mathcal{A}}) does not depend on the particular choice of operator norm; in particular we may use the Euclidean norm when discussing singular values. Set \displaystyle\ell^{\sup}_{i}:=\limsup_{n\to\infty}\frac{1}{n}\log\sigma_{i}(X_{n})\qquad\mbox{\rm and}\qquad\ell^{\inf}_{i}:=\liminf_{n\to\infty}\frac{1}{n}\log\sigma_{i}(X_{n}). (7) For a general theory of these growth rates and their relation to the Lyapunov exponents in the case when {\mathcal{A}}=(A_{n})_{n\in{\mathbb{N}}} is non-random, see [ 5 , 7 ] . If {\mathcal{A}} is a random, stationary and ergodic sequence and ( 4 ) holds, then (see, for instance, Theorem 3.4.1 in [ 5 ] ), \displaystyle\ell^{\sup}_{i}=\ell^{\inf}_{i}=\gamma_{i},\qquad\forall i\in[d],\quad\mbox{\rm a.\,s.} For a non random sequence {\mathcal{A}}, it has been shown in [ 7 ] that \displaystyle\qquad\ell_{1}^{\sup}=\gamma_{1}\qquad\mbox{\rm and}\qquad\ell_{i}^{\sup}\leq\gamma_{i}\quad\mbox{for}~i>1, (8) and, furthermore, the above inequalities may be strict. However, it turns out [ 6 , 7 ] that if ( 5 ) holds (such sequences are referred to as tempered in [ 6 , 7 ] ) and the matrices in {\mathcal{A}} are invertible, then following properties are equivalent: (a) (X_{n}^{T}X_{n})^{\frac{1}{2n}} converges as n\to\infty and  (b) \gamma_{i}=\ell_{i}^{\inf}=\ell_{i}^{\sup} for all i\in[d]. (9) A sequence {\mathcal{A}} that satisfies these conditions is called Lyapunov regular, see [ 6 ] for a number of other equivalent conditions (cf. Remark 2.5 below). Proof of lower bound: Let \lambda_{1}(X_{n}) be the largest by absolute value eigenvalue of X_{n}. By Weyl’s inequality [ 20 ] , |\lambda_{1}(X_{n})|\leq\sigma_{1}(X_{n}). Since X_{n}(j,j)=\prod_{i=1}^{n}A_{i}(j,j), \displaystyle\log|\lambda_{1}(X_{n})|=\max_{j\in[d]}\sum_{i=1}^{n}\log|A_{i}(j,j)|\leq\log\sigma_{1}(X_{n}), which implies the lower bound in ( 6 ) by virtue of ( 7 ) and the identity in ( 8 ). ∎ Proposition 2.1 makes precise a common heuristic: for an upper triangular product, the diagonal controls the exponential growth, while off-diagonal terms can only create transient amplification. The quantities \alpha_{i}^{\pm} record the asymptotic growth rates of the diagonal cocycles along each coordinate. When the diagonal averages converge (so \alpha_{i}^{+}=\alpha_{i}^{-} ), Corollary 2.2 recovers the clean identity \gamma_{1}=\max_{i}\alpha_{i} . When they do not, the additional correction term \sum_{ri, using a convention that X_{0} is the d\times d identity matrix, we have (cf. (3.10) and (3.11) in [ 7 ] ): \displaystyle C_{n}(i,j) \displaystyle= \displaystyle\sum_{t=i+1}^{j}B_{n}(i,t)C_{n-1}(t,j)+B_{n}(i,i)C_{n-1}(i,j) (15) \displaystyle= \displaystyle\sum_{t=i+1}^{j}B_{n}(i,t)C_{n-1}(t,j)+B_{n}(i,i)\sum_{t=i+1}^{k}B_{n-1}(i,t)C_{n-2}(t,j) \displaystyle\qquad\qquad+B_{n}(i,i)B_{n-1}(i,i)C_{n-2}(i,j)=\cdots \displaystyle= \displaystyle\sum_{r=0}^{n-1}B_{n}(i,i)\cdots B_{n-r+1}(i,i)\sum_{t=i+1}^{j}B_{n-r}(i,t)C_{n-1-r}(t,j). Fix some i^{*},j^{*}\in[m] such that i^{*}i^{*}. To finish the proof of the theorem, we will next use a backward induction to show that it is valid for (i,j)=(i^{*},j^{*}). By ( 5 ) and the induction hypothesis, for all \varepsilon>0 there exists a constant D_{\varepsilon} (which depends on {\mathcal{A}} ) such that for all n\in{\mathbb{N}}, \displaystyle\|B_{n}(i,j)\|_{1}\leq D_{\varepsilon}e^{n\varepsilon},\qquad i,j\in[m], and \displaystyle\|C_{n}(i,j^{*})\|_{1}\leq D_{\varepsilon}e^{n(\beta+\varepsilon)},\qquad i^{*}0 there exists a constant G_{\varepsilon} (which depends on {\mathcal{A}} ) such that for any i\in[m] and k,n\in{\mathbb{N}} with k0 is arbitrary. ∎ 3 Application to matrix perturbations We next apply the results of Section 2 to perturbations of linear systems. These perturbations represent an important class of matrix transformations with wide-ranging applications in science and engineering. Our first result concerns the product of random rank-one perturbations of a specific form. This proposition can also be viewed somewhat as a generalization of Theorem 5.1 in [ 4 ] , and contributes to the discussion around Remark 2.4 in the same paper. Proposition 3.1 . Let (u_{n},\eta_{n})_{n\in{\mathbb{N}}} be a random, stationary, and ergodic sequence, where u_{n}\in{\mathbb{R}}^{d} and \eta_{n}\in{\mathbb{R}} . Suppose v\in{\mathbb{R}}^{d} is a fixed vector such that \displaystyle{\mathbb{E}}\bigl(\log|\eta_{1}|\bigr)\leq{\mathbb{E}}\bigl(\log|\eta_{1}+v^{T}u_{1}|\bigr)<\infty. (17) (a) Let {\mathcal{A}}:=(A_{n})_{n\in{\mathbb{N}}} with A_{n}:=\eta_{n}I_{d}+u_{n}v^{T} satisfying ( 4 ). Then \displaystyle\gamma_{1}({\mathcal{A}})={\mathbb{E}}\bigl(\log|\eta_{1}+v^{T}u_{1}|\bigr)\quad\text{and}\quad\gamma_{r}({\mathcal{A}})={\mathbb{E}}\bigl(\log|\eta_{1}|\bigr),\quad r>1. (18) (b) Suppose A\in{\mathcal{M}}_{d} is a non-singular matrix. Let {\mathcal{A}}:=(A_{n})_{n\in{\mathbb{N}}} with A_{n}:=\eta_{n}A+u_{n}v^{T} satisfying condition ( 4 ), and \displaystyle P\bigl(Au_{1}v^{T}=u_{1}v^{T}A\bigr)=1. (19) Then, \displaystyle-\log\rho(A^{-1})\leq\gamma_{1}({\mathcal{A}})-{\mathbb{E}}\bigl(\log|\eta_{1}+v^{T}A^{-1}u_{1}|\bigr)\leq\log\rho(A), where \rho(A) denotes the spectral radius of the matrix A . We note that, under mild conditions on the sequence (\eta_{n},u_{n})_{n\in\mathbb{N}} , the inequality ( 17 ) can be relaxed, since the result may be applied directly to the inverse cocycle {\mathcal{A}}^{-1}:=(A_{n}^{-1})_{n\in{\mathbb{N}}} , with part (a) adjusted accordingly. Remark 3.2 (Varying right vector: two extendable regimes) . Consider A_{n}=\eta_{n}I+u_{n}v_{n}^{\top} . (i) If v_{n}=c_{n}v for a fixed v\neq 0 , then A_{n}=\eta_{n}I+\tilde{u}_{n}v^{\top} with \tilde{u}_{n}:=c_{n}u_{n} . Hence Proposition 3.1 applies verbatim (under the corresponding integrability for \tilde{u}_{n} ), yielding d-1 Lyapunov exponents equal to {\mathbb{E}}\log|\eta_{1}| and the remaining exponent {\mathbb{E}}\log|\eta_{1}+c_{1}v^{\top}u_{1}| . (ii) More generally, if v_{n}\in V a.s. for a fixed deterministic subspace V\subset{\mathbb{R}}^{d} of dimension r , then H:=V^{\perp} is a common invariant subspace and A_{n}|_{H}=\eta_{n}\,\mathrm{Id} . Consequently {\mathbb{E}}\log|\eta_{1}| is a Lyapunov exponent of multiplicity at least d-r . The remaining r exponents are those of the induced cocycle on the quotient {\mathbb{R}}^{d}/H ; in general they are not explicit if v_{n} rotates in V . Nevertheless, the determinant identity implies \sum_{i=1}^{d}\gamma_{i}=(d-1){\mathbb{E}}\log|\eta_{1}|+{\mathbb{E}}\log|\eta_{1}+v_{1}^{\top}u_{1}|. In order to prove Proposition 3.1 , we first present a preliminary result that explains how to extract the first few Lyapunov exponents of block upper triangular matrices by Lemma 2.3 . This extends Corollary 1 in [ 19 ] (cf. the paragraph following Proposition 1.1 in these notes). Proposition 3.3 . Fix d,m\in{\mathbb{N}} , and let {\mathcal{N}}:=(N_{n})_{n\in{\mathbb{N}}} be a random, stationary, and ergodic sequence of matrices \displaystyle N_{n}:=\begin{bmatrix}A_{n}&*\\ O&\eta_{n}I_{m}\end{bmatrix}, where \eta_{n}\in{\mathbb{R}} and A_{n}\in{\mathcal{M}}_{d} . Assume that {\mathcal{N}} satisfies ( 4 ) (i.e. {\mathbb{E}}(\log^{+}\|N_{1}\|)<\infty ), that A_{1} is almost surely invertible with {\mathbb{E}}(\log^{+}\|A_{1}^{-1}\|)<\infty , and that \eta_{1}\neq 0 almost surely with {\mathbb{E}}(\log^{+}|\eta_{1}|^{-1})<\infty . Set {\mathcal{A}}:=(A_{n})_{n\in{\mathbb{N}}} . Then \displaystyle\gamma_{1}({\mathcal{N}})=\max\bigl({\mathbb{E}}(\log|\eta_{1}|),\,\gamma_{1}({\mathcal{A}})\bigr), and for any 2\leq r\leq\min(m,d) , \displaystyle\gamma_{r}({\mathcal{N}})=\max_{0\leq\ell\leq r}\left(\sum_{s=1}^{\ell}\gamma_{s}({\mathcal{A}})+(r-\ell){\mathbb{E}}(\log|\eta_{1}|)\right) \displaystyle\qquad\qquad-\max_{0\leq\ell\leq r-1}\left(\sum_{s=1}^{\ell}\gamma_{s}({\mathcal{A}})+(r-\ell){\mathbb{E}}(\log|\eta_{1}|)\right). Proof. Recall that a minor of size r is associated to ordered sequences of indices J and L of length r , defined as the determinant of the submatrix formed by selecting the rows indexed by J and the columns indexed by L . We write [N]:=\{1,\dots,N\} and, for 0\leq r\leq N , we let [N]_{r}:=\{(i_{1},\dots,i_{r}):1\leq i_{1}<\cdots1, which is ( 18 ). Now we prove part (b). Define \tilde{\mathcal{A}}:=(\tilde{A}_{n})_{n\in{\mathbb{N}}} with \tilde{A}_{n}:=\eta_{n}I_{d}+A^{-1}u_{n}v^{T} . Note that A_{n}=A\tilde{A}_{n} . Repeatedly applying ( 19 ) gives \displaystyle X_{n}=A(\eta_{n}I_{d}+A^{-1}u_{n}v^{T})\cdots A(\eta_{1}I_{d}+A^{-1}u_{1}v^{T})=A^{n}Y_{n}, (21) where Y_{n}:=\prod_{i=1}^{n}\tilde{A}_{i} . Since the norm of a product is at most the product of norms, we get an upper bound: \displaystyle\gamma_{1}({\mathcal{A}}) \displaystyle\leq \displaystyle\lim\frac{1}{n}\log\|A^{n}\|+\gamma_{1}(\tilde{\mathcal{A}}) (22) \displaystyle= \displaystyle\log\rho(A)+{\mathbb{E}}\bigl(\log|\eta_{1}+v^{T}A^{-1}u_{1}|\bigr), where the last equality uses part (a) applied to \tilde{\mathcal{A}} and Gelfand’s formula for the spectral radius. Next, from ( 21 ), \displaystyle\|Y_{n}\|\leq\|X_{n}\|\,\|A^{-n}\|. Taking logarithms in the previous inequality, dividing by n , and letting n\to\infty (using part (a) for the cocycle (\tilde{A}_{n}) and Gelfand’s formula for \rho(A^{-1}) ) yields the lower bound: \displaystyle\gamma_{1}({\mathcal{A}})+\log\rho(A^{-1})\geq{\mathbb{E}}\bigl(\log|\eta_{1}+v^{T}A^{-1}u_{1}|\bigr). (23) Combining ( 23 ) and ( 22 ) concludes the proof of part (b). ∎ Proposition 3.1 illustrates a general mechanism: a low-rank perturbation often preserves a large invariant subspace, and the cocycle induced on the corresponding quotient captures the remaining Lyapunov exponent(s). In our setting the hyperplane H=\ker(v^{T}) is invariant and A_{n}|_{H}=\eta_{n}I , while the induced one-dimensional cocycle on {\mathbb{R}}^{d}/H is multiplication by \eta_{n}+v^{T}u_{n} (as witnessed by the identity v^{T}A_{n}=(\eta_{n}+v^{T}u_{n})v^{T} ). Equivalently, after a fixed change of basis that sends v^{T}x to the last coordinate, each A_{n} becomes block upper triangular with diagonal blocks \eta_{n}I_{d-1} and \eta_{n}+v^{T}u_{n} . This viewpoint is useful beyond rank one: when a cocycle preserves a filtration of subspaces, the Lyapunov spectrum is controlled by the induced cocycles on the successive quotients (cf. Lemma 2.3 and Proposition 3.3 ). Finally, we extend this result to the following simple lemma by suitably adapting a standard 2\times 2 technique to our context (cf. for instance, [ 27 , 29 ] ). Lemma 3.4 . For a given m\in{\mathbb{N}} and V\in{\mathcal{M}}_{d\times m} , let (U_{n},\eta_{n})_{n\in{\mathbb{N}}} be a random, stationary, and ergodic sequence, where U_{n}\in{\mathcal{M}}_{d\times m} and \eta_{n}\in{\mathbb{R}} . Define {\mathcal{A}}:=(A_{n})_{n\in{\mathbb{N}}} and \tilde{\mathcal{A}}:=(\tilde{A}_{n})_{n\in{\mathbb{N}}} , with A_{n}:=\eta_{n}I_{d}+U_{n}V^{T}\quad\text{and}\quad\tilde{A}_{n}:=\eta_{n}I_{m}+V^{T}U_{n}. Then \displaystyle\sum_{i=1}^{d}\gamma_{i}({\mathcal{A}})-\sum_{i=1}^{m}\gamma_{i}(\tilde{\mathcal{A}})=(d-m){\mathbb{E}}(\log|\eta_{1}|). (24) Moreover, if \gamma_{1}({\mathcal{A}})\geq{\mathbb{E}}(\log|\eta_{1}|) , then \gamma_{1}({\mathcal{A}})=\gamma_{1}(\tilde{\mathcal{A}}) . Similarly, if for some 2\leq r\leq\min(m,d) we have \gamma_{r}({\mathcal{A}})\geq{\mathbb{E}}(\log|\eta_{1}|) , then \gamma_{r}({\mathcal{A}})=\gamma_{r}(\tilde{\mathcal{A}}) . Proof. Consider the following square block matrices: R:=\begin{bmatrix}I_{d}&O\\ V^{T}&I_{m}\end{bmatrix},\quad R^{-1}=\begin{bmatrix}I_{d}&O\\ -V^{T}&I_{m}\end{bmatrix},\qquad\text{and}\qquad N_{n}=\begin{bmatrix}A_{n}&U_{n}\\ O&\eta_{n}I_{m}\end{bmatrix}. The proof of the lemma relies on the following identity: \displaystyle\tilde{N}_{n}:=RN_{n}R^{-1}=\begin{bmatrix}\eta_{n}I_{d}&V\\ O&\tilde{A}_{n}\end{bmatrix}. (25) Recalling ( 1 ) and using ( 25 ), we may write \prod_{i=1}^{n}N_{i}=\begin{bmatrix}X_{n}&*\\ O&\prod_{i=1}^{n}\eta_{i}I_{m}\end{bmatrix}=R^{-1}\begin{bmatrix}\prod_{i=1}^{n}\eta_{i}I_{d}&*\\ 0&\tilde{X}_{n}\end{bmatrix}R=R^{-1}\bigl(\prod_{i=1}^{n}\tilde{N}_{i}\bigr)R, where * denotes unspecified blocks. Let {\mathcal{N}}:=(N_{n})_{n\in{\mathbb{N}}} and \tilde{\mathcal{N}}:=(\tilde{N}_{n})_{n\in{\mathbb{N}}} . Observe that by the Oseledets theorem, \gamma_{i}({\mathcal{N}}) and \gamma_{i}(\tilde{\mathcal{N}}) s exist and \displaystyle\sum_{i=1}^{d}\gamma_{i}({\mathcal{A}})+m{\mathbb{E}}(\log|\eta_{1}|) \displaystyle={\mathbb{E}}\bigl(\log|\det(A_{1})|\bigr)+m{\mathbb{E}}(\log|\eta_{1}|) \displaystyle={\mathbb{E}}\bigl(\log|\det(N_{1})|\bigr)=\sum_{i=1}^{d+m}\gamma_{i}({\mathcal{N}})=\sum_{i=1}^{d+m}\gamma_{i}(\tilde{\mathcal{N}}) \displaystyle={\mathbb{E}}\bigl(\log|\det(\tilde{N}_{1})|\bigr)={\mathbb{E}}\bigl(\log|\det(\tilde{A}_{1})|\bigr)+d{\mathbb{E}}(\log|\eta_{1}|) \displaystyle=\sum_{i=1}^{m}\gamma_{i}(\tilde{\mathcal{A}})+d{\mathbb{E}}(\log|\eta_{1}|). Rearranging yields ( 24 ). Next, \gamma_{1}({\mathcal{N}}) and \gamma_{1}(\tilde{\mathcal{N}}) both exist and are equal. Hence, by Lemma 2.3 , \displaystyle\max\bigl(\gamma_{1}({\mathcal{A}}),{\mathbb{E}}(\log|\eta_{1}|)\bigr)=\max\bigl(\gamma_{1}(\tilde{\mathcal{A}}),{\mathbb{E}}(\log|\eta_{1}|)\bigr). (26) If \gamma_{1}({\mathcal{A}})\geq{\mathbb{E}}(\log|\eta_{1}|) , then ( 26 ) implies \gamma_{1}({\mathcal{A}})=\gamma_{1}(\tilde{\mathcal{A}}) . Similarly, by Proposition 3.3 , for any 2\leq r\leq\min(m,d) , one can show inductively that \max_{0\leq\ell\leq r}\Bigl(\sum_{s=1}^{\ell}\gamma_{s}({\mathcal{A}})+(r-\ell){\mathbb{E}}(\log|\eta_{1}|)\Bigr)=\max_{0\leq\ell\leq r}\Bigl(\sum_{s=1}^{\ell}\gamma_{s}(\tilde{\mathcal{A}})+(r-\ell){\mathbb{E}}(\log|\eta_{1}|)\Bigr). This yields the result under the assumption \gamma_{1}({\mathcal{A}})\geq\cdots\geq\gamma_{r}({\mathcal{A}})\geq{\mathbb{E}}(\log|\eta_{1}|) . ∎ The counterpart of part (b) of Proposition 3.1 of this result is stated below. Proposition 3.5 . Fix m,d\in\mathbb{N} , a matrix V\in\mathcal{M}_{d\times m}(\mathbb{R}) of rank m , and an invertible matrix A\in\mathcal{M}_{d\times d}(\mathbb{R}) . Let (U_{n},\eta_{n})_{n\geq 1} be a random stationary ergodic sequence with U_{n}\in\mathcal{M}_{d\times m}(\mathbb{R}) and \eta_{n}\in\mathbb{R} , and define A_{n}:=\eta_{n}A+U_{n}V^{T},\qquad\widetilde{A}_{n}:=\eta_{n}I_{m}+V^{T}A^{-1}U_{n}. Assume \mathbb{P}(AU_{1}V^{T}=U_{1}V^{T}A)=1. Then, writing {\mathcal{A}}=(A_{n}) and \widetilde{\mathcal{A}}=(\widetilde{A}_{n}) , -\log\rho(A^{-1})+\max\!\Big(\mathbb{E}\log|\eta_{1}|,\,\gamma_{1}(\widetilde{\mathcal{A}})\Big)\;\leq\;\gamma_{1}({\mathcal{A}})\;\leq\;\log\rho(A)+\max\!\Big(\mathbb{E}\log|\eta_{1}|,\,\gamma_{1}(\widetilde{\mathcal{A}})\Big). Proof. Define \widehat{A}_{n}:=\eta_{n}I_{d}+A^{-1}U_{n}V^{T}. By the commutation assumption, A commutes with \widehat{A}_{n} for every n , and hence X_{n}:=A_{n}\cdots A_{1}=A^{n}\widehat{X}_{n},\qquad\text{where }\widehat{X}_{n}:=\widehat{A}_{n}\cdots\widehat{A}_{1}. Therefore, by submultiplicativity, \|X_{n}\|\leq\|A^{n}\|\,\|\widehat{X}_{n}\|\quad\text{and}\quad\|\widehat{X}_{n}\|=\|A^{-n}X_{n}\|\leq\|A^{-n}\|\,\|X_{n}\|. Taking \frac{1}{n}\log and letting n\to\infty , and using Gelfand’s formula \lim_{n\to\infty}\frac{1}{n}\log\|A^{\pm n}\|=\log\rho(A^{\pm 1}) , gives -\log\rho(A^{-1})+\gamma_{1}(\widehat{\mathcal{A}})\leq\gamma_{1}({\mathcal{A}})\leq\log\rho(A)+\gamma_{1}(\widehat{\mathcal{A}}). It remains to identify \gamma_{1}(\widehat{\mathcal{A}}) . Let K:=\ker(V^{T}) , which has dimension d-m (since \mathrm{rank}(V)=m ). For x\in K , V^{T}x=0 and hence \widehat{A}_{n}x=\eta_{n}x , so vectors in K grow at rate \mathbb{E}\log|\eta_{1}| . On the quotient space \mathbb{R}^{d}/K , the induced action is computed via the surjective map q(x)=V^{T}x : q(\widehat{A}_{n}x)=V^{T}(\eta_{n}x+A^{-1}U_{n}V^{T}x)=\bigl(\eta_{n}I_{m}+V^{T}A^{-1}U_{n}\bigr)\,q(x)=\widetilde{A}_{n}\,q(x). Thus the cocycle induced on the quotient is precisely \widetilde{\mathcal{A}} . By the block/extension Furstenberg–Kifer lemma (Lemma 2.3 ), \gamma_{1}(\widehat{\mathcal{A}})=\max\big(\mathbb{E}\log|\eta_{1}|,\gamma_{1}(\widetilde{\mathcal{A}})\big). Substituting into the earlier inequality yields the claimed bounds. ∎ 4 Shape graphs We conclude these notes by presenting a generalization of Lemma 2.3 , partially inspired by the proof of Theorem A in [ 34 ] . As a prelude to this discussion, we first provide an alternative proof of the upper bound in Lemma 2.3 , based on the observation that zeros in specific entries of A_{n} allow the computation of the Lyapunov exponents in terms of those associated with matrices of simpler structure. We note that the proof previously given for the theorem offers more precise insight into the growth behavior of the blocks and, in particular, can be adapted to establish Proposition 2.1 . For the purpose of this section, let \mathcal{A}:=(A_{n})_{n\in\mathbb{N}} be a random, stationary, and ergodic sequence of matrices as in the statement of Lemma 2.3 , and write each matrix A_{n} as A_{n}:=A_{n,1}+A_{n,2}, where A_{n,1} denotes the block diagonal part and A_{n,2} the remaining strictly upper triangular component of A_{n} . Norm convention. Throughout Section 4 we take \|\cdot\| to be the operator norm induced by the vector \ell^{1} -norm (maximum absolute column sum); we write \|\cdot\|_{1} when clarity is helpful. By equivalence of norms on the finite-dimensional space \mathcal{M}_{d} , this choice does not change the Lyapunov exponents and ( 4 ) holds for \|\cdot\| if and only if it holds for \|\cdot\|_{1} . Then X_{n}=A_{n,1}\cdots A_{1,1}+\sum_{j=1}^{n}\sum_{1\leq i_{1}<\cdotsd vanish, and therefore X_{n}=A_{n,1}\cdots A_{1,1}+\sum_{j=1}^{d}\sum_{1\leq i_{1}<\cdots0 . We will use the following standard Borel–Cantelli estimate (applied to Y_{n}=\log^{+}\|A_{n,2}\|_{1} ). Lemma 4.1 . Let (Y_{n})_{n\geq 1} be a stationary sequence of nonnegative random variables with {\mathbb{E}}(Y_{1})<\infty . Then for every \varepsilon>0 , \sum_{n\geq 1}{\mathbb{P}}(Y_{n}>\varepsilon n)<\infty,\qquad\text{and hence}\qquad{\mathbb{P}}(Y_{n}>\varepsilon n\ \text{\rm i.o.})=0. Proof. By stationarity, {\mathbb{P}}(Y_{n}>\varepsilon n)={\mathbb{P}}(Y_{1}>\varepsilon n) . Using the tail-integral identity {\mathbb{E}}(Y_{1})=\int_{0}^{\infty}{\mathbb{P}}(Y_{1}>t)\,dt and partitioning the integral into intervals of length \varepsilon gives \sum_{n\geq 1}{\mathbb{P}}(Y_{1}>\varepsilon n)\leq\frac{1}{\varepsilon}\int_{0}^{\infty}{\mathbb{P}}(Y_{1}>t)\,dt=\frac{1}{\varepsilon}{\mathbb{E}}(Y_{1})<\infty. The Borel–Cantelli lemma yields the claim. ∎ Apply Lemma 4.1 with Y_{n}:=\log^{+}\|A_{n,2}\|_{1} . Since A_{1,2} is obtained from A_{1} by zeroing some entries, the induced \ell^{1} operator norm is monotone, so \|A_{1,2}\|_{1}\leq\|A_{1}\|_{1} and hence {\mathbb{E}}\log^{+}\|A_{1,2}\|_{1}<\infty by ( 4 ) (equivalently for \|\cdot\|_{1} ). Therefore, {\mathbb{P}}\!\left(\log^{+}\|A_{n,2}\|_{1}>\varepsilon n\ \text{\rm i.o.}\right)=0. In particular, almost surely there exists a (random) N_{\varepsilon}<\infty such that \|A_{n,2}\|_{1}\leq e^{\varepsilon n} for all n\geq N_{\varepsilon} . Setting C_{\varepsilon}:=\max\Bigl\{1,\ \max_{1\leq n\leq N_{\varepsilon}}\|A_{n,2}\|_{1}e^{-\varepsilon n}\Bigr\}, we obtain the uniform bound \|A_{n,2}\|_{1}\leq C_{\varepsilon}e^{\varepsilon n}\qquad\text{for all }n\geq 1. Consequently, using the expansion of X_{n} above and the fact that any nonzero monomial contains at most d-1 factors from the strictly upper-triangular part (A_{k,2}) , we obtain that for all sufficiently large n , almost surely, \|X_{n}\|_{1}\leq C_{\varepsilon}^{\,d-1}\,n^{d}\,e^{(d-1)\varepsilon n}\,\max_{1\leq j0 . Since \frac{1}{n}\sum_{t=1}^{n}\log|(A_{t,1})_{pp}|\to\beta_{p} almost surely, the random variables G_{\varepsilon,p}^{+}:=\sup_{n\geq 1}\exp\!\Big(\sum_{t=1}^{n}\log|(A_{t,1})_{pp}|-(\beta_{p}+\varepsilon)n\Big),\qquad G_{\varepsilon,p}^{-}:=\sup_{n\geq 1}\exp\!\Big(-\sum_{t=1}^{n}\log|(A_{t,1})_{pp}|-(-\beta_{p}+\varepsilon)n\Big) are almost surely finite, and therefore with G_{\varepsilon,p}:=\max(G_{\varepsilon,p}^{+},G_{\varepsilon,p}^{-}) we have for all n\geq 1 , \prod_{t=1}^{n}\big|(A_{t,1})_{pp}\big|\leq G_{\varepsilon,p}\,e^{(\beta_{p}+\varepsilon)n},\qquad\prod_{t=1}^{n}\big|(A_{t,1})_{pp}\big|^{-1}\leq G_{\varepsilon,p}\,e^{(-\beta_{p}+\varepsilon)n}. Consequently, for all 1\leq i\leq j , \displaystyle\prod_{t=i}^{j}\big|(A_{t,1})_{pp}\big|=\Big(\prod_{t=1}^{j}\big|(A_{t,1})_{pp}\big|\Big)\Big(\prod_{t=1}^{i-1}\big|(A_{t,1})_{pp}\big|\Big)^{-1} \displaystyle\qquad\leq G_{\varepsilon,p}^{2}\,e^{\beta_{p}(j-i+1)}\,e^{\varepsilon(j+i-1)}\leq G_{\varepsilon,p}^{2}\,e^{\beta_{p}(j-i+1)}\,e^{2\varepsilon j}. Taking the maximum over p\in[d] and setting G_{\varepsilon}:=\max_{p\in[d]}G_{\varepsilon,p} yields the uniform estimate \|A_{j,1}\cdots A_{i,1}\|_{1}\leq G_{\varepsilon}^{2}\,e^{\gamma_{1}(\mathcal{A}_{1})(j-i+1)}\,e^{2\varepsilon j}\qquad\text{for all }1\leq i\leq j. (28) Applying ( 28 ) to each factor in ( 27 ) and using that each endpoint is at most n and that j\leq d-1 gives \|X_{n}\|_{1}\leq\widetilde{C}_{\varepsilon}\,n^{d}\,\exp\!\big((\gamma_{1}(\mathcal{A}_{1})+C\,\varepsilon)n\big), for some deterministic constant C=C(d) and an almost surely finite (random) constant \widetilde{C}_{\varepsilon} . Since \varepsilon>0 is arbitrary, we conclude \gamma_{1}(\mathcal{A})\leq\gamma_{1}(\mathcal{A}_{1}) . Finally, for a diagonal (more generally, block-diagonal) cocycle, the top Lyapunov exponent is the maximum of the top Lyapunov exponents of its diagonal blocks, completing the proof. We now introduce several definitions to abstract and extend the preceding argument to a broader class of matrices beyond the block triangular case. Let \wedge denote the entrywise “AND” operation. Fix d,k\in\mathbb{N} with k\leq d^{2} . A shape set of order d , denoted \mathcal{L} , is a collection of nonzero, zero–one matrices of size d\times d , \mathcal{L}:=\{L_{j}\mid j\in[k]\}, such that L_{i}\wedge L_{j}=O_{d} for all distinct i,j\in[k] . For any matrix A\in{\mathcal{M}}_{d} , we define its shape , denoted \mbox{\it Shape}{\left(A\right)} , as the d\times d zero–one matrix whose (i,j) -th entry is one if A(i,j)\neq 0 , and zero otherwise. We next introduce the notion of an \mathcal{L} -shape graph (\mathcal{V},\mathcal{T})_{\mathcal{L}} , defined by its set of vertices \mathcal{V} and transition map \mathcal{T}:\mathcal{V}\times\mathcal{L}\to\mathcal{V} . Given the shape set \mathcal{L} , define the set of vertices as \mathcal{V}:=\Bigl\{\mbox{\it Shape}{\left(L_{n}\cdots L_{1}\right)}\,\big|\,n\in\mathbb{N},\ (L_{1},\ldots,L_{n})\in\mathcal{L}^{n}\Bigr\}. (29) Each vertex can be regarded as a zero–one matrix when necessary. Two vertices v_{1},v_{2}\in\mathcal{V} are connected, written v_{1}\to v_{2} , if and only if there exists some L\in\mathcal{L} such that v_{2}=\mathcal{T}(v_{1},L):=\mbox{\it Shape}{\left(Lv_{1}\right)}. Finally, given any sequence of matrices \mathcal{A}:=(A_{n})_{n\geq 0} , we use the shape set \mathcal{L} to decompose each A_{n} into a sum of k “non-overlapping” matrices \{A_{n,1},\ldots,A_{n,k}\} such that A_{n}=\sum_{j=1}^{k}A_{n,j},\quad\text{where}\quad\mbox{\it Shape}{\left(A_{n,j}\right)}\vee L_{j}=L_{j}. (30) To clarify these definitions, we conclude this section with several examples, including one illustrating a shape graph appropriate for triangular matrices. v_{1} v_{2} v_{3} v_{*} L_{2} L_{1} L_{2} L_{1} L_{2} L_{1} L_{1},L_{2} Figure 1 : The shape graph for ( 31 ) and ( 32 ). v_{1} v_{3} v_{2} v_{4} v_{*} L_{2} L_{1} L_{1} L_{3} L_{1} L_{1} L_{1},L_{2},L_{3} L_{3} L_{2},L_{3} L_{2} L_{2},L_{3} (a) See eq. ( 34 ) and ( 35 ) v_{1} v_{2} v_{3} v_{*} L_{2} L_{1} L_{2} L_{1} L_{2} L_{1} L_{1},L_{2} (b) See eq.( 36 ) and ( 37 ) Figure 2 : Two different graphs for the matrices described by ( 33 ) Example 4.2 . Let {\mathcal{A}} be a sequence of 3\times 3 upper-triangular matrices. Write each A_{i} as the sum of its diagonal part and its strictly upper triangular part. Then, an appropriate shape set is \displaystyle{\mathcal{L}}:=\left\{L_{1}:=I_{3},\ L_{2}:=\begin{bmatrix}0&1&1\\ 0&0&1\\ 0&0&0\end{bmatrix}\right\}. (31) By ( 29 ), the set of vertices of the {\mathcal{L}} -shape graph is then \displaystyle{\mathcal{V}}:=\left\{v_{1}:=I_{3},\ v_{2}:=\begin{bmatrix}0&1&1\\ 0&0&1\\ 0&0&0\end{bmatrix},\ v_{3}:=\begin{bmatrix}0&0&1\\ 0&0&0\\ 0&0&0\end{bmatrix},\ v_{*}:=O_{3}\right\}. (32) The corresponding shape graph is shown in Figure 1 . Our next example concerns the case where the matrices involved are not both upper triangular. Example 4.3 . Let {\mathcal{A}} be a sequence of matrices sampled from the set \displaystyle\left\{\begin{bmatrix}2&0&0&0\\ 0&1&-1&-1\\ 0&0&-1&0\\ 0&0&0&-2\end{bmatrix},\ \begin{bmatrix}1&0&0&0\\ 0&2&0&0\\ 0&0&3&0\\ 5&0&0&4\end{bmatrix}\right\}. (33) In this case, an appropriate choice for the shape set {\mathcal{L}} is \displaystyle{\mathcal{L}}=\left\{L_{1}:=I_{4},\ L_{2}:=\begin{bmatrix}0&0&0&0\\ 0&0&0&0\\ 0&0&0&0\\ 1&0&0&0\end{bmatrix},\ L_{3}:=\begin{bmatrix}0&0&0&0\\ 0&0&1&1\\ 0&0&0&0\\ 0&0&0&0\end{bmatrix}\right\}. (34) It is straightforward to verify that with this choice of {\mathcal{L}} , the set of vertices is \displaystyle{\mathcal{V}}:=\left\{v_{1}:=L_{1},\ v_{2}:=L_{2},\ v_{3}:=L_{3},\ v_{4}:=\begin{bmatrix}0&0&0&0\\ 1&0&0&0\\ 0&0&0&0\\ 0&0&0&0\end{bmatrix},\ v_{*}:=O_{4}\right\}. (35) The corresponding shape graph is depicted in part (a) of Fig. 2 . We note that the shape set {\mathcal{L}} is not unique, and therefore the resulting graph is also not unique. For instance, another possible choice for {\mathcal{L}} in this example is \displaystyle{\mathcal{L}}=\left\{L_{1}:=I_{4},\ L_{2}:=\begin{bmatrix}0&0&0&0\\ 0&0&1&1\\ 0&0&0&0\\ 1&0&0&0\end{bmatrix}\right\}. (36) In this case, the set of vertices becomes \displaystyle{\mathcal{V}}:=\left\{v_{1}:=L_{1},\ v_{2}:=L_{2},\ v_{3}:=\begin{bmatrix}0&0&0&0\\ 1&0&0&0\\ 0&0&0&0\\ 0&0&0&0\end{bmatrix},\ v_{*}:=O_{4}\right\}. (37) The corresponding shape graph is shown in part (b) of Fig. 2 . With the notion of the shape graph established, our strategy is to exploit its structural properties to analyze products of matrices in {\mathcal{A}} , thereby obtaining meaningful bounds on the Lyapunov exponents of {\mathcal{A}} . The main result of this section is the following theorem. Theorem 4.4 . Let {\mathcal{L}} be a shape set of order d with k elements, and let ({\mathcal{V}},{\mathcal{T}})_{{\mathcal{L}}} denote its corresponding shape graph. Assume that the shape graph contains only loops of length one (self-loops), and that each nonzero vertex has at most one self-loop. Let {\mathcal{A}}=(A_{n})_{n\in{\mathbb{N}}} be a random, stationary, and ergodic sequence of d\times d matrices, each admitting a decomposition as in ( 30 ) with respect to the shape set {\mathcal{L}} . Assume further that: (i) For every 1\leq s\leq k , {\mathbb{E}}\big(\log^{+}\|A_{1,s}\|\big)<\infty. (ii) Let {\mathcal{H}}\subset{\mathcal{V}}\setminus\{O_{d}\} be the set of vertices with a self-loop, and let {\mathcal{L}}_{{\mathcal{H}}} be the subset of labels corresponding to their self-loops. For every s\in{\mathcal{L}}_{\mathcal{H}} , the matrix A_{1,s} is almost surely invertible, and {\mathbb{E}}\big(\log^{+}\|A_{1,s}^{-1}\|\big)<\infty. Define \beta_{s}:=\lim_{n\to\infty}\frac{1}{n}\log\left\|A_{n,s}A_{n-1,s}\cdots A_{1,s}\right\|,\quad\text{a.s.}, and set \beta:=\max_{s\in{\mathcal{L}}_{\mathcal{H}}}\beta_{s}. Then: (a) The top Lyapunov exponent satisfies \gamma_{1}({\mathcal{A}})\leq\beta+\log k. Moreover, if O_{d}\in{\mathcal{V}} , define k_{*}:=\max_{v\in{\mathcal{V}}\setminus\{O_{d}\}}\#\bigl\{\,s\in[k]:{\mathcal{T}}(v,L_{s})\neq O_{d}\,\bigr\}, so that k_{*}\leq k and k_{*} is the maximal number of labels that keep a nonzero vertex from transitioning to O_{d} in one step. Then \gamma_{1}({\mathcal{A}})\leq\beta+\log k_{*}. (In particular, if every nonzero vertex has at least one outgoing label that transitions to O_{d} , then k_{*}\leq k-1 .) (b) Let {\mathcal{W}}\subset{\mathcal{H}}\setminus\{O_{d}\} be the set of self-loop vertices w such that every directed path in the shape graph that ends at w avoids loop vertices other than w (equivalently, it does not pass through any vertex in {\mathcal{H}}\setminus\{w\} ). Assume moreover that for each w\in{\mathcal{W}} , if s denotes the label of its self-loop, then there exists r=r(w)\geq 1 such that \mbox{\it Shape}{\left(L_{s}^{n}\right)}=w for all n\geq r . If, for every w\in{\mathcal{W}} and every v\in{\mathcal{V}}\setminus\{w\} , we have v\wedge w=O_{d}, and assume in addition that all matrices A_{n,s} are entrywise nonnegative almost surely (so that monomials with the same shape do not cancel entrywise). Then \max_{s\in{\mathcal{L}}_{\mathcal{W}}}\beta_{s}\leq\gamma_{1}({\mathcal{A}}), where {\mathcal{L}}_{\mathcal{W}} denotes the set of labels corresponding to the self-loops of vertices in {\mathcal{W}} . 4.1 Theorem 4.4 in practice Theorem 4.4 is intended as a “plug-in” estimate for cocycles whose random matrices admit a sparse decomposition with non-overlapping supports . In many situations, the verification reduces to a finite, combinatorial check on the associated shape graph. We record a short checklist. 1. Choose a shape set. Pick a shape set {\mathcal{L}}=\{L_{1},\ldots,L_{k}\} (disjoint supports: L_{i}\wedge L_{j}=O_{d} for i\neq j , where O_{d} is the d\times d zero matrix) that matches the sparsity types present in A_{n} . 2. Build the shape graph. Compute (or reason about) the vertex set {\mathcal{V}} in ( 29 ) and the transition map {\mathcal{T}}(v,L)=\mbox{\it Shape}{\left(vL\right)} . In practice, {\mathcal{V}} is generated by iterating the transitions starting from the labels. 3. Check the acyclicity condition. Verify that the directed graph contains no directed cycles other than self-loops, and that each nonzero vertex has at most one self-loop label. (In many common constructions, L_{1}=I_{d} is the unique self-loop label.) 4. Identify the loop labels and compute \beta . Let {\mathcal{H}} be the loop vertices and {\mathcal{L}}_{{\mathcal{H}}} their self-loop labels. Then \beta=\max_{s\in{\mathcal{L}}_{{\mathcal{H}}}}\beta_{s} , where \beta_{s} is the top Lyapunov exponent of the subcocycle (A_{n,s})_{n\geq 1} . 5. Apply the bound. Theorem 4.4 (a) gives \gamma_{1}({\mathcal{A}})\leq\beta+\log k , and if O_{d}\in{\mathcal{V}} the sharper \gamma_{1}({\mathcal{A}})\leq\beta+\log k_{*} . We now give two worked illustrations, the first using the non-triangular example introduced above, and the second describing a general “DAG-supported” family where the \log k term has a transparent combinatorial meaning. Example 4.5 (A worked bound for the non-triangular example ( 33 )) . Assume that (A_{n})_{n\geq 1} is i.i.d. and takes the first matrix in ( 33 ) with probability p\in(0,1) and the second with probability 1-p . Use the shape set {\mathcal{L}}=\{L_{1},L_{2},L_{3}\} from ( 34 ), so that k=3 , and note from Fig. 2 (a) that O_{4}\in{\mathcal{V}} and the shape graph has no directed cycles other than self-loops. The only self-loop label is L_{1}=I_{4} , hence {\mathcal{L}}_{{\mathcal{H}}}=\{1\} and \beta=\beta_{1} . Writing D_{n}:=A_{n,1} for the diagonal component in the decomposition ( 30 ), we have that D_{n} is diagonal with entries distributed as (D_{n}(1,1),D_{n}(2,2),D_{n}(3,3),D_{n}(4,4))=\begin{cases}(2,1,-1,-2),&\text{with prob. }p,\\ (1,2,3,4),&\text{with prob. }1-p.\end{cases} For diagonal cocycles, \beta_{1} is explicit: \beta_{1}=\max_{1\leq i\leq 4}\ {\mathbb{E}}\big(\log|D_{1}(i,i)|\big)=\max\Big\{p\log 2,\ (1-p)\log 2,\ (1-p)\log 3,\ p\log 2+(1-p)\log 4\Big\}. Therefore Theorem 4.4 (a) yields the concrete estimate \gamma_{1}({\mathcal{A}})\leq\beta_{1}+\log k_{*}=\beta_{1}+\log 2\qquad(\text{here }k_{*}=2). This bound is nontrivial in regimes where the diagonal growth \beta_{1} is modest while the off-diagonal entries induce large transient amplification; the shape-graph estimate isolates the genuine exponential growth (captured by \beta_{1} ) from the purely combinatorial proliferation of monomials (captured by \log 2 ). Example 4.6 (DAG-supported sparsity patterns) . One convenient way to view this family is as a random transfer-matrix (or random kinetic-network) model on a directed acyclic network. Let x_{n}\in\mathbb{R}^{d} be a vector of nonnegative “masses” (or partial partition functions) and evolve it by x_{n}=A_{n}x_{n-1},\qquad n\geq 1. Then \gamma_{1}({\mathcal{A}}) is the almost-sure exponential growth rate of \|x_{n}\| and may be interpreted as a quenched free-energy density . A concrete parameterization is to take (for an “inverse temperature” \theta>0 ) D_{n}=Diag\left(e^{-\theta E_{n,1}},\ldots,e^{-\theta E_{n,d}}\right),\qquad B_{n,e}=e^{-\theta U_{n,e}}\,E_{ij}\ \ \text{for }e=(i,j)\in E(G), where (E_{n,i}) and (U_{n,e}) are stationary ergodic energy/edge-weight fields. In this case the diagonal subcocycle is explicit and \beta_{1}=\max_{1\leq i\leq d}\ {\mathbb{E}}\big(\log D_{1}(i,i)\big)=-\theta\min_{1\leq i\leq d}\ {\mathbb{E}}(E_{1,i}), so Theorem 4.4 (a) bounds the quenched free energy by a simple “energy–entropy” upper bound (energy from \beta_{1} , entropy from the \log|E(G)| term). To make this interpretation more concrete, note that the expansion of X_{n}=A_{n}\cdots A_{1} into monomials naturally enumerates time-ordered paths in the state space [d] . Indeed, if we work in a basis where all entries are nonnegative (or simply take absolute values entrywise), then for each coordinate j one can view (X_{n}\mbox{\bf 1})_{j} as a sum over sequences i_{0}\to i_{1}\to\cdots\to i_{n}=j where each step either stays put (a diagonal choice from D_{t} ) or follows an allowed directed edge of G (a choice from some B_{t,e} ). The weight of a path is a product of the corresponding random factors along the path, so the total mass is a partition-function-like sum of random path weights. The top Lyapunov exponent \gamma_{1}({\mathcal{A}}) is then the quenched exponential growth rate of this partition function. Theorem 4.4 (a) can be read as follows: in an acyclic environment, the long-run exponential growth is controlled by the “best” loop (the diagonal cocycle, contributing \beta_{1} ), while the off-diagonal moves contribute only through the number of admissible local choices. The crude entropy term \log|E(G)| comes from bounding the number of admissible label sequences by |E(G)|^{n} ; in many applications this can be sharpened by replacing |E(G)| with a smaller quantity such as the maximal out-degree or the spectral radius of an associated transition matrix. Fix d\geq 2 and let G be a directed acyclic graph (DAG) on vertex set [d] . For each directed edge e=(i,j)\in E(G) , let L_{e}:=E_{ij} be the d\times d matrix with a single 1 in entry (i,j) and zeros elsewhere, and let L_{1}:=I_{d} . Then {\mathcal{L}}:=\{L_{1}\}\cup\{L_{e}:e\in E(G)\} is a shape set (supports are disjoint), with k=1+|E(G)| . Consider any stationary ergodic cocycle (A_{n})_{n\geq 1} of the form A_{n}=D_{n}+\sum_{e\in E(G)}B_{n,e},\qquad\mbox{\it Shape}{\left(D_{n}\right)}\vee L_{1}=L_{1},\ \ \mbox{\it Shape}{\left(B_{n,e}\right)}\vee L_{e}=L_{e}, where D_{n} is diagonal and each B_{n,e} is supported on the single entry prescribed by e . If D_{n} is a.s. invertible and {\mathbb{E}}\log^{+}\|D_{1}^{\pm 1}\|<\infty , and if {\mathbb{E}}\log^{+}\|B_{1,e}\|<\infty for all e , then Theorem 4.4 applies. The DAG assumption implies that the {\mathcal{L}} -shape graph has no directed cycles other than the self-loops induced by L_{1} (products of edge labels correspond to directed paths, which cannot return in a DAG). Hence {\mathcal{L}}_{{\mathcal{H}}}=\{1\} and \beta=\beta_{1} , where \beta_{1}=\lim_{n\to\infty}\frac{1}{n}\log\|D_{n}D_{n-1}\cdots D_{1}\|=\max_{1\leq i\leq d}\ \lim_{n\to\infty}\frac{1}{n}\sum_{t=1}^{n}\log|D_{t}(i,i)|\qquad\text{a.s.} If moreover O_{d}\in{\mathcal{V}} (this holds, for instance, whenever G has no directed path of length d ), then Theorem 4.4 (a) gives \gamma_{1}({\mathcal{A}})\leq\beta_{1}+\log k_{*}=\beta_{1}+\log|E(G)|\qquad(\text{here }k_{*}=|E(G)|). In this family the additive term \log|E(G)| may be interpreted as a coarse “branching entropy” that accounts for the number of allowed sparsity types at each multiplication step, while \beta_{1} captures the genuine exponential growth coming from the diagonal subcocycle. Remark 4.7 . The proof of Theorem 4.4 (a) expands X_{n} into monomials indexed by label sequences in \{1,\ldots,k\}^{n} and then applies a union bound over the k^{n} terms. This is where the additive \log k (or \log k_{*} ) originates. In applications one can often sharpen this step: • If only a subset of labels are ever reachable after a few steps (equivalently, the shape graph quickly collapses), one can replace k by the effective number of labels that actually contribute. • In “graph-like” constructions, one can bound the number of admissible label sequences in the expansion underlying part (a) by the number of directed walks in an auxiliary transition graph (equivalently, by the number of directed paths in the shape graph). If M is the adjacency matrix of that transition graph, then the number of length- n walks is at most \mathbf{1}^{\top}M^{n-1}\mathbf{1}\leq C\,\rho(M)^{\,n} , where \rho(M) is the spectral radius. Thus the additive entropy term can often be improved from \log k to \log\rho(M) (or more crudely to \log\Delta^{+} , where \Delta^{+} is the maximal out-degree). In particular, if the transition graph is acyclic, this count is subexponential and the limiting “entropy” contribution vanishes. We do not pursue these refinements here, but the shape-graph viewpoint makes them natural. 4.2 Proof of Theorem 4.4 The acyclicity assumption implies that every time-ordered monomial either (i) stays within a self-loop vertex for long stretches (hence inherits the exponential rate \beta from the corresponding loop cocycle) or (ii) eventually dies by hitting O_{d} . Since non-loop transitions cannot repeat indefinitely, their contribution is at most subexponential (controlled using the {\mathbb{E}}\log^{+}\|A_{1,s}\| hypotheses). The only remaining exponential cost is the number of distinct nonzero monomials, which is bounded by k_{\rm eff}^{n} ; when O_{d} is reachable one can take k_{\rm eff}=k_{*} as in Theorem 4.4 , yielding the corresponding additive \log k_{\rm eff} term. We now record the key uniform estimate needed in the proof of part (a). Lemma 4.8 (Uniform bound for nonzero monomials) . Assume the hypotheses of Theorem 4.4 . Then for every \varepsilon>0 there exists an almost surely finite random constant K_{\varepsilon} such that for all n\geq 1 and every multi-index (i_{1},\ldots,i_{n})\in[k]^{n} for which the monomial A_{1,n}(i_{1},\ldots,i_{n}):=A_{n,i_{n}}A_{n-1,i_{n-1}}\cdots A_{1,i_{1}} is nonzero, we have \|A_{1,n}(i_{1},\ldots,i_{n})\|_{1}\leq K_{\varepsilon}\,\exp\big((\beta+\varepsilon)n\big). Proof. Fix \varepsilon>0 and set m:=|{\mathcal{V}}| . Let \delta:=\varepsilon/(4m) . Define the stationary sequence Y_{n}:=\max_{1\leq j\leq k}\log^{+}\|A_{n,j}\|_{1}. Assumption (i) implies {\mathbb{E}}(Y_{1})<\infty . By Lemma 4.1 (applied to (Y_{n}) ), there exists an almost surely finite random constant C_{\delta} such that for all n\geq 1 and all 1\leq j\leq k , \|A_{n,j}\|_{1}\leq C_{\delta}\,e^{\delta n}. (Indeed the above bound holds for all sufficiently large n , and we absorb the finitely many remaining n into C_{\delta} .) Fix a self-loop label s\in{\mathcal{L}}_{\mathcal{H}} . By assumption (ii), the sequence (A_{n,s})_{n\geq 1} is stationary and ergodic, and A_{n,s} is almost surely invertible with {\mathbb{E}}\log^{+}\|A_{1,s}\|_{1}+{\mathbb{E}}\log^{+}\|A_{1,s}^{-1}\|_{1}<\infty . Realize this stationary process as a linear cocycle over an ergodic measure-preserving transformation \theta (so that A_{n,s}(\omega)=A_{1,s}(\theta^{n-1}\omega) ). By Oseledets’ multiplicative ergodic theorem for integrable linear cocycles (see e.g. [ 5 , 8 ] ), for each \delta>0 there exists a measurable tempered random variable \widetilde{K}_{s,\delta}(\omega)<\infty such that for all \ell\geq 1 , \big\|A_{\ell,s}(\omega)\cdots A_{1,s}(\omega)\big\|_{1}\leq\widetilde{K}_{s,\delta}(\omega)\,e^{(\beta_{s}+\delta)\ell}. Here “tempered” means that \lim_{n\to\infty}\frac{1}{n}\log\widetilde{K}_{s,\delta}(\theta^{n}\omega)=0 almost surely. In particular, \sup_{t\geq 1}\widetilde{K}_{s,\delta}(\theta^{t-1}\omega)e^{-\delta t}<\infty almost surely; define K_{s,\delta}(\omega):=\sup_{t\geq 1}\widetilde{K}_{s,\delta}(\theta^{t-1}\omega)e^{-\delta t}. Then for all t\geq 1 and all \ell\geq 1 , \Big\|A_{t+\ell-1,s}A_{t+\ell-2,s}\cdots A_{t,s}\Big\|_{1}\leq K_{s,\delta}(\omega)\,e^{\delta t}\,e^{(\beta_{s}+\delta)\ell}. (38) Let K_{\delta}:=\max_{s\in{\mathcal{L}}_{\mathcal{H}}}K_{s,\delta} , which is finite almost surely since {\mathcal{L}}_{\mathcal{H}} is finite. Fix n and a multi-index (i_{1},\ldots,i_{n}) with A_{1,n}(i_{1},\ldots,i_{n})\neq 0 . The associated walk on the shape graph visits at most m vertices because the graph has no directed cycles other than self-loops. Consequently the index set \{1,\ldots,n\} can be partitioned into at most m contiguous blocks in which either (i) the label is a self-loop label at the current vertex, repeated for the duration of the block, or (ii) the block consists of a single non-loop transition (a single time step at which the walk changes vertex). Let \ell_{1},\ldots,\ell_{r} be the lengths of the self-loop blocks (so \sum_{q=1}^{r}\ell_{q}\leq n and r\leq m ), and let t_{q} be the starting time index of the q th self-loop block (so t_{q}\leq n ). Using ( 38 ) for each loop block and the bound above for each of the at most m transition steps, we obtain \|A_{1,n}(i_{1},\ldots,i_{n})\|_{1}\leq(C_{\delta})^{m}(K_{\delta})^{m}\,\exp\!\Big(\delta mn\Big)\,\exp\!\Big(\sum_{q=1}^{r}(\beta_{s_{q}}+\delta)\ell_{q}\Big)\,\exp\!\Big(\delta mn\Big), where s_{q} denotes the self-loop label used in block q . Since \beta_{s_{q}}\leq\beta and \sum_{q=1}^{r}\ell_{q}\leq n , the middle exponential is bounded by \exp((\beta+\delta)n) . Absorbing constants, we find \|A_{1,n}(i_{1},\ldots,i_{n})\|_{1}\leq(C_{\delta}K_{\delta})^{m}\exp\!\big((\beta+\delta+2\delta m)n\big). With our choice \delta=\varepsilon/(4m) we have \delta+2\delta m\leq\varepsilon , so setting K_{\varepsilon}:=(C_{\delta}K_{\delta})^{m} yields \|A_{1,n}(i_{1},\ldots,i_{n})\|_{1}\leq K_{\varepsilon}\,e^{(\beta+\varepsilon)n}. This bound is uniform over all nonzero monomials of length n and all n\geq 1 . ∎ Proof of (a). Using the decomposition ( 30 ) in X_{n} and expanding the product, we write \displaystyle X_{n}=\sum_{i_{1}=1}^{k}\cdots\sum_{i_{n}=1}^{k}A_{1,n}(i_{1},\ldots,i_{n}),\quad\text{where}\quad A_{1,n}(i_{1},\ldots,i_{n}):=A_{n,i_{n}}A_{n-1,i_{n-1}}\cdots A_{1,i_{1}}. (39) Each multi-index (i_{1},\ldots,i_{n}) corresponds to a walk on the shape graph via the successive shapes \mbox{\it Shape}{\left(L_{i_{1}}\right)},\,\mbox{\it Shape}{\left(L_{i_{2}}L_{i_{1}}\right)},\,\ldots,\,\mbox{\it Shape}{\left(L_{i_{n}}\cdots L_{i_{1}}\right)} . If O_{d}\in{\mathcal{V}} and this walk ever enters the vertex O_{d} , then the corresponding monomial equals the zero matrix (its support becomes empty), hence contributes nothing to ( 39 ). Therefore the sum ( 39 ) contains at most k_{\rm eff}^{n} nonzero monomials, where we set k_{\rm eff}:=\begin{cases}k,&O_{d}\notin{\mathcal{V}},\\ k_{*},&O_{d}\in{\mathcal{V}},\end{cases} with k_{*} as in the statement of the theorem. Fix \varepsilon>0 . By Lemma 4.8 , there exists an almost surely finite random constant K_{\varepsilon} such that for all n\geq 1 and every nonzero monomial A_{1,n}(i_{1},\ldots,i_{n}) appearing in ( 39 ) , \|A_{1,n}(i_{1},\ldots,i_{n})\|_{1}\leq K_{\varepsilon}\,e^{(\beta+\varepsilon)n}. Consequently, \|X_{n}\|_{1}\leq k_{\rm eff}^{n}\,K_{\varepsilon}\,e^{(\beta+\varepsilon)n}. Taking logarithms, dividing by n , and letting n\to\infty yields \gamma_{1}({\mathcal{A}})\leq\beta+\log k_{\rm eff}+\varepsilon. Since \varepsilon>0 is arbitrary, this gives \gamma_{1}({\mathcal{A}})\leq\beta+\log k_{\rm eff} , which is \beta+\log k when O_{d}\notin{\mathcal{V}} and \beta+\log k_{*} when O_{d}\in{\mathcal{V}} . ∎ For v\in{\mathcal{V}} , define the partial sum of monomials whose final shape is v by Z_{n,v}:=\sum_{\begin{subarray}{c}(i_{1},\dots,i_{n})\in[k]^{n}:\ \mbox{\it Shape}{\left(L_{i_{n}}\cdots L_{i_{1}}\right)}=v\end{subarray}}A_{1,n}(i_{1},\ldots,i_{n}). Then X_{n}=\sum_{v\in{\mathcal{V}}}Z_{n,v} . Proof of (b). Fix w\in{\mathcal{W}} , and let s\in{\mathcal{L}}_{\mathcal{W}} be the label of the self-loop at w . By the additional assumption in (b), there exists r=r(w)\geq 1 such that \mbox{\it Shape}{\left(L_{s}^{n}\right)}=w for all n\geq r . For n\geq r let A_{1,n}^{(s)}:=A_{n,s}A_{n-1,s}\cdots A_{1,s} ; then A_{1,n}^{(s)} is one of the monomials contributing to Z_{n,w} . By the assumption v\wedge w=O_{d} for all v\in{\mathcal{V}}\setminus\{w\} , the supports of Z_{n,w} and X_{n}-Z_{n,w} are disjoint, so \langle Z_{n,w},\,X_{n}-Z_{n,w}\rangle_{F}=0\quad\text{and hence}\quad\|X_{n}\|_{F}\geq\|Z_{n,w}\|_{F}. Under the additional hypothesis that the matrices A_{n,s} are entrywise nonnegative a.s., the sum defining Z_{n,w} is entrywise nonnegative and dominates each of its summands. In particular, Z_{n,w}\geq A_{1,n}^{(s)} entrywise and therefore \|Z_{n,w}\|_{F}\geq\|A_{1,n}^{(s)}\|_{F}. Since all norms on {\mathcal{M}}_{d} are equivalent, the Lyapunov exponent \beta_{s} is the same whether defined with \|\cdot\| or \|\cdot\|_{F} , and thus \lim_{n\to\infty}\frac{1}{n}\log\|A_{1,n}^{(s)}\|_{F}=\beta_{s}. Combining the previous inequalities yields \beta_{s}\leq\gamma_{1}({\mathcal{A}}) . Taking the maximum over s\in{\mathcal{L}}_{\mathcal{W}} gives the claim. ∎ 5 Discussion and outlook We close with a brief discussion highlighting how the shape-graph bounds should be interpreted and where one might seek refinements. Energy–entropy structure and regimes. In the acyclic settings covered by Theorem 4.4 (a), the upper bound \gamma_{1}({\mathcal{A}})\leq\beta+\log k\qquad(\text{or }\beta+\log k_{*}\text{ when }O_{d}\in{\mathcal{V}}) splits into two conceptually distinct pieces. The term \beta is an “energy” contribution: it is the top Lyapunov exponent of the dominant loop cocycle(s), and it captures genuine exponential growth along directions that can persist indefinitely. The logarithmic term is an “entropy” contribution that accounts for the number of admissible monomials in the product expansion. In transfer-matrix language (Example above), \beta corresponds to the best long-run local weight accumulation, while the entropy term corresponds to the proliferation of admissible time-ordered paths. In many models the entropy term is deliberately crude: if the off-diagonal components are small or rare, then \gamma_{1}({\mathcal{A}}) is expected to be close to \beta , and the theorem quantifies that the discrepancy cannot exceed a logarithmic combinatorial correction. Conversely, when many off-diagonal components are simultaneously active and comparable in size to the loop components, the entropy term indicates that purely combinatorial proliferation can shift the top exponent by an O(1) amount. Possible refinements of the entropy term. As emphasized in Remark 4.7 , the \log k term comes from counting all label sequences. A natural refinement is to replace k by an effective growth factor associated with the shape graph itself (e.g. a spectral radius, or a maximal branching factor after reachability constraints are enforced). Such refinements would make the bound sensitive to the geometry of the sparsity pattern, not only to the number of labels. Beyond acyclic shape graphs. The self-loop-only hypothesis in Theorem 4.4 is tailored to situations where feedback through off-diagonal transitions is structurally impossible (e.g. DAG-supported sparsity). Allowing directed cycles would lead to genuinely new behavior: repeated off-diagonal transitions could create additional loop cocycles and may change the exponent in ways not captured by a single \beta . One possible direction is to analyze strongly connected components of the shape graph and to combine the present methods with subadditive/Kingman-type arguments on the induced component graph. Overlapping supports and cancellations. A second limitation is the disjoint-support requirement in the definition of a shape set, which eliminates cancellations between distinct components. Relaxing this assumption is delicate: cancellations can reduce growth and can also make the expansion-based counting argument too pessimistic. It would be interesting to identify intermediate classes (e.g. sign-definite entries, monotone cones, or nonnegative matrices) where overlaps are allowed but the combinatorics remains tractable. Practical use. From a user’s perspective, the shape-graph method is most useful as a diagnostic bound : given a structured model, it provides an explicit, checkable upper bound on the quenched growth rate and highlights which loop components control the exponent. Even when the bound is not tight, it can still be valuable for parameter scaling (e.g. dependence on temperature \theta in transfer-matrix parametrizations) and for separating structural from probabilistic sources of growth.