AFTD Auto-Formalizing Theoretical Domains

has_range_criterion_of_matrix_pencil

theoremverified

Existence of a linearly independent matrix pencil of size (k + ℓ) × n of full column rank for all nonzero x ∈ C^m implies the existence of range criterion subspaces D and E of codimensions k and ℓ.

Statement

open scoped BigOperators in
theorem has_range_criterion_of_matrix_pencil
    (m n k ℓ : ℕ)
    (A : Fin k → Matrix (Fin m) (Fin n) ℂ)
    (B : Fin ℓ → Matrix (Fin m) (Fin n) ℂ)
    (hA : LinearIndependent ℂ A)
    (hB : LinearIndependent ℂ B)
    (hcond : ∀ (x : Fin m → ℂ) (y : Fin n → ℂ),
      (∀ i : Fin k, ∑ r : Fin m, ∑ s : Fin n, x r * A i r s * y s = 0) →
      (∀ j : Fin ℓ, ∑ r : Fin m, ∑ s : Fin n, star (x r) * B j r s * y s = 0) →
      x = 0 ∨ y = 0) :
    has_range_criterion_subspaces m n k ℓ
Source
step towards sporadic_krawtchouk_range_criterion_subspaces
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • has_range_criterion_subspacesThere exist complex linear subspaces D and E in C^m ⊗ C^n of codimensions k and ℓ, respectively, such that for all x ∈ C^m and y ∈ C^n, if…
Used by 1

The proof, explained

To construct range criterion subspaces D and E of codimensions k and ℓ, we define linear maps from the tensor product to C^k and C^ℓ via the matrix pencils A and B, and set D and E to be their kernels. Linear independence of the pencils implies these maps are surjective, so the quotients have dimensions k and ℓ by the first isomorphism theorem. Finally, the given condition on bilinear forms ensures that no nonzero simple tensor can have its components lie simultaneously in D and E under the star involution.

  1. The pencil map is bilinear and lifts to a linear map on the tensor product automation

    The bilinearity conditions (additivity and scalar homogeneity in both arguments) are checked entrywise using ring arithmetic and sum distribution.

    lines 7–10

    uses add_mul, Finset.sum_add_distrib, Finset.mul_sum, mul_assoc, mul_add, Finset.sum_congr, rfl

        (by intro x x' y; ext i; simp [add_mul, Finset.sum_add_distrib])
        (by intro c x y; ext i; simp [Finset.mul_sum, mul_assoc])
        (by intro x y y'; ext i; simp [mul_add, Finset.sum_add_distrib])
        (by intro c x y; ext i; simp only [Pi.smul_apply, smul_eq_mul, Finset.mul_sum]; refine Finset.sum_congr rfl fun r _ => Finset.sum_congr rfl fun s _ => by ring))
  2. The pencil map acts on simple tensors as the expected bilinear form automation

    Unfolding the definition of pencilMap shows that it evaluates on x ⊗ y to the sum over r and s of x r * A i r s * y s.

    lines 14–15

    uses pencilMap_tmul

        (i : Fin k) : pencilMap m n k A (x ⊗ₜ[ℂ] y) i = ∑ r : Fin m, ∑ s : Fin n, x r * A i r s * y s := by
      simp [pencilMap]
  3. If the pencil map were not surjective, a nonzero linear functional would vanish on its range

    We argue by contradiction: if the range is not the whole space, there exists a nonzero linear functional f that vanishes on the range of pencilMap.

    lines 20–23

    uses LinearMap.range_eq_top, Submodule.exists_le_ker_of_lt_top, lt_top_iff_ne_top.mpr

      classical
      rw [← LinearMap.range_eq_top]
      by_contra hne
      obtain ⟨f, hf0, hf⟩ := Submodule.exists_le_ker_of_lt_top _ (lt_top_iff_ne_top.mpr hne)
  4. The functional f is represented as a linear combination with coefficients c i automation

    Expanding any vector v in the standard basis shows that f(v) = ∑ i, c i * v i, where c i = f(e i).

    lines 24–30

    uses Finset.sum_apply, Pi.single_apply, map_sum, mul_comm

      set c : Fin k → ℂ := fun i => f (Pi.single i 1)
      have hfc : ∀ v : Fin k → ℂ, f v = ∑ i, c i * v i := by
        intro v
        have hv : v = ∑ i, v i • (Pi.single i (1 : ℂ) : Fin k → ℂ) := by
          ext j; simp [Finset.sum_apply, Pi.single_apply]
        conv_lhs => rw [hv]
        simp [map_sum, c, mul_comm]
  5. The linear combination of the pencil matrices with coefficients c i vanishes automation

    Evaluating f on the image of standard basis simple tensors e_r ⊗ e_s under pencilMap yields that the (r, s)-entry of ∑ i, c i • A i is zero for all r, s.

    lines 31–36

    uses LinearMap.mem_range_self, LinearMap.mem_ker, pencilMap_tmul, Matrix.sum_apply, Pi.single_apply, Finset.sum_ite_eq

      have hzero : ∑ i, c i • A i = 0 := by
        ext r s
        have := hf (LinearMap.mem_range_self (pencilMap m n k A) (Pi.single r 1 ⊗ₜ[ℂ] Pi.single s 1))
        rw [LinearMap.mem_ker, hfc] at this
        simp only [pencilMap_tmul] at this
        simpa [Matrix.sum_apply, Pi.single_apply, Finset.sum_ite_eq] using this
  6. By linear independence of the pencil matrices, f must be zero, giving a contradiction automation

    Linear independence of A implies all coefficients c i are zero, which means f = 0, contradicting that f is nonzero. Thus pencilMap is surjective.

    lines 37–40

    uses Fintype.linearIndependent_iff.mp

      have hc := (Fintype.linearIndependent_iff.mp hA) c hzero
      apply hf0
      ext v
      simp [hfc, hc]
  7. Define the candidate subspaces D and E as the kernels of the pencil maps for A and B

    We choose D = ker(pencilMap A) and E = ker(pencilMap B) as the two required subspaces of the tensor product.

    line 55

      refine ⟨LinearMap.ker (pencilMap m n k A), LinearMap.ker (pencilMap m n ℓ B), ?_, ?_, ?_⟩
  8. Subspace D has codimension k automation

    By the first isomorphism theorem and surjectivity of pencilMap A, the quotient of the tensor product by D is isomorphic to C^k, so its dimension is k.

    lines 56–57

    uses LinearMap.quotKerEquivOfSurjective, pencilMap_surjective

      · rw [(LinearMap.quotKerEquivOfSurjective _ (pencilMap_surjective m n k A hA)).finrank_eq]
        simp
  9. Subspace E has codimension ℓ automation

    Similarly, by the first isomorphism theorem and surjectivity of pencilMap B, the quotient by E is isomorphic to C^ℓ, so its dimension is ℓ.

    lines 58–59

    uses LinearMap.quotKerEquivOfSurjective, pencilMap_surjective

      · rw [(LinearMap.quotKerEquivOfSurjective _ (pencilMap_surjective m n ℓ B hB)).finrank_eq]
        simp
  10. Pure tensors in D and E satisfy the range criterion condition automation

    Assuming x ⊗ y ∈ D and star x ⊗ y ∈ E, evaluating at each component gives the bilinear vanishing conditions, from which the hypothesis implies x = 0 or y = 0.

    lines 60–67

    uses congrFun, LinearMap.mem_ker.mp, pencilMap_tmul

      · intro x y hx hy
        apply hcond x y
        · intro i
          have := congrFun (LinearMap.mem_ker.mp hx) i
          simpa [pencilMap_tmul] using this
        · intro j
          have := congrFun (LinearMap.mem_ker.mp hy) j
          simpa [pencilMap_tmul] using this
add_mul
distribution of addition over multiplication on the right
Finset.sum_add_distrib
sum of a sum is the sum of sums
Finset.mul_sum
distributing multiplication over a finite sum
mul_assoc
associativity of multiplication
mul_add
distribution of multiplication over addition on the left
Finset.sum_congr
congruence for finite sums
rfl
reflexivity of equality
pencilMap_tmul
evaluating the pencil map on a simple tensor
LinearMap.range_eq_top
a linear map has range top if and only if it is surjective
Submodule.exists_le_ker_of_lt_top
a proper submodule has a nonzero functional vanishing on it
lt_top_iff_ne_top.mpr
strict inequality with top is equivalent to not being top
Finset.sum_apply
evaluating a finite sum of functions pointwise
Pi.single_apply
evaluating a single-basis function
map_sum
a linear map preserves finite sums
mul_comm
commutativity of multiplication
LinearMap.mem_range_self
the image of any element is in the range of the linear map
LinearMap.mem_ker
membership in the kernel is equivalent to mapping to zero
Matrix.sum_apply
evaluating a sum of matrices entrywise
Finset.sum_ite_eq
sum of an indicator equals the value if the point is in the set
Fintype.linearIndependent_iff.mp
linear independence means the only linear combination giving zero is the trivial one
LinearMap.quotKerEquivOfSurjective
the quotient by the kernel of a surjective linear map is isomorphic to the target
pencilMap_surjective
the linear map associated to a linearly independent matrix pencil is surjective
congrFun
evaluating equal functions at an argument yields equal values
LinearMap.mem_ker.mp
an element is in the kernel implies the linear map evaluates to 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 scoped TensorProduct innoncomputable def pencilMap (m n k : ℕ) (A : Fin k → Matrix (Fin m) (Fin n) ℂ) :    TensorProduct ℂ (Fin m → ℂ) (Fin n → ℂ) →ₗ[ℂ] (Fin k → ℂ) :=  TensorProduct.lift (LinearMap.mk₂ ℂ (fun (x : Fin m → ℂ) (y : Fin n → ℂ) (i : Fin k) =>      ∑ r : Fin m, ∑ s : Fin n, x r * A i r s * y s)    (by intro x x' y; ext i; simp [add_mul, Finset.sum_add_distrib])    (by intro c x y; ext i; simp [Finset.mul_sum, mul_assoc])    (by intro x y y'; ext i; simp [mul_add, Finset.sum_add_distrib])    (by intro c x y; ext i; simp only [Pi.smul_apply, smul_eq_mul, Finset.mul_sum]; refine Finset.sum_congr rfl fun r _ => Finset.sum_congr rfl fun s _ => by ring))open scoped TensorProduct inlemma pencilMap_tmul (m n k : ℕ) (A : Fin k → Matrix (Fin m) (Fin n) ℂ) (x : Fin m → ℂ) (y : Fin n → ℂ)    (i : Fin k) : pencilMap m n k A (x ⊗ₜ[ℂ] y) i = ∑ r : Fin m, ∑ s : Fin n, x r * A i r s * y s := by  simp [pencilMap]open scoped TensorProduct inlemma pencilMap_surjective (m n k : ℕ) (A : Fin k → Matrix (Fin m) (Fin n) ℂ)    (hA : LinearIndependent ℂ A) : Function.Surjective (pencilMap m n k A) := by  classical  rw [← LinearMap.range_eq_top]  by_contra hne  obtain ⟨f, hf0, hf⟩ := Submodule.exists_le_ker_of_lt_top _ (lt_top_iff_ne_top.mpr hne)  set c : Fin k → ℂ := fun i => f (Pi.single i 1)  have hfc : ∀ v : Fin k → ℂ, f v = ∑ i, c i * v i := by    intro v    have hv : v = ∑ i, v i • (Pi.single i (1 : ℂ) : Fin k → ℂ) := by      ext j; simp [Finset.sum_apply, Pi.single_apply]    conv_lhs => rw [hv]    simp [map_sum, c, mul_comm]  have hzero : ∑ i, c i • A i = 0 := by    ext r s    have := hf (LinearMap.mem_range_self (pencilMap m n k A) (Pi.single r 1 ⊗ₜ[ℂ] Pi.single s 1))    rw [LinearMap.mem_ker, hfc] at this    simp only [pencilMap_tmul] at this    simpa [Matrix.sum_apply, Pi.single_apply, Finset.sum_ite_eq] using this  have hc := (Fintype.linearIndependent_iff.mp hA) c hzero  apply hf0  ext v  simp [hfc, hc]open scoped BigOperators in/-- Existence of a linearly independent matrix pencil of size (k + ℓ) × n of full column rank for all nonzero x ∈ C^m implies the existence of range criterion subspaces D and E of codimensions k and ℓ. -/theorem has_range_criterion_of_matrix_pencil    (m n k ℓ : ℕ)    (A : Fin k → Matrix (Fin m) (Fin n) ℂ)    (B : Fin ℓ → Matrix (Fin m) (Fin n) ℂ)    (hA : LinearIndependent ℂ A)    (hB : LinearIndependent ℂ B)    (hcond : ∀ (x : Fin m → ℂ) (y : Fin n → ℂ),      (∀ i : Fin k, ∑ r : Fin m, ∑ s : Fin n, x r * A i r s * y s = 0) →      (∀ j : Fin ℓ, ∑ r : Fin m, ∑ s : Fin n, star (x r) * B j r s * y s = 0) →      x = 0 ∨ y = 0) :    has_range_criterion_subspaces m n k ℓ := by  refine ⟨LinearMap.ker (pencilMap m n k A), LinearMap.ker (pencilMap m n ℓ B), ?_, ?_, ?_⟩  · rw [(LinearMap.quotKerEquivOfSurjective _ (pencilMap_surjective m n k A hA)).finrank_eq]    simp  · rw [(LinearMap.quotKerEquivOfSurjective _ (pencilMap_surjective m n ℓ B hB)).finrank_eq]    simp  · intro x y hx hy    apply hcond x y    · intro i      have := congrFun (LinearMap.mem_ker.mp hx) i      simpa [pencilMap_tmul] using this    · intro j      have := congrFun (LinearMap.mem_ker.mp hy) j      simpa [pencilMap_tmul] using this
See it in the graphDiscuss this resultChallenge it