Unstrengthened completely positive covering value
DefinitionGraphTensorCP_Supplement_uCPcompletely-positive-programmingconvex-optimizationgraph-tensorsp2o-gran-per-chapterp2o-plan-paperp2o-v1tensor-rank
A real symmetric matrix is completely positive if it has a finite factorization
For a symmetric nonnegative zero-diagonal matrix , the unstrengthened completely positive covering value is
where is the all-one matrix and the objective includes every entry of , including its diagonal. This is the basic conic upper bound used in the graph-family applications; it has no path constraints.
Formalization Note Complete positivity is represented by an existentially quantified finite family of nonnegative factors. The minimum is a real infimum; the paper proves that the feasible set is nonempty and the minimum is attained on the stated domain.
Definition code
import Mathlib
namespace GraphTensorCP
namespace Supplement
/-- A real symmetric matrix is **completely positive** when it is a finite sum of outer
products `b bᵀ` with `b ≥ 0` (Zhou, *Asymptotic Rank of Weighted Graph Tensors via Completely
Positive Covers*, arXiv:2610.34273 (version of 2026-11-03), Definition 2.32, p.28, and
Definition 5.2, p.46).
**Formalization Note.** The finite number of factors is existentially quantified. Taking zero
factors represents the zero matrix. -/
def IsCompletelyPositive {n : ℕ} (Z : Matrix (Fin n) (Fin n) ℝ) : Prop :=
∃ t : ℕ, ∃ b : Fin t → Fin n → ℝ,
(∀ nu i, 0 ≤ b nu i) ∧ Z = fun i j => ∑ nu, b nu i * b nu j
/-- The **unstrengthened completely positive covering value** `U_CP(W)` (Zhou,
*Asymptotic Rank of Weighted Graph Tensors via Completely Positive Covers*,
arXiv:2610.34273 (version of 2026-11-03), Definition 5.2, eq. (10), p.46):
`(1/4) min {⟨J,Z⟩ | Z ∈ CP_n, Z_ij ≥ W_ij for i < j}`.
**Formalization Note.** `⟨J,Z⟩` is the sum of every entry of `Z`, including the diagonal.
The minimum is represented by `sInf`; the paper proves on p.46 that for every symmetric
nonnegative zero-diagonal `W` the feasible set is nonempty and the minimum is attained. No path
inequalities occur in this definition. -/
noncomputable def uCP {n : ℕ} (W : Matrix (Fin n) (Fin n) ℝ) : ℝ :=
(1 / 4 : ℝ) * sInf {c : ℝ | ∃ Z : Matrix (Fin n) (Fin n) ℝ,
IsCompletelyPositive Z ∧ (∀ i j, i < j → W i j ≤ Z i j) ∧
c = ∑ i, ∑ j, Z i j}
end Supplement
end GraphTensorCP
Source
Zhou, Asymptotic Rank of Weighted Graph Tensors via Completely Positive Covers, arXiv:2610.34273 (version of 2026-11-03), Definition 2.32, p.28; Definition 5.2, eqs. (10)–(11), p.46