Suppose that we have a basic feasible solution that is nondegenerate. Furthermore, suppose that an improving nonbasic variable enters the basis. How can we show that if the minimum ratio criterion for exiting from the basis occurs at a unique index, then the resulting basic feasible solution is nondegenerate.
any ideas ?
Let $B$ a feasible basis of $Ax=b, x \geq 0$. Then the corresponding basic feasible solution is \begin{align} &x_B = B^{-1}b \geq 0\\ &x_N =0 \end{align} Assume that the basis is nondegenerate, that is $x_B >0$. For semplicity of notation let us assume that the basic variable of the constraint $i$ is $x_i$ and let $k$ be a nonbasic improving variable. In order $x_k$ enters the basis it must increase from $0$ to $\delta \geq 0$. Then we get \begin{align} &x_B = B^{-1}b -\delta \hat{A_k}\\ &x_k =\delta \end{align} Where $\hat{A_k}=B^{-1}A_k$.
The previous expression shows that as $x_k$ increases there are some basic variables that increase (if $\hat{a}_{ik}<0$), some others decrease (if $\hat{a}_{ik}>0$). Therefore the maximum allowed increasing for the nonbasic variable $x_k$ must not make negative the basic variables. That is $$ \delta =\min_{i \: |\:\hat{a}_{ik} >0} \ \ \Big\{\dfrac{x_i}{\hat{a}_{ik}}\Big\}$$.
Since we have assumed that $x_B$ is nondegenerate, then $\delta>0$. It follows that if the minimum ratio occurs at single constraint $h$, then $x_h=0$, it leaves the basis and $x_k$ becomes a new basic variables. Obviously if the minimum ratio occurs at two different constraints then there are two basic variables that become $0$. One of them leaves the basis; the other one is still a basic variables but its value is $0$. Therefore the new basic solution is degenerate.