|
|
|
|
Van der Waerden's permanent conjecture
|
(Theorem)
|
|
|
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 $\frac1n$ ). Its permanent works out to $$ \per A^\circ \;=\; n!(\frac1n)^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$ : $$ \per A \;\gt\; n!(\frac1n)^n \quad\hbox{(for $A \ne A^\circ$).} $$ It was finally proven independently by Egorychev and by Falikman, in 1979/80.
- Hal86
- MARSHALL J. HALL, JR., Combinatorial Theory (2nd ed.),
Wiley 1986, repr. 1998, ISBN0471091383 and 0471315184
has a proof of the permanent conjecture.
|
"Van der Waerden's permanent conjecture" is owned by marijke.
|
|
(view preamble | get metadata)
| Other names: |
permanent conjecture |
| Keywords: |
doubly stochastic matrix |
|
|
Cross-references: conjecture, permanent, real, matrix, doubly stochastic
There is 1 reference to this entry.
This is version 2 of Van der Waerden's permanent conjecture, born on 2005-04-08, modified 2005-04-08.
Object id is 6935, canonical name is VanDerWaerdensPermanentConjecture.
Accessed 3448 times total.
Classification:
| AMS MSC: | 15A51 (Linear and multilinear algebra; matrix theory :: Stochastic matrices) | | | 15A15 (Linear and multilinear algebra; matrix theory :: Determinants, permanents, other special matrix functions) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
