2
votes
1answer
45 views

Showing that this family of vectors generates $\mathbb{R}^n$

Suppose that: $$\{x\in\mathbb{R}^n\mid a_i^Tx\le b_i, i=1,2,\dots,m\}=\{x\in\mathbb{R}^n\mid g_j^Tx\le h_j, j=1,2,\dots,k\}$$ How can I show that if the vectors $a_1,\dots,a_m$ span $\mathbb{R}^n$ ...
2
votes
1answer
93 views

Dimension of polyhedron defined by inequalities and rank of implied equalities

I'm looking at "Optimization Over Integers" by Bertsimas and Weismantel and I have a question about one of the examples in the book. I'm getting a conflicting answer and I'm not sure what I'm ...
1
vote
0answers
36 views

Convex polyhedron is union of simplices

Given a convex polyhedron $P$, how can we prove that every point $x \in P$ is in some simplex whose vertices are vertices of $P$? One proof is to inductively build a triangulation of $P$. If $P$ is ...
2
votes
0answers
32 views

The dimension of birkoff polytope

Let $P_m$ be a subset for R^mxm be the polytope given by: $x_i,_j \ge 0$ $x_i,_1 + ... + x_i,_m \le 1$ $x_1,_j + ... + x_m,_j \le 1$ $\sum_{1 \le i,j \le m } \ x_i,_j \ge m-1$ Contruct a ...
2
votes
0answers
46 views

Convex cone as sum of simplices?

In 3D a pyramid with a square base can be decomposed into the sum of two tetrahedra, i.e. two 3-simplices. I am dealing with a homogeneous N-dimensional system of inequalities and my solution is a ...
1
vote
1answer
133 views

How tell if a polyhedron contains a lattice point

So given a polyhedron $Ax \le b$ Is there an Algorithm or formula to determine whether said polyhedron contains a lattice point (integer point) I was thinking a couple things: brute force ...
1
vote
1answer
205 views

How to compute the image of a polyhedron under a linear transformation

Suppose $P$ is a polyhedron whose representation as a system of linear inequalities is given to us: $$ P = \{ x ~|~ Ax \leq b\}$$ Define $P'$ be the image of $P$ under the linear transformation which ...
2
votes
2answers
373 views

On gluing regular tetrahedra together to form a ring

The above are part of the articles and some background of it. And there is one claim in the articles, saying that " in order to show that no trivial ring can be formed, it is sufficient to show ...