op_979_csym_max_nullity_empty_graph
For the edgeless graph (the empty graph bot) on a finite vertex set V, the combinatorially symmetric maximum nullity equals the number of vertices |V|.
Statement
theorem op_979_csym_max_nullity_empty_graph {V : Type*} [Fintype V] [DecidableEq V] : simple_graph_csym_max_nullity (⊥ : SimpleGraph V) = Fintype.card V
- Formalizes
- arXiv:2611.01102 Sec. 6, Example 6.2
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- simple_graph_csym_max_nullityThe combinatorially symmetric maximum nullity N(G) of a finite simple graph G is the supremum of the nullities of all real matrices A…
- is_csym_matrixA real matrix A indexed by V is combinatorially symmetric and associated with the simple graph G if for all i, j in V, A i j is nonzero if…
- Used by 1
- op_979_csym_max_nullity_eq_fort_transversal_number_of_edgelessFor the edgeless graph bot on a finite vertex set V with decidable equality, the combinatorially symmetric maximum nullity equals the fort…
Read back from the Lean
For any type V with finite cardinality and decidable equality, the maximum combinatorially symmetric nullity (simple_graph_csym_max_nullity) of the empty graph (⊥ : SimpleGraph V) equals Fintype.card V.
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
The combinatorially symmetric maximum nullity of the edgeless graph ⊥ is defined as the supremum of the nullities of all matrices whose non-zero entries match the adjacency of ⊥. The zero matrix satisfies this condition vacuously and has nullity equal to |V|, showing that |V| is attained. Since the kernel of any matrix on V is a subspace of the |V|-dimensional space V → ℝ, no matrix can have nullity greater than |V|, so |V| is also an upper bound, making the supremum |V|.
Let S be the set of dimensions of kernels of real matrices that are combinatorially symmetric for the edgeless graph ⊥; the goal is to show sup S = |V|.
Unfolding the definition of simple_graph_csym_max_nullity, the maximum nullity is defined as the supremum of the set S of nullities of all combinatorially symmetric matrices for ⊥.
classical unfold simple_graph_csym_max_nullity set S : Set ℕ := { k : ℕ | ∃ A : Matrix V V ℝ, is_csym_matrix (⊥ : SimpleGraph V) A ∧ Module.finrank ℝ A.mulVecLin.ker = k } with hSdef
|V| is an element of S, witnessed by the zero matrix.
The zero matrix is combinatorially symmetric for the edgeless graph ⊥ because it has no non-zero entries, vacuously matching the absence of edges. The linear map induced by the zero matrix is the zero map (Matrix.mulVecLin_zero), whose kernel is the whole space V → ℝ (LinearMap.ker_zero, finrank_top). The dimension of V → ℝ over ℝ is |V| (Module.finrank_fintype_fun_eq_card), so the nullity of the zero matrix is |V|.
uses
Matrix.mulVecLin_zero,LinearMap.ker_zero,finrank_top,Module.finrank_fintype_fun_eq_cardhave hmem : Fintype.card V ∈ S := by refine ⟨0, ?_, ?_⟩ · exact ⟨fun i j => by simp, fun i j _ => by simp⟩ · rw [Matrix.mulVecLin_zero, LinearMap.ker_zero, finrank_top] exact Module.finrank_fintype_fun_eq_card ℝ
Every element b ∈ S satisfies b ≤ |V|.
Any b ∈ S is the nullity dim(ker A) of some matrix A. Because ker A is a linear subspace of V → ℝ, its dimension is bounded by dim(V → ℝ) (Submodule.finrank_le), which equals |V| (Module.finrank_fintype_fun_eq_card).
uses
Submodule.finrank_le,Module.finrank_fintype_fun_eq_cardhave hle : ∀ b ∈ S, b ≤ Fintype.card V := by rintro b ⟨A, -, hb⟩ rw [← hb] calc Module.finrank ℝ A.mulVecLin.ker ≤ Module.finrank ℝ (V → ℝ) := Submodule.finrank_le _ _ = Fintype.card V := Module.finrank_fintype_fun_eq_card ℝ
The supremum of S is |V|.
Since every element of S is at most |V|, S is bounded above. Because S is non-empty (containing |V|) and bounded above by |V|, sup S ≤ |V| (csSup_le). Conversely, since |V| ∈ S and S is bounded above, |V| ≤ sup S (le_csSup). By antisymmetry (le_antisymm), sup S = |V|.
uses
le_antisymm,csSup_le,le_csSuphave hbdd : BddAbove S := ⟨Fintype.card V, hle⟩ exact le_antisymm (csSup_le ⟨_, hmem⟩ hle) (le_csSup hbdd hmem)
Matrix.mulVecLin_zero- The linear map associated with the zero matrix is the zero linear map.
LinearMap.ker_zero- The kernel of the zero linear map is the top submodule (the entire domain).
finrank_top- The dimension of the top submodule of a module equals the dimension of the whole module.
Module.finrank_fintype_fun_eq_card- The dimension of the function space η → R over R equals the cardinality of the finite index set η.
Submodule.finrank_le- The dimension of any submodule is at most the dimension of the ambient module.
csSup_le- In a conditionally complete lattice, the supremum of a non-empty set is at most any upper bound of that set.
le_csSup- In a conditionally complete lattice, every element of a set bounded above is at most the supremum of the set.
le_antisymm- If a ≤ b and b ≤ a in a partial order, then a = b.
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.
/-- For the edgeless graph on a finite vertex set V, N(⊥) = |V|. -/theorem op_979_csym_max_nullity_empty_graph {V : Type*} [Fintype V] [DecidableEq V] : simple_graph_csym_max_nullity (⊥ : SimpleGraph V) = Fintype.card V := by classical unfold simple_graph_csym_max_nullity set S : Set ℕ := { k : ℕ | ∃ A : Matrix V V ℝ, is_csym_matrix (⊥ : SimpleGraph V) A ∧ Module.finrank ℝ A.mulVecLin.ker = k } with hSdef have hmem : Fintype.card V ∈ S := by refine ⟨0, ?_, ?_⟩ · exact ⟨fun i j => by simp, fun i j _ => by simp⟩ · rw [Matrix.mulVecLin_zero, LinearMap.ker_zero, finrank_top] exact Module.finrank_fintype_fun_eq_card ℝ have hle : ∀ b ∈ S, b ≤ Fintype.card V := by rintro b ⟨A, -, hb⟩ rw [← hb] calc Module.finrank ℝ A.mulVecLin.ker ≤ Module.finrank ℝ (V → ℝ) := Submodule.finrank_le _ _ = Fintype.card V := Module.finrank_fintype_fun_eq_card ℝ have hbdd : BddAbove S := ⟨Fintype.card V, hle⟩ exact le_antisymm (csSup_le ⟨_, hmem⟩ hle) (le_csSup hbdd hmem)