Minimizing the permanent over some faces of the polytope of doubly stochastic matrices (Q1890760)

The minimum permanents and minimizing matrices over certain faces of the polytope \(\Omega_ n\) of \(n\times n\) doubly stochastic matrices are determined. To be precise, let \(n\) be a positive integer, for a pair of positive integers \(p\), \(q\) with \(p+ q\leq n\) let \(D_{p,q}\) denote the matrix obtained from \[ C_ n= \left[\begin{matrix} 1 & 1 & 0 & 0 &\cdots & 0 & 0\\ 1 & 0 & 1 & 0 &\cdots & 0 & 0\\ 1 & 0 & 0 & 1 &\cdots & 0 & 0\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\ 1 & 0 & 0 & 0 &\cdots & 0 & 1\\ 1 & 1 & 1 & 1 &\cdots & 1 & 1\end{matrix}\right] \] by replacing each of the entries in the last \(q\) rows with 1 and the entries in the first \(p\) columns with 1. The problem discussed is to minimize the permanent over the face \(\Omega(D_{p,q})\) of \(\Omega_ n\). The main results are: 1. If \(p+ q< n\), then the minimum permanent over \(\Omega(D_{p, q})\) is \(\delta_ p \delta_ q(n- p- q)^{n- p- q}/(n- p- q+ 1)^{n- p- q+ 1}\). 2. If \(p+ q< n\) and \(A\in \Omega(D_{p, q})\), then \(A\) is a minimizing matrix over \(\Omega(D_{p, q})\) if and only if \(A\) satisfies (1) \(A[1, \dots, p- 1| 1,\dots, p]= {1\over p} K_{p- 1,p}\), (2) \(A[n- q+ 1,\dots, n| n- q+ 2,\dots, n]= {1\over q} K_{q,q- 1}\), (3) \(A[n- q+ 1,\dots, n| 1,\dots, p]= 0\), (4) \(A[p,\dots, n- q| p+ 1,\dots, n- q+1]= {m- 1\over m} I_ m\), where \(m= n- p- q+ 1\), and \(A[\alpha| \beta]\) is the matrix complementary to \(A(\alpha| \beta)\), the latter denote the matrix obtained from \(A\) by deleting the rows indexed by \(\alpha\) and the columns indexed by \(\beta\). 3. For fixed integers \(p\), \(q\), \[ \lim_{n\to \infty}= {\dim\text{Min}(D_{p, q})\over \dim \Omega(D_{p, q})}= {p+ q- 2\over p+ q- 1}. \] A conjecture on the number of points in a ``vanishing set'' is proposed.