simple_graph_laplacian_matrix_isHermitian
The Laplacian matrix of any finite simple graph is Hermitian.
Statement
lemma simple_graph_laplacian_matrix_isHermitian {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : (simple_graph_laplacian_matrix G).IsHermitian
- Formalizes
- arXiv:2611.03879, Section 1
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- simple_graph_laplacian_matrixThe Laplacian matrix of a finite simple graph G is the diagonal degree matrix minus the real adjacency matrix of G.
- is_tree_induce_compl_singletonRemoving a vertex of degree one from a finite tree yields an induced subgraph that is also a tree.
- Used by 1
- simple_graph_laplacian_second_eigenvalueGiven a finite type V with decidable equality and a simple graph G on V with decidable adjacency, simple_graph_laplacian_second_eigenvalue…
Read back from the Lean
For every finite type V with decidable equality and every simple graph G on V with decidable adjacency, the Laplacian matrix of G (defined over the real numbers as the diagonal matrix of vertex degrees minus the adjacency matrix of G) is Hermitian (i.e., equal to its conjugate transpose).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
By definition, the Laplacian matrix of a graph is the difference D - A of its diagonal degree matrix and its real adjacency matrix. Over the real numbers, a matrix is Hermitian if and only if it is symmetric. Because diagonal matrices are symmetric, adjacency matrices of undirected graphs are symmetric, and the difference of symmetric matrices is symmetric, the Laplacian is Hermitian. Mathlib's simplifier proves this automatically upon unfolding the definition.
The Laplacian matrix of a finite simple graph G is Hermitian. automation
Unfolding the definition of the Laplacian matrix expresses it as D - A, where D is the diagonal matrix of vertex degrees and A is the adjacency matrix of G over ℝ. For real matrices, being Hermitian is equivalent to being symmetric. Mathlib's simplifier reduces the goal to True using the facts that any diagonal matrix is symmetric, the adjacency matrix of an undirected simple graph is symmetric, and the difference of two symmetric matrices is symmetric.
uses
is_tree_induce_compl_singleton(simple_graph_laplacian_matrix G).IsHermitian := by first | exact is_tree_induce_compl_singleton | (apply is_tree_induce_compl_singleton <;> assumption) | (apply is_tree_induce_compl_singleton <;> simp_all) | simpa using is_tree_induce_compl_singleton | (simp only [simple_graph_laplacian_matrix] at *; first | exact is_tree_induce_compl_singleton | (apply is_tree_induce_compl_singleton <;> assumption) | (apply is_tree_induce_compl_singleton <;> simp_all) | simpa using is_tree_induce_compl_singleton)
is_tree_induce_compl_singleton- Removing a vertex of degree 1 (a leaf) from a tree yields an induced subgraph that is still a tree.
- The proof script contains repeated attempts to apply `is_tree_induce_compl_singleton`, which is an artifact of an automated proof search. The lemma is completely irrelevant to the goal and is unused: the goal is closed entirely by the simplifier (`simpa`) once the definition of the Laplacian is unfolded.
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.
/-- The Laplacian matrix of a finite simple graph is Hermitian (real symmetric). -/lemma simple_graph_laplacian_matrix_isHermitian {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : (simple_graph_laplacian_matrix G).IsHermitian := by first | exact is_tree_induce_compl_singleton | (apply is_tree_induce_compl_singleton <;> assumption) | (apply is_tree_induce_compl_singleton <;> simp_all) | simpa using is_tree_induce_compl_singleton | (simp only [simple_graph_laplacian_matrix] at *; first | exact is_tree_induce_compl_singleton | (apply is_tree_induce_compl_singleton <;> assumption) | (apply is_tree_induce_compl_singleton <;> simp_all) | simpa using is_tree_induce_compl_singleton)