Laplacian matrix factors as (oriented incidence matrix) times its transpose
ProvedClassicalGaps.lapMatrix_eq_orientedIncMatrix_mul_transposedeterminantsgraph-theorymatrix-tree-theoremspanning-trees
For a finite simple graph , the Laplacian matrix equals , where is the oriented (signed) incidence matrix of obtained from an arbitrary vertex ordering. This is the standard algebraic bridge used in the proof of Kirchhoff's matrix-tree theorem: it lets a cofactor of be computed via the Cauchy-Binet formula applied to . It is a child lemma of ClassicalGaps.kirchhoff_matrix_tree.
Formalization Note: fills the gap noted in Mathlib's SimpleGraph.IncMatrix TODO ('Define the graph Laplacian of a simple graph using the oriented incidence matrix from an arbitrary orientation'), using the newly published Definitions.Def_ClassicalGaps_orientedIncMatrix.
Preamble
import Mathlib import Definitions.Def_ClassicalGaps_orientedIncMatrix open Classical Matrix
Formal statement
namespace ClassicalGaps
theorem lapMatrix_eq_orientedIncMatrix_mul_transpose {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) [DecidableRel G.Adj] :
G.lapMatrix ℝ = orientedIncMatrix G * (orientedIncMatrix G)ᵀ := by sorry
end ClassicalGaps