8
$\begingroup$

Define $E_{i,j} \in \mathbb{R}^{n \times n}$ to be the canonical basis (that is all elements set to zero except the entry $i,j$ ) let the bloc matrix $M \in \mathbb{R}^{n^2 \times n^2}$ defined by :

$M = \begin{pmatrix}E_{\sigma(i), \sigma(j)} \end{pmatrix}_{ 1\leq i,j \leq n}$ for some permutation $\sigma$ of ${1,2,..,n}$

can you find the convex hull of this set of points ? Or at least is the number of equations that define this polytope is exponential?

Case $n=2,3$

case n=3

case n=2

the $x_i$ are such that they sum to $1$. That is, resulting matrices are the general form of some element from the convex hull.

From this experiment we can deduce that if a point $M$ is from the convex hull then it satisfy the equations:

  • $\forall i \qquad$ $\sum_{k} (M_{i,i})_{k,k}=1$
  • $\forall i \qquad$ the matrix $M_{i,i}$ is diagonal.
  • $\forall i \neq j \qquad$ the diagonal of $M_{i,j}$ is zeros.
  • $\forall i \neq j \qquad$ $\sum_{k,m}(M_{i,j})_{k,m}=1$
  • $\forall i \neq j \quad \forall p \quad$ $\sum_{k}(M_{i,k})_{j,j}=\sum_{k} (M_{i,k})_{j,p}$
  • $M$ is symmetric.

The question is, are they sufficient?

$\endgroup$
14
  • 1
    $\begingroup$ Which set of points in what space? Are the $M$ the points, in $\mathbb{R}^{n^2 \times n^2}$ where $\sigma$ runs over all permutations? $\endgroup$
    – Vincent
    Nov 15, 2017 at 13:59
  • $\begingroup$ yes the space is $\mathbb{R}^{n^2 \times n^2}$ $\endgroup$ Nov 15, 2017 at 14:12
  • 2
    $\begingroup$ Could you describe the polytope for $n = 1, 2, 3$ perhaps? $\endgroup$ Nov 15, 2017 at 18:46
  • 2
    $\begingroup$ So we are looking at the convex hull of $n!$ points in $\mathbb{R}^{n^4}$. So for $n=1, 2, 3,$ the polytopes will simply be simplices of dimension $0, 1, 5$ assuming there is no relation between the points. For $n=4$ the dimension of the polytope spanned by $24$ points is $22$. I think it is very plausible, that the number of equations will be exponential in $n$. From $n=7$ it is the case that $n!>n^4$, so all cases before that might be somewhat exceptional. $\endgroup$ Nov 16, 2017 at 19:08
  • 1
    $\begingroup$ .. in fact for $n=4$, the polytope you are looking for is the cyclic polytope of dimension $22$ with $24$ vertices. .. $\endgroup$ Nov 16, 2017 at 19:35

0

Your Answer

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