Exercise 4.12* (Degeneracy and uniqueness - I)

Proof. Consider the general primal problem and its dual

Now suppose that we have obtained a nondegenerate basic feasible solution $x^{\text{∗}}$ of the primal problem. By complementary slackness (Theorem 4.5), we have

In the exercise, we also assume that $x_i^{\text{∗}}\ne 0$ for all $i=1,\dots ,n$. The second condition thus becomes $c_j-p^{\prime }{A}_j$, $j=1,\dots ,n$. In other words, we want to deduce the dual vector from the system of linear equations

Let $B$ be the set of all indices at which constraints $a_i^{\prime }$ become active at $x^{\text{∗}}$ and let $N$ denote the rest. By Definition 2.9, the rows $a_i$, $i\in B$ must be linearly independent. By Definition 2.10, there are exactly $n$ such indices. Thus, the matrix $A_B$ is an $n\times n$ invertible matrix (cf. Theorem 1.2). Using this notation, we can equivalently rewrite (1) as

By construction, we have $a_i^{\prime }{x}^{\text{∗}}=b_i$ for $i\in B$, and we have $a_i^{\prime }{x}^{\text{∗}}>b_i$ for $i\in N$. Notice that the latter implies $p_i=0$, $i\in N$, when combined with the first complementary slackness condition. Thus, (2) equivalently becomes:

As already mentioned, $A_B$ is invertible, and the above system will therefore always result in a unique solution. Rearranging the indices back to the original positions in (1), we obtain the desired vector. □