Lemma 2.8 — padding a real quadratic system to equations in unknowns
ProvedTensorNP.Eigen.lemma_2_8p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1quadratic-feasibility
Let and . Let and , and define the matrices of size
where is the identity matrix, and . Then has a nonzero solution if and only if has a nonzero solution .
The lemma lets a quadratic system be made square, the shape of the eigenvalue equations of a tensor.
Formalization Note The case is included, where . Indices are 0-based, so is matrix number .
Preamble
import Mathlib import Definitions.Def_TensorNP_Eigen_Construction
Formal statement
namespace TensorNP.Eigen
open Matrix
/-- Lemma 2.8: for `A_1, …, A_m ∈ ℝ^{n×n}`, `r ≥ m + 1` and `s ≥ n`, the padded system
`xᵀ B_i x = 0` (`i = 1, …, r`) with `B_i = [A_i 0; 0 0]`, `B_j = 0` (`m < j < r`),
`B_r = [0 0; 0 I]` has a nonzero solution `x ∈ ℝ^s` if and only if `{xᵀ A_i x = 0}_{i=1}^m` has
a nonzero solution `x ∈ ℝ^n`. -/
theorem lemma_2_8 {m n r s : ℕ} (A : Fin m → Matrix (Fin n) (Fin n) ℝ) (hr : m + 1 ≤ r)
(hs : n ≤ s) :
QuadSolvable (padSystem A r s) ↔ QuadSolvable A := by sorry
end TensorNP.Eigen
Source
Hillar & Lim, Most Tensor Problems Are NP-Hard, J. ACM 60(6) (2013), Art. 45 (final version, arXiv:0911.1393v5), p. 0:14, Lemma 2.8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.