Download On Leonid Gurvits s proof for permanents...

On Leonid Gurvits’s proof for permanents Monique Laurent and Alexander Schrijver

Abstract We give a concise exposition of the elegant proof given recently by Leonid Gurvits for several lower bounds on permanents.

1. Permanents The permanent of a square matrix A = (ai,j )ni,j=1 is defined by (1)

perA =

n X Y

ai,π(i) ,

π∈Sn i=1

where Sn denotes the set of all permutations of {1, . . . , n}. (The name “permanent” has its root in Cauchy’s fonctions sym´etriques permanentes [2], as a counterpart to fonctions sym´etriques altern´ees — the determinants.) Despite its appearance as the simpler twin-brother of the determinant, the permanent has turned out to be much less tractable. Whereas the determinant can be calculated quickly (in polynomial time, with Gaussian elimination), determining the permanent is difficult (“number-P-complete”). As yet, the algebraic behaviour of the permanent function has appeared to a large extent unmanageable, and its algebraic relevance moderate. Most fruitful research on permanents concerns lower and upper bounds for the permanent (see the book of Minc [12]). In this paper we will consider only lower bounds. Indeed, most interest in the permanent function came from the famous Van der Waerden conjecture [16] (in fact formulated as question), stating that the permanent of any n × n doubly stochastic matrix is at least n!/nn , the minimum being attained only by the matrix with all entries equal to 1/n. (A matrix is doubly stochastic if it is nonnegative and each row and column sum is equal to 1.) This conjecture was unsolved for over fifty years, which, when contrasted with its simple form, also contributed to the reputation of intractability of permanents. Finally, Falikman [6] and Egorychev [4] were able to prove this conjecture, using a classical inequality of Alexandroff and Fenchel. The proof with eigenvalue techniques also revealed some unexpected nice algebraic behaviour of the permanent function (see, also for background, Knuth [9] and van Lint [10,11]). Before the proof of the Van der Waerden conjecture was found, a weaker conjecture was formulated by Erd˝os and R´enyi [5]. It claims the existence of a real number α3 > 1 such that, for each nonnegative integer-valued n × n matrix A with all row and column sums equal to 3, the permanent of A is at least α3n . This would follow from the Van der Waerden conjecture, since 13 A is doubly stochastic, hence 1

(2)

perA = 3n per( 31 A) ≥ 3n

³ 3 ´n n! . ≥ nn e

Erd˝os and R´enyi also asked for the largest value of α3 one can take in this bound. More generally, for any natural number k, they asked for the largest real number αk such that each nonnegative integer-valued n×n matrix A = (ai,j ) with all row and column sums equal to k has permanent at least αkn . Note that this permanent is equal to the number of perfect matchings in the k-regular bipartite graph with vertices u1 , . . . , un , v1 , . . . , vn , where ui and vj are connected by ai,j edges. In 1979, before the Van der Waerden conjecture was settled, the first conjecture of Erd˝os and R´enyi was proved, by Bang [1], Friedland [7], and Voorhoeve [15]. Bang and Friedland in fact showed that the permanent of any n × n doubly stochastic matrix is at least e−n . Note that limn→∞ (n!/nn )1/n = e−1 , so this may be seen as an asymptotic proof of the Van der Waerden conjecture. It also implies that the number αk of Erd˝os and R´enyi is at least k/e; in particular, α3 ≥ 3/e > 1. The proof of Voorhoeve gives a better bound: α3 ≥ 4/3. In fact, this bound is best possible. Indeed, it follows from a theorem of Wilf [18] that α3 ≤ 4/3, and more generally (3)

αk ≤

(k − 1)k−1 , k k−2

and Schrijver and Valiant [14] conjectured that equality holds for each k. For k = 1, 2, this is trivial, and for k = 3 this follows from Voorhoeve’s theorem. The proof of Voorhoeve that α3 ≥ 4/3 is very short and elegant, and it seduces one to search for similar arguments for general k. However, it was only at the cost of frightening technicalities that Schrijver [13] found a proof that equality indeed holds in (3) for each k. This amounts to a lower bound for permanents of doubly stochastic matrices in which all entries are integer multiples of 1/k. Under this restriction, this bound is larger than the Van der Waerden bound. In fact, both the bound of Falikman-Egorychev and that of Schrijver are best possible, in different asymptotic directions. Let µ(k, n) denotes the minimum permanent of n × n doubly stochastic matrices with all entries being integer multiples of 1/k. Then the two bounds state (4)

µ(k, n) ≥

³ k − 1 ´(k−1)n n! . and µ(k, n) ≥ nn k

They are best possible in the following sense: (5)

inf µ(k, n)1/n = k

³ k − 1 ´k−1 n!1/n . and inf µ(k, n)1/n = n n k

The proof of Falikman and Egorychev requires some nontrivial theorems, and the proof of Schrijver is combinatorially complex. It was a big surprise when Leonid Gurvits [8] gave an amazingly short proof of the two bounds. En route, he extended Schrijver’s theorem to: each doubly stochastic n × n matrix with at most k nonzeros in each column has permanent at least ((k − 1)/k)(k−1)n . In fact, Gurvits proved that each doubly stochastic n × n matrix

2

A satisfies (6)

perA ≥

n Y

g(min{i, λA (i)})

(Gurvits’s inequality),

i=1

where λA (i) is the number of nonzeros in the ith column of A, and where (7)

g(0) := 1 and g(k) :=

³ k − 1 ´k−1

for k = 1, 2, . . .

k

(setting 00 = 1). Gurvits’ bound implies both the bound of Falikman and Egorychev and the bound of Schrijver — see Section 4. We give here a proof based on Gurvits’s proof. The building blocks of the proof are from Gurvits [8], but we take a few shortcuts.

2. Description of Gurvits’s approach As usual, let R+ := {x ∈ R | x ≥ 0}. RecallPthe geometric-arithmetic mean inequality, saying that if λ1 , . . . , λn , x1 , . . . , xn ∈ R+ with ni=1 λi = 1, then (8)

n X

λi xi ≥

i=1

n Y

xλi i .

i=1

It amounts to the concavity of the log function. For any n × n matrix A, define the following multivariate polynomial pA in the variables x1 , . . . , xn : (9)

pA (x1 , . . . , xn ) :=

n Y i=1

ai x =

n n X Y

ai,j xj ,

i=1 j=1

where ai denotes the ith row of A (in ai x we take ai as a row vector and x = (x1 , . . . , xn )T as a column vector). So pA is hom*ogeneous of degree n. Then the coefficient of the monomial x1 · · · xn in pA is equal to perA. This can also be stated in terms of partial derivatives as (10)

perA =

∂ n pA . ∂x1 · · · ∂xn

Note that the latter expression is a constant function. The crux of the method is to consider more generally the following derivatives of pA , for any i = 0, . . . , n: (11)

∂ n−i pA qi (x1 , . . . , xi ) := ∂xi+1 · · · ∂xn

º

. xi+1 =···=xn =0

3

So qi ∈ R[x1 , . . . , xi ]. Then qn = pA and q0 = perA. The polynomials qi will be related through the following concept of “capacity” of a polynomial. The capacity cap(p) of a polynomial p ∈ R[x1 , . . . , xn ] is defined as (12)

cap(p) := inf p(x),

where the infimum ranges over all x ∈ Rn+ with we have:

Qn

j=1 xj

= 1. So cap(q0 ) = perA. Moreover,

Proposition 1. If A is doubly stochastic, then cap(pA ) = 1. Q Proof. For any x ∈ Rn+ with nj=1 xj = 1 we have, using the geometric-arithmetic mean inequality (8): (13)

pA (x) =

Y i

ai x ≥

YY i

a

xj i,j =

j

YY j

a

xj i,j =

i

Y

P

xj

i

j

ai,j

=

Y

xj = 1.

j

Hence cap(pA ) ≥ 1. As pA (1, . . . , 1) = 1, this gives cap(pA ) = 1. Then Gurvits’s inequality (6) follows inductively from the inequality (14)

cap(qi−1 ) ≥ cap(qi )g(min{i, λA (i)})

for i = 1, . . . , n, assuming A to be nonnegative. This is the basic inequality in Gurvits’s proof, which is established using the concept of “H-stable polynomial”, as follows. Define C+ := {z ∈ C | Re z ≥ 0} and C++ := {z ∈ C | Re z > 0}. A polynomial p ∈ C[x1 , . . . , xn ] is called H-stable if p has no zeros in Cn++ . (Here “H” stands for “halfplane.”) Note that for any doubly stoachastic matrix A, the polynomial pA indeed is Hstable. For any polynomial p ∈ R[x1 , . . . , xn ], let the polynomial p′ ∈ R[x1 , . . . , xn−1 ] be defined by (15)

p′ (x1 , . . . , xn−1 ) :=

∂p ∂xn

º

. xn =0

Then the polynomials introduced in (11) satisfy qi−1 = (qi )′ for i = 1, . . . , n. As noted above, we need to show inequality (14). This is what the following key result of Gurvits does, relating cap(p) and cap(p′ ). Theorem 1. Let p ∈ R+ [x1 , . . . , xn ] be H-stable and hom*ogeneous of degree n. Then p′ ≡ 0 or p′ is H-stable. Moreover, (16)

cap(p′ ) ≥ cap(p)g(k),

where k = degxn (p) denotes the degree of xn in p.

4

Note that the degree of the variable xi in qi is at most min{i, λA (i)}. Hence, as g is monotone nonincreasing, (14) indeed follows.

3. Proof of Theorem 1 We first prove a lemma. For any x ∈ Cn , let Re x := (Re x1 , . . . , Re xn ). Lemma 1. Let p ∈ C[x1 , . . . , xn ] be H-stable and hom*ogeneous. Then for each x ∈ Cn+ : (17)

|p(x)| ≥ |p(Re x)|.

Proof. By continuity, we can assume x ∈ Cn++ . Then, as p is H-stable, p(Re x) 6= 0. Fixing x, consider p(x + sRe x) as a function of s ∈ C. As p is hom*ogeneous, we can write (18)

m Y p(x + sRe x) = p(Re x) (s − bi ) i=1

for b1 , . . . , bm ∈ C, where m is the total degree of p. For each i, as p(x + bi Re x) = 0 and as p is H-stable, we know x + bi Re x 6∈ Cn++ , and so Re (1 + bi ) ≤ 0, that is, Re bi ≤ −1, which implies |bi | ≥ 1. Therefore, (19)

|p(x)| = |p(x + 0Re x)| = |p(Re x)|

m Y

|bi | ≥ |p(Re x)|.

i=1

Now we can prove Theorem 1. Qn−1 i=1 Re yi = 1: (20)

n−1 It suffices to prove that for each y ∈ C++ with

(i) if p′ (y) = 0 then p′ ≡ 0, and (ii) if y is real, then p′ (y) ≥ cap(p)g(k).

Before proving (20), note that for any real t > 0, (21)

cap(p) ≤

p(Re y, t) . t

Indeed, let λ := t−1/n and x := λ·(Re y, t). We chose λ so that 1. Hence, as p is hom*ogeneous of degree n, (22)

cap(p) ≤ p(x) = λn p(Re y, t) =

Qi

i=1 xi

= λn

³Q

n−1 i=1 Re yi

´

t=

p(Re y, t) , t

and we have (21). We now prove (20). First assume that p(y, 0) = 0. Then by (17) we have p(Re y, 0) = 0 (since 0 = |p(y, 0)| ≥ |p(Re y, 0)| ≥ 0). Moreover,

5

(23)

p′ (y) = lim t↓0

p(y, t) − p(y, 0) p(y, t) = lim , t↓0 t t

and a similar expression holds for p′ (Re y). By (17), as all coefficients of p are nonnegative, p(Re y, t) ≤ |p(y, t)| for all t ≥ 0. So, using (21), (24)

cap(p) ≤ lim t↓0

p(Re y, t) |p(y, t)| = p′ (Re y) ≤ lim = |p′ (y)|. t↓0 t t

This implies (20): we have (i) since if p′ (y) = 0 then p′ (Re y) = 0, so p′ ≡ 0 (as all coefficients of p′ are nonnegative); (ii) follows as g(k) ≤ 1 for each k. Second assume that p(y, t) has degree at most 1, as a polynomial in t. Then also p(Re y, t) has degree at most 1, since p(Re y, t) ≤ |p(y, t)|. Moreover, (25)

p(y, t) , t→∞ t

p′ (y) = lim

and a similar expression holds for p′ (Re y). Now again using (21), (26)

cap(p) ≤ lim

t→∞

p(Re y, t) |p(y, t)| = p′ (Re y) ≤ lim = |p′ (y)|, t→∞ t t

again implying (20). So we can assume that p(y, 0) 6= 0 and that p(y, t) has degree at least 2, as a polynomial in t. This implies k ≥ 2. Since p(y, 0) 6= 0, we can write (27)

p(y, t) = p(y, 0)

k Y (1 + ai t) i=1

for some a1 , . . . , ak ∈ C. Hence p′ (y) = p(y, 0) all ai are 0. Moreover, for i = 1, . . . , k: (28)

Pk

i=1 ai .

As p(y, t) has degree at least 2, not

if ai 6= 0, then a−1 is a nonnegative real linear combination of y1 , . . . , yn−1 . i

Otherwise there is a line in the complex plane C through 0 that separates a−1 from i ) < 0 and Re (λy ) > 0 for y1 , . . . , yn−1 . So there exists a λ ∈ C such that Re (λa−1 j i n . j = 1, . . . , n − 1. Hence (λy, −λa−1 ) belongs to C ++ i n p(y, −a−1 ) = 0 (this follows by substituting t = −a−1 in However, p(λy, −λa−1 ) = λ i i i (27)). This contradicts the H-stability of p, and thus proves (28). As the yi belong that Re ai > 0 if ai 6= 0. Hence, as P to C++ , (28) in particular impliesP not all ai are 0, ki=1 ai 6= 0. Therefore p′ (y) = p(y, 0) ki=1 ai 6= 0. This gives (20)(i). To prove (20)(ii) we now assume that y is real. Then by (28), all ai are real nonnegative. By scaling p we can assume that p(y, 0) = 1. Set (29)

t :=

k . (k − 1)p′ (y) 6

Then, using the geometric-arithmetic mean inequality (8) and the fact that p′ (y) =

(30)

p(y, t) =

Pk

i=1 ai ,

k k ´k ³ ³1 X ´k ³ 1 Y 1 ´k = (k + p′ (y)t) = 1 + (1 + ai t) ≤ (1 + ai t) = k k k−1

³ k ´ki=1 . k−1

i=1

Therefore, by (21), (31)

cap(p) ≤

³ k ´k−1 1 ³ k ´k p(y, t) = p′ (y) . ≤ t t k−1 k−1

The value (29) for t was determined by Gurvits to yield the best inequality relating cap(p′ ) and cap(p).

4. Applications to permanents Corollary 1a. For any nonegative n × n matrix A: (32)

perA ≥ cap(pA )

n Y

g(min{i, λA (i)}).

i=1

Proof. We may assume that A has no zero row. Then, as pA (x) = 0 implies that ai x = 0 for some i, pA is H-stable. Define qi ∈ R+ [x1 , . . . , xi ] as in (11). Then by Theorem 1, for i = 1, . . . , n, (33)

cap(qi−1 ) ≥ cap(qi )g(degxi (qi )) ≥ cap(qi )g(min{i, λA (i)}),

since degxi (qi ) ≤ min{i, λA (i)} and g is monotone nonincreasing. As cap(q0 ) = perA, (32) follows by induction. If A is doubly stochastic, cap(pA ) = 1 (Proposition 1), and hence Corollary 1a gives Gurvits’s inequality (6). This implies the theorem of Falikman [6] and Egorychev [4] (Van der Waerden’s conjecture [16]): Corollary 1b. If A is a doubly stochastic n × n matrix, then (34)

perA ≥

n! . nn

Proof. By (32),

7

(35)

perA ≥

n ³ Y i − 1 ´i−1

i

i=1

n Y (i − 1)i−1 n! i = = n. i i n i=1

Another consequence of Corollary 1a is the bound of Voorhoeve [15] (for k = 3) and Schrijver [13]: Corollary 1c. If A is a nonnegative integer n × n matrix with all row and column sums equal to k, then (36)

perA ≥

³ (k − 1)k−1 ´n k k−2

.

Proof. Let B := k1 A. Then B is doubly stochastic and each column has at most k nonzeros. Hence by Corollary 1a, (37)

perA = k n perB ≥ k n

³ k − 1 ´(k−1)n k

=

³ (k − 1)k−1 ´n k k−2

.

For each fixed k, the base (k − 1)k−1 /k k−2 in (36) is best possible (Wilf [18]). It is even best possible when A is restricted to 0, 1 matrices (Wanless [17]). As was observed by Henryk Minc, Corollary 1c for k = 6 implies the (currently best known) lower bound of 0.44007584 for the 3-dimensional dimer constant (see Ciucu [3]). One can also derive uniqueness of the doubly stochastic matrix having minimum permanent (a result of Egorychev [4]). Corollary 1d. Let A = (ai,j ) be a doubly stochastic n × n matrix with perA = n!/nn . Then ai,j = 1/n for all i, j. Proof. By symmetry it suffices to show that all entries in the last column of A are equal. Let the polynomials qi be as in (11). Then, since equality holds in (33), (38)

inf qn−1 (y) = cap(qn−1 ) = y

³ n − 1 ´n−1 n

cap(qn ) =

³ n − 1 ´n−1 n

,

Qn−1 n−1 yj = 1. Now for any such y we have the following, where y ranges over y ∈ R+ with j=1 where i and k range over 1, . . . , n and j ranges over 1, . . . , n − 1, and where a′i denotes the ith row of A with the last entry chopped off: (39)

qn−1 (y) =

X k

ak,n

Y

a′i y ≥

i6=k

YY

(a′i y)ak,n =

YY

(a′i y)ak,n =

i k6=i

k i6=k

Y (a′i y)1−ai,n i

´1−ai,n ai,j = (1 − ai,n ) yj = ai,j yj 1 − ai,n i j i j ´³ Y Y ´ Y³ Y ai,j ´ ³ Y a ≥ (1 − ai,n )1−ai,n yj = (1 − ai,n )1−ai,n yj i,j Y³X i

´1−ai,n

Y³

X

j

i

j

i

³Y ³ n − 1 ´n−1 ´³ Y ´ Y = (1 − ai,n )1−ai,n (1 − ai,n )1−ai,n ≥ yj = . n i

i

j

8

Here we used, in the first two inequalities, the geometric-arithmetic mean inequality (8) and, in the last inequality, the log-convexity of the function xx (note that (n − 1)/n is the average of the 1 − ai,n ). By (38) we must have equality in the last inequality of (39). Hence 1 − ai,n is the same for all i, and so the last column of A is constant. Acknowledgements. We thank the referees for helpful comments improving the presentation of the paper.

References [1] T. Bang, On matrix-functions giving a good approximation to the v.d.Waerden permanent conjecture, Preprint Series 1979 No. 30, Matematisk Institut, Københavns Universitet, Copenhagen, 1979. [2] A.-L. Cauchy, M´emoire sur les fonctions qui ne peuvent obtenir que deux valeurs ´egales et de signes contraires par suite des transpositions op´er´ees entre les variables qu’elles renferment, ´ Journal de l’Ecole Polytechnique 27, no. 10 (1812) 29–112. [3] M. Ciucu, An improved upper bound for the 3-dimensional dimer problem, Duke Math. J. 94 (1998) 1–11. [4] G. P. Egorychev, Proof of the van der Waerden conjecture for permanents [in Russian], Sibirsk. Mat. Zh. 22, no. 6 (1981) 65–71 [English translation: Siberian Math. J. 22 (1981) 854–859]. [5] P. Erd˝ os, A. R´enyi, On random matrices II, Studia Sci. Math. Hungar. 3 (1968) 459–464. [6] D. I. Falikman, Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix [in Russian], Mat. Zametki 29 (1981) 931–938 [English translation: Math. Notes 29 (1981) 475–479]. [7] S. Friedland, A lower bound for the permanent of a doubly stochastic matrix, Ann. of Math. (2) 110 (1979) 167–176. [8] L. Gurvits, Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) hom*ogeneous polynomials: one theorem for all, Electron. J. Combin. 15 (2008) # R66. [9] D. E. Knuth, A permanent inequality, Amer. Math. Monthly 88 (1981) 731–740. [10] J. H. van Lint, Notes on Egoritsjev’s proof of the van der Waerden conjecture, Linear Algebra Appl. 39 (1981) 1–8. [11] —, The van der Waerden conjecture: two proofs in one year, Math. Intelligencer 4, no. 2 (1982) 72–77. [12] H. Minc, Permanents, Addison-Wesley, Reading MA, 1978. [13] A. Schrijver, Counting 1-factors in regular bipartite graphs, J. Combin. Theory Ser. B 72 (1998) 122–135. [14] A. Schrijver, W. G. Valiant, On lower bounds for permanents, Indag. Math. (N.S.) 42 (1980) 425–427. [15] M. Voorhoeve, A lower bound for the permanents of certain (0, 1)-matrices, Indag. Math. (N.S.) 41 (1979) 83–86. [16] B. L. van der Waerden, [Aufgabe] 45, Jahresber. Deutsch. Math.-Verein. 35 (1926) 117.

9

[17] I. M. Wanless, Addendum to Schrijver’s work on minimum permanents, Combinatorica 26 (2006) 743–745. [18] H. S. Wilf, On the permanent of a doubly stochastic matrix, Canad. J. Math. 18 (1966) 758–761.

Monique Laurent received her Ph.D. in mathematics at the University Paris Diderot in 1986. After that she became researcher at CNRS in Paris, first with the University Paris Dauphine and later with Ecole Normale Sup´erieure. Since 1997 she is researcher at CWI (Centrum Wiskunde & Informatica) in Amsterdam and, since 2009, she is also professor at Tilburg University. CWI, Science Park 123, 1098 XG Amsterdam, The Netherlands, and Department of Econometrics and Operations Research, Tilburg University, Tilburg, The Netherlands [emailprotected] Alexander Schrijver received his Ph.D. in mathematics at the Free University in Amsterdam in 1977. He was a professor of mathematics at Tilburg University, and since 1989 researcher at CWI (Centrum Wiskunde & Informatica) in Amsterdam and professor of mathematics at the University of Amsterdam. CWI, Science Park 123, 1098 XG Amsterdam, The Netherlands, and Department of Mathematics, University of Amsterdam, Amsterdam, The Netherlands [emailprotected]

10