3
$\begingroup$

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)

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Hm, you mean similar to the Birkhoff polytope, as a nice list of inequalities and equalities? en.wikipedia.org/wiki/Birkhoff_polytope $\endgroup$
    – Per Alexandersson
    Commented Aug 27, 2015 at 1:47
  • $\begingroup$ Yes,a similar list of constraints.. $\endgroup$
    – zack
    Commented Aug 27, 2015 at 2:09
  • $\begingroup$ So the matrix with a single 1 somewhere is not in the convex hull. Also the convex hull gives weight 0 to the diagonal, so the convex hull is certainly more complicated than you think. $\endgroup$
    – Anthony Quas
    Commented Aug 27, 2015 at 5:55
  • $\begingroup$ another comment: the $i$th row and the $i$th column have the same sum for each $i$. $\endgroup$
    – Anthony Quas
    Commented Aug 27, 2015 at 5:55

1 Answer 1

Reset to default
0
$\begingroup$

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.

    • Improve this answer
    $\endgroup$
    4
    • $\begingroup$ But any column and any row must have sum $1/k$, yes? $\endgroup$
      – Fedor Petrov
      Commented Aug 27, 2015 at 7:15
    • $\begingroup$ I don't think so. For example if the permutation is a transposition, then there are 2 columns and rows with weight 1/2 and the rest with weight 0. $\endgroup$
      – Anthony Quas
      Commented Aug 27, 2015 at 7:26
    • $\begingroup$ Ah, I see, this one cycle is not presumed to be "long cycle". $\endgroup$
      – Fedor Petrov
      Commented Aug 27, 2015 at 9:42
    • $\begingroup$ Thanks, can we say something about the set of increasing cycle (ie $i_{1}<i_{2}<..<i_{k}$) $\endgroup$
      – zack
      Commented Aug 27, 2015 at 16:00

    You must log in to answer this question.

    Not the answer you're looking for? Browse other questions tagged .