§3, proof of Theorem 3.1, p. 10 — x_k is the unit vector along (AᵀA)^{k−1}Aᵀz and y_k the unit vector along (AAᵀ)^k z
ProvedKleinbergHITS.Conv.iterate_closed_formLet be the adjacency matrix of a directed graph on pages, , and let be the output of the procedure Iterate: , and for , , , and , are , normalized so that their squares sum to . Write for the unit vector in the direction of . Then for every ,
This identifies Kleinberg's iterates with normalized power iterates of the symmetric matrices and , which is what allows the convergence theory of the power method to be applied.
Formalization Note The identity holds for every graph, with no use of Assumption (†). "The unit vector in the direction of " is the mission's normalize w, which returns when ; both sides then vanish together, so the statement does not rely on that convention to be true, but it is part of its meaning when an iterate is . The restriction is needed: at the iterate is , not the unit vector along .
import Mathlib import Definitions.Def_KleinbergHITS_Conv_Setting
namespace KleinbergHITS.Conv
open Matrix
/-- Kleinberg (1999), §3, proof of Theorem 3.1, p. 10: "Thus x_k is the unit vector in the direction
of (AᵀA)^{k−1}Aᵀz, and y_k is the unit vector in the direction of (AAᵀ)^k z." Stated for `k ≥ 1`. -/
theorem iterate_closed_form {n : ℕ} (E : Fin n → Fin n → Prop) [DecidableRel E] :
∀ k : ℕ, 1 ≤ k →
(hitsIter E k).1 =
normalize ((((adjMatrix E)ᵀ * adjMatrix E) ^ (k - 1)) *ᵥ ((adjMatrix E)ᵀ *ᵥ allOnes n)) ∧
(hitsIter E k).2 = normalize (((adjMatrix E * (adjMatrix E)ᵀ) ^ k) *ᵥ allOnes n) := by sorry
end KleinbergHITS.Conv
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.