has_range_criterion_of_matrix_pencil
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
- range_criterion_subspaces_sporadic_five_five_three_fiveThere exist complex subspaces D and E in C^5 ⊗ C^5 of codimensions 3 and 5, respectively, satisfying the range criterion (no nonzero…
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.
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.
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))
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.
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]
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.
uses
LinearMap.range_eq_top,Submodule.exists_le_ker_of_lt_top,lt_top_iff_ne_top.mprclassical 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)
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).
uses
Finset.sum_apply,Pi.single_apply,map_sum,mul_commset 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]
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.
uses
LinearMap.mem_range_self,LinearMap.mem_ker,pencilMap_tmul,Matrix.sum_apply,Pi.single_apply,Finset.sum_ite_eqhave 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
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.
uses
Fintype.linearIndependent_iff.mphave hc := (Fintype.linearIndependent_iff.mp hA) c hzero apply hf0 ext v simp [hfc, hc]
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.
refine ⟨LinearMap.ker (pencilMap m n k A), LinearMap.ker (pencilMap m n ℓ B), ?_, ?_, ?_⟩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.
uses
LinearMap.quotKerEquivOfSurjective,pencilMap_surjective· rw [(LinearMap.quotKerEquivOfSurjective _ (pencilMap_surjective m n k A hA)).finrank_eq] simp
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 ℓ.
uses
LinearMap.quotKerEquivOfSurjective,pencilMap_surjective· rw [(LinearMap.quotKerEquivOfSurjective _ (pencilMap_surjective m n ℓ B hB)).finrank_eq] simp
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.
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
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 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