Exact computation of joint spectral characteristics of linear operators

Problem setting

• The JSR measures the highest asymptotic growth rate of matrix products, whereas the LSR measures the lowest; exact LSR computation had received much less attention.The paper describes the prior available LSR method as approximate.Source: §1 · pp. 2, 6

JSR computation

• For JSR, the method builds an extremal polytope norm around a candidate spectrum-maximizing product, certifying its value when the norm is extremal.The general algorithm can instead produce a polytope norm giving upper and lower bounds that converge to the JSR.Source: §1 · pp. 3, 5, 6

Limitations

• The method does not work for some families lacking an s.m.p. or an extremal polytope, and multiple s.m.p.s can prevent it from finding an existing extremal polytope.The paper notes that multiple s.m.p.s, though generally rare, arise in practical applications.Source: §1 · p. 6

LSR computation

• For families sharing an invariant cone, including nonnegative matrices, the LSR algorithm uses extremal antinorms and infinite polytopes to compute exact values.The paper reports that the algorithm works well in dimensions such as 100.Source: §1 · p. 7

Applications and results

• The algorithms compute exact JSR values for special matrix families up to dimension 40, solving three open problems; applications also prove two conjectures and disprove another.The applications include overlap-free words, the density of ones in the Pascal rhombus, and Euler partition functions.Source: §1 · pp. 7–8

Termination and stopping criteria

• The JSR algorithms terminate in finite time exactly when the family has a dominant product; a stopping criterion can reject a poor candidate and suggest one with a larger spectral radius.The criterion for finite termination is stated for Algorithms (R), (C), and (P).Source: §1 · pp. 7–8

Numerical tests

• In random-matrix tests spanning dimensions 5 to 100, the algorithms found exact JSR and LSR values in all considered cases.For general families, the paper reports exact JSR computations up to dimension 20; the nonnegative-matrix algorithms reach dimensions around 100.Source: §1 · pp. 7–8

2 Computing of the joint spectral radius: the case of real leading eigenvectors (R)

• For an irreducible normalized family with JSR at least 1, a bounded orbit Ω(v) spanning the space is the unit ball of an extremal norm.The algorithm’s initial-vector search uses a real leading eigenvector of a candidate product, though other choices are admissible.Source: §2 · p. 9

2.1 Algorithm (R)

• When U_k=∅, Algorithm (R) identifies Π as an s.m.p. and ρ(Π)^(1/n) as the exact JSR after k steps.Compared with a similar earlier algorithm, it includes new vertices on the polytope boundary, considers all leading eigenvectors as starting vertices, and adds a stopping criterion.Source: §2 · p. 10, §2.1 · p. 12

2.2 The cyclic tree structure of the algorithm

• The algorithm explores a cyclic tree, expanding alive leaves and pruning dead branches; it terminates when a step produces no alive leaves.A new vector is a dead leaf when it lies in the interior of the current symmetrized convex hull; otherwise, it is added as an alive leaf.Source: §2.2 · p. 13

2.3 Explanations and proofs

• When the algorithm terminates, its polytope is extremal: the scaled matrices preserve its unit ball, while the normalized candidate product has spectral radius 1.The resulting bounds imply that the original family’s JSR equals ρ(Π)^(1/n).Source: §2.3 · p. 14

2.4 Efficiency results for Algorithm (R)

• As the product-length limit l and iteration count N grow, t_N→1 and Algorithm (R)'s JSR bounds become arbitrarily close.If the algorithm does not terminate, its relative error is ε=(t_N)^-1−1.Source: §2.4 · p. 15
• t_N is non-decreasing in N, and (t_N)^-1 - 1 < ε whenever N ≥ N_ε and l ≥ l_δ, for suitable thresholds for each ε > 0.Source: §2.4 · p. 15
• When Π’s leading eigenvalue is real, unique, and simple, condition (9) is eventually violated for every j if Π is not an s.m.p.; any violation implies it is not.Source: §2.4 · p. 16
• If Π is not an s.m.p., Algorithm (R)’s stopping criterion identifies this in finite time; Theorem 4 gives a sharp criterion for finite termination and producing an extremal polytope.Source: §2.4 · p. 16

3 Computing of the joint spectral radius: the case of complex leading eigenvectors (C)

• Balanced complex polytopes provide unit balls for complex polytope norms.A balanced complex polytope is defined from a finite set of vectors; each such polytope is the unit ball of a norm on C^d.Source: §3 · pp. 16–17
• Complex polytope norms are dense among norms on C^d, allowing an ε-close approximation to an extremal norm even when no extremal polytope norm exists.The density of the induced matrix norms supports this approximation property.Source: §3 · p. 17

3.1 Main differences between Algorithm (C) and Algorithm (R).

• Algorithm (C) extends Algorithm (R), but computes the polytope norm through a real optimization problem and uses a complex-specific stopping condition.The optimization problem can be solved by conic quadratic programming; the stopping test replaces condition (9) with condition (15).Source: §3.1 · pp. 17–18

4.1 Operators with invariant cones. Monotone extremal norms

• If operators share an invariant cone and have no common invariant faces, their family possesses a monotone invariant norm on that cone.The existence result relaxes the irreducibility condition and allows the invariant norm to be chosen monotone with respect to the cone.Source: §4.1 · pp. 18–19

4.2 Algorithm (P) versus Algorithm (R)

• Algorithm (P) constructs a monotone extremal norm on the positive orthant using nonnegative vectors and a positive, nonsymmetric polytope.Unlike Algorithm (R), it does not add the negatives of the vertices; its LP uses an inequality where Algorithm (R) uses an equality constraint.Source: §4.2 · p. 21, §4.3 · p. 22

4.3 Explanations and proofs

• Algorithm (P) uses half as many LP variables and constraints as Algorithm (R), and its larger positive polytope removes more dead branches, reducing complexity.The paper reports that Algorithm (P) works much faster in practice.Source: §4.3 · p. 22
• For positively irreducible families, the approximation parameter t_N tends to 1 as l and N increase.The proof establishes convergence using the invariant-cone norm result.Source: §4.3 · p. 22
• With a unique simple Perron-Frobenius eigenvalue for the candidate product, a violated condition (19) detects that it is not spectrum maximizing, and nonnegative families can also be handled when reducible.The paper advises factoring reducible families first because it can significantly reduce dimension.Source: §4.3 · p. 22

5 The criterion for finite termination of Algorithms (R), (C) and (P).

• If an algorithm does not terminate, it supplies upper and lower JSR bounds that converge to the exact value.The paper also describes a nondominant example where the algorithms fail to converge unless boundary vertices are removed.Source: §5 · pp. 23–24
• A dominant product has a normalized spectral-radius gap: every product other than its powers and cyclic-permutation powers has spectral radius below some q < 1.A dominant product and its cyclic permutations are spectrum maximizing, but the converse does not hold.Source: §5 · p. 23
• Finite termination occurs if and only if the candidate product is dominant and has a unique, simple leading eigenvalue.If termination occurs, the algorithm produces an extremal polytope and establishes that the chosen product is spectrum maximizing.Source: §5 · p. 23

6.1 Antinorms on convex cones

• For families sharing an invariant cone, a monotone extremal antinorm exists, extending the extremal-norm approach where the lower-radius minimum need not be convex.The minimum of the norms of the images may fail to be a norm, even for irreducible positive families; for nonnegative matrices, the existence result applies on the nonnegative cone.Source: §6.1 · pp. 24, 26

6.2 Algorithm (L)

• When Algorithm (L) terminates, its candidate product is an s.l.p., and the constructed infinite polytope yields the exact LSR and an extremal antinorm.The algorithm builds nested infinite polytopes; at termination the polytope is extremal and the candidate product’s normalized spectral radius equals the LSR.Source: §6.2 · p. 28, §6.3 · p. 29

6.3 Explanations and proofs

• The algorithm expands nested infinite polytopes to construct an extremal antinorm, and removes points only when a strict inequality preserves exactness.If it does not terminate, the method provides an estimate for the LSR, though the lower bound may fail to converge.Source: §6.3 · pp. 28–29

6.4 Efficiency results for Algorithm (L)

• The algorithm’s stopping test determines whether a candidate is an s.l.p. whenever its Perron–Frobenius eigenvalue is unique and simple.A violation of condition (23) at some step certifies that the candidate is not an s.l.p.; if it is not an s.l.p., such a violation occurs.Source: §6.4 · p. 29
• The lower-bound estimate may fail to converge when a product’s leading eigenvector lies on the invariant cone’s boundary, making the algorithm ineffective in such cases.The paper suggests avoiding this situation by imposing a second invariant cone or enlarging the invariant cone.Source: §6.4 · pp. 29–30

6.5 Convergence of the algorithm. Case 1; the second invariant cone.

• For nonnegative matrix families, eventual positivity provides a sufficient condition for a second invariant cone embedded in the nonnegative cone.A family is eventually positive if all products of every sufficiently large length are positive; families consisting of positive matrices satisfy this condition.Source: §6.5 · p. 30
• An embedded pair of invariant cones guarantees a positive monotone invariant antinorm whose scaling constant equals the LSR.The embedded-pair assumption matters: invariant antinorms need not exist for every family sharing an invariant cone.Source: §6.5 · pp. 30–31
• With a second invariant cone, Algorithm (L) gives lower and upper LSR bounds arbitrarily close for sufficiently large iteration parameters.The ratio tN tends to 1 as l and N grow. Eventual positivity, or a second invariant cone with a simple leading eigenvalue of Π, suffices for this convergence.Source: §6.5 · pp. 31–32

6.6 The criterion for finite termination of Algorithm (L).

• For an eventually positive family, Algorithm (L) terminates finitely if and only if Π is under-dominant; such a family with an under-dominant product has an extremal infinite polytope.Eventual positivity is essential to the criterion, although the algorithm can produce extremal polytopes for some families without it.Source: §6.6 · p. 33

6.7 Case 2. Modification of Algorithm (L)

• Without a second invariant cone, Algorithm (L) may fail to converge to the LSR when a product has a simple leading eigenvector with zero entries and the stated spectral-radius inequality holds.In this case vertices can approach the cone boundary, tN may not converge to 1, and the algorithm becomes unusable.Source: §6.7 · p. 33
• An LP-based modification widens the invariant cone to cover vertices near its boundary and often makes Algorithm (L) terminate finitely.The modified construction uses the wider cone KH; when it terminates, it produces an extremal infinite polytope.Source: §6.7 · p. 34

7 Illustrative examples

• The JSR example terminates after two steps with bρ(M) = 2, after testing the generated points against the polytope.The example begins with the guess Π = A1A2 as a spectrum-maximizing product.Source: §7 · p. 35
• The LSR example gives 6.009313489… as ρ(Π)^1/8 for a spectrum-minimizing product, and the algorithm terminates after two steps.Its infinite polytope is extremal.Source: §7 · pp. 35, 37
• In the LSR example, the first step yields one new alive vertex and seven dead leaves; the next generated vertices are both dead.The procedure starts from eight points generated from the leading eigenvector of the normalized product.Source: §7 · pp. 36–37

8.1 The asymptotics of the number of overlap-free words

• The algorithms prove both conjectures on the upper and lower growth exponents of overlap-free words.The LSR computation terminates after 15 steps with an extremal infinite polytope of 104 vertices.Source: §8.1 · pp. 38–40

8.2 The density of ones in the Pascal rhombus

• The exact LSR computation disproves the golden number conjecture for the Pascal rhombus; A1^3A2^3 is an s.l.p.The product is identified as an s.l.p. for the matrix family.Source: §8.2 · p. 41

8.3 The Euler binary partition function

• For odd r≤41, Algorithms (P) and (L) prove the Euler binary partition conjecture; at r=51, Algorithm (L) terminates in 15 iterations with 135 vertices.For r=33, the JSR–LSR gap is under 0.00002%, yet the algorithms need only 11 and 10 iterations, respectively.Source: §8.3 · p. 43

8.4 The Euler ternary partition function

• Algorithms (P) and (L) determine precise values; Π = A2 A3 is an s.m.p., while Π = A1 A2 is an s.l.p.The corresponding cyclic trees have 12 vertices for Π = A2 A3 and 16 vertices for Π = A1 A2.Source: §8.4 · pp. 44–45

• The method effectively computes both JSR and LSR for nonnegative matrices, while computation complexity increases significantly with dimension.The authors expect reasonable-time computations to reach high dimensions for operator sets sharing an invariant cone.Source: §9 · p. 45
• The random tests include general normally distributed pairs scaled to equal spectral norm and nonnegative pairs scaled to equal norm.Binary pairs are scaled to have the same spectral radius; the tables report JSR and LSR computation for nonnegative and binary pairs.Source: §9 · pp. 45–46, Table 3 · p. 46
• For general random pairs, iteration counts and extremal-polytope vertex counts rise rapidly with dimension; 20×20 pairs are challenging.Computations at dimension 10 usually take minutes, while dimension 20 usually takes half an hour to an hour and sometimes up to eight hours.Source: §9 · pp. 45–47
• Finite convergence is not guaranteed when a starting matrix is itself an optimal product, and some such cases did not terminate finitely.The authors identify balancing leading eigenvectors from distinct optimal products as an open problem and leave it for future investigation.Source: §9 · pp. 47–48
• In nonnegative cases, vertices lie in the nonnegative orthant, reducing complexity, but quasi-optimal products slow the algorithm.Quasi-optimal products are described as products with eigenvalues close to 1.Source: §9 · p. 47
• For binary matrices, behavior depends somewhat on zero-entry density and dimension, yet the authors report computing large matrices across densities.Tables 4 and 5 cover pairs of binary matrices of dimensions 50 and 100.Source: §9 · pp. 47–48, Table 4 · p. 47, Table 5 · p. 48

10.1–10.2 Proofs

• Auxiliary cyclic-tree lemmas show that words outside powers of the generating word stay outside its root, while termination bounds later tree nodes within scaled polytopes.The bounds are (1 − ε)P_(k−1) for Algorithm (R) and (1 + ε)P_(k−1) for the stated cyclic-tree result.Source: §10.1 · pp. 48–49, §10.2 · p. 50

10.1 Proof of Theorem 4

• Under the proof's assumptions, Algorithm (R) terminates finitely exactly when its candidate product is dominant with a unique, simple leading eigenvalue.The necessity proof derives dominance and simplicity from termination; the sufficiency proof assumes these properties and rules out an infinite path.Source: §10.1 · pp. 49–50

10.2 Proof of Theorem 7

• For eventually positive families, the proof rules out failure to produce an extremal infinite polytope when the candidate product is under-dominant.The argument uses an invariant cone containing the leading eigenvectors and an invariant antinorm to derive a contradiction from an infinite path.Source: §10.2 · pp. 51–52

10.3 The 20 × 20 matrices

• The overlap-free-words example is certified by listing a 54-vertex extremal polytope and a 104-vertex extremal infinite polytope.The appendix says listing these vertices suffices for the rigorous proof using Algorithms (P) and (L).Source: §10.2 · pp. 52–53