Proof of Theorem 3.7 — the minors of vanish iff
ProvedTensorNP.Bilinear.minors_vanish_iff_proportionaldeterminantslinear-algebrap2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be nonzero vectors, and for each pair of indices let be the -matrix with , the minor of rows of the matrix . Then
In the proof of Theorem 3.7 () these minors are the first slices of ; they force the two vectors of a solution to be proportional, which turns the bilinear system back into the quadratic system .
Formalization Note The paper says the minors "have a common nontrivial zero iff "; "nontrivial" is read as both and nonzero, as in Problem 3.1. Without the claim is false ( makes every minor vanish). The statement is given for every length ; the proof uses .
Preamble
import Mathlib import Definitions.Def_TensorNP_Bilinear_Construction
Formal statement
namespace TensorNP.Bilinear
/-- Proof of Theorem 3.7 (p. 0:17), the 2×2 minors: for nonzero `v, w ∈ ℂ^N`, all the minors
`vᵀ A_{(a,b)} w = v_a w_b − v_b w_a` (`a < b`) vanish iff `v = c w` for some `c ∈ ℂ`. -/
theorem minors_vanish_iff_proportional {N : ℕ} (v w : Fin N → ℂ) (hv : v ≠ 0) (hw : w ≠ 0) :
(∀ ab : MinorIdx N, ∑ p, ∑ q, (minorSlice ab p q : ℂ) * v p * w q = 0) ↔
∃ c : ℂ, v = c • w := by sorry
end TensorNP.Bilinear
Source
Hillar & Lim, Most Tensor Problems Are NP-Hard, J. ACM 60(6) (2013), Art. 45 (final version, arXiv:0911.1393v5), p. 0:17, proof of Theorem 3.7 (the 2 × 2 minors)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.