Exercise 2.5 (Extreme points of isomorphic polyhedra)

(a)

Let $E(X)$ define the set of all extreme points of a polyhedron $X$. We know that $f$ defines a bijection between the sets of $P$ and $Q$. We now demonstrate that the restriction of $f$ to the extreme points of $P$ $$f:E(P)\mapsto E(Q)$$

defines a bijective relation between the set of extreme points of $P$ and the set of the extreme points of $Q$.

• (well-definedness) $f\left(E(P)\right)\subseteq E(Q)$.
  Let $x^{\text{∗}}$ be an extreme point of $P$. We demonstrate that $f\left(x^{\text{∗}}\right)$ is an extreme point of $Q$. By Theorem 2.3, we can use a vertex definition of an extreme point, i.e., we can find a $c\in {\Re }^n$ such that for all $x\in P:x\ne x^{\text{∗}}$ we have $c^{\prime }{x}^{\text{∗}}<c^{\prime }x$. By exercise hypothesis, this is equivalent to

  $$c^{\prime }g\left(f\left(x^{\text{∗}}\right)\right)<c^{\prime }g\left(f\left(x\right)\right)$$

  for all $x$ in $P$ such that $x\ne x^{\text{∗}}$.

  By exercise hypothesis, $f$ is a bijective function; thus, defining $y^{\text{∗}}:=f\left(x^{\text{∗}}\right)$, we obtain $f\left(P\setminus \{x^{\text{∗}}\}\right)=Q\setminus \{y^{\text{∗}}\}$. In other words,

  $$c^{\prime }g\left(y^{\text{∗}}\right)<c^{\prime }g\left(y\right)$$

  for all $y$ in $P$ such that $y\ne y^{\text{∗}}$.

  Since $g$ is affine, we can find a $n\times m$ matrix $A$ and a vector $b\in {\Re }^m$ such that $g(y)=Ay+b$ for any $y\in Q$. Using this, we can equivalently rewrite our inequality as

  $$\begin{array}{llll}\hfill c^{\prime }\left(A{y}^{\text{∗}}+b\right)& <c^{\prime }\left(Ay+b\right)& \hfill & \\ \hfill c^{\prime }A{y}^{\text{∗}}& <c^{\prime }Ay& \hfill & \end{array}$$

  for all $y\in P:y\ne y^{\text{∗}}$.

  Define $k:={(c^{\prime }A)}^{\prime }=A^{\prime }c$. Then, we have found a vector $k\in {\Re }^m$ such that for all $y\in P$ not equal to $y^{\text{∗}}$ we have

  $$u^{\prime }{y}^{\text{∗}}<u^{\prime }y.$$

  In other words, $f\left(x^{\text{∗}}\right)=y^{\text{∗}}$ is an extreme point of $Q$.

• (surjectivity) For all $y^{\text{∗}}\in E(Q)$ there exists a $x^{\text{∗}}\in E(P)$ such that $f(x^{\text{∗}})=y^{\text{∗}}$.
  By Theorem 2.3, we can find a $k\in {\Re }^m$ such that for all $y\in Q:y\ne y^{\text{∗}}$ we have

  $$k^{\prime }{y}^{\text{∗}}<k^{\prime }y.$$

  Symmetrically repeating the steps of the previous part, we can show the existence of a $c\in {\Re }^n$ such that for all $x\in P$ with $x\ne g\left(y^{\text{∗}}\right)$ we have

  $$c^{\prime }g\left(y^{\text{∗}}\right)<c^{\prime }x.$$

• (injectivity) Whenever $f\left(x^{\text{∗}}\right)=f\left(z^{\text{∗}}\right)$, we have $x^{\text{∗}}=z^{\text{∗}}$.
  This follows directly from the injectivity of $f$ on $P$ since

  $$f\left(x^{\text{∗}}\right)=f\left(z^{\text{∗}}\right)⟺g\left(f\left(x^{\text{∗}}\right)\right)=g\left(f\left(z^{\text{∗}}\right)\right)⟺x^{\text{∗}}=z^{\text{∗}}$$

(b)

Based on the previous part, we need to find an isomorphism $f$ and its inverse $g$, i.e., affine bijections, which transform $P$ into $Q$ and vice versa. We argue that both functions are given by $$\begin{array}{llll}\hfill f:P\mapsto Q,& f\left(x\right)=\left[\begin{array}{c}\hfill x\hfill \\ \hfill Ax-b\hfill \end{array}\right]=\left[\begin{array}{c}\hfill I_{n\times n}\hfill \\ \hfill A\hfill \end{array}\right]x+\left[\begin{array}{c}\hfill 0_{n\times 1}\hfill \\ \hfill -b\hfill \end{array}\right]& \hfill & \\ \multicolumn{4}{c}{\text{and}}\\ \\ \hfill g:Q\mapsto P,& g\left(\left[\begin{array}{c}\hfill x\hfill \\ \hfill z\hfill \end{array}\right]\right)=\left[\begin{array}{cc}\hfill I_{n\times n}\hfill & \hfill 0_{n\times k}\hfill \end{array}\right]\left[\begin{array}{c}\hfill x\hfill \\ \hfill z\hfill \end{array}\right]& \hfill & \end{array}$$

It is then easy to verify that

• (well-definedness) for any $x\ge 0$ with $Ax\ge b$, its transformation $f(x)={[x,z]}^{\prime }\ge 0$ satisfies $Ax-z=b$; the converse is true for $g$. In other words, $f(P)=Q$ and $g(Q)=P$.
• (affinity) $f$ and $g$ are affine by definition;
• (bijectivity) $f$ and $g$ are bijective with $f\circ g={\mathrm{id}}_Q$ and $g\circ f={\mathrm{id}}_P$.

In the solution of this exercise we are going to use the notation $g\circ f={\mathrm{id}}_P$ and $f\circ g={\mathrm{id}}_Q$ to denote respectively $g(f(x))=x$ for all $x\in P$, and $f(g(y))=y$ for all $y\in Q$.

(a) In this part of the exercise we need to show that if there exist affine functions $f:P\mapsto$ $Q,g:Q\mapsto P$ such that $g\circ f={\mathrm{id}}_P$ and $f\circ g={\mathrm{id}}_Q$, then $x^{\text{∗}}$ is an extreme point of $P$ if and only if $f\left(x^{\text{∗}}\right)$ is an extreme point of $Q$. Consider an extreme point of $P$, let it be $x^{\text{∗}}.$ By Theorem $2.3$ we know that $x^{\text{∗}}$ is also a vertex of $P$, meaning that there exists $c\in {ℝ}^n$ such that $c^{\prime }{x}^{\text{∗}}<c^{\prime }x$ for any $x\in P$ different from $x^{\text{∗}}$. Therefore $c^{\prime }g\left(f\left(x^{\text{∗}}\right)\right)<c^{\prime }g(f(x))$ for every $x\in P,x\ne x^{\text{∗}}$, since $g\circ f={\mathrm{id}}_P.$ Let $y^{\text{∗}}=f\left(x^{\text{∗}}\right)$ and $y=f(x)$, hence $c^{\prime }g\left(y^{\text{∗}}\right)<c^{\prime }g(y)$ for any $y\in Q,y\ne y^{\text{∗}}$ $g$ is an affine function, which means that there exist $D$ matrix $n\times m$ and a vector $e\in {ℝ}^n$ such that $g(y)=\mathit{Dy}+e$ for every $y\in Q.$ So

Defining $u:=D^{\prime }c\in {ℝ}^m$ we get that $u^{\prime }{y}^{\text{∗}}<u^{\prime }y$ for every $y\in Q,y\ne y^{\text{∗}}$, i.e. $y^{\text{∗}}$ is a vertex of $Q$ and therefore an extreme point of $Q$. Thus we showed that if $x^{\text{∗}}$ is an extreme point of $P$, then $f\left(x^{\text{∗}}\right)$ is an extreme point of $Q.$ Applying an identical argument to $y^{\text{∗}}$ extreme point of $Q$ we get that the other direction of the statement.

(b) In order to finish the exercise, we need to find two affine functions $f,g$ such that $g\circ f=$ id ${}_P$ and $f\circ g={\mathrm{id}}_Q.$ Define $f:P\to Q$ and $g:Q\to P$ like this:

where $I_{n\times n}$ is the identity matrix with $n$ rows and columns, $0_{n\times 1}$ is the zero vector with $n$ components and $0_{n\times k}$ is the zero matrix with $n$ rows and $k$ columns. Clearly $f$ and $g$ are affine functions, also $g\circ f={\mathrm{id}}_P$ and $f\circ g={\mathrm{id}}_Q.$ Therefore $P$ and $Q$ are isomorphic.