# Perturbation approach to lexicography in Linear Programming

Consider a standard form problem, under the usual assumption that the rows of $$\textbf{A}$$ are linearly independent. Let $$\epsilon$$ be a scalar and define $$\textbf{b}(\epsilon)=\textbf{b}+\begin{bmatrix} \epsilon \\ \epsilon^{2} \\ \vdots \\ \epsilon^{m} \end{bmatrix}$$ For every $$\epsilon>0$$, we define the $$\epsilon$$-perturbed problem to the linear programming obtained by replacing $$\textbf{b}$$ with $$\textbf{b}(\epsilon)$$.

(a) Given a basis matrix $$\textbf{B}$$, show that the corresponding basic solution $$x_B(\epsilon)$$ in the $$\epsilon$$-perturbed problem is equal to $$\textbf{B}^{-1}[\textbf{b}|\textbf{I}]\begin{bmatrix} 1 \\ \epsilon \\ \vdots \\ \epsilon^{m} \end{bmatrix}$$

(b) Show that there exists some $$\epsilon^*>0$$ such that all basic solutions to the $$\epsilon$$-perturbed problem are nondegenerate, for $$0<\epsilon<\epsilon^*$$.

This is a question (3.15) from 'Introduction to Linear Optimization' by Dimitris Bertsimas. I am practicing all the problems in this textbook but I'm having hard time even understanding this question and solving it. Could anyone please help me how to approach to this problem or how to solve it? Thank you.