Van der Waerden’s permanent conjecture

Let $A$ be any doubly stochastic $n\times n$ matrix (i.e. nonnegative real entries, each row sums to 1, each column too, hence square).

Let $A^{\circ}$ be the one where all entries are equal (i.e. they are $\mathord{\mathchoice{\textstyle{1\over n}}{\textstyle{1\over n}}{\scriptstyle{% 1\over n}}{\scriptscriptstyle{1\over n}}}$ ). Its permanent works out to

\mathop{\rm per}\nolimits A^{\circ}\;=\;n!(\mathord{\mathchoice{\textstyle{1% \over n}}{\textstyle{1\over n}}{\scriptstyle{1\over n}}{\scriptscriptstyle{1% \over n}}})^{n}

and Van der Waerden conjectured in 1926 that this is the smallest value for the permanent of any doubly stochastic $A$ , and is attained only for $A=A^{\circ}$ :

\mathop{\rm per}\nolimits A\;>\;n!(\mathord{\mathchoice{\textstyle{1\over n}}{% \textstyle{1\over n}}{\scriptstyle{1\over n}}{\scriptscriptstyle{1\over n}}})^% {n}\quad\hbox{(for $A\neq A^{\circ}$).}

It was finally proven independently by Egorychev and by Falikman, in 1979/80.

References

1
Hal86 Marshall J. Hall, Jr., Combinatorial Theory (2nd ed.),
Wiley 1986, repr. 1998, ISBN 0 471 09138 3 and 0 471 31518 4
has a proof of the permanent conjecture.

Title	Van der Waerden’s permanent conjecture
Canonical name	VanDerWaerdensPermanentConjecture
Date of creation	2013-03-22 15:10:51
Last modified on	2013-03-22 15:10:51
Owner	marijke (8873)
Last modified by	marijke (8873)
Numerical id	5
Author	marijke (8873)
Entry type	Theorem
Classification	msc 15A15
Classification	msc 15A51
Synonym	permanent conjecture