Ask Your Question
1

Klee-Minty cube vertices for D=5

asked 2020-11-23 17:04:16 +0100

Cyrille gravatar image

updated 2020-11-23 17:45:47 +0100

slelievre gravatar image

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 flag offensive close merge delete

Comments

2

Une erreur ici:

254 != 25
FrédéricC gravatar imageFrédéricC ( 2020-11-23 17:13:44 +0100 )edit

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

Cyrille gravatar imageCyrille ( 2020-11-23 18:50:51 +0100 )edit

1 Answer

Sort by » oldest newest most voted
1

answered 2020-11-23 20:57:47 +0100

rburing gravatar image

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))
edit flag offensive delete link more

Comments

Thanks I am profoundly stupid.

Cyrille gravatar imageCyrille ( 2020-11-23 22:27:09 +0100 )edit

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

rburing gravatar imagerburing ( 2020-11-23 22:46:33 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2020-11-23 17:04:16 +0100

Seen: 44 times

Last updated: Nov 23 '20