3
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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$.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Jul 12, 2020 at 14:52

You must log in to answer this question.

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