§3, proof of Theorem 3.1, p. 11 — z is not orthogonal to ω₁(AAᵀ)
ProvedKleinbergHITS.Conv.allOnes_not_orthogonal_AAthitsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1principal-eigenvector
Let be the adjacency matrix of a directed graph on pages and . Suppose satisfies Assumption (†). Then for every principal eigenvector of ,
Together with the power-iteration milestone and the closed form of , this gives the convergence of the hub weights .
Formalization Note "Not orthogonal to " is stated for every unit vector spanning the principal eigenspace; under (†) there are exactly two, , so this is the same condition. Only (†) for is assumed; (†) for , a standing assumption of the paper, is dropped because it is not needed, which makes the statement stronger.
Preamble
import Mathlib import Definitions.Def_KleinbergHITS_Conv_Setting
Formal statement
namespace KleinbergHITS.Conv
open Matrix
/-- Kleinberg (1999), §3, proof of Theorem 3.1, p. 11: "z is not orthogonal to ω₁(AAᵀ)", under
Assumption (†) for `AAᵀ`. -/
theorem allOnes_not_orthogonal_AAt {n : ℕ} (E : Fin n → Fin n → Prop) [DecidableRel E]
(hAAt : Dagger (adjMatrix E * (adjMatrix E)ᵀ)) :
∀ ω, IsPrincipalEigenvector (adjMatrix E * (adjMatrix E)ᵀ) ω → allOnes n ⬝ᵥ ω ≠ 0 := by sorry
end KleinbergHITS.Conv
Source
Kleinberg, Authoritative sources in a hyperlinked environment, J. ACM 46(5) (1999), author's copy, p. 11, §3, proof of Theorem 3.1, third paragraph ("Consequently, z is not orthogonal to ω₁(AAᵀ)")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.