ABSTRACT

In [1] Ando proves that the doubly stochastic matrix having minimum permanent for a given zero-one pattern has the property that all its minors have equal permanent. If all minors are equal then a will equal one. Ando also shows that the Sinkhorn balance, |B| for a given zero-one pattern maximizes the entropy (= –å bi,jlog bi,j). This is proved in a new way in [3] where it was also shown that maximizing the entropy is similar to minimizing the permanent. The connection is via the Bregman map. For a matrix B the Bregman map [4] is defined as

(=-E6t , j log6i j ) -

F(B) = F b1,1 b1,2 . . . b1,n bn,l bn,2 . . . bn,n

bn,n.|Bn,n||B|

Figure 4. Permanent versus entropy for iterations of the Bregman map and its inverse on a worst case matrix.