Consider the standard form polyhedron, and assume that the rows of the matrix A are linearly independent.
$ \left \{ x | Ax = b, x \geq 0 \right \} $
(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 counterexample.
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?
Addendum
I found great description of (a) and (b), but level of this text is much higher than I can apprehend. I will appreciate if someone could shed light on this explanation.
(a) every basic feasible solution is equivalent to an extreme point. However, there may exist more than one basic corresponding to the same basic feasible solution or extreme point. Case of degeneracy corresponds to that of a extreme point at which some $r > p \equiv n- m $ defining hyperplanes from $x\geq 0$ are binding. Hence, for any associated basis, $(r-p)$ of the $X_{B}$ - variables area also zero. Consequently, the number of positive variables is $q = m-(r-p)
(b) Consider example $x_{1} + x_{2} + x_{3} = 1$
$-x_{1} + x_{2} + x_{3} = 1$
$x_{1}, x_{2}, x_{3} \geq 0$
Consider the solution $\bar{x}=(0,1,0)$. Observer that this is an extreme point or a basic feasible solution with a corresponding basis having $x_{1}$ and $x_{2}$ as basic variables. Moreover, this is a degenerate extreme point. There are four defining hyperplanes binding at $\bar{x}$. Moreover, there are three ways of choosing three linearly independent hyperplanes from this set that yield $\bar{x}$ as the (unique) solution. However, the basis associated with $\bar{x}$ is unique. Consider a degenerate basic variable ${x_{B}}_{r}$ (with $\bar{b}_{r}=0$), which is such that $Ax=b$ does not necessarily imply that ${x_{B}}_{r}=0$. Given that such a variable exists, we will construct another basis representing this point. Let $x_{k}$ be some component of $x_{N}$ that has a nonzero coefficient $\theta_{r}$ in the row corresponding to ${x_{B}}_r$. Note that $x_{k}$ exists. Then consider a new choice of $(n-m)$ nonbasic variables given by ${x_{B}}_{r}$ and $x_{N-k}$, where $x_{N-k}$ represents the components of $x_{N}$ other than $x_{k}$. Putting ${x_{B}}_{r}= 0$ and $x_{N-k}=0$ above uniquely gives $x_{k}=\frac{\bar{b}_{r}}{\theta_{r}}=0$ from row $r$, and so ${x_{B}}_{i} = \bar{b}_{i}$ is obtained as before from the other rows. Hence, this corresponds to an alternative basis that represents the same extreme point. Finally, note that if no degenerate basic variable ${x_{B}}_{r}$ of this type exists, then there is only one basis that represents this extreme point.