Background
I'm working on the following linear program \begin{equation} \begin{aligned} \max_{P} &\sum_{i=1}^{\min(m,n)} (MP)_{ii}\\ \text{st} \quad & 1_n'P=1_n'\\ &P 1_n= 1_n\\ &P_{ij}\geq 0 \qquad j,i = 1,\dots, n \end{aligned} \tag{2} \end{equation} where $M$ is a given $m\times n$ matrix and $P$ should be a $n\times n$ permutation matrix. Such problem can be formulated in the following standard form \begin{equation*} \begin{aligned} \min_{x \geq 0} \, & c'x\\ \text{s.t.}\, & Ax \leq b \\ \end{aligned} \end{equation*} where $x=\textrm{vec}[P]$ and \begin{equation*}\begin{aligned} c&\triangleq -\textrm{vec}\left[{M}'\right]\\ A&\triangleq \left[\begin{array}{c} -(I_{{n}}\otimes 1_{{n}}')\\ \phantom{-}(I_{{n}}\otimes 1_{{n}}')\\ -(1_{{n}}'\otimes I_{{n}})\\ \phantom{-}(1_{{n}}'\otimes I_{{n}}) \end{array}\right]\\ b&\triangleq \left[\begin{array}{c} -1_{{n}} \\ \phantom{-}1_{{n}}\\ -1_{{n}} \\ \phantom{-}1_{{n}}\\ \end{array}\right]\end{aligned} \end{equation*} The notation used is the following: $\text{vec}[A]$ is the operator that stacks the columns of the matrix $A$, $1_n$ is a $n\times 1$ vector of $1$s, $I_n$ is the $n\times n$ identity matrix,$\otimes$ is the Kronecker product and $'$ is the transpose operator.
Question
The involved constraints guarantee only that $P$ is double-stochastic (and not a a permutation matrix). However, I've done some numerical test and it seems that the returned solution is always a permutation matrix. My question is thus the following:
- Is it true that the optimal solution of the linear program $(2)$ is a permutation matrix? If yes, how can be shown this fact?
To be honest, I don't have a clue about how to show my conjecture. The only thing that come in my mind is that the objective is to show that the entries of $P$ can be only $0$ or $1$ (which, in additition of the double stochasticity, should be enough).
We have to be careful about the word "the" in the optimal solution. It is true that at least one optimal solution to your linear program will be a permutation matrix. For most, but not all, matrices $M$ the optimal solution will be unique, and in that case, you'll always get a permutation matrix. (Even when the solution is not unique, algorithms such as the simplex method will give a permutation matrix as the answer.)
The reason begins with the Birkhoff–von Neumann theorem, which says that the polytope of $n\times n$ doubly stochastic matrices is the convex hull of the set of $n\times n$ permutation matrices. You should imagine this as a high-dimensional polyhedron in $n^2$-dimensional space, with the permutation matrices at its corners.
The expression $\sum_{i=1}^{\min(m,n)} (MP)_{ii}$ represents a direction in $n^2$-dimensional space, and to maximize it we want to as far as possible in that direction while staying in the polytope. Usually, this will lead us to a corner. The exception occurs when the direction is perpendicular to some $k$-dimensional face of the polytope (for $1 \le k < n^2$). In such a scenario, several corners will be tied for optimality, and any convex combination of those corners will also be equally good.