Exercise 2.9 (Degeneracy and bases)

(a)

Let $x^{\text{∗}}$ be a basic feasible solution with two distinct bases $A_{B(1)},\dots ,A_{B(m)}$ and $A_{C(1)},\dots ,A_{C(m)}$. By definition (Theorem 2.4), the entries of $x^{\text{∗}}$ are zero at both $$\{1,\dots ,n\}\setminus \{B(1),\dots ,B(m)\}$$

and

$$\{1,\dots ,n\}\setminus \{C(1),\dots ,C(m)\}.$$

Since both bases are different, there is at least one $A_{C(i)}$ not equal to any $A_{B(j)},j=1,\dots ,m$; thus, the number of indices in the union of the above sets,

$$\{1,\dots ,n\}\setminus \left(\{B(1),\dots ,B(m)\}\cap \{C(1),\dots ,C(m)\}\right),$$

must be at least $n-m+1$. In other words, $x^{\text{∗}}$ has more than $n-m$ zero components and so it must be degenerate by Definition 2.11.

(b)

No. To see why, consider a polyhedron defined by the following constraints $$\left\{\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \\ \hfill x_3\hfill \end{array}\right]\in {\Re }^3|\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill -1\hfill & \hfill 1\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \\ \hfill x_3\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 1\hfill \end{array}\right],\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \\ \hfill x_3\hfill \end{array}\right]\ge 0\right\}.$$

The given matrix has three columns: $A_1={\left[\begin{array}{cc}\hfill 1\hfill & \hfill -1\hfill \end{array}\right]}^{\prime }$, $A_2={\left[\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \end{array}\right]}^{\prime }$ and $A_3={\left[\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \end{array}\right]}^{\prime }$. Out of these, only the combination $\{1,2\}$ and $\{1,3\}$ can produce a basis, the columns $\{2,3\}$ are not linearly independent. We compute vertices based on procedure from Theorem 2.4:

$$\left[\begin{array}{c}\hfill x_1^{\text{∗}}\hfill \\ \hfill x_2^{\text{∗}}\hfill \end{array}\right]={\left[\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill -1\hfill & \hfill 1\hfill \end{array}\right]}^{-1}\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 1\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 0\hfill \\ \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill y_1^{\text{∗}}\hfill \\ \hfill y_3^{\text{∗}}\hfill \end{array}\right]={\left[\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill -1\hfill & \hfill 1\hfill \end{array}\right]}^{-1}\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 1\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 0\hfill \\ \hfill 1\hfill \end{array}\right]$$

We thus obtain two vertices

$$x^{\text{∗}}=\left[\begin{array}{c}\hfill 0\hfill \\ \hfill 1\hfill \\ \hfill 0\hfill \end{array}\right]y^{\text{∗}}=\left[\begin{array}{c}\hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 1\hfill \end{array}\right].$$

Both solutions are degenerate by definition, yet correspond to distinct bases $\left[\begin{array}{cc}\hfill A_1\hfill & \hfill A_2\hfill \end{array}\right]$ and $\left[\begin{array}{cc}\hfill A_1\hfill & \hfill A_3\hfill \end{array}\right]$ (cf. argument on the page 55). Thus, degenerate solutions are sometimes corresponding to unique bases.

(c)

No. To see why, consider the polyhedron $$\left\{\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \\ \hfill x_3\hfill \end{array}\right]\in {\Re }^3|\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \\ \hfill x_3\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 1\hfill \end{array}\right],\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \\ \hfill x_3\hfill \end{array}\right]\ge 0\right\}.$$

It is easy to verify that there are only three choices for a basis, $\{1,2\}$ and $\{1,3\}$ and $\{2,3\}$. By procedure from Theorem 2.4, the corresponding basic solutions are calculated via

$$\left[\begin{array}{c}\hfill x_1^{\text{∗}}\hfill \\ \hfill x_2^{\text{∗}}\hfill \end{array}\right]={\left[\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 1\hfill \end{array}\right]}^{-1}\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 1\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 0\hfill \\ \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill y_1^{\text{∗}}\hfill \\ \hfill y_3^{\text{∗}}\hfill \end{array}\right]={\left[\begin{array}{cc}\hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill \end{array}\right]}^{-1}\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 1\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill z_2^{\text{∗}}\hfill \\ \hfill z_3^{\text{∗}}\hfill \end{array}\right]={\left[\begin{array}{cc}\hfill 1\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill 1\hfill \end{array}\right]}^{-1}\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 1\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 0\hfill \end{array}\right].$$

In other words, we obtain the vertices

$$x,z=\left[\begin{array}{c}\hfill 0\hfill \\ \hfill 1\hfill \\ \hfill 0\hfill \end{array}\right],y=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 0\hfill \\ \hfill 1\hfill \end{array}\right].$$

Both of the obtained vertices differ by more two columns and are thus not adjacent by definition.

(a) Assume otherwise the basic solution is not degenerate. Then the basic solution have $n-m$ zero components. This uniquely determine $m$ non-zero components, which correspond to a unique choice of basis. Contradiction. Therefore, a basic solution with two different bases must be degenerate.

(b) No, a degenerate basic solution does not necessarily correspond to two different bases. Consider the polyhedron in standard form

This is a polyhedron that contains only one point $(0,0)$ which is also a degenerate basic solution (all constraints are active). However, clearly there is only one choice of basis.

(c) No, it is not true. Consider the example in (b). The polyhedron contains only one basic solution, and hence no adjacent basic solution exists.