What is the linear description of a transformation of Birkhoff polytope?

51 Views Asked by At

Let $I, J$ be finite sets and $|I|=|J|=n$, Let $F$ be a Birkhoff polytope formed by the convex hull of $n\times n$ doubly stochastic matrices:

$$F=\{R^{I\times J}_+: \sum_j x( i,j)=1,\forall i\in I, \sum_i x( i,j)=1,\forall j\in J \}$$

Suppose $a=(a( i,j))\in R^{I\times J}_+$ is given (i.e., $a$ is a probability distribution on $I\times J$. For each $x\in F$ Define

$$y(i):=\sum_j a( i,j)x( i,j)$$ $$y(j):=\sum_i a( i,j)x( i,j)$$

Denote $G$ the set of all vectors $y$ by mapping all $x\in F$.

Then $G$ is a polytope. My problem is that what are the facets of $G$ (i.e., a linear representation $A y\leq b$ for some $(A,b)$)?

Thanks.