Underlying assumption in a Primal/Dual table

Question

I just read in one of the questions answered by @MikeSpivey that the following table is provided in Sierksma's Linear and Integer Programming: Theory and Practice, Volume 1, page 144.

Primal Optimal Solution                     Dual Optimal Solution
(a) Multiple                     implies    Degenerate
(b) Unique and nondegenerate     implies    Unique and nondegenerate
(c) Multiple and nondegenerate   implies    Unique and degenerate
(d) Unique and degenerate        implies    Multiple

I wonder if the information provided in this table is provided based on the assumption that matrix A has full rank.

Answer 1

An LP is degenerate if in a basic feasible solution, one of the basic variables takes on a zero value. Degeneracy is caused by redundant constraint(s) and could cost simplex method extra iterations, as demonstrated in the following example.

$max \space z=x_{1}+x_{2}+x_{3}$

$x_{1}+x_{2} \leq 1$

$-x_{2}+x_{3} \leq 0$

$x_{1},x_{2},x_{3} \geq 0$

Note that constraints $x_{2} \geq 0$ follows from constraints $-x_{2}+x_{3} \leq 0$ and $x_{3} \geq 0$, and is thus redundant. You can check that after iteration 2, the value of the objective function remains the same $z = 1$. Due to degeneracy, basis change does not cause the iteration to follow an edge; we are still in the same vertex.

The example was taken from here An Example of Degeneracy in Linear Programming

This example shows that redundancy may occur even if matrix $A$ has full rank.