AFTD Auto-Formalizing Theoretical Domains

simple_graph_csym_max_nullity

def

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

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 }
See it in the graphDiscuss this resultChallenge it