§3, p.3 — a zero diagonal entry kills the row, the column and
ProvedPsdPermanent.permanent_eq_zero_of_diagapproximation-algorithmsconvex-relaxationdifferential-entropyp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1permanentpositive-semidefinite
Let be an Hermitian matrix with for some . Then:
- , that is, row of vanishes in every factorization ;
- for all ;
- the th row and the th column of are zero;
- .
This reduces the sandwich to the case of nonzero rows.
Differences from the source:
- generalization: a Gram factor of full column rank → every factorization A = V V†, with any number of columns; reason: full column rank factors are a special case
- encoding: per(A) = ∑_σ ∏i A{i,σ(i)} → Mathlib permanent ∑_σ ∏i A{σ(i),i}; reason: reindexing by σ⁻¹ gives the same value
Preamble
import Mathlib open Matrix open scoped ComplexOrder
Formal statement
namespace PsdPermanent
/-- **Zero diagonal entries.**
Anari, Ebrahimnejad, *Optimal e^{(γ+o(1))n}-Approximation of the Permanent of Positive
Semidefinite Matrices*, arXiv:2605.21946 (held copy sha256 5e70fa63…), §3, p.3: "If A_ii = 0 for some i, then v_i = 0. Equivalently, by Cauchy–Schwarz for the PSD inner
product, |A_ij|² ≤ A_ii A_jj = 0 for all j. Hence the ith row and column of A are zero, and per(A) = 0."
**Formalization Note.** `v_i = 0` is stated for every factorization `A = V * Vᴴ`, with or without full column
rank. Mathlib's `Matrix.permanent` is `∑ σ, ∏ i, A (σ i) i`, the paper's `∑ σ, ∏ i, A i (σ i)` after reindexing
by `σ⁻¹`. -/
theorem permanent_eq_zero_of_diag {n : ℕ} (A : Matrix (Fin n) (Fin n) ℂ) (hA : A.PosSemidef) (i : Fin n)
(hi : A i i = 0) :
(∀ (d : ℕ) (V : Matrix (Fin n) (Fin d) ℂ), A = V * Vᴴ → V i = 0) ∧
(∀ j, Complex.normSq (A i j) ≤ (A i i).re * (A j j).re) ∧
(∀ j, A i j = 0 ∧ A j i = 0) ∧ A.permanent = 0 := by sorry
end PsdPermanent
Source
N. Anari, F. Ebrahimnejad, Optimal e^{(γ+o(1))n}-Approximation of the Permanent of Positive Semidefinite Matrices, arXiv:2605.21946 (held copy sha256 5e70fa63…), §3, p.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.