is_irreducible_real_matrix_uniform
For any positive natural number n, an n-by-n real matrix P whose entries all equal 1/n is irreducible.
Statement
theorem is_irreducible_real_matrix_uniform (n : ℕ) [NeZero n] (P : Matrix (Fin n) (Fin n) ℝ) (hP : ∀ i j, P i j = 1 / (n : ℝ)) : is_irreducible_real_matrix P- Source
- folklore
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_irreducible_real_matrixA real matrix P : Matrix (Fin n) (Fin n) ℝ is irreducible if for every pair of indices i, j : Fin n, there exists a natural number m such…
Read back from the Lean
For every positive natural number $n$ and every $n \times n$ real matrix $P$, if every entry of $P$ satisfies $P_{i, j} = 1 / n$ for all $i, j \in \mathrm{Fin}\ n$, then $P$ is an irreducible real matrix.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that P is irreducible, it suffices to find, for any pair of states (i, j), some power m such that (P ^ m) i j > 0. Since every entry of P is already 1 / n, choosing m = 1 yields (P ^ 1) i j = P i j = 1 / n. Because n is a positive natural number, 1 / n is strictly positive, completing the proof.
For any pair of states i and j, it suffices to show that (P ^ 1) i j > 0.
By definition, a real matrix P is irreducible if for every pair of indices (i, j) there exists a power m such that (P ^ m) i j > 0. We fix arbitrary indices i and j and choose the exponent m = 1.
intro i j use 1
The required inequality simplifies to 0 < 1 / n.
Using pow_one, P ^ 1 simplifies to P. The hypothesis hP states that every entry P i j equals 1 / n, reducing the goal to showing 0 < 1 / n.
uses
pow_onerw [pow_one, hP]0 < 1 / n, concluding the proof.
Since n is non-zero (given by the NeZero typeclass), n is strictly positive by NeZero.pos. Its embedding into the real numbers is strictly positive by Nat.cast_pos.mpr, and taking the reciprocal preserves positivity by one_div_pos.mpr.
uses
one_div_pos.mpr,Nat.cast_pos.mpr,NeZero.posexact one_div_pos.mpr (Nat.cast_pos.mpr (NeZero.pos n))
pow_one- Any element of a monoid raised to the first power equals itself: a ^ 1 = a.
NeZero.pos- A non-zero element in a partially ordered structure with bottom zero is strictly positive; for n : ℕ, n ≠ 0 implies 0 < n.
Nat.cast_pos.mpr- The canonical embedding of ℕ into an ordered semiring preserves strict positivity: if 0 < n, then 0 < (n : ℝ).
one_div_pos.mpr- The reciprocal of a strictly positive number is strictly positive: if 0 < x, then 0 < 1 / x.
- In Lean, deducing 1 / (n : ℝ) > 0 from the typeclass hypothesis NeZero n requires explicit cast and reciprocal lemmas (NeZero.pos, Nat.cast_pos.mpr, and one_div_pos.mpr), which would be taken for granted on paper.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The uniform transition matrix with all entries 1/n is irreducible. -/theorem is_irreducible_real_matrix_uniform (n : ℕ) [NeZero n] (P : Matrix (Fin n) (Fin n) ℝ) (hP : ∀ i j, P i j = 1 / (n : ℝ)) : is_irreducible_real_matrix P := by intro i j use 1 rw [pow_one, hP] exact one_div_pos.mpr (Nat.cast_pos.mpr (NeZero.pos n))