Computations for "Four Dimensional Polytopes of Minimum Positive Semidefinite Rank"

João Gouveia, Kanstantsin Pashkovich, Richard Z Robinson, Rekha R Thomas



Here, you can find all the computations which we rely on in "Four Dimensional Polytopes of Minimum Positive Semidefinite Rank". The files are available both as a zip file containing all the source files and as pdfs.



Conditions for Psd-Minimality: Approach


Let us explain the way in which we organize the computations to obtain precise conditions for psd-minimality of 4-polytopes.


Recall the approach from the paper. This approach results in precise conditions for a polytope $P$ in a given combinatorial class to be psd-minimal:

  1. Compute the slack ideal $I_P \subset \mathbb{R}[x_1,\ldots,x_t]$ of a polytope $P$ in the class and let $J_P$ be a copy of $I_P$ in the variables $y_1, \ldots, y_t$.
  2. Consider the ideal $$K_P = I_P + J_P + \langle y_i^2 - x_i \,\,i=1,\ldots,t \rangle \subset \mathbb{R}[x_1,\ldots, x_t, y_1, \ldots, y_t].$$ By construction, for any $(x, y)\in \mathcal{V}(K_P)$ the matrix $S_P(y)$ is a Hadamard square root of $S_P(x)$. Thus, the polytope $P$ is psd-minimal if and only if there are $s$, $r\in\mathbb{R}^t$ such that $(s,r)\in \mathcal{V}(K_P)$ and $S_P=S_P(s)$.
  3. Eliminating $y_1,\ldots, y_t$ from $K_P$ we obtain the ideal $K_P \cap \mathbb{R}[x_1,\ldots,x_t]$. A minimal generating set of this elimination ideal gives the conditions for a polytope in the class of $P$ to be psd-minimal.


However, in some cases even the first step is difficult, i.e. for some combinatorial classes of polytopes it is a hard task to compute a full list of generators for their slack ideals. For example, the symbolic slack matrix for the 4-cube is big and involves many variables, making the first step problematic. We rely on several ideas to simplify the computations, which are all explained in the paper (see the examples below for an illustration).



Conditions for Psd-Minimality: Example (Class 22)


Let us consider a symbolic matrix $S_P(y)$ corresponding to a Hadamard square root of rank five for a slack matrix of a psd-minimal 4-polytope in class 22. Recall, that some entries in the matrix can be set to one by scaling rows and columns: $$\begin{bmatrix} 1& 1& 1& 0& 0& 0& 0& 0& 0\\ 1& y_1& 0& 1& 0& 1& 0& 1& 0\\ 1& 0& 0& y_4& 0& y_8& 0& 0& 1\\ 0& 0& 0& 1& 0& 0&y_{11}& y_{14}& 0\\ 1& 0& y_2& y_5& 0& 0&y_{12}& 0&y_{17}\\ 0& 1& 0& 0& 1& y_9& 0& y_{15}& 0\\ 0& 0& 0& 0& 1&y_{10}& 0& 0&y_{18}\\ 0& 1& y_3& 0&y_6& 0&y_{13}& y_{16}& 0\\ 0& 0& 1& 0&y_7& 0& 1& 0&y_{19} \end{bmatrix}\,.$$


Computing 6-minors of $S_P(y)$ and saturating the obtained ideal, we see that $$y_{16}-y_{18},\, y_{15}-y_{18},\, y_{14}-y_{18},\, y_{11}-1, y_5-1,\, y_4-1,\, y_3- y_{13},\, y_2-y_{12}$$ are in the ideal $J_P$, showing that the relations $$y_{16}=y_{18},\, y_{15}=y_{18},\, y_{14}=y_{18},\, y_{11}=1, y_5=1,\, y_4=1,\, y_3=y_{13},\, y_2=y_{12}$$ hold whenever the matrix $S_P(y)$ has rank five and has the given zero pattern. Thus we can simplify the parametrization: $$\begin{bmatrix} 1& 1& 1& 0& 0& 0& 0& 0& 0\\ 1& y_1& 0& 1& 0& 1& 0& 1& 0\\ 1& 0& 0& 1& 0& y_8& 0& 0& 1\\ 0& 0& 0& 1& 0& 0& 1& y_{14}& 0\\ 1& 0& y_2& 1& 0& 0& y_2& 0&y_{17}\\ 0& 1& 0& 0& 1& y_9& 0& y_{14}& 0\\ 0& 0& 0& 0& 1&y_{10}& 0& 0&y_{14}\\ 0& 1& y_3& 0&y_6& 0& y_3& y_{14}& 0\\ 0& 0& 1& 0&y_7& 0& 1& 0&y_{19} \end{bmatrix}\,.$$


Computing 6-minors for the simplified matrix and saturating the obtained ideal, we get an ideal containing $$y_8y_{17}-y_2-y_{17}+1\,.$$ Thus, whenever the matrix $S_P(y)$ has rank five and has the given zero pattern, $$y_8y_{17}-y_2-y_{17}+1=0\,.$$ Moreover, since the corresponding slack matrix $S_P(x)$ has the same parametrization and the same rank, $$x_8x_{17}-x_2-x_{17}+1=0$$ holds as well. Substituting $x_1,\ldots,x_t$ by $y^2_1,\ldots, y^2_t$, we obtain $$y^2_8y^2_{17}-y^2_2-y^2_{17}+1=0, $$ which leads to $$0=(y_8y_{17}+1)^2-(y_2+y_{17})^2-(y^2_8y^2_{17}-y^2_2-y^2_{17}+1)=2y_2y_{17}-2y_8y_{17}.$$ Because $y_{17}$ cannot take value zero, we obtain $y_2=y_8$, whenever $S_P(y)$ is a Hadamard square root of rank five for a slack matrix of a $4$-polytope.


Note, that the first simplification relies on the slack ideal $J_P$ only, while the second uses the information about the ideal $K_P$. Simplifying the patrametrization of $S_P(y)$ in the same manner, we obtain a list of admissible parametrizations. For example, here is one of the admissible parametrizations: $$\begin{bmatrix} 1& 1& 1& 0& 0& 0& 0& 0& 0\\ 1& 1& 0& 1& 0& 1& 0& 1& 0\\ 1& 0& 0& 1& 0& y_2& 0& 0& 1\\ 0& 0& 0& 1& 0& 0& 1& 1& 0\\ 1& 0& y_2& 1& 0& 0& y_2& 0& 1\\ 0& 1& 0& 0& 1& 1& 0& 1& 0\\ 0& 0& 0& 0& 1& y_2& 0& 0& 1\\ 0& 1& 1& 0& 1& 0& 1& 1& 0\\ 0& 0& y_2& 0& 1& 0& y_2& 0& 1 \end{bmatrix}\,,$$ by permuting rows and columns we bring it in the form: $$\begin{bmatrix} 1& 1& 1& 0& 0& 0& 0& 0& 0\\ 1& 1& 0& 1& 0& 1& 0& 1& 0\\ 1& 0& 0& 1& 0& 1& 0& 0& 1\\ 0& 0& 0& 1& 0& 0& 1& 1& 0\\ 1& 0& 1& 1& 0& 0& 1& 0& 1\\ 0& y_2& 0& 0& 1& 1& 0& y_2& 0\\ 0& 0& 0& 0& 1& 1& 0& 0& y_2\\ 0& y_2& 1& 0& 1& 0& 1& y_2& 0\\ 0& 0& 1& 0& 1& 0& 1& 0& y_2 \end{bmatrix}\,.$$


By permutations and scalings of rows and columns for all other admissible parametrizations, we show that a polytope in class 22 is psd-minimal if and only if it has a slack matrix in the form: $$\begin{bmatrix} 1& 1& 1& 0& 0& 0& 0& 0& 0\\ 1& 1& 0& 1& 0& 1& 0& 1& 0\\ 1& 0& 0& 1& 0& 1& 0& 0& 1\\ 0& 0& 0& 1& 0& 0& 1& 1& 0\\ 1& 0& 1& 1& 0& 0& 1& 0& 1\\ 0& x& 0& 0& 1& 1& 0& x& 0\\ 0& 0& 0& 0& 1& 1& 0& 0& x\\ 0& x& 1& 0& 1& 0& 1& x& 0\\ 0& 0& 1& 0& 1& 0& 1& 0& x \end{bmatrix}\,.$$



Conditions for Psd-Minimality: Example (Class 28)


Let us illustrate the technique which we use for polytopes with a cubical or an octahedral facet. Here is the sign pattern of the slack matrix for polytopes in class 28: $$\begin{bmatrix} 0& *& 0& *& 0& *& 0\\ 0& *& 0& *& 0& 0& *\\ 0& *& 0& 0& *& *& 0\\ 0& *& 0& 0& *& 0& *\\ 0& 0& *& *& 0& *& 0\\ 0& 0& *& *& 0& 0& *\\ 0& 0& *& 0& *& *& 0\\ 0& 0& *& 0& *& 0& *\\ *& 0& 0& *& 0& *& 0\\ *& 0& 0& *& 0& 0& *\\ *& 0& 0& 0& *& *& 0\\ *& 0& 0& 0& *& 0& * \end{bmatrix}\,.$$


It is easy to see that the first column of the matrix corresponds to a cubical facet and the first eight rows correspond to the vertices in this facet. Using the parametrizations of Hadamard square roots of rank four for slack matrices of psd-minimal 3-cubes, we can assume that the Hadamard square root of rank five for a psd-minimal polytope in class 28 has one of the three parametrizations below: $$\begin{bmatrix} 0& 1& 0& 1& 0& 1& 0\\ 0& 1& 0&y_1& 0& 0& 1\\ 0& 1& 0& 0& 1& 1& 0\\ 0& 1& 0& 0&y_1& 0& 1\\ 0& 0& 1& 1& 0& 1& 0\\ 0& 0& 1&y_1& 0& 0& 1\\ 0& 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 0&y_1& 0& 1\\ y_2& 0& 0&y_6& 0&y_{10}& 0\\ y_3& 0& 0&y_7& 0& 0& y_{12}\\ y_4& 0& 0& 0&y_8&y_{11}& 0\\ y_5& 0& 0& 0&y_9& 0& y_{13} \end{bmatrix}\,,\qquad\begin{bmatrix} 0& 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 0& 1\\ 0& 1& 0& 0& 1& y_1& 0\\ 0& 1& 0& 0& 1& 0& y_1\\ 0& 0& 1& 1& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 0& 1& y_1& 0\\ 0& 0& 1& 0& 1& 0& y_1\\ y_2& 0& 0&y_6& 0&y_{10}& 0\\ y_3& 0& 0&y_7& 0& 0& y_{12}\\ y_4& 0& 0& 0&y_8&y_{11}& 0\\ y_5& 0& 0& 0&y_9& 0& y_{13} \end{bmatrix}\,,\qquad\begin{bmatrix} 0& 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 0& 1\\ 0& 1& 0& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 0& 1\\ 0& 0& 1& 1& 0& y_1& 0\\ 0& 0& 1& 1& 0& 0& y_1\\ 0& 0& 1& 0& 1& y_1& 0\\ 0& 0& 1& 0& 1& 0& y_1\\ y_2& 0& 0&y_6& 0&y_{10}& 0\\ y_3& 0& 0&y_7& 0& 0& y_{12}\\ y_4& 0& 0& 0&y_8&y_{11}& 0\\ y_5& 0& 0& 0&y_9& 0& y_{13} \end{bmatrix}\,.$$


Note, that the first parametrization can be obtained from the second by permuting rows and columns and renaming the variables. Hence, we can run the computations only for the second and third parametrizations. Scaling the last four rows and the first column, we set some variables to one and obtain the parametrizations below: $$\begin{bmatrix} 0& 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 0& 1\\ 0& 1& 0& 0& 1& y_1& 0\\ 0& 1& 0& 0& 1& 0& y_1\\ 0& 0& 1& 1& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 0& 1& y_1& 0\\ 0& 0& 1& 0& 1& 0& y_1\\ 1& 0& 0& 1& 0& y_2& 0\\ 1& 0& 0&y_3& 0& 0& y_4\\ 1& 0& 0& 0&y_5& y_6& 0\\ 1& 0& 0& 0&y_7& 0& y_8 \end{bmatrix}\,,\qquad\begin{bmatrix} 0& 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 0& 1\\ 0& 1& 0& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 0& 1\\ 0& 0& 1& 1& 0& y_1& 0\\ 0& 0& 1& 1& 0& 0& y_1\\ 0& 0& 1& 0& 1& y_1& 0\\ 0& 0& 1& 0& 1& 0& y_1\\ 1& 0& 0& 1& 0& y_2& 0\\ 1& 0& 0&y_3& 0& 0& y_4\\ 1& 0& 0& 0&y_5& y_6& 0\\ 1& 0& 0& 0&y_7& 0& y_8 \end{bmatrix}\,.$$



Files


Here are the pdfs illustrating all the computational results.

Lemma 3.4
Corollary 5.12 (Class 3)
Corollary 5.12 (Class 10)
Proposition 6.2 (Class 12)
Proposition 6.4 (Class 14)
Proposition 7.1
Proposition 7.3 (Class 18)
Proposition 7.3 (Class 20)
Proposition 7.3 (Class 22)
Proposition 7.3 (Class 24)
Proposition 7.3 (Class 26)
Proposition 7.4 (Class 28)
Proposition 7.5 (Class 30)

Here is the zip file containing all the source files (for more information on how to run the files see sagemath.org).