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