Dittert conjecture

The Dittert conjecture, or Dittert–Hajek conjecture, is a mathematical hypothesis in combinatorics concerning the maximum achieved by a particular function [math]\displaystyle{ \phi }[/math] of matrices with real, nonnegative entries satisfying a summation condition. The conjecture is due to Eric Dittert and (independently) Bruce Hajek. Let [math]\displaystyle{ A = [a_{ij}] }[/math] be a square matrix of order [math]\displaystyle{ n }[/math] with nonnegative entries and with [math]\displaystyle{ \sum_{i=1}^n \left ( \sum_{j=1}^n a_{ij} \right ) = n }[/math]. Its permanent is defined as [math]\displaystyle{ \operatorname{per}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}, }[/math] where the sum extends over all elements [math]\displaystyle{ \sigma }[/math] of the symmetric group.

The Dittert conjecture asserts that the function [math]\displaystyle{ \operatorname{\phi}(A) }[/math] defined by [math]\displaystyle{ \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) }[/math] is (uniquely) maximized when [math]\displaystyle{ A = (1/n) J_n }[/math], where [math]\displaystyle{ J_n }[/math] is defined to be the square matrix of order [math]\displaystyle{ n }[/math] with all entries equal to 1.