Van der Waerdensche permanent presumption

The van der Waerden permanent conjecture ( English: van der Waerden permanent conjecture ) is a famous, now proven mathematical theorem , which was put forward as a conjecture by the mathematician Bartel Leendert van der Waerden in 1926. It asserts an elementary lower estimate for permanents of real double-stochastic matrices .

Confirmation of the presumption

Van der Waerden's conjecture remained unproven for several decades and was finally confirmed by the two mathematicians Georgi P. Jegortschow and Dmitry I. Falikman - who worked independently of each other - in the years 1980–1981. So the following theorem applies :

A natural number and a real double-stochastic matrix are given . ${\displaystyle n\geq 1}$ ${\displaystyle A\in {\mathbb {R} }^{n\times n}}$

Then there is the inequality

${\displaystyle \operatorname {perm} (A)\geq {\frac {n!}{n^{n}}}}$.

In this inequality, the equal sign applies if and only if all elements of the matrix are equal . ${\displaystyle A}$ ${\displaystyle \textstyle {\frac {1}{n}}}$

Note on naming

In the English-language specialist literature, the inequality given above is sometimes also referred to as Van der Waerden-Egorychev-Falikman inequality .

literature

• Marshall Hall, Jr .: Combinatorial Theory (=  Wiley-Interscience Series in Discrete Mathematics ). 2nd Edition. John Wiley & Sons, Inc. , New York 1986, ISBN 0-471-09138-3 ( MR0840216 ).
• Donald E. Knuth : A permanent inequality . In: American Mathematical Monthly . tape 88 , 1981, pp. 731-740, 798 ( MR0668399 ).
• Henryk Minc : Nonnegative Matrices (=  Wiley-Interscience Series in Discrete Mathematics and Optimization ). John Wiley & Sons, Inc., New York 1988, ISBN 0-471-83966-3 ( MR0932967 ).
• Henryk Minc: The van der Waerden permanent conjecture . In: General inequalities 3 (Oberwolfach, April 26 - May 2, 1981; edited by EF Beckenbach and W. Walter ) (=  International Series of Numerical Mathematics . Volume 64 ). Birkhäuser Verlag , Basel 1983, p. 23-40 ( MR0785765 ).
• Kenneth H. Rosen (Ed.): Handbook of Discrete and Combinatorial Mathematics (=  Discrete Mathematics and its Applications ). CRC Press, 2000, ISBN 0-8493-0149-1 .
• BL van der Waerden: Exercise 45 . In: Annual report of the German Mathematicians Association . tape 35 , 1926, pp. 117 .

Remarks

1. ↑ Please note the different transcriptions of Russian names into German and English.

Individual evidence

1. ↑ ^{a b c} Kenneth H. Rosen (Ed.): Handbook of Discrete and Combinatorial Mathematics. 2000, p. 423
2. ^ ^{A b} Marshall Hall, Jr .: Combinatorial Theory. 1986, p. 58 ff.
3. ^ ^{A b} Henryk Minc: Non-negative matrices. 1988, p. 128 ff.
4. ^ Henryk Minc: The van der Waerden permanent conjecture. General inequalities 3, pp. 731-740, 798
5. ^ Donald E. Knuth: A permanent inequality. Amer. Math. Monthly 88, pp. 731-740, 798