Van der Waerden’s permanent conjecture
Let be any doubly stochastic matrix (i.e. nonnegative real entries, each row sums to 1, each column too, hence square).
Let be the one where all entries are equal (i.e. they are ). Its permanent works out to
and Van der Waerden conjectured in 1926 that this is the smallest value for the permanent of any doubly stochastic , and is attained only for :
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.