Pfaffians, hafnians and products of real linear functionals
Pfa�ans, hafnians and produ
ts of real linear
fun
tionals
Péter E. Frenkel
Alfréd Rényi Institute of Mathemati
s
Hungarian A
ademy of S
ien
es
P.O.B. 127, 1364 Budapest, Hungary
frenkelp�renyi.hu
Abstra
t
We prove pfa�an and hafnian versions of Lieb's inequalities on deter-
minants and permanents of positive semi-de�nite matri
es. We use the
hafnian inequality to improve the lower bound of Révész and Sarantopou-
los on the norm of a produ
t of linear fun
tionals on a real Eu
lidean
spa
e (this subje
t is sometimes 
alled the `real linear polarization 
on-
stant' problem).
Mathemati
s Subje
t Classi�
ation: 46C05, 15A15
Keywords: polarization 
onstant, real Eu
lidean spa
e, hafnian, pfaf-
�an, positive semi-de�nite matrix
-1. Introdu
tion
The 
ontents of this paper are as follows. In Se
tion 0, we sket
h one part of
the histori
 ba
kground: 
lassi
al inequalities on determinants and permanents
of positive semi-de�nite matri
es. In Se
tion 1, we prove pfa�an and hafnian
versions of these inequalities, and we formulate Conje
ture 1.5, another hafnian
inequality. In Se
tion 2, we apply the hafnian inequality of Theorem 1.4 to
our main goal: improving the lower bound of Révész and Sarantopoulos on the
norm of a produ
t of linear fun
tionals on a real Eu
lidean spa
e (this subje
t
is sometimes 
alled the `real linear polarization 
onstant' problem, its history is
sket
hed at the end of the paper). This is a
hieved in Theorem 2.3. We point
out that Conje
ture 1.5 would be su�
ient to 
ompletely settle the real linear
polarization 
onstant problem.
Partially supported by OTKA grants T 046365, K 61116 and NK 72523.
http://arxiv.org/abs/0704.0028v2
0. Old inequalities on determinants and perma-
nents
Re
all that the determinant and the permanent of an n× n matrix A = (ai,j)
are de�ned by
detA =
(−1)π
ai,π(i), per A =
ai,π(i),
where Sn is the symmetri
 group on n elements. Throughout this se
tion, we
assume that A is a positive semi-de�nite Hermitian n × n matrix (we write
A ≥ 0). For su
h A, Hadamard proved that
detA ≤
ai,i,
with equality if and only if A has a zero row or is a diagonal matrix. Fis
her
generalized this to
detA ≤ detA′ · detA′′
B∗ A′′
≥ 0, (1)
with equality if and only if detA′ · detA′′ · B = 0.
Con
erning the permanent of a positive semi-de�nite matrix, Mar
us [Mar1,
Mar2℄ proved that
per A ≥
ai,i, (2)
with equality if and only if A has a zero row or is a diagonal matrix. Lieb [L℄
generalized this to
per A ≥ per A′ · per A′′ (3)
for A as in (1), with equality if and only if A has a zero row or B = 0. Moreover,
he proved that in the polynomial P (λ) of degree n′ (=size of A′) de�ned by
P (λ) = per
λA′ B
B∗ A′′
all 
oe�
ients ct are real and non-negative. This is indeed a stronger theorem
sin
e it implies
per A = P (1) =
ct ≥ cn′ = per A′ · per A′′.
�okovi¢ [D, Mi℄ gave a simple proof of Lieb's inequalities, and showed also that if
A′ and A′′ are positive de�nite then cn′−t = 0 if and only if all subpermanents of
B of order t vanish. Lieb [L℄ also states an analogous (and analogously provable)
theorem for determinants: for A as in (1), let
D(λ) = det
λA′ B
B∗ A′′
If detA′ · detA′′ = 0, then D(λ) = 0. If A′ and A′′ are positive de�nite, then
(−1)tdn′−t is positive for t ≤ rk B and is zero for t > rk B.
Remark. In all of Lieb's inequalities mentioned above, the 
ondition that
the matrix A is positive semi-de�nite 
an be repla
ed by the weaker 
ondition
that the diagonal blo
ks A′ and A′′ are positive semi-de�nite. The proof goes
through virtually un
hanged. Alternatively, this stronger form of the inequali-
ties 
an be easily dedu
ed from the seemingly weaker form above.
1 New inequalities on pfa�ans and hafnians
For an n × n matrix A = (ai,j) and subsets S, T of N := {1, . . . , n}, we write
AS,T := (ai,j)i∈S,j∈T . If |T | = 2t is even, we write
(−1)T := (−1)t+
1.1 Pfa�ans
As far as the appli
ations in Se
tion 2 are 
on
erned, this subse
tion may be
skipped.
Re
all that the pfa�an of a 2n × 2n antisymmetri
 matrix C = (ci,j) is
de�ned by
pf C =
π∈S2n
(−1)πcπ(1),π(2) · · · cπ(2n−1),π(2n).
We have (pf C)
= detC.
For antisymmetri
 A and symmetri
 B, both of size n× n, we 
onsider the
polynomial
(−1)⌊n/2⌋pf
−λA B
⌊n/2⌋
Theorem 1.1 Let A and B be real n×n matri
es with A antisymmetri
 and B
symmetri
. If B is positive semi-de�nite, then pt ≥ 0 for all t. If B is positive
de�nite, then pt > 0 for t ≤ (rk A)/2 and pt = 0 for t > (rk A)/2.
Proof. If B = (bi,j) is positive semi-de�nite, then there exist ve
tors x1, . . . , xn
in a real Eu
lidean spa
e V su
h that (xi, xj) = bi,j. Re
all that in the exterior
tensor algebra
V a positive de�nite inner produ
t (and the 
orresponding
Eu
lidean norm) is de�ned by
:= det((vi, wj)).
We have
|S|=2t
|T |=2t
(−1)S(−1)Tpf AS,S · pf AT,T · detBN\S,N\T =
|S|=2t
|T |=2t
(−1)Spf AS,S ·
xi, (−1)Tpf AT,T ·
j 6∈T
|S|=2t
(−1)Spf AS,S ·
Assume that B is positive de�nite. Then the ve
tors xi are linearly independent.
It follows that the tensors
i6∈S xi are also linearly independent as S runs over
the subsets of N . Thus pt = 0 if and only if pf AS,S = 0 for all |S| = 2t, i.e., if
and only if 2t > rk A. �
Theorem 1.2 Let A and B be real n × n matri
es with A antisymmetri
 and
B symmetri
. Let λ ≥ 0. If B is positive semi-de�nite, then
(−1)⌊n/2⌋pf
−λA B
≥ detB.
If B is positive de�nite, then equality o

urs if and only if λA = 0.
Proof. The left hand side is
p0 + p1λ+ · · ·+ p⌊n/2⌋λ⌊n/2⌋.
The right hand side is p0. �
I am grateful to the anonymous referee of this paper for the idea of the
following alternative proof of Theorems 1.1 and 1.2. We may assume B > 0,
sin
e every positive semi-de�nite matrix is a limit of positive de�nite ones.
The matrix B−1/2AB−1/2 being real and antisymmetri
, there exists a unitary
matrix U su
h that D := U−1B−1/2AB−1/2U is diagonal with purely imaginary
eigenvalues a1
−1, . . . , an
−1. The real multiset {a1, . . . , an} is invariant
under a ↔ −a. We have
= det
−λA B
= det
BUDU−1
BUDU−1
= det
−λD 1
0 U−1
= det
−1 ai
= detB2 ·
(1 + a2iλ).
Extra
ting square roots, and 
hoosing the sign in a

ordan
e with p0 = +detB,
we get
t = (−1)⌊n/2⌋pf
−λA B
= detB ·
(1 + a2iλ),
when
e both theorems immediately follow, sin
e detB > 0.
1.2 Hafnians
Re
all that the hafnian of a 2n× 2n symmetri
 matrix C = (ci,j) is de�ned by
haf C =
π∈S2n
cπ(1),π(2) · · · cπ(2n−1),π(2n).
For symmetri
 A and B, both of size n× n, we 
onsider the polynomial
⌊n/2⌋
Theorem 1.3 Let A and B be symmetri
 real n× n matri
es. If B is positive
semi-de�nite, then ht ≥ 0 for all t. If B is positive de�nite, then ht = 0 if and
only if all 2t× 2t subhafnians of A vanish.
Proof. If B = (bi,j) is positive semi-de�nite, then there exist ve
tors x1, . . . , xn
in a real Eu
lidean spa
e V su
h that (xi, xj) = bi,j . Re
all [Mar1, Mar2, MN,
Mi℄ that in the symmetri
 tensor algebra SV a positive de�nite inner produ
t
(and the 
orresponding Eu
lidean norm) is de�ned by
:= per ((vi, wj)).
We have
|S|=2t
|T |=2t
haf AS,S · haf AT,T · per BN\S,N\T =
|S|=2t
haf AS,S ·
Assume that B is positive de�nite. Then the ve
tors xi are linearly independent.
It follows that the tensors
i6∈S xi are also linearly independent as S runs over
the subsets of N . Thus ht = 0 if and only if haf AS,S = 0 for all |S| = 2t. �
Theorem 1.4 Let A and B be symmetri
 real n× n matri
es. Let λ ≥ 0. If B
is positive semi-de�nite, then
≥ per B.
If B is positive de�nite, then equality o

urs if and only if A is a diagonal matrix
or λ = 0.
Proof. The left hand side is
h0 + h1λ+ · · ·+ h⌊n/2⌋λ⌊n/2⌋.
The right hand side is h0. �
Setting A = B and λ = 1, and 
ombining with Mar
us's inequality (2), we
arrive at 
ase p = 1 of
Conje
ture 1.5 If A = (ai,j) is a positive semi-de�nite symmetri
 real n× n
matrix, then the hafnian of the 2pn× 2pn matrix 
onsisting of 2p× 2p blo
ks A
is at least (2p− 1)!!n
i,i, with equality if and only if A has a zero row or is
a diagonal matrix.
2 Produ
ts of real linear fun
tionals
In this se
tion, we apply Theorem 1.4 to produ
ts of jointly normal random
variables and then to produ
ts of real linear fun
tionals, whi
h was the main
motivation for this work. The ideas in this se
tion are analogous to those that
Arias-de-Reyna [A℄ used in the 
omplex 
ase.
Let ξ1, . . . , ξd denote independent random variables with standard Gaussian
distribution, i.e., with joint density fun
tion (2π)−d/2 exp(−|ξ|2/2), where |ξ|2 =
ξ2k.We write Ef(ξ) for the expe
tation of a fun
tion f = f(ξ) = f(ξ1, . . . , ξd).
Re
all that
k = (2p− 1)!! = (2p− 1)(2p− 3) · · · 3 · 1
for k = 1, . . . , d (easy indu
tive proof via integration by parts), and thus
(2pk − 1)!!.
, we write (·, ·) for the standard Eu
lidean inner produ
t. We re
all
the well-known [B2, G, S, Z℄
Wi
k formula. Let x1, . . . , xn be ve
tors in R
with Gram matrix A =
((xi, xj)). Then
(xi, ξ) = haf A. (4)
(For odd n, we de�ne haf A = 0.)
Proof. Both sides are multilinear in the xi, so we may assume that ea
h xi is
an element of the standard orthonormal basis e1, . . . , ed. If there is an ek that
o

urs an odd number of times among the xi, then both sides are zero. If ea
h
ek o

urs 2pk times, then the left hand side is E
k=1 ξ
k , and the right hand
side is
k=1(2pk − 1)!!, whi
h are equal. �
The following theorems are easy 
orollaries of Theorem 1.4 together with
the Wi
k formula (4) and Mar
us's theorem (2).
Theorem 2.1 If X1, . . . , Xn are jointly normal random variables with zero
expe
tation, then
X21 · · ·X2n
≥ EX21 · · ·EX2n.
Equality holds if and only if they are independent or at least one of them is
almost surely zero.
Proof. The variables 
an be written as Xi = (xi, ξ) with ξ of standard normal
distribution and the xi 
onstant ve
tors with a positive semi-de�nite Gram
matrix A = (ai,j) = ((xi, xj)). Then
X2i = E
(xi, ξ)
= haf
≥ per A ≥
ai,i =
E(xi, ξ)
EX2i ,
with equality if and only if A is a diagonal matrix or has a zero row, i.e., the xi
are pairwise orthogonal or at least one of them is zero. �
The generalization of Theorem 2.1 to an arbitrary even exponent 2p is equiv-
alent to Conje
ture 1.5.
Theorem 2.2 For any x1, . . . , xn ∈ Rd, |xi| = 1, the average of
(xi, ξ)
the unit sphere {ξ ∈ Rd : |ξ| = 1} is at least
Γ(d/2)
2nΓ(d/2 + n)
(d− 2)!!
(d+ 2n− 2)!!
d(d+ 2)(d+ 4) . . . (d+ 2n− 2)
with equality if and only if the ve
tors xi are pairwise orthogonal.
Proof. The average on the unit sphere is the 
onstant in the theorem times
the expe
tation w.r.t. the standard Gaussian measure (see e.g. [B1℄). By The-
orem 2.1, the latter expe
tation is minimal if and only if the xi are pairwise
orthogonal, in whi
h 
ase it is 1. �
Theorem 2.3 For real linear fun
tionals fi on a real Eu
lidean spa
e,
||f1 · · · fn|| ≥
||f1|| · · · ||fn||
n(n+ 2)(n+ 4) · · · (3n− 2)
Here || · || means supremum of the absolute value on the unit sphere. In the
in�nite-dimensional 
ase, fun
tionals with in�nite norm may be allowed. Then
the 
onvention 0 · ∞ = 0 should be used on the right hand side.
Proof. We may assume that the spa
e is R
with d ≤ n, and the fun
tionals are
given by fi(ξ) = (xi, ξ) with ||fi|| = |xi| = 1. Then ||f1 · · · fn||2 is at least the
average of
f2i (ξ) =
(xi, ξ)
on the unit sphere, whi
h by Theorem 2.2 and
d ≤ n is at least 1/(n(n+ 2)(n+ 4) · · · (3n− 2)). �
It is an unsolved problem, raised by Benítez, Sarantopoulos and Tonge [BST℄
(1998), whether Theorem 2.3 is true with nn under the square root sign in the
denominator on the right hand side. This is 
alled the `real linear polarization

onstant' problem. In the 
omplex 
ase, the a�rmative answer was proved by
Arias-de-Reyna [A℄ in 1998, based on the 
omplex analog of the Wi
k formula
[A, B2, G℄ and on Lieb's inequality (3).
Keith Ball [Ball℄ gave another proof
of the a�rmative answer in the 
omplex 
ase by solving the 
omplex plank
problem.
In the real 
ase, the a�rmative answer for n ≤ 5 was proved by Pappas and
Révész [PR℄ in 2004. For general n, the best estimate known before the present
paper was that of Révész and Sarantopoulos [RS℄ (2004), based on results of
[MST℄, with (2n)n/4 under the square root sign. See [Mat1, Mat2, MM, R℄ for
a

ounts on this and related questions. Note that
n(n+ 2)(n+ 4) · · · (3n− 2) =
= exp (logn+ log(n+ 2) + log(n+ 4) + · · ·+ log(3n− 2)) <
< exp
log u · du
= exp
[u(log u− 1)]3nn /2
= exp((3n log 3n− 3n− n logn+ n)/2) =
= exp
n(2 logn+ 3 log 3− 2)
and 3
3/e < 3 · 1.8/2.7 = 2, so Theorem 2.3 is an improvement. Note also that
the statement with nn under the square root sign would follow from Conje
-
ture 1.5.
A
knowledgements
I am grateful to Péter Major, Máté Matol
si and Szilárd Révész for helpful
dis
ussions, and to the anonymous referee for useful 
omments.
Referen
es
[A℄ J. Arias-de-Reyna, Gaussian variables, polynomials and permanents, Lin.
Alg. Appl. 285 (1998), 107�114.
The referee of the present paper 
alled my attention to the fa
t that Arias-de-Reyna used
only the spe
ial 
ase of (3) where the matrix A
is of rank 1. This is mu
h simpler than (3) in
general, it 
an be proved essentially by the argument Mar
us used in [Mar1, Mar2℄ to prove
the even more spe
ial 
ase n
= 1, whi
h still implies inequality (2).
[Ball℄ K. M. Ball, The 
omplex plank problem, Bull. London. Math. So
. 33
(2001), 433�442.
[B1℄ A. Barvinok, Estimating L∞ norms by L2k norms for fun
tions on orbits,
Found. Comput. Math. 2 (2002), 393�412.
[B2℄ A. Barvinok, Integration and optimization of multivariate polynomials by
restri
tion onto a random subspa
e, arXiv preprint: math.OC/0502298
[BST℄ C. Benítez, Y. Sarantopoulos, A. Tonge, Lower bounds for norms of
produ
ts of polynomials, Math. Pro
. Camb. Phil. So
. 124 (1998), 395�408.
[D℄ D. �. �okovi¢, Simple proof of a theorem on permanents, Glasgow Math. J.
10 (1969), 52�54.
[G℄ L. Gurvits, Classi
al 
omplexity and quantum entanglement, J. Comput.
System S
i. 69 (2004), no. 3, 448�484.
[L℄ E. H. Lieb, Proofs of some 
onje
tures on permanents, J. Math. Me
h. 16
(1966), 127�134.
[Mar1℄ M. Mar
us, The permanent analogue of the Hadamard determinant the-
orem, Bull. Amer. Math. So
. 69 (1963), 494�496.
[Mar2℄ M. Mar
us, The Hadamard theorem for permanents, Pro
. Amer. Math.
So
. 15 (1964), 967�973.
[MN℄ M. Mar
us, M. Newman, The permanent fun
tion as an inner produ
t,
Bull. Amer. Math. So
. 67 (1961), 223�224.
[Mat1℄ M. Matol
si, A geometri
 estimate on the norm of produ
t of fun
tionals,
Lin. Alg. Appl. 405 (2005), 304�310.
[Mat2℄ M. Matol
si, The linear polarization 
onstant of R
, A
ta Math. Hungar.
108 (2005), no. 1-2, 129�136.
[MM℄ M. Matol
si, G. A. Muñoz, On the real linear polarization 
onstant prob-
lem, Math. Inequal. Appl. 9 (2006), no. 3, 485�494.
[Mi℄ H. Min
, Permanents, En
y
lopedia of Mathemati
s and its Appli
ations,
Addison-Wesley, 1978
[MST℄ G. A. Muñoz, Y. Sarantopoulos, A. Tonge, Complexi�
ations of real
Bana
h spa
es, polynomials and multilinear maps, Studia Math. 134 (1999),
no. 1, 1�33.
http://arxiv.org/abs/math/0502298
[PR℄ A. Pappas, Sz. Révész, Linear polarization 
onstants..., J. Math. Anal.
Appl. 300 (2004), 129�146.
[R℄ Sz. Gy. Révész, Inequalities for multivariate polynomials, Annals of the
Marie Curie Fellowships 4 (2006), http://www.marie
urie.org/annals/, arXiv
preprint: math.CA/0703387
[RS℄ Sz. Gy. Révész, Y. Sarantopoulos, Plank problems, polarization and Cheby-
shev 
onstants, J. Korean Math. So
. 41 (2004) 157�174.
[S℄ B. Simon, The P(φ)2 Eu
lidean (Quantum) Field Theory, Prin
eton Series
in Physi
s, Prin
eton University Press, 1974
[Z℄ A. Zvonkin, Matrix integrals and map enumeration: an a

esible introdu
-
tion, Combinatori
s and physi
s (Marseille, 1995), Math. Comput. Modelling
26 (1997), 281�304.
http://arxiv.org/abs/math/0703387
	New inequalities on pfaffians and hafnians
	Pfaffians
	Hafnians
	Products of real linear functionals
