AFTD Auto-Formalizing Theoretical Domains

op_979_csym_max_nullity_le_fort_transversal_number

theoremverifiedformalization

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).

  1. 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.

    lines 13–30

    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_iff

    lemma 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]
    
  2. 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.

    lines 32–43

    uses Finset.mem_filter, Finset.coe_nonempty, op_979_csym_max_nullity_le_fort_transversal_number_vec_supp_nonempty_iff

    lemma 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
  3. 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.

    lines 44–80

    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
  4. 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.

    lines 83–115

    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_iff

    lemma 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
  5. 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₀}.

    lines 116–136

    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_zero

      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 this
    
  6. 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.

    lines 138–144

    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
    
  7. 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.

    lines 146–168

    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_iff

    lemma 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
    
  8. 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|.

    lines 170–179

    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_coe

    lemma 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
    
  9. 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|.

    lines 181–196

    uses Finset.card_univ, Finset.mem_inter, Finset.mem_univ, Nat.sInf_le

    lemma 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
  10. 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).

    lines 199–231

    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_trans

    lemma 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
  11. 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).

    lines 234–246

    uses csSup_empty, bot_le, csSup_le, op_979_csym_max_nullity_le_fort_transversal_number_finrank_ker_le_fort_transversal_number

    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
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.

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

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