Spectral toolkit: real symmetric matrices and the random walk on a regular graph #
The eigenbasis on plain vectors. For a real symmetric matrix A on a finite type V,
Mathlib's orthonormal eigenbasis bₖ = hA.eigenvectorBasis k (eigenvalues μₖ = hA.eigenvalues k)
lives in EuclideanSpace ℝ V. Here its vectors are read as plain functions V → ℝ with the dot
product ⬝ᵥ:
- orthonormality
bₖ ⬝ bₗ = δₖₗ(eigenvectorBasis_dotProduct), the expansiony = ∑ₖ (bₖ ⬝ y) bₖ(sum_dotProduct_smul_eigenvectorBasis) and Parsevaly ⬝ z = ∑ₖ (bₖ ⬝ y)(bₖ ⬝ z)(dotProduct_eq_sum_eigenvectorBasis); - the coefficients of
Aᵗ z:bₖ ⬝ (Aᵗ z) = μₖᵗ (bₖ ⬝ z)(eigenvectorBasis_dotProduct_mulVec,eigenvectorBasis_dotProduct_pow_mulVec) and the spectral expansion of the bilinear formy ⬝ A z = ∑ₖ μₖ (bₖ ⬝ y)(bₖ ⬝ z)(dotProduct_mulVec_eq_sum_eigenvectorBasis); - orthogonality to eigenvectors of other eigenvalues
(
eigenvectorBasis_dotProduct_eq_zero_of_mulVec_eq_smul) and the spectral bound for powers‖Aᵗ y‖² ≤ λ²ᵗ ‖y‖²whenyhas no component along eigenvectors with|μ| > λ(pow_mulVec_dotProduct_self_le).
The random walk on a d-regular graph. transitionMatrix G d = A / d, its eigenvalues
λ₁ ≥ λ₂ ≥ ⋯ ≥ λₙ in non-increasing order (walkEigenvalues, read off Mathlib's sorted
Matrix.IsHermitian.eigenvalues₀) and λ_G = max {λ₂, |λₙ|} (lambdaG). Every eigenvalue other
than the top one has |μ| ≤ λ_G (abs_eigenvalues_le_lambdaG), and when λ_G < 1 the top
eigenvector is the constant vector ±1/√n with eigenvalue 1 (exists_top_eigenvectorBasis).
The indicator vector 1_S of a set of vertices is indVec S.
The eigenbasis of a real symmetric matrix, on plain vectors #
Orthonormality of the eigenbasis: bₖ ⬝ bₗ = δₖₗ.
Expansion of a vector in the orthonormal eigenbasis: y = ∑ₖ (bₖ ⬝ y) bₖ.
Parseval: y ⬝ z = ∑ₖ (bₖ ⬝ y)(bₖ ⬝ z).
The coefficients of A z: bₖ ⬝ (A z) = μₖ (bₖ ⬝ z).
The eigenvectors of A are eigenvectors of Aᵗ: Aᵗ bₖ = μₖᵗ bₖ.
The coefficients of Aᵗ z: bₖ ⬝ (Aᵗ z) = μₖᵗ (bₖ ⬝ z).
Spectral expansion of the bilinear form: y ⬝ A z = ∑ₖ μₖ (bₖ ⬝ y)(bₖ ⬝ z).
Eigenvectors for distinct eigenvalues of a symmetric matrix are orthogonal: if A u = c u
and μₖ ≠ c, then bₖ ⬝ u = 0.
Spectral bound for powers. If y has no component along the eigenvectors whose
eigenvalue exceeds λ in absolute value, then ‖Aᵗ y‖² ≤ λ²ᵗ ‖y‖².
The random walk on a regular graph #
The transition matrix P = A / d of the random walk on a d-regular graph with adjacency
matrix A.
Equations
- Dynamics.transitionMatrix G d = (↑d)⁻¹ • SimpleGraph.adjMatrix ℝ G
Instances For
P = A / d is real symmetric.
The eigenvalues λ₁ ≥ λ₂ ≥ ⋯ ≥ λₙ of the transition matrix, in non-increasing order
(Matrix.IsHermitian.eigenvalues₀_antitone), indexed from 0.
Equations
Instances For
λ_G = max {λ₂, |λₙ|} (set to 0 on graphs with fewer than two vertices). Since
λₙ ≤ λ₂, it is the largest absolute value max_{i ≥ 2} |λᵢ| of the eigenvalues other than
the top one.
Equations
- Dynamics.lambdaG G d = if h : 2 ≤ Fintype.card V then max (Dynamics.walkEigenvalues G d ⟨1, ⋯⟩) |Dynamics.walkEigenvalues G d ⟨Fintype.card V - 1, ⋯⟩| else 0
Instances For
λ_G ≥ 0.
P 1 = 1 on a d-regular graph, d > 0: the transition matrix is stochastic.
Every eigenvalue of P other than the top one (index 0 in the sorted order) has absolute
value at most λ_G.
The top eigenvector. On a d-regular graph with d > 0 and λ_G < 1, the eigenvector
b_{k₀} at the top of the sorted spectrum of P has eigenvalue 1, every other eigenvalue has
absolute value at most λ_G, and b_{k₀} = ±1/√n is constant, so that its coefficients satisfy
(b_{k₀} ⬝ y)(b_{k₀} ⬝ z) = (∑ y)(∑ z) / n. Proof: P 1 = 1, and every other eigenvector has an
eigenvalue ≤ λ_G < 1, hence is orthogonal to 1; Parseval does the rest.
Indicator vectors #
The indicator vector 1_S of a set of vertices.
Instances For
∑ᵥ 1_S(v) = |S|.