Proving the image of a convex polyhedron under a linear map is a polyhedronprove for A ∈ R m × n and a convex polyhedron Q ⊆ R n that the setis 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.

Question

Proving the image of a convex polyhedron under a linear map is a polyhedronprove for   A  ∈        R          m      ×      n       and a convex polyhedron   Q  ⊆        R    n   that the setis 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&#039;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&#039;t quite work since A may not be invertible. More importantly, it does not use the statement (#1) given above.

lilao8x · Accepted Answer

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.

Proving the image of a convex polyhedron under a linear map is a polyhedron prove for A &#x2

Answered question

Answer & Explanation

New Questions in Algebra I