Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

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

Proved
AccelVI.MVC.reversible_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 set SSS (nonnegative entries, rows summing to 111), and suppose the chain is irreducible and reversible: there is a stationary probability distribution ν\nuν with νiLij=νjLji\nu_i L_{ij} = \nu_j L_{ji}νi​Lij​=νj​Lji​ for all i,ji, ji,j. Then every eigenvalue of LLL is real:

Sp⁡(L)⊂R.\operatorname{Sp}(L) \subset \mathbb{R}.Sp(L)⊂R.

The paper quotes this fact from Brémaud (Chapter 6, Section 2.1); it is what makes the eigenvalues of BπB_\piBπ​ explicit in the proof of Lemma B.2.

Formalization Note. The spectrum is taken over C\mathbb{C}C: Sp⁡(L)\operatorname{Sp}(L)Sp(L) is the spectrum of the complexified matrix, and "real" means zero imaginary part. Irreducibility, stationarity and detailed balance are the published mm_basic notions.

Preamble
import Mathlib
import Definitions.Def_mm_basic
import Definitions.Def_AccelVI_MVC_Setting
Formal statement
namespace AccelVI.MVC

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

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

end AccelVI.MVC
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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me