# Klee-Minty cube vertices for D=5

According to Wikipedia (but this is well known), A Klee-Minty cube in $D$ dimensions is defined by

$x_1\leq 5$

$4 x_1 + x_2 \leq 25$

$8 x_1 + 4 x_2 + x_3 \leq 125$

$16 x_1 + 8 x_2 + 4 x_3 + x_4 \leq 625$

$32 x_1+ 16 x_2 + 8 x_3 + 4 x_4 + x_5 \leq 3125$

$\vdots \vdots$

$2^D x_1 + 2^{D-1} x_2 + 2^{D-2} x_3 + \ldots + 4 x_{D-1} + x_D \leq 5^D$

$x_1 \geq 0$

$x_2 \geq 0$

$x_3 \geq 0$

$x_4 \geq 0$

$x_5 \geq 0$

This polyhedron has $2^D$ vertices. How can I find them?

I have tried the following code for $D = 5$ --- that is 32 vertices.

A = matrix(QQ, 10, 5,
[0, 0, 0, 0, -1,
0, 0, 0, -1, -4,
0, 0, -1, -4, -8,
0, -1, -4, -8, -16,
-1, -4, -8, -16, -32,
1, 0, 0, 0, 0,
0, 1, 0, 0, 0,
0, 0, 1, 0, 0,
0, 0, 0, 1, 0,
0, 0, 0, 0, 1])
show(LatexExpr(r"\text{A = }"), A)
b = vector(QQ, [5, 254, 125, 625, 3125, 0, 0, 0, 0, 0])
show(LatexExpr(r"\text{b = }"), b)
c = vector(QQ, [2^4, 2^3, 2^2, 2^1, 2^0])
show(LatexExpr(r"\text{c = }"), c)
AA = matrix(list(list([b]) + list(transpose(A))))
show(transpose(AA))
pol = Polyhedron(ieqs=AA)
pol.Hrepresentation()


But I am far away from the account and some of the vertices are in the negative part of the hyperplane (which is impossible). Need some help to decipher my mistake(s). Thanks.

edit retag close merge delete

2

Une erreur ici:

254 != 25

( 2020-11-23 17:13:44 +0200 )edit

Thanks to have sen that error but it doesn't change the fact that I could not find the vertices.

( 2020-11-23 18:50:51 +0200 )edit

Sort by » oldest newest most voted

In addition to the typo, you displayed the correct transpose(AA) but you accidentally passed the un-transposed AA as the ieqs argument to Polyhedron. It should be:

sage: pol = Polyhedron(ieqs=transpose(AA))
sage: pol.Hrepresentation()
(An inequality (-1, -4, -8, -16, -32) x + 3125 >= 0,
An inequality (0, -1, -4, -8, -16) x + 625 >= 0,
An inequality (0, 0, -1, -4, -8) x + 125 >= 0,
An inequality (0, 0, 0, -1, -4) x + 25 >= 0,
An inequality (0, 0, 0, 0, -1) x + 5 >= 0,
An inequality (1, 0, 0, 0, 0) x + 0 >= 0,
An inequality (0, 0, 0, 0, 1) x + 0 >= 0,
An inequality (0, 0, 0, 1, 0) x + 0 >= 0,
An inequality (0, 0, 1, 0, 0) x + 0 >= 0,
An inequality (0, 1, 0, 0, 0) x + 0 >= 0)
sage: len(pol.vertices())
32
sage: pol.vertices()
(A vertex at (3125, 0, 0, 0, 0),
A vertex at (865, 505, 0, 5, 5),
A vertex at (1625, 125, 125, 0, 0),
A vertex at (1225, 325, 25, 25, 0),
A vertex at (1385, 245, 65, 5, 5),
A vertex at (1465, 205, 85, 0, 5),
A vertex at (785, 545, 0, 0, 5),
A vertex at (625, 625, 0, 0, 0),
A vertex at (1025, 425, 0, 25, 0),
A vertex at (2725, 0, 0, 25, 0),
A vertex at (2885, 0, 0, 5, 5),
A vertex at (2125, 0, 125, 0, 0),
A vertex at (2525, 0, 25, 25, 0),
A vertex at (2365, 0, 65, 5, 5),
A vertex at (2285, 0, 85, 0, 5),
A vertex at (2965, 0, 0, 0, 5),
A vertex at (0, 0, 0, 0, 5),
A vertex at (0, 0, 0, 0, 0),
A vertex at (0, 505, 0, 5, 5),
A vertex at (0, 125, 125, 0, 0),
A vertex at (0, 325, 25, 25, 0),
A vertex at (0, 245, 65, 5, 5),
A vertex at (0, 205, 85, 0, 5),
A vertex at (0, 545, 0, 0, 5),
A vertex at (0, 625, 0, 0, 0),
A vertex at (0, 425, 0, 25, 0),
A vertex at (0, 0, 0, 25, 0),
A vertex at (0, 0, 0, 5, 5),
A vertex at (0, 0, 125, 0, 0),
A vertex at (0, 0, 25, 25, 0),
A vertex at (0, 0, 65, 5, 5),
A vertex at (0, 0, 85, 0, 5))

more

Thanks I am profoundly stupid.

( 2020-11-23 22:27:09 +0200 )edit

Don't worry; an expert is someone who has made every possible mistake :)

( 2020-11-23 22:46:33 +0200 )edit