Existence of a critical cycle.
ProvedTropicalLA.IsTropEigen.exists_critical_cycleaether-catalogalgebra
Existence of a critical cycle. If lam is an eigenvalue, some closed walk
has mean weight exactly lam; moreover it can be taken simple: its p vertices
y, f y, …, f^{p-1} y are pairwise distinct.
theorem TropicalLA.IsTropEigen.exists_critical_cycle(h : IsTropEigen A lam v) :
∃ (f : ι → ι) (y : ι) (p : ℕ), 0 < p ∧ f^[p] y = y ∧
Set.InjOn (fun t => f^[t] y) (Finset.range p : Finset ℕ) ∧
(∀ i, A i (f i) + v (f i) = lam + v i) ∧
pathWeight A (fun t => f^[t] y) p = p * lam := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Algebra/TropicalLinearAlgebra/TropicalEigenvalue.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Algebra/TropicalLinearAlgebra/TropicalEigenvalue.lean
import Mathlib
import Definitions.Def_Algebra_TropicalLinearAlgebra_TropicalDeterminant
import Definitions.Def_Algebra_TropicalLinearAlgebra_TropicalEigenvalue
import Definitions.Def_Algebra_TropicalLinearAlgebra_TropicalMatrix
/-
# Tropical eigenvalues and the max-plus Perron–Frobenius theorem
An eigenpair of a max-plus matrix `A` (finite real entries) is a pair `(lam, v)`
with `A ⊗ v = lam ⊗ v`, i.e.
`max_j (A i j + v j) = lam + v i` for every `i`.
Main results of this file:
* `IsTropEigen.cycle_le` : every closed walk (cycle) of `A` has weight at most
`length · lam` — an eigenvalue dominates all cycle means;
* `IsTropEigen.exists_critical_cycle` : some *simple* cycle attains the mean `lam`
exactly (the critical cycle), obtained from the argmax function of the eigenvector
by a minimal-period pigeonhole argument;
* `IsTropEigen.isGreatest_cycleMean` : **tropical Perron–Frobenius (spectral part)** —
`lam` is the *maximum cycle mean* of `A`, and hence
* `tropEigenvalue_unique` : a max-plus matrix has at most one eigenvalue.
-/
open TropicalLA
variable {ι : Type*} [Fintype ι] [Nonempty ι]
open IsTropEigen
variable {A : Matrix ι ι ℝ} {lam : ℝ} {v : ι → ℝ}Formal statement
theorem TropicalLA.IsTropEigen.exists_critical_cycle(h : IsTropEigen A lam v) :
∃ (f : ι → ι) (y : ι) (p : ℕ), 0 < p ∧ f^[p] y = y ∧
Set.InjOn (fun t => f^[t] y) (Finset.range p : Finset ℕ) ∧
(∀ i, A i (f i) + v (f i) = lam + v i) ∧
pathWeight A (fun t => f^[t] y) p = p * lam := by sorrySource