Proof of Theorem 1.3 — is a real eigenvalue of iff a square quadratic system is feasible
ProvedTensorNP.Eigen.eigen_zero_iff_square_feasiblep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1quadratic-feasibilitytensor-eigenvalue
Let and, for , let be its slice . Then is an eigenvalue of over , i.e. there is with for all , if and only if the square system
of quadratic equations in unknowns has a nonzero real solution.
This identifies tensor -eigenvalue with square quadratic feasibility ( in Problem 2.2), the first step of the paper's proof of Theorem 1.3.
Preamble
import Mathlib import Definitions.Def_TensorNP_Eigen_Defs
Formal statement
namespace TensorNP.Eigen
open Matrix
/-- Proof of Theorem 1.3, first sentence: `0` is a real eigenvalue of `A ∈ ℚ^{n×n×n}` if and only
if the square system `xᵀ A_k x = 0` (`k = 1, …, n`) with `A_k(i, j) = a_{ijk}` has a nonzero
real solution. -/
theorem eigen_zero_iff_square_feasible {n : ℕ} (A : Fin n → Fin n → Fin n → ℚ) :
IsEigenvalue (castTensor ℝ A) 0 ↔
QuadSolvable (castMatrices ℝ (fun k : Fin n => Matrix.of fun i j => A i j k)) := 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:20, proof of Theorem 1.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.