op_979_csym_max_nullity_le_fort_transversal_number
For every finite simple graph G on a finite type V with decidable equality, the combinatorially symmetric maximum nullity N(G) is at most the fort transversal number T(G).
Statement
theorem op_979_csym_max_nullity_le_fort_transversal_number {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) : simple_graph_csym_max_nullity G ≤ simple_graph_fort_transversal_number G
- Formalizes
- arXiv:2611.01102 Sec. 2, Theorem 2.10
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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…
- simple_graph_fort_transversal_numberThe fort transversal number T(G) of a finite simple graph G on a finite type V with decidable equality is the supremum of the transversal…
- 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…
- is_compatible_collectionFor an arbitrary type V with decidable equality, a finite collection C of finite subsets of V (C : Finset (Finset V)) is compatible if for…
- simple_graph_is_fortFor a simple graph G on an arbitrary type V, a subset F of V is a fort if F is nonempty and for every vertex v not in F, it is not the…
- finset_transversal_numberThe transversal number of a collection C of subsets of a finite set V is the minimum cardinality of a subset T of V that intersects every…
Read back from the Lean
For every finite type $V$ with decidable equality and every simple graph $G$ on $V$, the combinatorially symmetric maximum nullity of $G$ (simple_graph_csym_max_nullity G) is less than or equal to the fort transversal number of $G$ (simple_graph_fort_transversal_number G).
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
To bound the combinatorially symmetric maximum nullity N(G) by the fort transversal number T(G), the proof associates with any combinatorially symmetric matrix A the collection of supports of non-zero vectors in its kernel. It shows that each such support is a fort of G and that the collection of all kernel supports is compatible, satisfying the circuit elimination axiom via linear combinations. A transversal T of this collection forces the coordinate restriction map on ker(A) to be injective, which bounds dim ker(A) by |T| and consequently by the fort transversal number T(G). Taking the supremum over all combinatorially symmetric matrices yields N(G) ≤ T(G).
A vertex belongs to the support of a vector if and only if the vector is non-zero at that vertex, and the support is nonempty if and only if the vector is non-zero.
By definition, the support consists of the vertices where the vector takes non-zero values. The support is empty exactly when the vector vanishes everywhere, which is equivalent to being the zero vector; thus, the support is nonempty precisely when the vector is non-zero.
uses
Finset.filter_eq_empty_iff,funext_iff,Finset.nonempty_iff_ne_empty,not_iff_not,op_979_csym_max_nullity_le_fort_transversal_number_vec_supp_eq_empty_ifflemma op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff {V : Type*} [Fintype V] {x : V → ℝ} {v : V} : v ∈ op_979_csym_max_nullity_le_fort_transversal_number_vec_supp x ↔ x v ≠ 0 := by simp [op_979_csym_max_nullity_le_fort_transversal_number_vec_supp] open Classical in lemma op_979_csym_max_nullity_le_fort_transversal_number_vec_supp_eq_empty_iff {V : Type*} [Fintype V] {x : V → ℝ} : op_979_csym_max_nullity_le_fort_transversal_number_vec_supp x = ∅ ↔ x = 0 := by simp [op_979_csym_max_nullity_le_fort_transversal_number_vec_supp, Finset.filter_eq_empty_iff, funext_iff] open Classical in lemma op_979_csym_max_nullity_le_fort_transversal_number_vec_supp_nonempty_iff {V : Type*} [Fintype V] {x : V → ℝ} : (op_979_csym_max_nullity_le_fort_transversal_number_vec_supp x).Nonempty ↔ x ≠ 0 := by rw [Finset.nonempty_iff_ne_empty, not_iff_not, op_979_csym_max_nullity_le_fort_transversal_number_vec_supp_eq_empty_iff]
The support of any non-zero vector in the kernel of a matrix is nonempty.
Any set in the collection of kernel supports of a matrix is by definition the support of some non-zero kernel vector x. Because x ≠ 0, its support is nonempty by the characterization of vector supports.
uses
Finset.mem_filter,Finset.coe_nonempty,op_979_csym_max_nullity_le_fort_transversal_number_vec_supp_nonempty_ifflemma op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports_is_fort {V : Type*} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {A : Matrix V V ℝ} (hA : is_csym_matrix G A) {s : Finset V} (hs : s ∈ op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports A) : simple_graph_is_fort G (s : Set V) := by rw [op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports, Finset.mem_filter] at hs rcases hs.2 with ⟨x, hx_ker, hx_ne, rfl⟩ rw [simple_graph_is_fort] refine ⟨?_, ?_⟩ · rw [Finset.coe_nonempty, op_979_csym_max_nullity_le_fort_transversal_number_vec_supp_nonempty_iff] exact hx_ne
The support of any non-zero vector in the kernel of a combinatorially symmetric matrix is a fort.
Suppose for contradiction that some vertex v outside the support s = supp(x) has a unique neighbor u in s. Since x ∈ ker(A), the v-th entry of Ax is the sum over w of A(v, w) * x(w), which equals 0. For any w ≠ u, if x(w) = 0 the term vanishes, and if x(w) ≠ 0 then w ∈ s, so w is not adjacent to v by uniqueness of u; by combinatorial symmetry, A(v, w) = 0. Therefore all terms except w = u vanish, leaving A(v, u) * x(u) = 0. But u is adjacent to v so A(v, u) ≠ 0, and u ∈ s so x(u) ≠ 0, which contradicts their product being zero.
uses
Finset.mem_coe,op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff,not_not,LinearMap.mem_ker,mul_zero,zero_mul,Finset.sum_eq_single,False.elim,Finset.mem_univ,mul_ne_zero· intro v hv rw [Finset.mem_coe, op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff, not_not] at hv rintro ⟨u, ⟨hu_s, hu_adj⟩, hu_uniq⟩ rw [Finset.mem_coe, op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff] at hu_s have hx_ker_v : (A.mulVecLin x) v = 0 := by have : x ∈ LinearMap.ker A.mulVecLin := hx_ker rw [LinearMap.mem_ker] at this rw [this] rfl have hmul : (A.mulVecLin x) v = ∑ w, A v w * x w := rfl rw [hmul] at hx_ker_v have hterm : ∀ w, w ≠ u → A v w * x w = 0 := by intro w hw by_cases hxw : x w = 0 · rw [hxw, mul_zero] · have hws : w ∈ op_979_csym_max_nullity_le_fort_transversal_number_vec_supp x := op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff.mpr hxw have hnotadj : ¬ G.Adj v w := by intro hadj have : w = u := hu_uniq w ⟨hws, hadj⟩ exact hw this have hne : v ≠ w := by rintro rfl exact hxw hv have hAvw : A v w = 0 := by have := (hA.2 v w hne).not.mpr hnotadj exact not_not.mp this rw [hAvw, zero_mul] rw [Finset.sum_eq_single u (fun w _ hw => hterm w hw) (fun hu => False.elim (hu (Finset.mem_univ u)))] at hx_ker_v have hne_vu : v ≠ u := by rintro rfl exact hu_s hv have hAvu : A v u ≠ 0 := (hA.2 v u hne_vu).mpr hu_adj exact mul_ne_zero hAvu hu_s hx_ker_v
Given two distinct kernel supports C₁ = supp(x₁) and C₂ = supp(x₂) sharing a vertex v₀, the linear combination y = x₂(v₀)x₁ - x₁(v₀)x₂ is a non-zero vector in the kernel of A.
Because v₀ ∈ C₁ ∩ C₂, both x₁(v₀) and x₂(v₀) are non-zero. The vector y is a linear combination of vectors in the subspace ker(A), so y ∈ ker(A). If y = 0, then x₁ would be a scalar multiple of x₂ with non-zero scaling factor, which would force their supports to be identical, contradicting C₁ ≠ C₂. Hence y ≠ 0.
uses
Finset.mem_filter,Finset.mem_inter,op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff,Submodule.sub_mem,Submodule.smul_mem,congr_fun,mul_div_cancel_left₀,div_ne_zero,mul_ne_zero_ifflemma op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports_compatible {V : Type*} [Fintype V] [DecidableEq V] (A : Matrix V V ℝ) : is_compatible_collection (op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports A) := by intro C1 hC1 C2 hC2 hne v0 hv0 rw [op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports, Finset.mem_filter] at hC1 hC2 rcases hC1.2 with ⟨x1, hx1_ker, hx1_ne, rfl⟩ rcases hC2.2 with ⟨x2, hx2_ker, hx2_ne, rfl⟩ rw [Finset.mem_inter] at hv0 have hv1 : x1 v0 ≠ 0 := op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff.mp hv0.1 have hv2 : x2 v0 ≠ 0 := op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff.mp hv0.2 let y : V → ℝ := (x2 v0) • x1 - (x1 v0) • x2 have hy_ker : y ∈ LinearMap.ker A.mulVecLin := by exact Submodule.sub_mem _ (Submodule.smul_mem _ _ hx1_ker) (Submodule.smul_mem _ _ hx2_ker) have hy_ne : y ≠ 0 := by intro hy_zero have h_prop : ∀ w, x1 w = (x1 v0 / x2 v0) * x2 w := by intro w have hy_w : y w = 0 := congr_fun hy_zero w dsimp [y] at hy_w have : x2 v0 * x1 w = x1 v0 * x2 w := by linarith calc x1 w = (x2 v0 * x1 w) / x2 v0 := by rw [mul_div_cancel_left₀ (x1 w) hv2] _ = (x1 v0 * x2 w) / x2 v0 := by rw [this] _ = (x1 v0 / x2 v0) * x2 w := by ring have h_same_supp : op_979_csym_max_nullity_le_fort_transversal_number_vec_supp x1 = op_979_csym_max_nullity_le_fort_transversal_number_vec_supp x2 := by ext w simp only [op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff] have hc : x1 v0 / x2 v0 ≠ 0 := div_ne_zero hv1 hv2 rw [h_prop w, mul_ne_zero_iff] simp [hc] exact hne h_same_supp
The collection of kernel supports of A is a compatible collection, with supp(y) ⊆ (C₁ ∪ C₂) \ {v₀}.
Since y is a non-zero kernel vector, its support belongs to the kernel supports of A. At v₀, y(v₀) = x₂(v₀)x₁(v₀) - x₁(v₀)x₂(v₀) = 0, so v₀ ∉ supp(y). Moreover, for any vertex w outside C₁ ∪ C₂, both x₁(w) and x₂(w) vanish, so y(w) = 0. Hence supp(y) ⊆ (C₁ ∪ C₂) \ {v₀}.
uses
Finset.mem_filter,Finset.mem_univ,op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff,Finset.mem_sdiff,Finset.mem_union,Finset.mem_singleton,not_or,not_not,mul_zero,sub_zerorefine ⟨op_979_csym_max_nullity_le_fort_transversal_number_vec_supp y, ?_, ?_⟩ · rw [op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports, Finset.mem_filter] refine ⟨Finset.mem_univ _, ⟨y, hy_ker, hy_ne, rfl⟩⟩ · intro w hw rw [op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff] at hw rw [Finset.mem_sdiff, Finset.mem_union, Finset.mem_singleton] refine ⟨?_, ?_⟩ · by_contra hnot rw [not_or, op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff, op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff, not_not, not_not] at hnot have : y w = 0 := by dsimp [y] rw [hnot.1, hnot.2, mul_zero, mul_zero, sub_zero] exact hw this · intro hw_eq have : y w = 0 := by rw [hw_eq] dsimp [y] ring exact hw this
Restriction to a subset T defines a linear map from ker(A) to functions on T.
Evaluating kernel vectors at coordinates in T defines a map ker(A) → (T → ℝ), which preserves addition and scalar multiplication pointwise.
def op_979_csym_max_nullity_le_fort_transversal_number_ker_restrict {V : Type*} [Fintype V] [DecidableEq V] (A : Matrix V V ℝ) (T : Finset V) : A.mulVecLin.ker →ₗ[ℝ] (T → ℝ) where toFun x t := (x : V → ℝ) t.1 map_add' x y := by ext; rfl map_smul' c x := by ext; rfl
If T is a transversal of the kernel supports of A, the restriction map ker(A) → (T → ℝ) is injective.
Suppose an element x ∈ ker(A) maps to zero, so x vanishes on T. If x were non-zero, its support supp(x) would be in the collection of kernel supports. Since T is a transversal, T intersects supp(x) at some vertex t. But then x(t) = 0 (since t ∈ T) and x(t) ≠ 0 (since t ∈ supp(x)), a contradiction. Hence the restriction has trivial kernel and is injective.
uses
LinearMap.ker_eq_bot,Submodule.eq_bot_iff,Subtype.ext_iff,Finset.mem_filter,Finset.mem_univ,Finset.mem_inter,congr_fun,LinearMap.mem_ker,op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_ifflemma op_979_csym_max_nullity_le_fort_transversal_number_ker_restrict_injective {V : Type*} [Fintype V] [DecidableEq V] (A : Matrix V V ℝ) (T : Finset V) (hT : ∀ S ∈ op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports A, (T ∩ S).Nonempty) : Function.Injective (op_979_csym_max_nullity_le_fort_transversal_number_ker_restrict A T) := by rw [← LinearMap.ker_eq_bot, Submodule.eq_bot_iff] rintro ⟨x, hx_ker⟩ hx_in_ker rw [Subtype.ext_iff] dsimp by_contra hx_ne have hs_mem : op_979_csym_max_nullity_le_fort_transversal_number_vec_supp x ∈ op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports A := by rw [op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports, Finset.mem_filter] refine ⟨Finset.mem_univ _, ⟨x, hx_ker, hx_ne, rfl⟩⟩ have h_inter := hT (op_979_csym_max_nullity_le_fort_transversal_number_vec_supp x) hs_mem rcases h_inter with ⟨t, ht⟩ rw [Finset.mem_inter] at ht have ht_zero : x t = 0 := by have := congr_fun (LinearMap.mem_ker.mp hx_in_ker) ⟨t, ht.1⟩ exact this have ht_nonzero : x t ≠ 0 := op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff.mp ht.2 exact ht_nonzero ht_zero
The dimension of ker(A) is bounded by the cardinality of any transversal T of its kernel supports.
Because the restriction map ker(A) → (T → ℝ) is injective, dim ker(A) ≤ dim(T → ℝ). Since dim(T → ℝ) = |T|, the nullity of A is at most |T|.
uses
op_979_csym_max_nullity_le_fort_transversal_number_ker_restrict_injective,LinearMap.finrank_le_finrank_of_injective,Module.finrank_fintype_fun_eq_card,Fintype.card_coelemma op_979_csym_max_nullity_le_fort_transversal_number_finrank_ker_le_card_of_transversal {V : Type*} [Fintype V] [DecidableEq V] (A : Matrix V V ℝ) (T : Finset V) (hT : ∀ S ∈ op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports A, (T ∩ S).Nonempty) : Module.finrank ℝ A.mulVecLin.ker ≤ T.card := by have hinj := op_979_csym_max_nullity_le_fort_transversal_number_ker_restrict_injective A T hT have hle := LinearMap.finrank_le_finrank_of_injective hinj have hdim : Module.finrank ℝ (T → ℝ) = T.card := by rw [Module.finrank_fintype_fun_eq_card, Fintype.card_coe] rwa [hdim] at hle
The set of transversal numbers of compatible fort collections of G is bounded above by |V|.
Because every fort in any collection is nonempty, the full vertex set V intersects every fort. Thus V is a transversal of size |V|, so the minimum transversal number is at most |V|.
uses
Finset.card_univ,Finset.mem_inter,Finset.mem_univ,Nat.sInf_lelemma op_979_csym_max_nullity_le_fort_transversal_number_bdd_above_fort_transversal {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) : BddAbove { k : ℕ | ∃ C : Finset (Finset V), (∀ F ∈ C, simple_graph_is_fort G (F : Set V)) ∧ is_compatible_collection C ∧ finset_transversal_number C = k } := by refine ⟨Fintype.card V, ?_⟩ rintro k ⟨C, hC_fort, -, rfl⟩ unfold finset_transversal_number have hmem : Fintype.card V ∈ { k : ℕ | ∃ T : Finset V, (∀ S ∈ C, (T ∩ S).Nonempty) ∧ T.card = k } := by refine ⟨Finset.univ, ?_, Finset.card_univ⟩ intro S hS have hF := hC_fort S hS rcases hF.1 with ⟨v, hv⟩ refine ⟨v, ?_⟩ rw [Finset.mem_inter] exact ⟨Finset.mem_univ v, hv⟩ exact Nat.sInf_le hmem
For any combinatorially symmetric matrix A of G, dim ker(A) is at most the fort transversal number T(G).
The kernel supports of A form a compatible collection C of forts of G. Choosing a minimal transversal T for C gives dim ker(A) ≤ |T| = τ(C). Since C is a compatible collection of forts, τ(C) belongs to the set defining T(G), so τ(C) ≤ T(G). By transitivity, dim ker(A) ≤ T(G).
uses
op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports_is_fort,op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports_compatible,Finset.card_univ,Finset.mem_inter,Finset.mem_univ,Nat.sInf_mem,op_979_csym_max_nullity_le_fort_transversal_number_finrank_ker_le_card_of_transversal,op_979_csym_max_nullity_le_fort_transversal_number_bdd_above_fort_transversal,le_csSup,le_translemma op_979_csym_max_nullity_le_fort_transversal_number_finrank_ker_le_fort_transversal_number {V : Type*} [Fintype V] [DecidableEq V] {G : SimpleGraph V} (A : Matrix V V ℝ) (hA : is_csym_matrix G A) : Module.finrank ℝ A.mulVecLin.ker ≤ simple_graph_fort_transversal_number G := by let C := op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports A have hC_fort : ∀ F ∈ C, simple_graph_is_fort G (F : Set V) := fun F hF => op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports_is_fort hA hF have hC_comp : is_compatible_collection C := op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports_compatible A have h_nonempty : { k : ℕ | ∃ T : Finset V, (∀ S ∈ C, (T ∩ S).Nonempty) ∧ T.card = k }.Nonempty := by refine ⟨Fintype.card V, Finset.univ, ?_, Finset.card_univ⟩ intro S hS have hS_fort := hC_fort S hS rcases hS_fort.1 with ⟨v, hv⟩ refine ⟨v, ?_⟩ rw [Finset.mem_inter] exact ⟨Finset.mem_univ v, hv⟩ have h_sinf_mem := Nat.sInf_mem h_nonempty rcases h_sinf_mem with ⟨T, hT_hit, hT_card⟩ have h_le_card : Module.finrank ℝ A.mulVecLin.ker ≤ T.card := op_979_csym_max_nullity_le_fort_transversal_number_finrank_ker_le_card_of_transversal A T hT_hit have h_trans_mem : finset_transversal_number C ∈ { k : ℕ | ∃ C' : Finset (Finset V), (∀ F ∈ C', simple_graph_is_fort G (F : Set V)) ∧ is_compatible_collection C' ∧ finset_transversal_number C' = k } := ⟨C, hC_fort, hC_comp, rfl⟩ have hbdd := op_979_csym_max_nullity_le_fort_transversal_number_bdd_above_fort_transversal G have h_trans_le : finset_transversal_number C ≤ simple_graph_fort_transversal_number G := le_csSup hbdd h_trans_mem have h_le_trans : Module.finrank ℝ A.mulVecLin.ker ≤ finset_transversal_number C := by change Module.finrank ℝ A.mulVecLin.ker ≤ sInf { k : ℕ | ∃ T : Finset V, (∀ S ∈ C, (T ∩ S).Nonempty) ∧ T.card = k } rw [← hT_card] exact h_le_card exact le_trans h_le_trans h_trans_le
The combinatorially symmetric maximum nullity N(G) is at most the fort transversal number T(G).
By definition, N(G) is the supremum of dim ker(A) over all combinatorially symmetric matrices A for G. If no such matrix exists, the set is empty and its supremum is 0 ≤ T(G). When the set is nonempty, every element in it is at most T(G) by the previous lemma, so the supremum N(G) is at most T(G).
uses
csSup_empty,bot_le,csSup_le,op_979_csym_max_nullity_le_fort_transversal_number_finrank_ker_le_fort_transversal_numbertheorem op_979_csym_max_nullity_le_fort_transversal_number {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) : simple_graph_csym_max_nullity G ≤ simple_graph_fort_transversal_number G := by classical unfold simple_graph_csym_max_nullity cases { k : ℕ | ∃ A : Matrix V V ℝ, is_csym_matrix G A ∧ Module.finrank ℝ A.mulVecLin.ker = k }.eq_empty_or_nonempty with | inl he => rw [he, csSup_empty] exact bot_le | inr hne => apply csSup_le hne rintro k ⟨A, hA, rfl⟩ exact op_979_csym_max_nullity_le_fort_transversal_number_finrank_ker_le_fort_transversal_number A hA
bot_le- The bottom element of a bounded-below preorder is less than or equal to any element.
congr_fun- If two functions are equal, their values at any argument are equal.
csSup_empty- The supremum of the empty set in a conditionally complete lattice with a bottom element is the bottom element.
csSup_le- The supremum of a nonempty set is at most any upper bound of that set.
div_ne_zero- The quotient of two non-zero elements is non-zero.
False.elim- From False, any proposition follows.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
Finset.coe_nonempty- A finset is nonempty if and only if its coercion to a set is nonempty.
Finset.filter_eq_empty_iff- A filtered finset is empty if and only if no element of the ambient finset satisfies the predicate.
Finset.mem_coe- An element belongs to the set coercion of a finset if and only if it belongs to the finset.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
Finset.mem_inter- An element belongs to the intersection of two finsets if and only if it belongs to both.
Finset.mem_sdiff- An element belongs to the difference of two finsets if and only if it is in the first and not in the second.
Finset.mem_singleton- An element belongs to a singleton finset if and only if it equals the unique member.
Finset.mem_union- An element belongs to the union of two finsets if and only if it is in at least one of them.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
Finset.nonempty_iff_ne_empty- A finset is nonempty if and only if it is not the empty set.
Fintype.card_coe- The cardinality of a subtype given by a finset equals the cardinality of the finset.
funext_iff- Two functions are equal if and only if they agree on all arguments.
LinearMap.finrank_le_finrank_of_injective- An injective linear map between finite-dimensional vector spaces implies the dimension of the domain is at most that of the codomain.
LinearMap.ker_eq_bot- The kernel of a linear map is trivial if and only if the map is injective.
LinearMap.mem_ker- A vector belongs to the kernel of a linear map if and only if the linear map evaluates to zero at that vector.
le_csSup- Any element of a set bounded above is less than or equal to the supremum of the set.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Module.finrank_fintype_fun_eq_card- The dimension of the space of functions from a finite type to the base field equals the cardinality of the type.
mul_div_cancel_left₀- Multiplying by a non-zero element and then dividing by it recovers the original element.
mul_ne_zero- The product of two non-zero elements in a domain is non-zero.
mul_ne_zero_iff- A product in a domain is non-zero if and only if both factors are non-zero.
mul_zero- Multiplying any element by zero yields zero.
Nat.sInf_le- The infimum of a set of natural numbers is less than or equal to any element in the set.
Nat.sInf_mem- The infimum of a nonempty set of natural numbers belongs to the set.
not_not- Double negation elimination: not not P is equivalent to P.
not_iff_not- Equivalence of negations is equivalent to equivalence of the original propositions.
not_or- The negation of a disjunction is equivalent to the conjunction of the negations.
op_979_csym_max_nullity_le_fort_transversal_number_bdd_above_fort_transversal- The set of transversal numbers of compatible fort collections of a finite graph is bounded above.
op_979_csym_max_nullity_le_fort_transversal_number_finrank_ker_le_card_of_transversal- The dimension of the kernel of a matrix is at most the cardinality of any transversal of its kernel supports.
op_979_csym_max_nullity_le_fort_transversal_number_finrank_ker_le_fort_transversal_number- The nullity of any combinatorially symmetric matrix of a graph is at most the fort transversal number of the graph.
op_979_csym_max_nullity_le_fort_transversal_number_ker_restrict_injective- The linear restriction map to any transversal of the kernel supports of a matrix is injective.
op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports_compatible- The collection of kernel supports of any matrix is a compatible collection.
op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports_is_fort- The support of any non-zero kernel vector of a combinatorially symmetric matrix is a fort of the graph.
op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff- A vertex belongs to the support of a vector if and only if the vector is non-zero at that vertex.
op_979_csym_max_nullity_le_fort_transversal_number_vec_supp_eq_empty_iff- The support of a vector is empty if and only if the vector is zero everywhere.
op_979_csym_max_nullity_le_fort_transversal_number_vec_supp_nonempty_iff- The support of a vector is nonempty if and only if the vector is non-zero.
sub_zero- Subtracting zero leaves an element unchanged.
Submodule.eq_bot_iff- A submodule is the bottom submodule if and only if every element in it is zero.
Submodule.smul_mem- A submodule is closed under scalar multiplication.
Submodule.sub_mem- A submodule is closed under subtraction.
Subtype.ext_iff- Two elements of a subtype are equal if and only if their underlying values are equal.
Finset.sum_eq_single- A finite sum reduces to a single term if all other summands vanish.
zero_mul- Multiplying zero by any element yields zero.
- The supremum and infimum operations on natural numbers (sSup and sInf) are defined via conditionally complete lattices, requiring explicit nonemptiness or case splits on emptiness.
- The restriction map from the kernel to functions on T is formally verified as a bundled linear map whose linearity holds definitionally.
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.
open Classical innoncomputable def op_979_csym_max_nullity_le_fort_transversal_number_vec_supp {V : Type*} [Fintype V] (x : V → ℝ) : Finset V := Finset.filter (fun v => x v ≠ 0) Finset.univopen Classical innoncomputable def op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports {V : Type*} [Fintype V] (A : Matrix V V ℝ) : Finset (Finset V) := Finset.filter (fun s => ∃ x ∈ A.mulVecLin.ker, x ≠ 0 ∧ op_979_csym_max_nullity_le_fort_transversal_number_vec_supp x = s) Finset.univopen Classical inlemma op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff {V : Type*} [Fintype V] {x : V → ℝ} {v : V} : v ∈ op_979_csym_max_nullity_le_fort_transversal_number_vec_supp x ↔ x v ≠ 0 := by simp [op_979_csym_max_nullity_le_fort_transversal_number_vec_supp]open Classical inlemma op_979_csym_max_nullity_le_fort_transversal_number_vec_supp_eq_empty_iff {V : Type*} [Fintype V] {x : V → ℝ} : op_979_csym_max_nullity_le_fort_transversal_number_vec_supp x = ∅ ↔ x = 0 := by simp [op_979_csym_max_nullity_le_fort_transversal_number_vec_supp, Finset.filter_eq_empty_iff, funext_iff]open Classical inlemma op_979_csym_max_nullity_le_fort_transversal_number_vec_supp_nonempty_iff {V : Type*} [Fintype V] {x : V → ℝ} : (op_979_csym_max_nullity_le_fort_transversal_number_vec_supp x).Nonempty ↔ x ≠ 0 := by rw [Finset.nonempty_iff_ne_empty, not_iff_not, op_979_csym_max_nullity_le_fort_transversal_number_vec_supp_eq_empty_iff]open Classical inlemma op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports_is_fort {V : Type*} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {A : Matrix V V ℝ} (hA : is_csym_matrix G A) {s : Finset V} (hs : s ∈ op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports A) : simple_graph_is_fort G (s : Set V) := by rw [op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports, Finset.mem_filter] at hs rcases hs.2 with ⟨x, hx_ker, hx_ne, rfl⟩ rw [simple_graph_is_fort] refine ⟨?_, ?_⟩ · rw [Finset.coe_nonempty, op_979_csym_max_nullity_le_fort_transversal_number_vec_supp_nonempty_iff] exact hx_ne · intro v hv rw [Finset.mem_coe, op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff, not_not] at hv rintro ⟨u, ⟨hu_s, hu_adj⟩, hu_uniq⟩ rw [Finset.mem_coe, op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff] at hu_s have hx_ker_v : (A.mulVecLin x) v = 0 := by have : x ∈ LinearMap.ker A.mulVecLin := hx_ker rw [LinearMap.mem_ker] at this rw [this] rfl have hmul : (A.mulVecLin x) v = ∑ w, A v w * x w := rfl rw [hmul] at hx_ker_v have hterm : ∀ w, w ≠ u → A v w * x w = 0 := by intro w hw by_cases hxw : x w = 0 · rw [hxw, mul_zero] · have hws : w ∈ op_979_csym_max_nullity_le_fort_transversal_number_vec_supp x := op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff.mpr hxw have hnotadj : ¬ G.Adj v w := by intro hadj have : w = u := hu_uniq w ⟨hws, hadj⟩ exact hw this have hne : v ≠ w := by rintro rfl exact hxw hv have hAvw : A v w = 0 := by have := (hA.2 v w hne).not.mpr hnotadj exact not_not.mp this rw [hAvw, zero_mul] rw [Finset.sum_eq_single u (fun w _ hw => hterm w hw) (fun hu => False.elim (hu (Finset.mem_univ u)))] at hx_ker_v have hne_vu : v ≠ u := by rintro rfl exact hu_s hv have hAvu : A v u ≠ 0 := (hA.2 v u hne_vu).mpr hu_adj exact mul_ne_zero hAvu hu_s hx_ker_vopen Classical inlemma op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports_compatible {V : Type*} [Fintype V] [DecidableEq V] (A : Matrix V V ℝ) : is_compatible_collection (op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports A) := by intro C1 hC1 C2 hC2 hne v0 hv0 rw [op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports, Finset.mem_filter] at hC1 hC2 rcases hC1.2 with ⟨x1, hx1_ker, hx1_ne, rfl⟩ rcases hC2.2 with ⟨x2, hx2_ker, hx2_ne, rfl⟩ rw [Finset.mem_inter] at hv0 have hv1 : x1 v0 ≠ 0 := op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff.mp hv0.1 have hv2 : x2 v0 ≠ 0 := op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff.mp hv0.2 let y : V → ℝ := (x2 v0) • x1 - (x1 v0) • x2 have hy_ker : y ∈ LinearMap.ker A.mulVecLin := by exact Submodule.sub_mem _ (Submodule.smul_mem _ _ hx1_ker) (Submodule.smul_mem _ _ hx2_ker) have hy_ne : y ≠ 0 := by intro hy_zero have h_prop : ∀ w, x1 w = (x1 v0 / x2 v0) * x2 w := by intro w have hy_w : y w = 0 := congr_fun hy_zero w dsimp [y] at hy_w have : x2 v0 * x1 w = x1 v0 * x2 w := by linarith calc x1 w = (x2 v0 * x1 w) / x2 v0 := by rw [mul_div_cancel_left₀ (x1 w) hv2] _ = (x1 v0 * x2 w) / x2 v0 := by rw [this] _ = (x1 v0 / x2 v0) * x2 w := by ring have h_same_supp : op_979_csym_max_nullity_le_fort_transversal_number_vec_supp x1 = op_979_csym_max_nullity_le_fort_transversal_number_vec_supp x2 := by ext w simp only [op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff] have hc : x1 v0 / x2 v0 ≠ 0 := div_ne_zero hv1 hv2 rw [h_prop w, mul_ne_zero_iff] simp [hc] exact hne h_same_supp refine ⟨op_979_csym_max_nullity_le_fort_transversal_number_vec_supp y, ?_, ?_⟩ · rw [op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports, Finset.mem_filter] refine ⟨Finset.mem_univ _, ⟨y, hy_ker, hy_ne, rfl⟩⟩ · intro w hw rw [op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff] at hw rw [Finset.mem_sdiff, Finset.mem_union, Finset.mem_singleton] refine ⟨?_, ?_⟩ · by_contra hnot rw [not_or, op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff, op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff, not_not, not_not] at hnot have : y w = 0 := by dsimp [y] rw [hnot.1, hnot.2, mul_zero, mul_zero, sub_zero] exact hw this · intro hw_eq have : y w = 0 := by rw [hw_eq] dsimp [y] ring exact hw thisopen Classical indef op_979_csym_max_nullity_le_fort_transversal_number_ker_restrict {V : Type*} [Fintype V] [DecidableEq V] (A : Matrix V V ℝ) (T : Finset V) : A.mulVecLin.ker →ₗ[ℝ] (T → ℝ) where toFun x t := (x : V → ℝ) t.1 map_add' x y := by ext; rfl map_smul' c x := by ext; rflopen Classical inlemma op_979_csym_max_nullity_le_fort_transversal_number_ker_restrict_injective {V : Type*} [Fintype V] [DecidableEq V] (A : Matrix V V ℝ) (T : Finset V) (hT : ∀ S ∈ op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports A, (T ∩ S).Nonempty) : Function.Injective (op_979_csym_max_nullity_le_fort_transversal_number_ker_restrict A T) := by rw [← LinearMap.ker_eq_bot, Submodule.eq_bot_iff] rintro ⟨x, hx_ker⟩ hx_in_ker rw [Subtype.ext_iff] dsimp by_contra hx_ne have hs_mem : op_979_csym_max_nullity_le_fort_transversal_number_vec_supp x ∈ op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports A := by rw [op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports, Finset.mem_filter] refine ⟨Finset.mem_univ _, ⟨x, hx_ker, hx_ne, rfl⟩⟩ have h_inter := hT (op_979_csym_max_nullity_le_fort_transversal_number_vec_supp x) hs_mem rcases h_inter with ⟨t, ht⟩ rw [Finset.mem_inter] at ht have ht_zero : x t = 0 := by have := congr_fun (LinearMap.mem_ker.mp hx_in_ker) ⟨t, ht.1⟩ exact this have ht_nonzero : x t ≠ 0 := op_979_csym_max_nullity_le_fort_transversal_number_mem_vec_supp_iff.mp ht.2 exact ht_nonzero ht_zeroopen Classical inlemma op_979_csym_max_nullity_le_fort_transversal_number_finrank_ker_le_card_of_transversal {V : Type*} [Fintype V] [DecidableEq V] (A : Matrix V V ℝ) (T : Finset V) (hT : ∀ S ∈ op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports A, (T ∩ S).Nonempty) : Module.finrank ℝ A.mulVecLin.ker ≤ T.card := by have hinj := op_979_csym_max_nullity_le_fort_transversal_number_ker_restrict_injective A T hT have hle := LinearMap.finrank_le_finrank_of_injective hinj have hdim : Module.finrank ℝ (T → ℝ) = T.card := by rw [Module.finrank_fintype_fun_eq_card, Fintype.card_coe] rwa [hdim] at hleopen Classical inlemma op_979_csym_max_nullity_le_fort_transversal_number_bdd_above_fort_transversal {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) : BddAbove { k : ℕ | ∃ C : Finset (Finset V), (∀ F ∈ C, simple_graph_is_fort G (F : Set V)) ∧ is_compatible_collection C ∧ finset_transversal_number C = k } := by refine ⟨Fintype.card V, ?_⟩ rintro k ⟨C, hC_fort, -, rfl⟩ unfold finset_transversal_number have hmem : Fintype.card V ∈ { k : ℕ | ∃ T : Finset V, (∀ S ∈ C, (T ∩ S).Nonempty) ∧ T.card = k } := by refine ⟨Finset.univ, ?_, Finset.card_univ⟩ intro S hS have hF := hC_fort S hS rcases hF.1 with ⟨v, hv⟩ refine ⟨v, ?_⟩ rw [Finset.mem_inter] exact ⟨Finset.mem_univ v, hv⟩ exact Nat.sInf_le hmemopen Classical inlemma op_979_csym_max_nullity_le_fort_transversal_number_finrank_ker_le_fort_transversal_number {V : Type*} [Fintype V] [DecidableEq V] {G : SimpleGraph V} (A : Matrix V V ℝ) (hA : is_csym_matrix G A) : Module.finrank ℝ A.mulVecLin.ker ≤ simple_graph_fort_transversal_number G := by let C := op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports A have hC_fort : ∀ F ∈ C, simple_graph_is_fort G (F : Set V) := fun F hF => op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports_is_fort hA hF have hC_comp : is_compatible_collection C := op_979_csym_max_nullity_le_fort_transversal_number_kernel_supports_compatible A have h_nonempty : { k : ℕ | ∃ T : Finset V, (∀ S ∈ C, (T ∩ S).Nonempty) ∧ T.card = k }.Nonempty := by refine ⟨Fintype.card V, Finset.univ, ?_, Finset.card_univ⟩ intro S hS have hS_fort := hC_fort S hS rcases hS_fort.1 with ⟨v, hv⟩ refine ⟨v, ?_⟩ rw [Finset.mem_inter] exact ⟨Finset.mem_univ v, hv⟩ have h_sinf_mem := Nat.sInf_mem h_nonempty rcases h_sinf_mem with ⟨T, hT_hit, hT_card⟩ have h_le_card : Module.finrank ℝ A.mulVecLin.ker ≤ T.card := op_979_csym_max_nullity_le_fort_transversal_number_finrank_ker_le_card_of_transversal A T hT_hit have h_trans_mem : finset_transversal_number C ∈ { k : ℕ | ∃ C' : Finset (Finset V), (∀ F ∈ C', simple_graph_is_fort G (F : Set V)) ∧ is_compatible_collection C' ∧ finset_transversal_number C' = k } := ⟨C, hC_fort, hC_comp, rfl⟩ have hbdd := op_979_csym_max_nullity_le_fort_transversal_number_bdd_above_fort_transversal G have h_trans_le : finset_transversal_number C ≤ simple_graph_fort_transversal_number G := le_csSup hbdd h_trans_mem have h_le_trans : Module.finrank ℝ A.mulVecLin.ker ≤ finset_transversal_number C := by change Module.finrank ℝ A.mulVecLin.ker ≤ sInf { k : ℕ | ∃ T : Finset V, (∀ S ∈ C, (T ∩ S).Nonempty) ∧ T.card = k } rw [← hT_card] exact h_le_card exact le_trans h_le_trans h_trans_le/-- Theorem 2.10: For every finite simple graph G, N(G) ≤ T(G). -/theorem op_979_csym_max_nullity_le_fort_transversal_number {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) : simple_graph_csym_max_nullity G ≤ simple_graph_fort_transversal_number G := by classical unfold simple_graph_csym_max_nullity cases { k : ℕ | ∃ A : Matrix V V ℝ, is_csym_matrix G A ∧ Module.finrank ℝ A.mulVecLin.ker = k }.eq_empty_or_nonempty with | inl he => rw [he, csSup_empty] exact bot_le | inr hne => apply csSup_le hne rintro k ⟨A, hA, rfl⟩ exact op_979_csym_max_nullity_le_fort_transversal_number_finrank_ker_le_fort_transversal_number A hA