Is there a short representation for the convex hull of all row and column permutations of a matrix?

55 Views Asked by At

Suppose $S$ is the set of all $n\times n$ permutation matrices. For a matrix $\mathbf{A}\in\mathbb{R}^{n\times n}$ define the set $P(\mathbf{A})$ as the set of all equal row and column permutations of $\mathbf{A}$. \begin{equation} P(\mathbf{A}) = \left\{\mathbf{\Pi} \mathbf{A}\mathbf{\Pi}^T\;|\; \mathbf{\Pi}\in S\right\} \end{equation} My question is: What can be said about the convex hull $\text{conv}(P(\mathbf{A}))$? Is there a nice short representation of it other than writing it as a convex linear combination \begin{equation} conv(P(\mathbf{A})) = \left\{\sum_{\mathbf{\Pi} \in S} w_{\mathbf{\Pi}}\mathbf{\Pi} \mathbf{A}\Pi^T \;|\sum_{\mathbf{\Pi} \in S}w_{\mathbf{\Pi}} = 1, \forall \mathbf{\Pi} \in S:\;w_{\mathbf{\Pi}}\geq 0\;\right\} \end{equation} I know from the Birkhoff–von Neumann theorem that the convex hull of the set of permutation matrices has the short representation \begin{equation} conv(S) = \left\{\mathbf{\Pi}\in(\mathbb{R}_0^{+})^{n\times n}\;|\;\mathbf{\Pi} \mathbf{1}=\mathbf{1},\;\mathbf{\Pi}^T \mathbf{1}=\mathbf{1}\right\} \end{equation} where $\mathbf{1}$ is the column vector of ones. This is the set of doubly stochastic matrices and may be helpful for this question.