Proposition 2.1 — Perron–Frobenius:
ProvedQNoiseStab.proposition_2_1complexity-theorynoise-operatorp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquantum-query-complexity
Let and let be symmetric with for all . Write for the row sums and for the largest eigenvalue of . Then
and in particular, if every row sum equals , then .
In the proof of Theorem 3.4 this bounds the norm of the compressed noise operator by its largest row sum .
Formalization Note is the maximum of the real eigenvalues of the Hermitian (= symmetric) real matrix .
Differences from the source:
- encoding: with minima and maxima over →
M : Matrix (Fin N) (Fin N) ℝwith0 < N; reason: min and max over are undefined for ; indices are 0-based - encoding: symmetric; →
M.IsHermitian; theFinset.sup'ofhM.eigenvalues; reason: for a real matrix Hermitian means symmetric, and its eigenvalues are real
Preamble
import Mathlib
Formal statement
namespace QNoiseStab
/-- **Proposition 2.1** (Perron–Frobenius; Beame–Holman–Kornerup, *A Noise Operator Approach to
Quantum Query Complexity and Time-Space Tradeoff Lower Bounds*, arXiv:2609.40334 (version of
2026-11-02, sha256 814fe20e…), p.5). Let `M ∈ ℝ^{N×N}` be symmetric and entrywise nonnegative, and
let `r_i = Σ_j M_ij`. Then `min_i r_i ≤ λ_max(M) ≤ max_i r_i`; in particular, if every row sum
equals `r`, then `λ_max(M) = r`.
**Formalization Note** Symmetry of a real matrix is `M.IsHermitian`; `λ_max(M)` is the largest of
its (real) eigenvalues `hM.eigenvalues`, a `Finset.sup'` over the nonempty index `Fin N`
(`0 < N`, since `min` and `max` over `[N]` are undefined for `N = 0`). Indices are 0-based. -/
theorem proposition_2_1 {N : ℕ} (hN : 0 < N) (M : Matrix (Fin N) (Fin N) ℝ)
(hM : M.IsHermitian) (hnn : ∀ i j, 0 ≤ M i j) :
let hne : (Finset.univ : Finset (Fin N)).Nonempty := ⟨⟨0, hN⟩, Finset.mem_univ _⟩
let r : Fin N → ℝ := fun i => ∑ j, M i j
let lamMax : ℝ := Finset.univ.sup' hne hM.eigenvalues
(Finset.univ.inf' hne r ≤ lamMax ∧ lamMax ≤ Finset.univ.sup' hne r) ∧
∀ c : ℝ, (∀ i, r i = c) → lamMax = c := by sorry
end QNoiseStab
Source
Beame–Holman–Kornerup, A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds, arXiv:2609.40334 (version of 2026-11-02, sha256 814fe20e…), Proposition 2.1, p.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.