Prove2Me
Navigate
DiscoverFormalpediaBlogsUsersMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Convergence of the rescaled power iterates

Proved
PowerMethod.rescaled_iterate_tendsto

by Elsie66 · Sep 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

linearalgebranumericalanalysis

If lambda_{i0} is strictly dominant in absolute value over every other eigenvalue, lambda_{i0} != 0, and x0 has nonzero i0-component, then lambda_{i0}^{-k} T^k x0 -> c_{i0} e_{i0} as k -> infinity.

Formal statement
import Mathlib

namespace PowerMethod

/-- **Convergence of the rescaled power iterates.** Let `T` be self-adjoint on a finite-dimensional
inner product space `E`, with eigenvalue `hT.eigenvalues hn i0` strictly dominant in absolute value
over every other eigenvalue, and let `x0` have a nonzero component along the corresponding
eigenvector. Then the iterates `T^k x0`, rescaled by `(eigenvalues i0)^k`, converge to the
projection of `x0` onto the dominant eigenspace. -/
theorem rescaled_iterate_tendsto
    {𝕜 : Type*} [RCLike 𝕜] {E : Type*} [NormedAddCommGroup E] [InnerProductSpace 𝕜 E]
    [FiniteDimensional 𝕜 E] {T : E →ₗ[𝕜] E} (hT : T.IsSymmetric) {n : ℕ}
    (hn : Module.finrank 𝕜 E = n) (x0 : E) (i0 : Fin n)
    (hdom : ∀ j, j ≠ i0 → |hT.eigenvalues hn j| < |hT.eigenvalues hn i0|)
    (hne0 : hT.eigenvalues hn i0 ≠ 0)
    (hx0 : (hT.eigenvectorBasis hn).repr x0 i0 ≠ 0) :
    Filter.Tendsto
      (fun k => ((hT.eigenvalues hn i0 : 𝕜) ^ k)⁻¹ • (T ^ k) x0)
      Filter.atTop
      (nhds (((hT.eigenvectorBasis hn).repr x0 i0) • hT.eigenvectorBasis hn i0)) := by
  sorry

end PowerMethod
Source
L. N. Trefethen and D. Bau III, Numerical Linear Algebra, SIAM, 1997, Lecture 27.
Read-back

What the Lean code literally says, in plain math · claude-sonnet-5

The declaration states a convergence claim about iterating a self-adjoint linear operator, phrased as follows. Fix a scalar field k\mathbb{k}k that is either R\mathbb{R}R or C\mathbb{C}C (an instance of the RCLike class), and a finite-dimensional inner product space EEE over k\mathbb{k}k; let T:E→ET:E\to ET:E→E be a linear map that is self-adjoint (symmetric) with respect to the inner product. Let n∈Nn\in\mathbb{N}n∈N be given together with a hypothesis identifying it with dim⁡kE\dim_{\mathbb{k}}Edimk​E. Since TTT is self-adjoint on this finite-dimensional space, it comes with an associated list of nnn real eigenvalues λ0,…,λn−1\lambda_0,\dots,\lambda_{n-1}λ0​,…,λn−1​ (indexed by jjj ranging over {0,…,n−1}\{0,\dots,n-1\}{0,…,n−1}) and an associated orthonormal basis e0,…,en−1e_0,\dots,e_{n-1}e0​,…,en−1​ of EEE with Tej=λjejTe_j=\lambda_j e_jTej​=λj​ej​ for each jjj; these are fixed data determined by TTT and by the chosen identification of dim⁡kE\dim_{\mathbb k}Edimk​E with nnn, not further hypotheses. An arbitrary vector x0∈Ex_0\in Ex0​∈E is fixed, and so is a distinguished index i0∈{0,…,n−1}i_0\in\{0,\dots,n-1\}i0​∈{0,…,n−1} — note that supplying such an index forces n≥1n\ge 1n≥1. Three hypotheses are imposed: (a) for every index j≠i0j\ne i_0j=i0​ in {0,…,n−1}\{0,\dots,n-1\}{0,…,n−1}, ∣λj∣<∣λi0∣|\lambda_j|<|\lambda_{i_0}|∣λj​∣<∣λi0​​∣, i.e. the eigenvalue at index i0i_0i0​ strictly exceeds in absolute value every other eigenvalue on the list (so no other index attains the same absolute value, and this condition is vacuously true when n=1n=1n=1, since then there is no j≠i0j\ne i_0j=i0​); (b) λi0≠0\lambda_{i_0}\ne 0λi0​​=0, stated as its own hypothesis even though, whenever n≥2n\ge2n≥2, it already follows from (a); and (c), writing x0=∑j=0n−1cjejx_0=\sum_{j=0}^{n-1}c_j e_jx0​=∑j=0n−1​cj​ej​ for the unique coordinates cj∈kc_j\in\mathbb{k}cj​∈k of x0x_0x0​ with respect to the basis (ej)(e_j)(ej​), that ci0≠0c_{i_0}\ne0ci0​​=0. Given all of this, the conclusion asserts that the sequence of vectors (λi0k)−1⋅(Tkx0)∈E\big(\lambda_{i_0}^{k}\big)^{-1}\cdot\big(T^{k}x_0\big)\in E(λi0​k​)−1⋅(Tkx0​)∈E, indexed by k∈Nk\in\mathbb{N}k∈N and tending toward k→∞k\to\inftyk→∞ (with respect to the atTop filter on N\mathbb{N}N and the norm-induced topology on EEE), converges to the fixed vector ci0⋅ei0c_{i_0}\cdot e_{i_0}ci0​​⋅ei0​​; here Tkx0T^kx_0Tkx0​ means TTT applied kkk times to x0x_0x0​, λi0k\lambda_{i_0}^kλi0​k​ is regarded as an element of k\mathbb{k}k via the canonical real-to-k\mathbb{k}k cast, its inverse is the field inverse in k\mathbb{k}k (which, because λi0≠0\lambda_{i_0}\ne0λi0​​=0 and hence λi0k≠0\lambda_{i_0}^k\ne0λi0​k​=0 for every kkk, is always the genuine multiplicative inverse and never invokes the field's convention 0−1=00^{-1}=00−1=0), and both "⋅\cdot⋅" symbols denote scalar multiplication of a vector of EEE by a scalar in k\mathbb{k}k. As given, this theorem's proof term is sorry, so no proof of this claim is supplied in the code shown.

Human review
  • Endorsed by Shuze Chen · Sep 8, 2026

  • Endorsed by Elsie66 · Sep 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactJoin Slack© 2026 Prove2Me