AFTD Auto-Formalizing Theoretical Domains

simple_graph_adj_eigenvalues_sorted_antitone

theoremverified

The sorted adjacency eigenvalues of a finite simple graph are nonincreasing in the index.

Statement

theorem simple_graph_adj_eigenvalues_sorted_antitone {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) : Antitone (simple_graph_adj_eigenvalues_sorted G)
Source
sanity lemma for simple_graph_adj_eigenvalues_sorted (OP-546)
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • simple_graph_adj_eigenvalues_sortedFor a type V with [Fintype V] and [DecidableEq V] (implicit V) and a simple graph G : SimpleGraph V, simple_graph_adj_eigenvalues_sorted G…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

The proof, explained

The theorem states that the sorted adjacency eigenvalues of a finite simple graph form an antitone (nonincreasing) sequence. The proof proceeds in one move: by definition, the sorted eigenvalues are given by `eigenvalues₀` applied to the graph's real adjacency matrix. Because the adjacency matrix of a simple graph is Hermitian, the result is an immediate application of `Matrix.IsHermitian.eigenvalues₀_antitone`.

  1. The sequence of sorted eigenvalues of the graph's adjacency matrix is antitone.

    Unfolding `simple_graph_adj_eigenvalues_sorted` shows that the graph's sorted eigenvalues are defined as the sequence `eigenvalues₀` of its real adjacency matrix. Since the adjacency matrix of a simple graph is Hermitian, the lemma `Matrix.IsHermitian.eigenvalues₀_antitone` immediately proves that this sequence is antitone (monotonically nonincreasing).

    lines 3–4

    uses Matrix.IsHermitian.eigenvalues₀_antitone

      unfold simple_graph_adj_eigenvalues_sorted
      exact Matrix.IsHermitian.eigenvalues₀_antitone _
Matrix.IsHermitian.eigenvalues₀_antitone
For any Hermitian matrix over an RCLike field (such as ℝ), its sequence of eigenvalues `eigenvalues₀` is antitone, meaning nonincreasing in the index.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem simple_graph_adj_eigenvalues_sorted_antitone {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) : Antitone (simple_graph_adj_eigenvalues_sorted G) := by  unfold simple_graph_adj_eigenvalues_sorted  exact Matrix.IsHermitian.eigenvalues₀_antitone _
See it in the graphDiscuss this resultChallenge it