Documentation

Dynamics.Spectral

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 ⬝ᵥ:

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 #

theorem Dynamics.pow_mulVec_of_mulVec_eq_smul {V : Type u_1} [Fintype V] [DecidableEq V] {M : Matrix V V ℝ} {u : V → ℝ} {c : ℝ} (hu : M.mulVec u = c • u) (t : ℕ) :
(M ^ t).mulVec u = c ^ t • u

An eigenvector of M is an eigenvector of every power Mᵗ.

theorem Dynamics.eigenvectorBasis_dotProduct {V : Type u_1} [Fintype V] [DecidableEq V] {A : Matrix V V ℝ} (hA : A.IsHermitian) (k l : V) :

Orthonormality of the eigenbasis: bₖ ⬝ bₗ = δₖₗ.

theorem Dynamics.sum_dotProduct_smul_eigenvectorBasis {V : Type u_1} [Fintype V] [DecidableEq V] {A : Matrix V V ℝ} (hA : A.IsHermitian) (y : V → ℝ) :
∑ k : V, ((hA.eigenvectorBasis k).ofLp ⬝ᵥ y) • (hA.eigenvectorBasis k).ofLp = y

Expansion of a vector in the orthonormal eigenbasis: y = ∑ₖ (bₖ ⬝ y) bₖ.

theorem Dynamics.dotProduct_eq_sum_eigenvectorBasis {V : Type u_1} [Fintype V] [DecidableEq V] {A : Matrix V V ℝ} (hA : A.IsHermitian) (y z : V → ℝ) :
y ⬝ᵥ z = ∑ k : V, (hA.eigenvectorBasis k).ofLp ⬝ᵥ y * (hA.eigenvectorBasis k).ofLp ⬝ᵥ z

Parseval: y ⬝ z = ∑ₖ (bₖ ⬝ y)(bₖ ⬝ z).

theorem Dynamics.eigenvectorBasis_dotProduct_mulVec {V : Type u_1} [Fintype V] [DecidableEq V] {A : Matrix V V ℝ} (hA : A.IsHermitian) (k : V) (z : V → ℝ) :

The coefficients of A z: bₖ ⬝ (A z) = μₖ (bₖ ⬝ z).

theorem Dynamics.pow_mulVec_eigenvectorBasis {V : Type u_1} [Fintype V] [DecidableEq V] {A : Matrix V V ℝ} (hA : A.IsHermitian) (t : ℕ) (k : V) :

The eigenvectors of A are eigenvectors of Aᵗ: Aᵗ bₖ = μₖᵗ bₖ.

theorem Dynamics.eigenvectorBasis_dotProduct_pow_mulVec {V : Type u_1} [Fintype V] [DecidableEq V] {A : Matrix V V ℝ} (hA : A.IsHermitian) (t : ℕ) (k : V) (z : V → ℝ) :

The coefficients of Aᵗ z: bₖ ⬝ (Aᵗ z) = μₖᵗ (bₖ ⬝ z).

theorem Dynamics.dotProduct_mulVec_eq_sum_eigenvectorBasis {V : Type u_1} [Fintype V] [DecidableEq V] {A : Matrix V V ℝ} (hA : A.IsHermitian) (y z : V → ℝ) :
y ⬝ᵥ A.mulVec z = ∑ k : V, hA.eigenvalues k * ((hA.eigenvectorBasis k).ofLp ⬝ᵥ y * (hA.eigenvectorBasis k).ofLp ⬝ᵥ z)

Spectral expansion of the bilinear form: y ⬝ A z = ∑ₖ μₖ (bₖ ⬝ y)(bₖ ⬝ z).

theorem Dynamics.eigenvectorBasis_dotProduct_eq_zero_of_mulVec_eq_smul {V : Type u_1} [Fintype V] [DecidableEq V] {A : Matrix V V ℝ} (hA : A.IsHermitian) {u : V → ℝ} {c : ℝ} (hu : A.mulVec u = c • u) {k : V} (hk : hA.eigenvalues k ≠ c) :

Eigenvectors for distinct eigenvalues of a symmetric matrix are orthogonal: if A u = c u and μₖ ≠ c, then bₖ ⬝ u = 0.

theorem Dynamics.pow_mulVec_dotProduct_self_le {V : Type u_1} [Fintype V] [DecidableEq V] {A : Matrix V V ℝ} (hA : A.IsHermitian) {lam : ℝ} {y : V → ℝ} (hy : ∀ (k : V), lam < |hA.eigenvalues k| → (hA.eigenvectorBasis k).ofLp ⬝ᵥ y = 0) (t : ℕ) :
(A ^ t).mulVec y ⬝ᵥ (A ^ t).mulVec y ≤ (lam ^ t) ^ 2 * y ⬝ᵥ y

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 #

noncomputable def Dynamics.transitionMatrix {V : Type u_1} (G : SimpleGraph V) [DecidableRel G.Adj] (d : ℕ) :

The transition matrix P = A / d of the random walk on a d-regular graph with adjacency matrix A.

Equations
Instances For

    P = A / d is real symmetric.

    noncomputable def Dynamics.walkEigenvalues {V : Type u_1} (G : SimpleGraph V) [DecidableRel G.Adj] [Fintype V] [DecidableEq V] (d : ℕ) :

    The eigenvalues λ₁ ≥ λ₂ ≥ ⋯ ≥ λₙ of the transition matrix, in non-increasing order (Matrix.IsHermitian.eigenvalues₀_antitone), indexed from 0.

    Equations
    Instances For
      noncomputable def Dynamics.lambdaG {V : Type u_1} (G : SimpleGraph V) [DecidableRel G.Adj] [Fintype V] [DecidableEq V] (d : ℕ) :

      λ_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
      Instances For
        theorem Dynamics.lambdaG_nonneg {V : Type u_1} (G : SimpleGraph V) [DecidableRel G.Adj] [Fintype V] [DecidableEq V] (d : ℕ) :
        0 ≤ lambdaG G d

        λ_G ≥ 0.

        theorem Dynamics.transitionMatrix_mulVec_one {V : Type u_1} (G : SimpleGraph V) [DecidableRel G.Adj] [Fintype V] {d : ℕ} (hd : 0 < d) (hreg : G.IsRegularOfDegree d) :

        P 1 = 1 on a d-regular graph, d > 0: the transition matrix is stochastic.

        theorem Dynamics.abs_eigenvalues_le_lambdaG {V : Type u_1} (G : SimpleGraph V) [DecidableRel G.Adj] [Fintype V] [DecidableEq V] (d : ℕ) (k : V) (hk : (Fintype.equivOfCardEq ⋯).symm k ≠ ⟨0, ⋯⟩) :

        Every eigenvalue of P other than the top one (index 0 in the sorted order) has absolute value at most λ_G.

        theorem Dynamics.exists_top_eigenvectorBasis {V : Type u_1} (G : SimpleGraph V) [DecidableRel G.Adj] [Fintype V] [DecidableEq V] [Nonempty V] {d : ℕ} (hd : 0 < d) (hreg : G.IsRegularOfDegree d) (hL : lambdaG G d < 1) :
        ∃ (k₀ : V), ⋯.eigenvalues k₀ = 1 ∧ (∀ (k : V), k ≠ k₀ → |⋯.eigenvalues k| ≤ lambdaG G d) ∧ ∀ (y z : V → ℝ), (⋯.eigenvectorBasis k₀).ofLp ⬝ᵥ y * (⋯.eigenvectorBasis k₀).ofLp ⬝ᵥ z = ((∑ v : V, y v) * ∑ v : V, z v) / ↑(Fintype.card V)

        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 #

        def Dynamics.indVec {V : Type u_1} [DecidableEq V] (S : Finset V) :
        V → ℝ

        The indicator vector 1_S of a set of vertices.

        Equations
        Instances For

          1_S ⬝ 1_S = |S|.

          theorem Dynamics.sum_indVec {V : Type u_1} [Fintype V] [DecidableEq V] (S : Finset V) :
          ∑ v : V, indVec S v = ↑S.card

          ∑ᵥ 1_S(v) = |S|.