AFTD Auto-Formalizing Theoretical Domains

is_irreducible_real_matrix_uniform

theoremverified

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.

  1. 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.

    lines 3–4

      intro i j
      use 1
  2. 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.

    line 5

    uses pow_one

      rw [pow_one, hP]
  3. 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.

    line 6

    uses one_div_pos.mpr, Nat.cast_pos.mpr, NeZero.pos

      exact 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.

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

/-- 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))
See it in the graphDiscuss this resultChallenge it