Extremes of permanents of \((0,1)\)-matrices. (Q1414140): Difference between revisions

For an \(m\times n\) matrix \(A=(a_{i,j})\) the permanent of \(A\) is \[ \text{Per}(A)=\sum_{\sigma \in S_p} a_{1,\sigma(1)} a_{2,\sigma (2) }\cdots a_{p,\sigma(p)} \] where \(p=\min\{ m, n\}\) and \(S_p\) denotes the permutation group on the set \(\{1,2,\ldots, p\}\). The authors investigate the values of permanents of \((0,1)\)-matrices according to the positions of zeros. Let \(U(m\times n,k)\) denote the set of all \((0,1)\)-matrices of size \(m\times n\), \(m\leq n\), with exactly \(k\) zeros. It is proved that for matrices from \(U(m\times n,k)\), \(2\leq k\leq m\), the maximal permanent is equal to \[ \sum\limits_{i=0}^m (-1)^i {k\choose i} {n-i\choose m-i} (m-i)! \] and is attained at the matrix with all zeros on the main diagonal. For \(2\leq k\leq n\) the minimal permanent is equal to \[ {n \choose m}m!-k{n-1\choose m-1}(m-1)! \] and is attained at the matrix with all zeros in the first row. Some generalization of the first formula for \(m<k\leq n\) is provided. Also for \(2\leq k\leq m\) the second largest and the second and third smallest values of the permanent are evaluated. A detailed comparison of the permanent values for \(k\leq 4\) is given.