A geometric programming approach to the Van der Waerden conjecture on doubly stochastic matrices

Abstract

Let @p be the set of all doubly stochastic square matrices of order p i.e. the set of all p × p matrices with non-negative entries with row and column sums equal to unity. The permanent of a p × p matrix A = (aij) is defined by P(A)= ]~,esplI~=t ai~,) where Sp is the symmetric group of order p. Van der Waerden conjectured that P(A) >~ p ![p p for all A E ~p with equality occurring if and only if A = Jp, where Yp is the matrix all of whose entries are equal to 1/p. The validity of this conjecture has been shown for a few values of p and for general p under certain assumptions. In this paper the problem of finding the minimum of the permanent of a doubly stochastic matrix has been formulated as a reversed geometric program with a single constraint and an equivalent dual program is given. A related problem of reversed homogeneous posynomial programming problem is also studied.