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)

$\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$ Aug 27, 2015 at 1:47
  • $\begingroup$ Yes,a similar list of constraints.. $\endgroup$
    – zack
    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$ 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$ Aug 27, 2015 at 5:55

1 Answer 1

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.

  • $\endgroup$
    4
    • $\begingroup$ But any column and any row must have sum $1/k$, yes? $\endgroup$ 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$ Aug 27, 2015 at 7:26
    • $\begingroup$ Ah, I see, this one cycle is not presumed to be "long cycle". $\endgroup$ 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
      Aug 27, 2015 at 16:00

    Your Answer

    By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

    Not the answer you're looking for? Browse other questions tagged or ask your own question.