Exercise 3.14

Let the given feasible tableau be associated with a basis matrix $B$, corresponding to the basic indices $B(1),\dots ,B(m)$. A row $i$ of the tableau, corresponding to the basic variable $x_{B(i)}$, is lexicographically positive if its first non-zero entry is positive.

If the basic feasible solution $x$ is non-degenerate, then $x_{B(i)}>0$ for all $i$. Since $x_{B(i)}$ is the first entry in row $i$ (in the zeroth column), all rows are already lexicographically positive.

The issue arises if the solution is degenerate, i.e., $x_{B(i)}=0$ for some $i$. In this case, the lexicographical sign of row $i$ depends on the subsequent entries, which are the components of the $i$-th row of the matrix $B^{-1}A$.

To resolve this, we apply the hint and permute the columns of the tableau. We define a new column ordering such that the basic columns $B(1),\dots ,B(m)$ appear first, followed by all non-basic columns. Consider the $i$-th row of this reordered tableau.

• The entry in the zeroth column is still $x_{B(i)}$.
• The next $m$ columns correspond to the basic variables. The column for the basic variable $x_{B(k)}$ in the tableau is $B^{-1}{A}_{B(k)}$, which is the $k$-th unit vector $e_k$. Therefore, the entries in row $i$ for these columns are all 0, except for a 1 in the position corresponding to column $B(i)$.

We now check for lexicographical positivity of row $i$:

• If $x_{B(i)}>0$, the first element of the row is positive, and the row is lexicographically positive.
• If $x_{B(i)}=0$, the first element is zero. Reading from left to right, the first non-zero element we encounter will be the ’1’ corresponding to the column of the basic variable $x_{B(i)}$. Since this ’1’ is positive, the row is lexicographically positive.

Since this holds for all rows $i=1,\dots ,m$, this permutation of columns yields a new tableau in which every row (other than the zeroth row) is lexicographically positive. □