Mathematical Programming
https://doi.org/10.1007/s10107-021-01616-3
SHORT COMMUNICATION

Series A

Maximizing products of linear forms, and the permanent of
positive semidefinite matrices
Chenyang Yuan1· Pablo A. Parrilo1

Received: 11 April 2020 / Accepted: 4 January 2021
© Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2021

Abstract
We study the convex relaxation of a polynomial optimization problem, maximizing
a product of linear forms over the complex sphere. We show that this convex program is also a relaxation of the permanent of Hermitian positive semidefinite (HPSD)
matrices. By analyzing a constructive randomized rounding algorithm, we obtain an
improved multiplicative approximation factor to the permanent of HPSD matrices, aswell as computationally efficient certificates for this approximation. We also propose
an analog of van der Waerden’s conjecture for HPSD matrices, where the polynomial
optimization problem is interpreted as a relaxation of the permanent.

1 Introduction
We study the problem√ of maximizing a product of linear forms on the complex (n −1)sphere of radius n:r (A) ≡ max

x2 =nn|x, vi |2 ,

(1)

i=1

where A = V † V and vi are the columns of V . We show that the natural convex
relaxation of (1),

max

n

vi† Pvi s.t. Tr(P) = n, P  0,

(2)

i=1

B Chenyang Yuan
ycy@mit.edu

Pablo A. Parrilo
parrilo@mit.edu
1

Massachusetts Institute of Technology, Cambridge, MA, USA

123

C. Yuan, P. A. Parrilo

is also a relaxation of the permanent of A, which is defined byper(A) =n

Ai,σ (i) ,(3)

σ ∈Sn i=1

where the sum is over all n! permutations of n elements. Computing the permanent
exactly is #P-hard [14], and approximation efforts have been focused on classes ofmatrices with computationally efficient certificates of permanent non-negativity. For
matrices with non-negative entries, [9] gave a randomized algorithm achieving a (1 +)-approximation. There has been recent interest in approximating the permanent of
HPSD matrices due to their applications in quantum information [7]. The work by [1]gave the first polynomial-time algorithm for approximating the permanent of HPSD
matrices with a simply exponential multiplicative approximation factor of nn!n e−nγ ,where γ ≈ 0.577 is the Euler–Mascheroni constant. Their algorithm is based on thefollowing convex program relaxation of the permanent.
Definition 1.1 Given a HPSD matrix A ∈ Cn×n , we define rel(A) as the solution tothe optimization problem:
rel(A) ≡n
min i=1
Diis.t. A D, D is diagonal(4)

In this paper, we show that rel(A) is equivalent to the convex relaxation (2). Our
main result, Theorem 4.4, uses this connection between the polynomial optimization
problem (1) and per(A) to provide a new analysis of the approximation of per(A) interms of the rank of the optimal solution to (2). By bounding this rank, we prove an
improved approximation factor for all finite n:Corollary 1.2 Given a HPSD matrix A ∈ Cn×n , rel(A) is an nn!n e−n L r -approximation
to per(A):n! −n L rerel(A) ≤ per(A) ≤ rel(A)nn√where r = O( n), L r = Hr −1 − log(r ), and Hr = rk=1 k1 is the r -th harmonic
number.
From the definition of the Euler–Mascheroni constant, limn→∞ L r = γ . For any finite
n, L r < γ and thus nn!n e−n L r > nn!n e−nγ . More precisely, using Proposition A.1, we√
can show that this is a e O( n) multiplicative improvement. [1] also constructed a seriesof matrices Ak such that (rel(Ak )/ per(Ak )))1/n → e1+γ as k → ∞. However since
this result only rules out improvements on the order of e O(n) , it does not contradict
Corollary 1.2.
In Sect. 3 we analyze the convex relaxation of (1), describe a rounding procedureand prove its approximation factor. In particular we prove thate−n L r rel(A) ≤ r (A) ≤ rel(A).

123

Maximizing products of linear forms, and the permanent. . .

In Sect. 4 we prove Theorem 4.4. We first show that the convex relaxation of r (A)is equivalent to rel(A). Then using the vector produced by the rounding procedure of
the relaxation, we construct a rank-1 matrix whose permanent lower bounds per(A),thus showing that rel(A) also well-approximates per(A). Note that in [1] only theexistence of this rank-1 matrix is shown, but in our analysis we provide an explicit
construction of a rank-1 matrix whose permanent lower bounds per(A). This combinedwith the diagonal matrix in (4) whose permanent upper-bounds per(A) certifies theapproximation. In Sect. 5 we explore reasons why the convex relaxation of (1) isequivalent to rel(A). We conjecture that (1) is itself a nn!n approximation to per(A),explain why it is an analogue of van der Waerden’s conjecture, and show that it is
implied by another long-standing permanent conjecture.

2 Preliminaries
For any x ∈ C, let x ∗ be its complex conjugate, and |x|2 = x x ∗ . For any matrix A ∈Cn×m , let A† = (A∗ )T be its conjugate transpose. Given a, b ∈ Cn , let a, b = a † b
Let SC (n) = {x ∈be the inner product on the Hilbert space Cn , and a2 = a, a. √Cn | x2 = n} be the complex sphere in n dimensions of radius n. A matrix A is
Hermitian if A = A† , and is Hermitian positive semidefinite (HPSD) if in additionx † Ax ≥ 0 for all x ∈ Cn . We can also denote this as A  0. The  operator induces
a partial order called the Löwner order, where A  B if A − B  0. If A  0,
it can be factorized as A = L † L, where L ∈ Cn×n (for example by the Cholesky
decomposition).
2.1 Circularly-symmetric gaussian random variables
In this paper we will use a few results involving vectors of circularly-symmetric valued
Gaussian variables.
Definition 2.1 (Circularly-symmetric Gaussian random vector) The complex-valued
Gaussian random variable Z = Z r + i Z c is circularly-symmetric if Z r and Z c are
i.i.d. drawn from N (0, 21 ). The random vector Z = [Z 1 , . . . , Z n ]T is drawn from the
distribution CN (0, ) if Z i are i.i.d. circularly-symmetric Gaussians and E[ZZ† ] =.
The name circularly-symmetric comes from the fact that Z is invariant under rotationsin the complex plane, meaning that eiθ Z has the same distribution as Z for all real θ . All
complex multivariate Gaussians in this paper are circularly symmetric. Similar to realmultivariate Gaussians, a linear transform on the random vector induces a congruencetransform on the covariance matrix.
Proposition 2.2 (Linear transformations of complex multivariate Gaussians) Given
Z ∼ CN (0, ) and any complex matrix A, AZ is also circularly symmetric and has
the distribution CN (0, A A† ).

123

C. Yuan, P. A. Parrilo

The proof of this proposition and more about complex multivariate Gaussians can befound in [6]. In particular, this tells us that Z ∼ CN (0, I ) is invariant under unitarytransformations.
In the analysis of our rounding procedure, we use some results about the gamma
distribution.
Fact 2.3 (Expectation of log of gamma random variable) Let X ∼ Gamma(α, β) be
drawn from the gamma distribution, with density p(x; α, β) = (α)−1 β α x α−1 e−βx .
ThenE[log X ] = ψ(α) − log(β),
where ψ(x) = ddx log (x) is the digamma function.
This follows from the fact that the gamma distribution is an exponential family, andlog x is a sufficient statistic (see section 2.2 of [10] for more details). Next we provea useful identity.

Fact 2.4 Let [z 1 , . . . , zr ]T ∼ CN (0, Ir ), Hn = nk=1 k1 be the n-th harmonic numberand γ = limn→∞ (Hn − log n) be the Euler-Mascheroni constant. Then1|z i |2
E log
r
r


= Hr −1 − γ − log(r ) = L r − γ .

i=1

r
2
Proof
of freei=1 2 |z i | is distributed as a chi-squared distribution with 2r degrees
r
2
|z
=
dom, which is equivalent to Gamma r , 21 . Using Fact 2.3, E log
i=1 i |
ψ(r ). Since ψ(1) = −γ by Gauss’s digamma theorem, the recurrence relation of thegamma function shows that for all positive integers r , ψ(r ) = Hr −1 − γ .
Integrating a homogeneous polynomial over the complex sphere is equivalent to taking
its expectation with respect to x ∼ CN (0, I ), up to a correction factor. This factor canbe found by computing moments of a chi-squared distribution.
Fact 2.5 Let p(x) be a degree d homogeneous polynomial in n variables, μn (x) be
the measure associated with the random variable x ∼ CN (0, In ). Then| p(x)|2 dμn (x) =Cn(n + d − 1)!
n n (n − 1)!

| p(x)|2 d x.
SC (n)

2.2 Permanent of HPSD matrices
One remarkable property of the permanent of HPSD matrices is that it respects the
Löwner order. See section 2.3 of [1] for a proof.
Proposition 2.6 If A  B  0, then per(A) ≥ per(B) ≥ 0.
We can efficiently compute the permanent of rank-1 matrices. The following proposition immediately follows from the definition of the permanent in (3).

123Maximizing products of linear forms, and the permanent. . .

Proposition 2.7 For any v ∈ Cn , per(vv † ) = n!

n2i=1 |vi | .

The permanent of HPSD matrices also has an integral representation using complex
multivariate Gaussians. See section 4 of [3] for more details and a proof.
variable x ∼Proposition 2.8 Let μn (x) be the measure associated with the random√
CN (0, In ), and SC (n) be the complex (n − 1)-sphere with radius n. For any HPSD
A = V † V , where vi are the columns of V ,per(A) =n
Cn i=1(2n − 1)!
|vi , x| dμn (x) = nn (n − 1)!

n2|vi , x|2 d x.

SC (n) i=1

3 Convex relaxation and rounding
In this section we analyze the convex relaxation (2) and a natural rounding algorithm
for maximizing a product of linear forms over the complex sphere.
Remark 3.1 Both r (A) and rel(A) are independent of the factorization of A = V † V .
This is because any two different factorizations of A = V1† V1 = V2† V2 are related bya unitary transform V1 = U V2 for some unitary matrix U 1 . This induces a change ofvariables x → U † x in (1) but does not change the value of r (A).
Lemma 3.2 Any A  0 can be factorized as A = V † V , where vi are the columns of
V . Consider the following pair of convex programs:⎧
V Diag(α)V † λIn⎨n∗nμ (A) ≡ min λ s.t.
(5)α≥1
⎩ i=1 i>0αi⎧n
⎨ Tr(P) = nν ∗ (A) ≡ max
vi† Pvi s.t.
(6)
P†
=P
⎩
P
0
i=1
Then r (A) ≤ ν ∗ (A) = μ∗ (A), thus the convex programs are relaxations of r (A) (seeEq. (1)).
Proof If we add a rank-1 constraint to (6), we get (1), showing that r (A) ≤ ν ∗ (A).
Suppose we have feasible solutions λ, αi and P to (5) and (6) respectively. Thennnvi† Pvi =αi vi† Pvi ≤
i=1

i=1



1
αi vi† Pvi
n
n

i=1

n


≤

Tr(P)λn

n= λn ,

showing weak duality, i.e. ν ∗ (A) ≤ μ∗ (A). Since (6) comes from taking the dualof (5) and has a strictly feasible solution, strong duality holds, i.e. ν ∗ (A) = μ∗ (A).
If P = x x † is rank-1, then vi† Pvi = |x, vi |2 , thus in (6) the variable P can beinterpreted as the convex relaxation of the rank-1 constraint in (1).

1 We are assuming here that V , V ∈ Cn×n even if rank(A) < n, padding with zero columns if necessary.
1 2

123

C. Yuan, P. A. Parrilo

Although (5) and (6) have non-linear objective functions and are not semidefinite
programs in standard form, the geometric mean constraint/objective in them can beconverted to second-order conic constraints after a change of variables [11]. They
can also be solved efficiently with convex programming techniques such as interior
point methods (see [15]). Our main result (Theorem 4.4) is proven with the following
analysis of a randomized rounding procedure to the convex relaxation of the productof linear forms. This produces a vector that gives an e−n L r -approximation to (1).
Theorem 3.3 Given a matrix A  0, let ν ∗ (A) be the optimum of (6), with optimum
achieved by P ∗ = UU † . Suppose P ∗ has rank r , therefore U ∈ Cn×r . If we produce
a vector y ∈ SC (n) using the following procedure:
1. Sample z ∈ Cr uniformly at random from the complex multivariate Gaussian
CN (0, Ir )√2. Return the normalized vector y = nU z/ U z
Recalling that L r = Hr −1 − log r , we have the following lower bound on the expectedvalue of the objective:
E

 n


z


|vi , y|2≥ e−n L r ν ∗ (A)i=1

Proof We use Jensen’s inequality to bound the expectation:E n
 n |vi , U z|2zU z2i=1

= E exp

 n


z


(log |vi , U z|2 − log z † U † U z + log n)

i=1

 n


2
† †
≥ exp
(E log |vi , U z| − E log z U U z + log n)
i=1

z

z

We can exactly compute the first expectation:
 2


 


E log |vi , U z|2 = log vi† UU † vi + E log  U † vi / U † vi  , z zz††= log vi UU vi + E log |z 1 |2z

= log vi† P ∗ vi − γ
Where the first equality follows from normalizing U † vi , the second equality follows fromthe rotational symmetry of the complex multivariate Gaussian sinceU † vi / U † vi  is a unit vector, and the third equality follows from Fact 2.4 for r = 1.
Let λ1 , . . . , λr be the eigenvalues of U † U . Then
E log z † U † U z = E log
z

123

z

 r

i=1




λi |z i |2

≤ E logzn|z i |2rri=1

= Hr −1 − γ + log

n 
r

,

Maximizing products of linear forms, and the permanent. . .

where the first equality follows from the invariance of the complex multivariate Gaussian under unitary transformations (see Proposition 2.2), and the second
equality follows from Fact 2.4. Next we prove the inequality. Since Tr(U † U ) == n, λ = (λ1 , . . . , λr ) lies on the scaled r -simplex. The function λ →Tr(P ∗ ) r2
is concave on the scaled r -simplex and is symmetric with
Ez logi=1 λi |z i |respect to all permutations of the coordinates of λ, therefore it is maximized when allnvi† P ∗ vi =λi = nr . Finally we put the above together, along with the fact that i=1∗ν (A), to prove the theorem.

4 Approximating the permanent
We present a new analysis of the relaxation of the permanent of HPSD matrices in [1].
First we show that rel(A) is a relaxation of per(A).
Lemma 4.1 Given any A  0,
per(A) ≤ rel(A).
Proof Using the monotonicity of the permanent with respect to the Löwner order(Proposition
D implies that per(A) ≤ per(D). Since D is diagonal,
 2.6), A
per(D) = i Dii , showing that the permanent is always bounded by rel(A).
Next we show that rel(A) is equivalent to the convex relaxation of (1).
Lemma 4.2 Recall that μ∗ (A) = ν ∗ (A) is the optimal value of the convex relaxationin Lemma 3.2. Thenrel(A) = μ∗ (A) = ν ∗ (A).

Proof By a scaling argument, the optimum of (5) is achieved when i αi = 1. Taking−1  V † V = A.
Schur complements, V Diag(α)V † λIn is equivalent to λ Diag(α)
Thus by making the substitution Dii = λ/αi and noting that i Dii = λn , we showthat rel(A) = μ∗ (A).
The following lemma shows that given any vector y ∈ SC (n) returned by the rounding
algorithm, we can construct a lower bound on per(A).
Lemma 4.3 Given HPSD A = V † V ∈ Cn×n , where vi are columns of V , and a vectory ∈ SC (n),n! |vi , y|2 ≤ per(A).
nn
n

i=1

† †
Proof Since y2 = n, yy † n I and V † yy † V nV † V . Thus n −n per(V yy V ) ≤per(V † V ) = per(A). Since V † yy † V is a rank-1 matrix, its permanent is n! i |vi , y|2by Proposition 2.7.



123

C. Yuan, P. A. ParriloNow we can state our result about approximating the permanent of a HPSD matrix.
Theorem 4.4 Given a HPSD matrix A ∈ Cn×n , rel(A) is a relaxation of per(A)computable in polynomial-time by convex programs (5) or (6). Let r be the rank ofP ∗ , the solution to (6). Then rel(A) is an nn!n e−n L r -approximation to per(A):n! −n L rerel(A) ≤ per(A) ≤ rel(A)nn(7)

Next we state a result that we will use to bound the rank of P ∗ .
Lemma 4.5 (Theorem 2.2 in [2]) Suppose there is a non-zero solution X to the systemof equations {X  0, Tr(Ai X ) = bi , i = 1, . . . , d}, where Ai is Hermitian andbi ∈ C. If d < (r + 1)2 , then one can find in polynomial time another solution X 
where rank(X  ) = r .
We can now prove Corollary 1.2.
Proof of Corollary 1.2 Given a solution P to (6), any HPSD matrix P  that satisfy then + 1 equalities Tr(vi vi† P  ) = vi† Pvi and Tr(P  ) = n will have the same objective
value as that of P. Applying Lemma√ 4.5, we can find in polynomial time an optimal
solution P ∗ with rank(P ∗ ) ≤ O( n). We then apply Theorem 4.4.
Finally we prove Theorem 4.4.
Proof of Theorem 4.4 We use the vector y produced in the rounding procedure in Theorem 3.3 to construct a rank-1 matrix V † yy † V . We then compare the permanent of
this matrix to per(A) and rel(A):
 n


2 n!
4
n! −n L r
1 n! −n L r ∗2 3|vi , y| ≤ per(A) ≤ rel(A)erel(A) = n e
ν (A) ≤ n E
n
n
n
n
i=1

1. Apply Lemma 4.2.
2. Apply Theorem 3.3.
n|vi , y|2 . This
3. Lemma 4.3 shows that for any vector y ∈ SC (n), per(A) ≥ nn!n i=1
is also true when taking an expectation of any distribution supported on SC (n).
4. Apply Lemma 4.1.

4.1 Low rank instances
There are structured classes of HPSD matrices where we can prove a priori that therank of P ∗ is low and thus a better approximation ratio can be obtained. For example,
it is easy to show that rank(P ∗ ) ≤ rank(A). Often such instances also have additional
symmetry, such as the class of circulant matrices.

123Maximizing products of linear forms, and the permanent. . .

Fig. 1 Plot of average of rank(P ∗ ) (along with error bars indicating standard deviation) of 50 random
instances as a function of n. A = V † V is constructed by sampling each entry of V ∈ Rn×n from a standard
Gaussian. The theoretical upper bound for rank(P ∗ ) in Lemma 4.5 is also shown for comparison

Corollary 4.6 A square matrix is circulant if each row is cyclically shifted one position
to the right compared to the previous row. If A ∈ Cn×n is HPSD and circulant, thenthere is a solution P ∗ to (6) where rank(P ∗ ) = 1 and we have the boundn!
rel(A) ≤ per(A) ≤ rel(A).
nn
Proof Since A = V † V is circulant it is invariant under the map Ai, j →
A(i+1 mod n),( j+1 mod n) . Suppose we have an optimal solution D ∗ to rel(A) in (4),D ∗ . We then average over all cyclic
where D ∗ is a diagonal matrix satisfying A∗
shifts of D to show that D = λI is also optimal, which corresponds to αi = 1 in (5),with an optimal solution P of (6) satisfying the complementary slackness conditionof Tr(P V V † ) = nλ. This shows that P = vv † is also a solution, where v is a suitable
multiple of the top eigenvector of V V † .
We also observed experimentally that rank(P ∗ ) is small for random A. Figure 1
plots this rank as a function of n, for instances of A drawn from the Gaussian orthogonal∗ensemble.
√ The results suggest that rank(P ) for these random instances grows slower
than O( n).

5 A conjecture
Our analysis of rel(A) was inspired by the optimization problem (1), maximizing a
product of linear forms over the complex sphere. We conjecture that the exact solution
to this optimization problem is a tighter relaxation of the permanent.
Conjecture 5.1 Given A = V † V , where vi are the columns of V , recall that r (A) isthe maximum of a product of linear forms as defined in (1). Thenn!
r (A) ≤ per(A) ≤ r (A).
nn

(8)

123

C. Yuan, P. A. Parrilo

If the matrix A is scaled so that r (A) = 1, then (8) is exactly the same bounds given by
the van der Waerden’s conjecture for doubly stochastic matrices (proved by [4,5,8]).
The lower bound follows from Lemma 4.3, but the upper bound cannot be proven by
naively applying Proposition 2.8 and bounding the integral over the complex sphereby its maximum. However, we can show that the upper bound is implied by anotherconjecture on permanents:
Conjecture 5.2 (Pate’s conjecture [12]) Given any n × n HPSD matrix A, let A ⊗ Jk
be the Kronecker product of A with the k × k all-ones matrix. Thenper(A ⊗ Jk ) ≥ per(A)k (k!)n .

(9)This conjecture has been proved in the case where n = 2, see [16] for a surveyof subsequent progress on this conjecture. Using the integral representation of thepermanent (Proposition 2.8), we can write (9) as:

E

 n


x∼CN (0,In )1/k|vi , x|2k≥ per(A)

i=1

E

 n


x∼CN (0,In )

1/k
|xi |

2k

i=1

Since both expectations are taken over homogeneous polynomials of degree d, we canapply Fact 2.5, take k → ∞ and get:max

x2 =nn|vi , x| ≥ per(A) max
2

i=1

x2 =nn|xi |2 = per(A).

i=1

6 Discussion and conclusion
There are a few interesting directions that stem from this work. For random A (i.e.
drawn from the Gaussian orthogonal ensemble), numericalexperiments in Sect. 4.1√
suggest that rank(P ∗ ) is very small compared to n. It would be interesting to provide concrete bounds on the rank of random instances. One might also ask if we
can construct sequences of matrices Ak of increasing size but with fixed rank r , where(rel(Ak )/ per(Ak ))1/n → e1+L r . This is related to the question called the linear polarization constant of Hilbert spaces, see [13] for such a construction and its analysis.
The main result of this paper uses the connection between the permanent and the
optimization of a product of linear forms over the sphere (1). Although it is natural
to conjecture the hardness of computing r (A), we do not know of any formal results
establishing this. We also proposed Conjecture 5.1 which would explain why thisoptimization problem is intimately related to the permanent. Better understanding of
this problem may lead to further insights about the permanent of HPSD matrices.
Acknowledgements This work was partially supported by NSF AF 1565235.

123

Maximizing products of linear forms, and the permanent. . .

Δr
Δr+1

...

y = x1rr+1

r+2

Fig. 2 Illustration of the asymptotics of L r . r is the area between the curve y = x1 and the rectangle of
1 . The lower dotted lines are tangent to the curve at r + 1 and r + 2 respectively
height r +1

Appendix: Asymptotics of the approximation factor
Proposition A.1 For all positive integers r ,r +2
1< γ − Lr <.
2r
2r (r + 1)

(10)

Proof It is easy to see that (10) follows from1
1
< Hn − log(r ) − γ < .
2(r + 1)2r

From Fig. 2, we can see that Hn − log(r ) − γ = ∞k=r k . The upper bound is given
by computing the sum of the areas of the larger triangles:
∞


k <

k=r


∞

1 1
k=r

2

1
−
k
k+1


=

∞

k=r

1
1
=
2k(k + 1)
2r

The lower bound is given by computing the sum of the areas of the smaller triangles:
∞

k=r

k >

∞

1

∞

k=r

k=r


1
1
1
=
>
2
2 (k + 1)
2(k + 1)(k + 2)
2(r + 1)

References
1. Ai, W., Huang, Y., Zhang, S.: On the low rank solutions for linear matrix inequalities. Math. Oper.
Res. 33(4), 965–975 (2008)
2. Anari, N., Gurvits, L., Gharan, S.O., Saberi, A.: Simply exponential approximation of the permanentof positive semidefinite matrices. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer
Science (FOCS), pp. 914–925 (2017)123

C. Yuan, P. A. Parrilo
3. Barvinok, A.: Integration and optimization of multivariate polynomials by restriction onto a random
subspace. Found. Comput. Math. 7(2), 229–244 (2007)
4. Egorychev, G.P.: The solution of van der Waerden’s problem for permanents. Adv. Math. 42(3), 299–
305 (1981)
5. Falikman, D.I.: Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic
matrix. Math. Notes Acad. Sci. USSR 29(6), 475–479 (1981)
6. Gallager, R.G.: Circularly-symmetric gaussian random vectors. http://www.rle.mit.edu/rgallager/
documents/CircSymGauss.pdf
7. Grier, D., Schaeffer, L.: New hardness results for the permanent using linear optics. In: Proceedingsof the 33rd Computational Complexity Conference (San Diego, CA), CCC ’18, Schloss Dagstuhl–
Leibniz-Zentrum fuer Informatik, June 2018, pp. 1–29
8. Gurvits, L.: Van der Waerden/Schrijver-Valiant like Conjectures and Stable (aka Hyperbolic) Homogeneous Polynomials: One Theorem for all. Electron. J. Combin. 15 (2008)
9. Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanentof a matrix with nonnegative entries. J. ACM 51(4), 671–697 (2004)
10. Keener, R.W.: Theoretical Statistics: Topics for a Core Course. Springer Texts in Statistics. Springer,
New York (2010)
11. Lobo, M.S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming.
Linear Algebra Its Appl. 284(1–3), 193–228 (1998)
12. Pappas, A., Révész, S.G.: Linear polarization constants of Hilbert spaces. J. Math. Anal. Appl. 300(1),129–146 (2004)
13. Pate, T.H.: An inequality involving permanents of certain direct products. Linear Algebra Its Appl. 57,
147–155 (1984)
14. Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8(2), 189–201 (1979)
15. Vandenberghe, L., Boyd, S., Wu, S.-P.: Determinant maximization with linear matrix inequality constraints. SIAM J. Matrix Anal. Appl. 19(2), 499–533 (1998)
16. Zhang, F.: An update on a few permanent conjectures. Spec. Matrices 4(1) (2016)
Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps
and institutional affiliations.

123