Extremal sequences of polynomial complexity

DOI10.1017/S0305004113000157MaRDI QIDQ2845616zbMATH OpenFDO

Authors Kevin G. Hare, Ian D. Morris, Nikita Sidorov

Publication date 2 September 2013

Published in Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.6236

zbMATH Keywords

Eigenvalueseigenvectorssingular values

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60)

Abstract: The joint spectral radius of a bounded set of $dimesd$ real matrices is defined to be the maximum possible exponential growth rate of products of matrices drawn from that set. For a fixed set of matrices, a sequence of matrices drawn from that set is called emph{extremal} if the associated sequence of partial products achieves this maximal rate of growth. An influential conjecture of J. Lagarias and Y. Wang asked whether every finite set of matrices admits an extremal sequence which is periodic. This is equivalent to the assertion that every finite set of matrices admits an extremal sequence with bounded subword complexity. Counterexamples were subsequently constructed which have the property that every extremal sequence has at least linear subword complexity. In this paper we extend this result to show that for each integer $pgeq1$, there exists a pair of square matrices of dimension $2^p(2^{p+1}-1)$ for which every extremal sequence has subword complexity at least $2^{-p^2}{n}^p$.

Review text

The authors define the joint spectral radius of a bounded set of \(d\times d\) real matrices as the maximum possible exponential growth rate of products of matrices drawn from that set. For a fixed set of matrices, a sequence of matrices drawn from that set is called extremal if the associated sequence of partial products achieves this maximal rate of growth. An influential conjecture of \textit{J. C. Lagarias} and \textit{Y. Wang} [Linear Algebra Appl. 214, 17--42 (1995; Zbl 0818.15007)] asked whether every finite set of matrices admits an extremal sequence which is periodic. This is equivalent to the assertion that every finite set of matrices admits an extremal sequence with bounded subword complexity. Counterexamples were subsequently constructed which have the property that every extremal sequence has at least linear subword complexity. In the paper, the authors extend this result to show that for each integer \(p\geq 1\) there exists a pair of square matrices of dimension \(2^p (2^{ p+1} -1)\) for which every extremal sequence has subword complexity at least \(2^{ -p^2}n^p\).

Recommendations

• Extremal matrix products and the finiteness property
• On Nonnegative Integer Matrices and Short Killing Words
• An explicit counterexample to the Lagarias-Wang finiteness conjecture
• Overlap-free words and spectra of matrices
• Joint spectral characteristics of matrices: a conic programming approach
• On linear forbidden submatrices
• The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate
• Cycle Lengths in A^k b
• Optimal norms and the computation of joint spectral radius of matrices
• JSR: a toolbox to compute the joint spectral radius

Cites work

• A Combinatorial Application of the Maximal Ergodic Theorem
• A rapidly-converging lower bound for the joint spectral radius via multiplicative ergodic theory
• An Elementary Counterexample to the Finiteness Conjecture
• An explicit counterexample to the Lagarias-Wang finiteness conjecture
• Automatic Sequences
• Explicit construction of a Barabanov norm for a class of positive planar discrete-time linear switched systems
• On the finiteness property for rational matrices
• Stability of discrete linear inclusion
• Structure of extremal trajectories of discrete linear systems and the finiteness conjecture
• Substitutions in dynamics, arithmetics and combinatorics
• The finiteness conjecture for the generalized spectral radius of a set of matrices
• The generalized spectral radius and extremal norms

Cited in

(9)

• Non-Sturmian sequences of matrices providing the maximum growth rate of matrix products
• Growth degree classification for finitely generated semigroups of integer matrices
• The entropy of Lyapunov-optimizing measures of some matrix cocycles
• Lyapunov-maximizing measures for pairs of weighted shift operators
• Extremal ergodic measures and the finiteness property of matrix semigroups
• Regular sequences and the joint spectral radius
• An explicit counterexample to the Lagarias-Wang finiteness conjecture
• On marginal growth rates of matrix products
• Structure of extremal trajectories of discrete linear systems and the finiteness conjecture

This page was built for publication: Extremal sequences of polynomial complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2845616)