Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Positive scaling preserves the coefficient-change objective

Open
QAlgorithms.Papers.Independent.Intakenext100.P36.positive_scaling

by Gohan · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let n,k≥1n,k\ge1n,k≥1, let p≥0p\ge0p≥0, and let Ei∈Mk,nE_i\in M_{k,n}Ei​∈Mk,n​ and Fi∈Mn,kF_i\in M_{n,k}Fi​∈Mn,k​ be finite families. For invertible S∈MpS\in M_pS∈Mp​, put Gj(S)=∑i(S−1)ijEiG_j(S)=\sum_i(S^{-1})_{ij}E_iGj​(S)=∑i​(S−1)ij​Ei​, Hi(S)=∑jSijFjH_i(S)=\sum_jS_{ij}F_jHi​(S)=∑j​Sij​Fj​, and

C(S)=∥∑iGi(S)Gi(S)†∥∥∑iHi(S)†Hi(S)∥.C(S)=\sqrt{\left\|\sum_iG_i(S)G_i(S)^\dagger\right\|}\sqrt{\left\|\sum_iH_i(S)^\dagger H_i(S)\right\|}.C(S)=​i∑​Gi​(S)Gi​(S)†​​​i∑​Hi​(S)†Hi​(S)​​.

For every positive definite SSS and every positive real ccc, C(cS)=C(S)C(cS)=C(S)C(cS)=C(S). Each positive definite SSS admits a positive scalar multiple cScScS with 0<cS≤I0<cS\le I0<cS≤I and the same cost. Consequently,

inf⁡S>0C(S)=inf⁡0<S≤IC(S).\inf_{S>0}C(S)=\inf_{0<S\le I}C(S).S>0inf​C(S)=0<S≤Iinf​C(S).

The condition 0<S≤I0<S\le I0<S≤I means precisely that all eigenvalues lie in (0,1](0,1](0,1]. Empty families have zero cost.

This explains the sampling-domain normalization mathematically, without providing any sampling success or accuracy guarantee.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P36
Formal statement
noncomputable section

open scoped Matrix ComplexConjugate ENNReal ComplexOrder

namespace QAlgorithms.Papers.Independent.Intakenext100.P36

local notation "Mat" => QAlgorithms.Papers.Independent.Information100.P50.M

local notation "Map" => QAlgorithms.Papers.Independent.Information100.P50.Lin

open QAlgorithms.Papers.Independent.Dependency50.P49 (traceDual)

/-- PDF p.17: scalar invariance and normalization of the positive domain.
For positive definite S, S <= I is equivalent to all eigenvalues belonging to (0,1].
Zero coefficient dimension is included, with empty objective equal to zero. -/
theorem positive_scaling {n k p : ℕ} (hn : 0 < n) (hk : 0 < k)
    (E : Fin p → Matrix (Fin k) (Fin n) ℂ)
    (F : Fin p → Matrix (Fin n) (Fin k) ℂ) :
    (∀ S : Mat p, S.PosDef → ∀ c : ℝ, 0 < c →
      changeCost E F ((c : ℂ) • S) = changeCost E F S) ∧
    (∀ S : Mat p, S.PosDef → ∃ c : ℝ, 0 < c ∧
      ((c : ℂ) • S).PosDef ∧ (1 - (c : ℂ) • S).PosSemidef ∧
      changeCost E F ((c : ℂ) • S) = changeCost E F S) ∧
    sInf {v : ℝ≥0∞ | ∃ S : Mat p, S.PosDef ∧
      v = ENNReal.ofReal (changeCost E F S)} =
    sInf {v : ℝ≥0∞ | ∃ S : Mat p, S.PosDef ∧ (1 - S).PosSemidef ∧
      v = ENNReal.ofReal (changeCost E F S)} := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P36

end
Source
Computing Stabilized Norms for Quantum Operations via the Theory of Completely Bounded Maps, arXiv:0711.3636v1, PDF p. 17, §5, unnumbered normalization of the positive minimization domain
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

For every pair of positive natural numbers n,kn,kn,k, every natural number ppp, and arbitrary families Ei∈Mk×n(C)E_i\in M_{k\times n}(\mathbb C)Ei​∈Mk×n​(C) and Fi∈Mn×k(C)F_i\in M_{n\times k}(\mathbb C)Fi​∈Mn×k​(C), indexed by 0≤i<p0\le i<p0≤i<p, define, for each p×pp\times pp×p matrix SSS,

Aj(S)=∑i=0p−1(S−1)ijEi,Bi(S)=∑j=0p−1SijFj,C(S)=∥∑j=0p−1Aj(S)Aj(S)†∥op ∥∑i=0p−1Bi(S)†Bi(S)∥op,A_j(S)=\sum_{i=0}^{p-1}(S^{-1})_{ij}E_i,\qquad B_i(S)=\sum_{j=0}^{p-1}S_{ij}F_j,\qquad C(S)= \sqrt{\left\|\sum_{j=0}^{p-1}A_j(S)A_j(S)^\dagger\right\|_{\mathrm{op}}}\, \sqrt{\left\|\sum_{i=0}^{p-1}B_i(S)^\dagger B_i(S)\right\|_{\mathrm{op}}},Aj​(S)=i=0∑p−1​(S−1)ij​Ei​,Bi​(S)=j=0∑p−1​Sij​Fj​,C(S)=​j=0∑p−1​Aj​(S)Aj​(S)†​op​​​i=0∑p−1​Bi​(S)†Bi​(S)​op​​,

where ∥⋅∥op\|\cdot\|_{\mathrm{op}}∥⋅∥op​ is the Euclidean operator norm. The declaration asserts all three of the following: every positive-definite SSS and every real c>0c>0c>0 satisfy C(cS)=C(S)C(cS)=C(S)C(cS)=C(S); for every positive-definite SSS, there exists a real c>0c>0c>0 such that cScScS is positive definite, Ip−cSI_p-cSIp​−cS is positive semidefinite, and C(cS)=C(S)C(cS)=C(S)C(cS)=C(S); and

inf⁡{ofReal⁡(C(S)):S is positive definite}=inf⁡{ofReal⁡(C(S)):S is positive definite and Ip−S is positive semidefinite},\inf\left\{\operatorname{ofReal}(C(S)):S\text{ is positive definite}\right\} = \inf\left\{\operatorname{ofReal}(C(S)): S\text{ is positive definite and }I_p-S\text{ is positive semidefinite}\right\},inf{ofReal(C(S)):S is positive definite}=inf{ofReal(C(S)):S is positive definite and Ip​−S is positive semidefinite},

with both infima taken in the extended nonnegative reals and ofReal⁡(t)=max⁡(t,0)\operatorname{ofReal}(t)=\max(t,0)ofReal(t)=max(t,0). No independence or representation condition is imposed on either family. The case p=0p=0p=0 is included: all displayed sums are empty, the cost is zero, the unique empty matrix satisfies the stated positivity conditions, and both infima are zero.

Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Oct 31, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me