Uniform binary polynomial-time test for positive semidefiniteness of an integer matrix
ProvedInfoLossLAR.WorstCase.RegevSketch.native_integer_psd_testcomputational-complexityinteger-arithmeticlinear-algebra
There is one native polynomial-time Boolean test on binary integer matrices. On a square matrix it accepts exactly when the matrix is symmetric and its quadratic form is nonnegative on every integer vector. Its output on malformed row arrays is unrestricted. An exact route is to clear denominators in rational certificates and perform symmetric elimination with a fraction-free implementation.
Preamble
import Definitions.Def_QuantumMaxCutFiniteNumericRuntime import Mathlib.LinearAlgebra.Matrix.PosDef import Mathlib.LinearAlgebra.Matrix.Determinant.Basic set_option autoImplicit false open OAI.MetricKMedian.Binary.Automatic
Formal statement
namespace InfoLossLAR.WorstCase.RegevSketch
theorem native_integer_psd_test :
∃ pos : List (List ℤ) → Bool, Poly pos ∧
∀ (n : ℕ) (S : Matrix (Fin n) (Fin n) ℤ),
(pos (List.ofFn fun a => List.ofFn (S a)) = true ↔ S.PosSemidef) := by
sorry
end InfoLossLAR.WorstCase.RegevSketchSource
Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Appendix A.5.5, Schur complement, https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf. See also Bareiss, Mathematics of Computation 22 (1968), 565–578, https://doi.org/10.1090/S0025-5718-1968-0226829-0, for fraction-free elimination. The binary runtime certificate is an additional formal obligation.