Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§2, p. 4 — the eigenvalues of the transition matrix of a reversible Markov chain are all real

Proved
AccelVI.AVC.real_spectrum

by mikedeng1 · Oct 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

markov-chainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reversible-markov-chainspectrum

Let LLL be the transition matrix of a Markov chain on a finite state space S\mathbb SS (nonnegative entries, rows summing to one), and suppose the chain is reversible in the sense of Definition 2.1: LLL is irreducible and has a stationary distribution ν\nuν with νiLij=νjLji\nu_iL_{ij}=\nu_jL_{ji}νi​Lij​=νj​Lji​ for all i,ji,ji,j. Then every eigenvalue of LLL is real:

μ∈Sp⁡(L)⊂C ⟹ Im⁡μ=0.\mu\in\operatorname{Sp}(L)\subset\mathbb C\ \Longrightarrow\ \operatorname{Im}\mu=0.μ∈Sp(L)⊂C ⟹ Imμ=0.

The paper cites this from Brémaud (2013, Ch. 6, §2.1) and uses it to locate the spectrum of LπL_\piLπ​ in the analysis of A-VC.

Formalization Note. The spectrum is that of LLL viewed as a complex matrix, so non-real eigenvalues are not excluded by the choice of field. The stationary distribution is a probability vector by the definition of stationarity in mm_basic.

Preamble
import Mathlib
import Definitions.Def_mm_basic
import Definitions.Def_AccelVI_AVC_Setting
Formal statement
namespace AccelVI.AVC

variable {S : Type*} [Fintype S] [DecidableEq S]

/-- §2, p. 4 (after Definition 2.1): the eigenvalues of the transition matrix `L` of a
reversible Markov chain are all real. -/
theorem real_spectrum (L : Matrix S S ℝ) (hL : MarkovMixing.IsStochastic L)
    (hrev : IsReversible L) :
    ∀ μ ∈ spectrum ℂ (L.map (algebraMap ℝ ℂ)), μ.im = 0 := by sorry

end AccelVI.AVC
Source
Goyal & Grand-Clément, A First-Order Approach to Accelerated Value Iteration, arXiv:1905.09963v7, p. 4, paragraph after Definition 2.1
Human review
  • Endorsed by Shuze Chen · Oct 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 15, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me