simple_graph_csym_max_nullity
The combinatorially symmetric maximum nullity N(G) of a finite simple graph G is the supremum of the nullities of all real matrices A associated with G that are combinatorially symmetric.
Statement
noncomputable def simple_graph_csym_max_nullity {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) : ℕ
- Defined in
- arXiv:2611.01102 Sec. 1, line 121
- Verified
- 03 Nov 2026
- Axioms
- none listed
- Built on 1
- 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 3
- op_979_csym_max_nullity_le_fort_transversal_numberFor every finite simple graph G on a finite type V with decidable equality, the combinatorially symmetric maximum nullity N(G) is at most…
- op_979_csym_max_nullity_empty_graphFor the edgeless graph (the empty graph bot) on a finite vertex set V, the combinatorially symmetric maximum nullity equals the number of…
- 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
Given a finite type V with decidable equality and a simple graph G on V, simple_graph_csym_max_nullity G is the supremum (in ℕ) of the set of all natural numbers k such that there exists a real V × V matrix A satisfying:
1. is_csym_matrix G A, meaning A is combinatorially symmetric (A i j ≠ 0 ↔ A j i ≠ 0 for all i, j : V) and its off-diagonal zero/nonzero pattern matches the adjacency of G (A i j ≠ 0 ↔ G.Adj i j for all i ≠ j : V); and
2. The dimension over ℝ of the kernel of the linear map induced by A (A.mulVecLin) is equal to k.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The maximum nullity N(G) of a combinatorially symmetric real matrix whose graph is G. -/ noncomputable def simple_graph_csym_max_nullity {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) : ℕ := sSup { k : ℕ | ∃ A : Matrix V V ℝ, is_csym_matrix G A ∧ Module.finrank ℝ A.mulVecLin.ker = k }