Linear Trace-Deficit Decay for Permanents of Positive Semidefinite Contractions

Introduction

Background and the source problem

For $A=(A_{ij})\in\mathbb{C}^{n\times n}$, its permanent is

When $A$ is Hermitian positive semidefinite, the permanent is nonnegative and admits a useful complex Gaussian representation. The permanent of a positive semidefinite matrix is also monotone in the Loewner order; both facts will be proved below.

There are two related questions: how accurately a permanent can be approximated, and how small it must be when the matrix falls below the identity. For the first, Anari, Gurvits, Oveis Gharan, and Saberi [3 Theorem 1 and Definition 1] obtained a deterministic $e^{(\gamma+1)n}$-approximation through a diagonal-majorant relaxation; here $\gamma$ is Euler’s constant. Yuan and Parrilo [4 Corollary 1.2] sharpened the guarantee for that relaxation using its connection with products of linear forms and low-rank solutions. Ebrahimnejad, Nagda, and Oveis Gharan [1 Theorems 1.1–1.2] subsequently improved the approximation exponent below $\gamma+1$ and established hardness below $\gamma$. Anari and Ebrahimnejad [2 Theorem 1] have now obtained the optimal $e^{(\gamma+o(1))n}$ exponent. The present paper concerns the second question, a structural inequality for each individual matrix.

In their work on approximating positive semidefinite permanents, Ebrahimnejad, Nagda, and Oveis Gharan established the following trace-sensitive estimate.

In Section 1.4 of [1], the authors identify the $O(\varepsilon^2)$ dependence in Theorem 1.1 as the bottleneck to a better approximation ratio and conjecture that it can be improved to $O(\varepsilon)$. Since the estimate in Theorem 1.1 is expressed through its base, the corresponding quantitative target is the following.

Contribution

The main result establishes Conjecture 1.2 through an exponential estimate in the actual trace deficit.

The proof has two principal components.

1. The local estimate in Theorem 4.1 shows that, for $K \succeq0$ of sufficiently small operator norm,

Its linear term comes from an exact Gaussian density calculation, while Lemma 3.1 keeps the quadratic error proportional to $\operatorname{tr}(K^2)$, rather than to $(\operatorname{tr}K)^2$.

2. Lemma 5.2 compares a general contraction $A=I_n-D$ to the rational majorant $(I_n+\theta D)^{-1}$ in Loewner order. Taking $\theta=1/34$, applying Theorem 4.1, and using $D^2\preceq D$ yields Theorem 1.3.

Intuition and related methods

For a diagonal contraction, the scalar inequality $a\le e^{-(1-a)}$ immediately gives $\operatorname{per}(A)\le e^{-\operatorname{tr}(I-A)}$. Off-diagonal entries introduce additional permutation terms, and Example 6.2 shows that this constant cannot hold for all contractions. Nevertheless, the total spectral deficit remains the right quantity. The spectral cutoff in the proof of [1 Lemma 1.3] first finds sufficiently many eigenvalues a sufficient distance below one. Both quantities cost a factor of the normalized deficit. The rational majorant above instead shrinks every deficit by the same fixed factor and retains their entire sum.

The local calculation explains why this is possible. Gaussian Wick identities for PSD permanents are standard; see [1 Lemma 2.9]. Barvinok [5] uses such an integral representation for an approximation scheme when the eigenvalues lie in $[1,2]$, and [1 Lemma 3.2] uses it to bound permanents by determinants. Here a change of density absorbs the product of squared coordinates into independent size-biased complex Gaussian variables. Their expected quadratic form is $2\operatorname{tr}K$, whereas the determinant factor contributes at most $\operatorname{tr}K$. This leaves a negative linear term. The essential estimate is that its fluctuation costs only $O(\operatorname{tr}K^2)$.

The random partition and Gaussian linearization used to control that fluctuation follow the proof strategy of Rudelson and Vershynin [6], proof of Theorem 1.1, Steps 2–4. The auxiliary-Gaussian comparison also appears in Hsu, Kakade, and Zhang [7, Theorem 1 and Remark 2]. These are precedents for the method, rather than statements of the permanent inequality. Each complex coordinate here gives an independent two-dimensional real block; its real and imaginary parts are dependent after size biasing. Lemma 3.1 therefore gives the block argument explicitly, with constants sufficient for the application. The exact Gamma transform handles the diagonal part separately.

Corollary 1.4 provides the replacement requested in [1 Section 1.4]. It is not needed to claim the current best approximation ratio, which is already supplied by [2]. The entropic upper certificate in [2 Eq. (4) and Theorem 7] does not by itself give trace-deficit decay: on $A=aI_n$, $a>0$, it equals $(4a/e)^n$. Indeed, its logarithm is the maximum of

Hadamard’s determinant inequality bounds this by $n\log a+\sum_i(2\log X_{ii}-X_{ii}+1)$. Each summand is maximized at $X_{ii}=2$, and $X=2I_n$ attains equality. Thus this certificate exceeds one for $e/4<a<1$, even though the trace deficit is positive. Theorem 1.3 supplies a direct pointwise estimate; its constant is not asserted to be optimal.

Another algorithmic upper bound is the permanent process of Laddha and Pittu [8, Algorithm 1 and Theorem 1.3], valid for real PSD matrices as well as nonnegative matrices. Its elimination-type certificate need not decay on contractions: on the rank-one projection $J_n/n$, where $J_n$ is the all-ones matrix, each step doubles all entries of the remaining submatrix. The product of its pivots is therefore $2^{n(n-1)/2}/n^n$, which already exceeds one at $n=7$. Yi’s recent deterministic approximation scheme [9, Theorem 1.1(b)] instead treats nonnegative matrices with dense support and nonzero entries in a fixed positive interval. That input regime differs from arbitrary complex PSD contractions.

Gaussian preliminaries

We write $X^*$ for the conjugate transpose of a complex matrix $X$. The symbols $\lVert\cdot\rVert_{\operatorname{op}}$ and $\lVert\cdot\rVert_F$ denote the operator and Frobenius norms. A standard circular complex Gaussian random variable has density

Equivalently, $W=(G_1+iG_2)/\sqrt{2}$, where $G_1,G_2$ are independent standard real Gaussian variables.

Wick's formula

The following representation is the complex version of Wick’s formula. It also appears as Lemma 2.9 in [1].

Proof. For a circular complex Gaussian vector, the only nonzero pairings in the mixed moment

pair each unbarred coordinate with a barred coordinate. Such a pairing is specified by a permutation $\sigma\in S_n$, and its contribution is

Summing over all $\sigma\in S_n$ gives (2). A singular covariance follows either from the same moment identity or by approximation with $B+\delta I_n$.

A size-biased complex Gaussian law

Define a probability measure $\nu_1$ on $\mathbb{C}$ by

It is normalized because $\mathbb{E}_{\gamma}|W|^2=1$. The next lemma records both a subgaussian estimate in real coordinates and the exact radial Laplace transform.

Proof. Under the untilted law $\gamma$, the vector $(\sqrt{2}\,\Re W,\sqrt{2}\,\Im W)$ is a standard real Gaussian vector $G=(G_1,G_2)$, while $|W|^2=(G_1^2+G_2^2)/2$. Hence, for every nonnegative measurable function $f$,

Differentiating the standard Gaussian moment-generating function gives

Summing over $j=1,2$ and dividing by 2 yields the equality in (4). Its inequality follows from $1+t/2\leq e^{t/2}$ for $t\geq0$.

Under $\gamma$, the variable $|W|^2$ has density $e^{-x}$ on $[0,\infty)$. The size bias in (3) changes this to $xe^{-x}$. Direct integration gives

and differentiating at $a=0$ gives $\mathbb{E}R=2$.

Proof. Apply (4) to each two-dimensional block of $v$ and multiply the resulting estimates.

An off-diagonal quadratic MGF estimate

The local permanent estimate will separate the diagonal and off-diagonal parts of a quadratic form. The diagonal transform is explicit by (5). The following dimension-free estimate controls the off-diagonal part.

Proof. Choose a random set $\Lambda\subset\{1,\ldots,n\}$ by including each block index independently with probability $1/2$, and define

Because the diagonal blocks of $R$ vanish, every ordered pair $(i,j)$ with $i\ne j$ occurs in this sum with probability $1/4$. Consequently,

For every fixed value of $\Xi$, convexity of the exponential gives

Fix $\Lambda$. Write $a=\Xi_\Lambda$ and $b=\Xi_{\Lambda^c}$, and let $T_\Lambda$ be the rectangular cross-cut block of $R$ for which

For $u\in\mathbb{R}$, conditioning on $a$ and applying Corollary 2.3 to the independent blocks in $b$ yields

Let $g$ be a standard real Gaussian vector of the row dimension of $T_\Lambda$, independent of all other variables. Gaussian linearization and another use of Corollary 2.3 give

Combining (10)–(12), and denoting the singular values of $T_\Lambda$ by $\sigma_1,\ldots,\sigma_m$, gives

provided $4u^2\lVert T_\Lambda\rVert_{\mathrm{op}}^2<1$. For $0\le x\le1/2$, the elementary inequality $-\frac{1}{2}\log(1-x)\le x$ holds. It follows from (13) that, whenever $4u^2\lVert T_\Lambda\rVert_{\mathrm{op}}^2\le1/2$,

The cross-cut block is a rectangular compression of $R$, so

In the decomposition into the coordinates indexed by $\Lambda$ and $\Lambda^{c}$, the two cross-cut blocks of the symmetric matrix $R$ are $T_{\Lambda}$ and $T_{\Lambda}^{\mathsf{T}}$. Thus

Set $u=4s$. The hypothesis (6) implies the condition for (14), and hence

This bound is uniform in $\Lambda$. Taking expectations in (9) and then applying the uniform bound proves (7).

Local stability near the identity

We now combine the exact radial transform and Lemma 3.1. The resulting estimate is local only in operator norm and has no dependence on the dimension.

Independence therefore implies

The elementary inequality $\log(1+x)\ge x-x^2/2$ for $x\ge0$ turns (19) into

It remains to control the off-diagonal factor. Write $K=P+iS$, where $P$ is real symmetric and $S$ is real skew-symmetric. Its realification is

For $\xi_i=(\sqrt{2}\,\Re W_i,\sqrt{2}\,\Im W_i)$ and $\Xi=(\xi_1,\ldots,\xi_n)$, after the harmless orthogonal permutation that groups coordinates by $i$, one has

Let $H=K-\operatorname{diag}(K)$, and let $M_o$ be obtained from $M$ by deleting its diagonal $2\times2$ blocks. Then

up to the same coordinate permutation. The realification identities give

Since $K\succeq0$,

It follows from (21) that

The norm hypothesis and $q=17/16$ now give the exact threshold

Lemma 3.1, applied with $R=M_o$ and $s=-q$, therefore yields

Because $H$ is Hermitian with zero diagonal,

Since $32q=34$, we obtain

Combining (18), (20), and (23), and using

gives

Equivalently,

Finally, applying $\log(1+x)\leq x$ to the eigenvalues of $K$ gives $\log\det(I_n+K)\leq\operatorname{tr}(K)$. Together with (17), this implies

which is (16).

Loewner comparison and the global estimate

For completeness, we first prove the monotonicity used in the source paper as Lemma 2.8 [1].

Proof of Theorem 1.3. Set $D=I_n-A$, so that $0\preceq D\preceq I_n$, and choose

Lemma 5.2 gives $A\preceq B$. Furthermore,

so Theorem 4.1 applies. Since $D^2\preceq D$,

Therefore,

By Lemma 5.1,

Proof of Corollary 1.4. The trace hypothesis gives $\operatorname{tr}(I_n-A)\ge\varepsilon n$, so Theorem 1.3 implies

The function $x\mapsto e^{-x/68}$ is convex. On $[0,1]$, it therefore lies below the chord joining its endpoint values:

Raising this scalar inequality to the $n$th power proves the result.

Examples and remarks

Example 6.1 (Diagonal contractions). For $A=\operatorname{diag}(a_1,\ldots,a_n)$ with $0\le a_i\le1$,

Here the first inequality is the scalar bound $\log a\le a-1$, with the case $a=0$ understood by continuity. Thus the trace deficit is the natural first-order quantity already in the diagonal case, although the universal constant furnished by the noncommutative argument is smaller.

Example 6.2 (A restriction on the universal constant). The rank-one projection

has eigenvalues zero and one, $\operatorname{per}(P)=1/4+1/4=1/2$, and $\operatorname{tr}(I_2-P)=1$. For the block diagonal contraction consisting of $m$ copies of $P$, a nonzero permutation term must preserve each block. The permanent is therefore $2^{-m}$, while the trace deficit is $m$. Consequently any universal inequality $\operatorname{per}(A)\le e^{-\kappa\operatorname{tr}(I-A)}$ must have $\kappa\le\log2$. In particular, the diagonal-case constant one does not extend to all PSD contractions.