Minimum permanents of doubly stochastic matrices with prescribed zero entries on the main diagonal (Q1330003): Difference between revisions

Let \(Z = \{(i_ 1, i_ 1), \dots, (i_ k, i_ k)\}\) be a subset of \(\{1, \dots, n\} \times \{1, \dots, n\}\); \(\Omega_ n(Z)\) denotes the doubly stochastic matrices with zeros at least in the positions of \(Z\). A matrix \(A \in \Omega_ n (Z)\) is said to be (permanent) minimizing in \(\Omega_ n (Z)\) if \(\text{per} A \leq \text{per} S\) for all \(S \in \Omega_ n(Z)\). Let \(C\) be the \(n\times n\) (0,1) matrix with 0's in positions \(Z\) and 1's elsewhere. \(B = (b_{ij}) \in \Omega_ n (Z)\), where \(b_{ij} = \text{per} C (i | j)/ \text{per} C\) for all \((i,j) \notin Z\), is called the barycenter of \(\Omega_ n(Z)\); if \(B\) is a minimizing matrix, \(\Omega_ n(Z)\) is said to be barycentric. It is shown that \(\Omega_ n (Z_ 2)\) and \(\Omega_ n (Z_ 3)\) are not barycentric. For a fixed \(k \geq 2\), the set \(\Omega_ n (Z_ k)\) is not barycentric, except possibly for less than \(k^ 2 + k\) values of \(n\). \(Z_ k\) is the particular \(Z = \{(1,1,), \dots,(k,k)\}\).