Perron–Frobenius theorem

A nonnegative square matrix has its Collatz–Wielandt value as an eigenvalue with a nonnegative eigenvector, and for irreducible matrices this eigenvector is positive and the eigenvalue is the spectral radius.

Results

Let $A$ be a nonnegative real $n\times n$ matrix, $n\ge1$. The Perron root is $$ r(A) = \sup_{v \geq 0,\ v \neq 0}\ \min_{i\,:\,v_i > 0} \frac{(Av)_i}{v_i}. $$

Theorem (Perron–Frobenius). [Per07]

Proof

Existence comes from upper semicontinuity of the Collatz–Wielandt function on the standard simplex. The irreducible case reduces to the primitive case through $1+A$.

References

[Per07]; G. Frobenius, “Über Matrizen aus nicht negativen Elementen,” Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften (1912), 456–477.

  1. [Per07] Oskar Perron. Zur Theorie der Matrices. Mathematische Annalen, 64(2), 248-263, 1907.
    BibTeX
    @article{Perron1907,
      author = {Perron, Oskar},
      title = {Zur {T}heorie der {M}atrices},
      year = {1907},
      journal = {Mathematische Annalen},
      volume = {64},
      number = {2},
      pages = {248--263},
      doi = {10.1007/BF01449896},
      url = {https://doi.org/10.1007/BF01449896}
    }

Definitions

  • Perron root

    Matrix.CollatzWielandt.perronRootsource
    noncomputable def perronRoot (A : Matrix n n ℝ) : ℝ :=
      sSup (collatzWielandtFn A '' nonnegNeZero)
    
    omit [Nonempty n] in

Theorems

  • The Perron root has a nonnegative eigenvector

    Matrix.exists_nonneg_mulVec_eq_perronRoot_smulsource
    theorem exists_nonneg_mulVec_eq_perronRoot_smul [Nonempty n]
        {A : Matrix n n ℝ} (hA_nonneg : ∀ i j, 0 ≤ A i j) :
        ∃ v : n → ℝ, (∀ i, 0 ≤ v i) ∧ v ≠ 0 ∧ A *ᵥ v = perronRoot A • v
  • Irreducible matrices have a positive eigenvectorMain result

    Matrix.exists_positive_eigenvector_of_irreduciblesource
    theorem exists_positive_eigenvector_of_irreducible [Nonempty n]
      (hA_irred : A.IsIrreducible) :
        ∃ (r : ℝ) (v : n → ℝ),
          0 < r ∧ (∀ i, 0 < v i) ∧ A *ᵥ v = r • v
  • Primitive matrices: uniqueness of the eigenvector

    Matrix.pft_primitivesource
    theorem pft_primitive
        {n : Type*} [Fintype n] [Nonempty n] [DecidableEq n]
        {A : Matrix n n ℝ} (hA_prim : IsPrimitive A)
        (hA_nonneg : ∀ i j, 0 ≤ A i j) :
        ∃! (v : RealRooted.standardSimplex ℝ n), ∃ (r : ℝ) (_ : r > 0), A *ᵥ v.val = r • v.val
  • The Perron root is the spectral radius

    Matrix.perron_root_is_spectral_radiussource
    theorem perron_root_is_spectral_radius (hA_irred : A.IsIrreducible) (hA_nonneg : ∀ i j, 0 ≤ A i j) :
        let r
  • A positive eigenvector belongs to the Perron root

    Matrix.CollatzWielandt.eq_perron_root_of_positive_eigenvectorsource
    theorem eq_perron_root_of_positive_eigenvector
        {A : Matrix n n ℝ} {r : ℝ} {v : n → ℝ}
        (hA_nonneg : ∀ i j, 0 ≤ A i j)
        (hv_pos : ∀ i, 0 < v i)
        (hr_pos : 0 < r)
        (h_eig : A *ᵥ v = r • v) :
        r = CollatzWielandt.perronRoot (A := A)

Lean source RealRooted/Challenges/Matrices/PerronFrobenius.lean at revision d6670742. Formalized 2026-08-21.