Misplaced Pages

The Dittert conjecture, or Dittert–Hajek conjecture, is a mathematical hypothesis in combinatorics concerning the maximum achieved by a particular function ${\displaystyle \phi }$ of matrices with real, nonnegative entries satisfying a summation condition. The conjecture is due to Eric Dittert and (independently) Bruce Hajek.

Let ${\displaystyle A=}$ be a square matrix of order ${\displaystyle n}$ with nonnegative entries and with ${\textstyle \sum _{i=1}^{n}\left(\sum _{j=1}^{n}a_{ij}\right)=n}$. Its permanent is defined as $${\displaystyle \operatorname {per} (A)=\sum _{\sigma \in S_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)},}$$ where the sum extends over all elements ${\displaystyle \sigma }$ of the symmetric group.

The Dittert conjecture asserts that the function ${\displaystyle \operatorname {\phi } (A)}$ defined by ${\textstyle \prod _{i=1}^{n}\left(\sum _{j=1}^{n}a_{ij}\right)+\prod _{j=1}^{n}\left(\sum _{i=1}^{n}a_{ij}\right)-\operatorname {per} (A)}$ is (uniquely) maximized when ${\displaystyle A=(1/n)J_{n}}$, where ${\displaystyle J_{n}}$ is defined to be the square matrix of order ${\displaystyle n}$ with all entries equal to 1.

References

1. ^ Hogben, Leslie, ed. (2014). Handbook of Linear Algebra (2nd ed.). CRC Press. pp. 43–8. ISBN 978-1-4665-0729-6.
2. ^ Cheon, Gi-Sang; Wanless, Ian M. (15 February 2012). "Some results towards the Dittert conjecture on permanents". Linear Algebra and Its Applications. 436 (4): 791–801. doi:10.1016/j.laa.2010.08.041. hdl:1885/28596.
3. Eric R. Dittert at the Mathematics Genealogy Project
4. Bruce Edward Hajek at the Mathematics Genealogy Project

This combinatorics-related article is a stub. You can help Misplaced Pages by expanding it.

• v
• t
• e

• Conjectures
• Combinatorics
• Inequalities
• Combinatorics stubs