simple_graph_adj_eigenvalues_sorted_antitone
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
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`.
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).
uses
Matrix.IsHermitian.eigenvalues₀_antitoneunfold 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.
- In Lean, `Antitone` means order-reversing ($i \le j \implies f(i) \ge f(j)$), which formalizes the standard convention of listing eigenvalues in descending (nonincreasing) order.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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 _