2
$\begingroup$

It is known that the convex hull of permutation matrices yields exactly the stochastic matrices. I am interested in the convex hull of cyclic permutation matrices. Trivially this is a subset of the stochachastic matrices, but what more do we know than that about the relationship to the convex hull of all permutations?

My intuition would be that the chull of cyclic permutations is strictly smaller, but is this true? I have not yet found an example demonstrasting this!

If it is strictly smaller can we say something about those stochastic matrices within the "cyclic cone"? It seems they should hold some common property but i am unable to pinpoint it or find literature about it!

$\endgroup$
2
$\begingroup$

The convex hull (not cone) of permutation matrices is the set of doubly stochastic matrices. The convex hull of cyclic permutation matrices is the set of doubly stochastic cyclic matrices. That is, they can be expressed like this:

$$ \begin{bmatrix} a_1 & a_2 & \ldots & a_n \\ a_n & a_1 & & a_{n-1} \\ \vdots & & \ddots & \vdots \\ a_2 & a_3 & \ldots & a_1 \end{bmatrix}, \quad a_1 + a_2 \ldots + a_n = 1, \quad a_i \ge 0. $$

This should be clear since cyclic permutation matrices are cyclic matrices, and cyclic matrices form a linear space. (Any linear combination of cyclic permutation matrices must be a cyclic matrix.)

$\endgroup$
  • $\begingroup$ thank you for the important correction, that was a serious error on my part! I'll edit the question accordingly! $\endgroup$ – ckrk Jan 17 '14 at 22:51
  • $\begingroup$ Can this be right? It only has $n$ vertices instead of $(n-1)!$ (the number of cyclic permutations). $\endgroup$ – Austen Nov 6 '19 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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