Dittert conjecture

The Dittert conjecture, or Dittert–Hajek conjecture, is a mathematical hypothesis in <a href="/facts/Combinatorics/k14xUoKT">combinatorics</a> 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) <a href="/facts/Bruce_Hajek/u6pvkwFS">Bruce Hajek</a>.
Let 
 
 
 
 A
 =
 [
 
 a
 
 i
 j
 
 
 ]
 
 
 {\displaystyle A=[a_{ij}]}
 
 be a <a href="/facts/Square_matrix/5TP9mNNn">square matrix</a> of order 
 
 
 
 n
 
 
 {\displaystyle n}
 
 with nonnegative entries and with 
 
 
 
 
 ∑
 
 i
 =
 1
 
 
 n
 
 
 
 (
 
 
 ∑
 
 j
 =
 1
 
 
 n
 
 
 
 a
 
 i
 j
 
 
 
 )
 
 =
 n
 
 
 {\textstyle \sum _{i=1}^{n}\left(\sum _{j=1}^{n}a_{ij}\right)=n}
 
. Its <a href="/facts/Permanent_(mathematics)/eJWgdahx">permanent</a> is defined as

per
        ⁡
        (
        A
        )
        =
        
          ∑
          
            σ
            ∈
            
              S
              
                n
              
            
          
        
        
          ∏
          
            i
            =
            1
          
          
            n
          
        
        
          a
          
            i
            ,
            σ
            (
            i
            )
          
        
        ,
      
    
    {\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 <a href="/facts/Symmetric_group/RUksK5l5">symmetric group</a>. 
The Dittert conjecture asserts that the function 
 
 
 
 
 ϕ
 
 ⁡
 (
 A
 )
 
 
 {\displaystyle \operatorname {\phi } (A)}
 
 defined by 
 
 
 
 
 ∏
 
 i
 =
 1
 
 
 n
 
 
 
 (
 
 
 ∑
 
 j
 =
 1
 
 
 n
 
 
 
 a
 
 i
 j
 
 
 
 )
 
 +
 
 ∏
 
 j
 =
 1
 
 
 n
 
 
 
 (
 
 
 ∑
 
 i
 =
 1
 
 
 n
 
 
 
 a
 
 i
 j
 
 
 
 )
 
 −
 per
 ⁡
 (
 A
 )
 
 
 {\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 
 
 
 
 A
 =
 (
 1
 
 /
 
 n
 )
 
 J
 
 n
 
 
 
 
 {\displaystyle A=(1/n)J_{n}}
 
, where 
 
 
 
 
 J
 
 n
 
 
 
 
 {\displaystyle J_{n}}
 
 is defined to be the square matrix of order 
 
 
 
 n
 
 
 {\displaystyle n}
 
 with all entries equal to 1.

Dittert conjecture open-in-new

Dittert conjecture