Proving the image of a convex polyhedron under a linear map is a polyhedronprove for...

Kendrick Hampton

Kendrick Hampton

Answered

2022-07-01

Proving the image of a convex polyhedron under a linear map is a polyhedron
prove for A R m × n and a convex polyhedron Q R n that the set
is also a convex polyhedron. However, I am asked to do so using the following statement about convex polyhedra (which is easy to prove):
P R m + n  is a polyhedron  { x R n ( x , y ) P  for some  y R m } .         ( 1 )
This seems like it should be easy but I'm having trouble.
One approach is to write Q as a set of linear inequalities
Q = { x R n B x b }
and then try to write A ( Q ) as as system of linear inequalities
A ( Q ) = { y R m B A 1 y b } .
This doesn't quite work since A may not be invertible. More importantly, it does not use the statement (#1) given above.

Answer & Explanation

lilao8x

lilao8x

Expert

2022-07-02Added 22 answers

Statement (1) tells us the projection maps (over any variables) take polyhedral to polyhedral.
Now set
P = { ( x , y ) :   B x b ,   y = A x }
Clearly P is polyhedral. Now observe that the projection map ( x , y ) y takes P to A ( Q ). Therefore A ( Q ) is a polyhedral.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?