is there a way to describe the convex hull of the set of permutation matrices with exactly one non-trivial cycle?


or maybe I should ask for the convex hull of cycle matrices :


let $(i\_{1},..,i\_{k})$ be a cycle then $A$ is a cycle matrix if the entries $(i\_{1},i\_{2})$ ...$(i\_{k},i\_{1})$ are $1/k$, and all the others are 0.
(it seems to me that this convex hull is the set of non-negative matrices of entries sum equal to 1)



convex hull of the set of permutations with one cycle
Yes. It's exactly the collection of non-negative matrices subject to:
- The entries sum to 1;
- The diagonal entries are 0;
- For each $i$, the $i$th column and $i$th row have equal sums.



The proof is by induction on the number of non-zero entries.
Suppose that matrices satisfying the above conditions with at most $k$ non-zero entries are in the convex hull. Then given a matrix $A$ with $k+1$ non-zero entries, pick an entry $(i,j)$ of the matrix so that $A\_{ij}$ is non-zero. Let $i\_0=i$ and $i\_1=j$. Since the $i\_1$st row has a non-zero entry, the $i\_1$st column must also have a non-zero entry. Continue in this way until $i\_l=i\_m$ for some $l<m$. Then there is a cycle $i\_l,i\_{l+1},\ldots,i\_m,i\_l$ where all the entries corresponding to an edge are non-zero. Take the minimum of the edge-weights $w$ and let $B$ be the matrix with weights $1/(m-l)$ on the $m-l$ edges forming the cycle. Then $A=w(m-l)B+(1-w(m-1))C$ for a matrix $C$ satisfying the constraints and having at least one less non-zero entry. 


