Exercise 2.17

Clearly, $p:=\left[\begin{array}{c}\hfill x^{\text{∗}}\hfill \\ \hfill b-A{x}^{\text{∗}}\hfill \end{array}\right]$ is in the new polyhedron. Without loss of generality, we may assume that, after reordering the inequalities and renumbering the variables, the active constraints at $x^{\text{∗}}$ are the first $k$ inequalities in $\mathit{Ax}\le b$ and $x_i\ge 0$ for $i=1,\dots ,l$ for some integers $k,l\ge 0$. Then the active constraints at $p$ are precisely the equalities $\mathit{Ax}+z=b,x_i\ge 0$ for $i=1,\dots ,l$, and $z_j\ge 0$ for $j=1,\dots ,k$. Now, for any $\left[\begin{array}{c}x\hfill \\ z\hfill \end{array}\right]$ satisfying $\mathit{Ax}+z=b,x_i=0$ for $i=1,\dots ,l$, and $z_j=0$ for $j=1,\dots ,k$, we must have $x$ satisfying the first $k$ inequalities in $\mathit{Ax}\le b$ at equality since $z_j=0$ for $j=1,\dots ,k$. Hence, $x$ is a solution to $a_i^{\top <!--\; FUNCTION\; APPLICATION\; -->}x=b_i$ for $i=1,\dots ,k$, and $x_1=\cdots =x_l=0$, implying that $x=x^{\text{∗}}$ since $x^{\text{∗}}$ is the unique solution to the system. This gives $z=b-A{x}^{\text{∗}}$. Hence, $p$ is a basic feasible solution.

Note that the number of active constraints at $p$ is $m+l+k$. If $p$ is degenerate, then $m+l+k>n+m$, implying that $l+k>n$. This shows that there are more than $n$ active constraints at $x^{\text{∗}}$, contradicting that $x^{\text{∗}}$ is nondegenerate.

Let $k$ denote the number of active constraints at $x^{\text{∗}}$ in $Ax\le b$ and $l$ denote the number of active non-negativity constraints. In other words,

By theorem assumption, $k+l\ge n$ since $x^{\text{∗}}$ is basic and $k+l\le n$ since $x^{\text{∗}}$ is nondegenerate; thus, $k+l=n$. Denote $y^{\text{∗}}:=\left[\begin{array}{cc}\hfill x^{\text{∗}}\hfill & \hfill b-A{x}^{\text{∗}}\hfill \end{array}\right]$ and consider the standard form polyhedron

We then have

1.

$y^{\text{∗}}$ is feasible.
This is obvious, as we have $A{x}^{\text{∗}}+(b-A{x}^{\text{∗}})=b$ with $x^{\text{∗}}\ge 0$ and $z=b-A{x}^{\text{∗}}\ge 0$ by the properties of the original polyhedron.

2.

$y^{\text{∗}}$ is non-degenerate basic.
At the point $y^{\text{∗}}$ we have $$\begin{array}{cc}\forall <!--\; FUNCTION\; APPLICATION\; -->i=1,\dots ,m:\hfill & a_{(i)}^{\prime }{x}_{(i)}+(b_{(i)}-a_i^{\prime }{x}_{(i)})=b_{(i)}\\ \forall <!--\; FUNCTION\; APPLICATION\; -->i=1,\dots ,k\hfill & z_i=b_i-a_i^{\prime }{x}_i=0\\ \forall <!--\; FUNCTION\; APPLICATION\; -->j=1,\dots ,l:\hfill & x_{(j)}=0\end{array}$$

Thus, we have exactly $m+k+l$ active constraints in a polyhedron of an $m+n$-dimensional space. In other words, $y^{\text{∗}}$ is a basic nondegenerate solution.