Suppose that $v=(v_1,\ldots, v_d)\in \mathbb{R}^d$ lies in the linear subspace $v_1+\cdots +v_d=0$, and moreover that the coordinates are pairwise distinct. The permutahedron \begin{equation} P(\mathcal{S}_d;v)=Conv(\mathcal{S}_d\cdot v) \end{equation} is the convex hull of $v$ under the symmetric group action on coordinates. It is a $(d-1)$-dimensional polytope.

Now consider the cyclic subgroup $C_d$ of $\mathcal{S}_d$ generated by the permutation $(123\cdots d)$ and consider the corresponding orbitope $P(C_d; v)=Conv(C_d\cdot v)$.

Question: Is $P(C_d;v)$ necessarily a $(d-1)$-dimensional simplex?


1 Answer 1


Let $M$ be the circulant matrix whose rows are given by cyclic shifts of $(v_1,\dots v_d)$ and let $P(x)=v_1+v_2x+\cdots+v_dx^{d-1}$ be the associated polynomial. Moreover, let $s$ be the degree of $\gcd(P(x),x^{d}-1)$.Then the rank of $M$ is equal to $d-s$, so it is possible to come up with examples of vectors $v$ such that the $C_d$ orbit is not $(d-1)$-dimensional by making $s$ large.

For example the matrix $$\begin{bmatrix} 2 & 1 & -2 & -1 \\ 1 & -2 & -1 & 2 \\ -2 & -1 & 2 & 1 \\ -1 & 2 & 1 & -2 \end{bmatrix}$$ has rank 2, so the associated orbit polytope has dimension $2$ rather than $3$.

  • $\begingroup$ Thank you! Given the gcd interpretation (thank you for altering me to that), It doesn't seem possible to find linear conditions so that the circulant matrix has rank $d-1$ provided $(v_1,\ldots, v_d)$ lies outside the resulting linear subspaces (that's really what I needed for my purposes) $\endgroup$
    – Bob
    Jul 12, 2020 at 14:52

Your Answer

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

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