Decidability of right-convergent matrix-product families: the RCP SET, CONTINUOUS RCP SET, and subunit joint spectral radius problems of Daubechies and Lagarias

Daubechies and Lagarias (1992) introduced RCP (right-convergent-product) sets — finite families of $n\times n$ matrices for which every infinite right product $\prod_{i=1}^{k} M_i$ , $M_i\in\Sigma$ , converges as $k\to\infty$ — and, in a 2001 corrigendum, characterized product-bounded RCP sets through a block decomposition whose decisive condition is $\hat\rho(P_V\Sigma_B P_V)<1$ , where $\Sigma_B$ is a possibly infinite set of block products and $P_V$ a projection. The algorithmic problems left open by this work concern a finite family of rational matrices: whether there is a finite decision procedure for being an RCP set, or for being an RCP set with a continuous (real-continuous) limit function; whether the class of finite rational RCP sets is recursively enumerable; and whether the subunit joint spectral radius condition $\hat\rho<1$ — equivalently the block criterion with possibly infinite $\Sigma_B$ — can be certified effectively. Later work delimits but does not settle these questions: boundedness of all products of a pair is undecidable (Blondel and Tsitsiklis, 2000), the threshold problem $\hat\rho\ge 1$ is conjectured undecidable but remains open, the finiteness conjecture is refuted, and the stochastic/consensus special case is decidable with tight Paz-type bounds.

Background

For a finite set $\Sigma=\{M_1,\dots,M_m\}$ of $n\times n$ complex or real matrices, consider infinite right products $\prod_{i=1}^{k} M_{d_i}$ in which each factor is drawn arbitrarily from $\Sigma$ . The set $\Sigma$ is called an RCP set (right-convergence of products) if every such infinite product converges as $k\to\infty$ ; the limits define a limit function on the sequence space of digit strings. $\Sigma$ is product-bounded if the norms of all finite products are bounded by a single constant. Two growth invariants quantify the worst case over products: the joint spectral radius $\hat\rho(\Sigma)$ , the exponential growth rate of the largest norm of a length- $k$ product, and the generalized spectral radius $\bar\rho(\Sigma)$ , the analogous quantity defined with spectral radii instead of norms. Daubechies and Lagarias (1992) proved that every finite RCP set satisfies $\hat\rho(\Sigma)\le 1$ , that the limit function is identically zero exactly when $\hat\rho(\Sigma)<1$ , and gave criteria for the limit function to be continuous on sequence space, and to descend to a continuous (real-continuous) function on $[0,1]$ via $m$ -ary digit expansions; the criteria combine a common, simple left $1$ -eigenspace $E_1(\Sigma)$ with contraction of the projected family $P_V\Sigma P_V$ on a complementary subspace $V$ , where $P_V$ is a projection. Their characterization of product-bounded RCP sets, corrected in the 2001 corrigendum, reduces the analysis to blocks — minimal finite products $B$ whose left $1$ -eigenspace equals $E_1(\Sigma)$ — collected in a set $\Sigma_B$ that can be infinite, and requires $\hat\rho(P_V\Sigma_B P_V)<1$ . A decision problem here means a terminating algorithm that, given the finitely many (rational) entries of $\Sigma$ , answers yes or no; recursive enumerability means the existence of a certificate system whose finite members can be listed effectively. Two neighboring undecidability results frame the question: the mortality problem for finite integer matrix families (whether some product is the zero matrix, Paterson 1970) and the result of Blondel and Tsitsiklis (2000) that boundedness of all products of a pair of rational matrices is undecidable. In the opposite direction, the stochastic case is decidable: by a bound of Paz, all infinite products of stochastic matrices converge to rank-one matrices iff a condition on all products of length $\frac12(3^n-2^{n+1}+1)$ holds, a bound tightened by Chevalier, Hendrickx and Jungers (2016). The Lagarias–Wang finiteness conjecture — that $\hat\rho(\Sigma)$ is always attained by a periodic product — was refuted by Bousch and Mairesse (2002), removing the most natural route to deciding spectral-radius thresholds via finitely many periodic products.

Problem Statement

Decide, or settle the decision status of, the algorithmic problems left open by Daubechies and Lagarias (1992; corrigendum 2001) for a finite set $\Sigma$ of $n\times n$ matrices with rational entries. (i) RCP SET: given $\Sigma$ , decide whether every infinite right product $\prod_{i=1}^{k} M_{d_i}$ with $M_{d_i}\in\Sigma$ converges as $k\to\infty$ ; and, as the companion certificate question posed alongside it, determine whether the class of finite rational RCP sets is recursively enumerable, i.e., whether it admits a finite certificate system by which its members can be listed effectively. (ii) CONTINUOUS RCP SET: decide whether $\Sigma$ is an RCP set whose limit function is continuous on the sequence space, and in the real-parameter formulation whether the induced limit function on $[0,1]$ (via $m$ -ary digit expansions, where $m=|\Sigma|$ is the number of matrices and each digit selects one factor) is well defined and continuous. (iii) SUBUNIT JOINT SPECTRAL RADIUS: decide whether $\hat\rho(\Sigma)<1$ ; more generally, certify effectively the corrected block criterion $\hat\rho(P_V\Sigma_B P_V)<1$ of the 2001 corrigendum, where $\Sigma_B$ is the set of minimal block products and may be infinite. These three questions are linked: an effective procedure for (iii) would yield one for (ii) under the projection-based criterion, and (i) subsumes the certificate question for the whole class. Each of (i)–(iii) bundles two parts that stand alone and may be settled separately: (i) the RCP-membership decision problem, and its companion recursive-enumerability (certificate) question; (ii) continuity of the limit function on the sequence space, and well-definedness and continuity of the induced function on $[0,1]$ ; (iii) the decision problem $\hat\rho(\Sigma)<1$ , and the more general effective certification of the block criterion with possibly infinite $\Sigma_B$ . Settling any one part, in either direction — a terminating decision procedure or a proof of undecidability — resolves the task, while the remaining parts stand as residual open questions. The companion threshold question of Blondel and Tsitsiklis — whether checking $\hat\rho(\Sigma)\ge 1$ for finite rational families is undecidable, which remains the standard open conjecture in this line — is part of the surrounding landscape and is not required as a separate deliverable. The spectral-radius equality sub-question is excluded from the target because it is resolved (Berger and Wang 1992 for bounded, hence finite, families; failure in infinite dimensions by Gurvits 1995), and the boundedness sub-question is excluded because it is likewise not open: a finite matrix family all of whose infinite products converge is automatically product-bounded, since the partial products along every infinite product are then bounded and this pointwise boundedness forces a uniform bound over all finite products (Berger and Wang 1992; Daubechies and Lagarias 1992), and its continuous-limit case is settled by the paracontraction results of Beyn and Elsner (1997).

References

Ingrid Daubechies and Jeffrey C. Lagarias, Sets of matrices all infinite products of which converge, Linear Algebra and its Applications 161 (1992) 227-263, doi:10.1016/0024-3795(92)90012-y.
Ingrid C. Daubechies and Jeffrey C. Lagarias, Corrigendum/addendum to: Sets of matrices all infinite products of which converge, Linear Algebra and its Applications 327 (1-3) (2001) 69-83, doi:10.1016/S0024-3795(00)00314-1.
Marc A. Berger and Yang Wang, Bounded semigroups of matrices, Linear Algebra and its Applications 166 (1992) 21-27, doi:10.1016/0024-3795(92)90267-E.
Victor Kozyakin, The Berger-Wang formula for the Markovian joint spectral radius, Linear Algebra and its Applications 448 (2014) 315-328, doi:10.1016/j.laa.2014.01.022, arXiv:1401.2711.
Leonid Gurvits, Stability of discrete linear inclusion, Linear Algebra and its Applications 231 (1995) 47-85, doi:10.1016/0024-3795(95)90006-3.
Leonid Gurvits and Leiba Rodman, Convergence of polynomially bounded semigroups of matrices, SIAM Journal on Matrix Analysis and Applications 18 (2) (1997) 360-368, doi:10.1137/S089547989528939X.
Wolf-Jurgen Beyn and Ludwig Elsner, Infinite products and paracontracting matrices, The Electronic Journal of Linear Algebra 2 (1997), doi:10.13001/1081-3810.1006.
Vincent D. Blondel and John N. Tsitsiklis, The boundedness of all products of a pair of matrices is undecidable, Systems & Control Letters 41 (2) (2000) 135-140, doi:10.1016/S0167-6911(00)00049-9.
Jeffrey C. Lagarias and Yang Wang, The finiteness conjecture for the generalized spectral radius of a set of matrices, Linear Algebra and its Applications 214 (1995) 17-42, doi:10.1016/0024-3795(93)00052-2.
T. Bousch and J. Mairesse, Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture, Journal of the American Mathematical Society 15 (1) (2002) 77-111, doi:10.1090/S0894-0347-01-00378-2.
Oliver Jenkinson and Mark Pollicott, Joint spectral radius, Sturmian measures and the finiteness conjecture, Ergodic Theory and Dynamical Systems 38 (8) (2018) 3062-3100, doi:10.1017/etds.2017.18, arXiv:1501.03419.
P.-Y. Chevalier, J. M. Hendrickx and R. M. Jungers, Tight bound for deciding convergence of consensus systems, Systems & Control Letters 105 (2017) 78-83, doi:10.1016/j.sysconle.2017.05.001, arXiv:1601.04975.
Victor Kozyakin, On convergence of infinite matrix products with alternating factors from two sets of matrices, Discrete Dynamics in Nature and Society 2018, Article ID 9216760, doi:10.1155/2018/9216760, arXiv:1712.06356.
Victor Kozyakin, On the boundedness of infinite matrix products with alternating factors from two sets of matrices, arXiv:2010.03890.
Vuong Bui, Growth of bilinear maps III: Decidability, Theoretical Computer Science (2025), doi:10.1016/j.tcs.2025.115515, arXiv:2201.09850.
Ron Ofir and A. Stephen Morse, On determining the convergence rate of an infinite product of stochastic matrices, arXiv:2607.03623 (2026).
Jianhong Shen, Compactification of a set of matrices with convergent infinite products, Linear Algebra and its Applications 311 (2000) 177-186, doi:10.1016/S0024-3795(00)00080-X.