Lemma 12.1 -- basic spectral facts for stochastic matrices
ProvedMarkovMixing.eigenvalue_basicmarkov-chainsmixing-timesprobability
Let be a stochastic matrix on a finite state space (nonnegative entries, rows summing to one). A real number is an eigenvalue of when there is a nonzero function — an eigenfunction — with , where . Recall that is irreducible when every state can reach every other in some number of steps, and aperiodic when the return times to each state have greatest common divisor one.
The theorem (Lemma 12.1 of Levin–Peres–Wilmer) asserts:
- every eigenvalue of satisfies ;
- if is irreducible, every function with is constant — the eigenspace of the eigenvalue is one-dimensional;
- if is irreducible and aperiodic, then is not an eigenvalue of .
These are the basic facts that position the spectrum inside with a simple eigenvalue and excluded, so that the spectral gap of an irreducible aperiodic chain is genuinely positive — the starting point of the spectral theory of Chapters 12–13.
Preamble
import Definitions.Def_mm_spectral
Formal statement
namespace MarkovMixing
/-- **Lemma 12.1** (LPW): (i) every eigenvalue of a transition matrix has
`|λ| ≤ 1`; (ii) for an irreducible chain the eigenfunctions of eigenvalue `1`
are the constants; (iii) an irreducible aperiodic chain does not have `−1`
as an eigenvalue. -/
theorem eigenvalue_basic {V : Type*} [Fintype V] [DecidableEq V]
(P : Matrix V V ℝ) (hP : IsStochastic P) :
(∀ lam : ℝ, IsEigenvalue P lam → |lam| ≤ 1) ∧
(Irreducible P → ∀ f : V → ℝ, P.mulVec f = f → ∀ x y : V, f x = f y) ∧
(Irreducible P → Aperiodic P → ¬IsEigenvalue P (-1)) := by
sorry
end MarkovMixing
Source
D. A. Levin, Y. Peres, E. L. Wilmer, Markov Chains and Mixing Times, AMS 2009, https://documents.epfl.ch/groups/i/ip/ipg/www/2013-2014/Random_Walks/markovmixing.pdf, Section 12.1, Lemma 12.1, p. 153