# 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 VanDerWaerdensPermanentConjecture 2013-03-22 15:10:51 2013-03-22 15:10:51 marijke (8873) marijke (8873) 5 marijke (8873) Theorem msc 15A15 msc 15A51 permanent conjecture