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.
Collections
- Journal Articles [3677]