# Degeneracy in Linear Programming

1. Nov 14, 2011

### elg

1. The problem statement, all variables and given/known data

Consider the standard form polyhedron {x | Ax = b, x>=0} , and assume that the rows of the
matrix A are linearly independent.

(a) Suppose that two different bases lead to the same basic solution. Show that the basic solution is degenerate (has less than m non-zero entries).
(b) Consider a degenerate basic solution. Is it true that it corresponds to two or more distinct bases? Prove or give a counterexample.
(c) Suppose that a basic solution is degenerate. Is it true that there exists an adjacent basic solution which is degenerate? Prove or give a conterexample.

2. Relevant equations

3. The attempt at a solution

(a) I think it's obvious but how build the proof, the two different bases lead to the same basic solution, when the last entering variable cannot be increased at all because it's b value equals 0 therefore as result we have the same basic solution. But how to prove that?

(b) no, degenerate basic solution can correspond to one basis only as well. But how to prove that?