Introduction to Linear Optimization: Driving the artificial variables out of the basis (case: no entries in the $j$-row are nonzero)

Question

Reading the book Introduction to Linear Optimization by Bertsimas and Tsiklisis, I've come across the following subject: Driving the artificial variables out of the basis.

The description is as follows: suppose an artificial variable $x_{B(j)}$ is in the basis, then examining the $j$-row of the simplex tableau there are two cases:

Either the $j$-row of $B^{-1}A$ contains a nonzero element (I understand this case !), otherwise all elements in the row are equal to $0$, which imply that the rows of $A$ are linearly independent and it is shown that the constraint $a_j x = b_j$ is redundant.

The book then suggest we delete the $j$-row of the simplex tableau and continue from there. Why is this possible ? By deleting the $j$-row of the tableau, we remove the $j$-basic variable from the basis. Also, deleting the $j$-row of the simplex tableau corresponds to deleting the $j$-row of $A$, form the basis of the basic variables, not including the $j$'th basic variable (now one dimension smaller), and then forming the simplex tableau corresponding to these ?

Now, how can we be sure the vectors corresponding to the basic variables excluding the $j$'th are linearly independent and form a basis ($j$-element is removed from these vectors) ? How do I know the simplex tableau with the $j$-row removed is actually a real simplex tableau and what vectors and basis matrix does it correspond to ?

Please give me advice and tell me whether I'm wrong and what to do, I've been really thinking over this, but haven't come to a conclusion.

Answer 1

The Proof is on Theorem 2.5 of the section 2.3. If you consider the polyhedron with artificial variables and redundant equality constraints as P and original with no artificial variables and no redundant equality constraints as Q. As you may see, they assumes that the l(th) basic variable is an artificial variable, so remove it will not affect original polyhedron. On the Example 3.8, the last tableau with artificial variables shows a case where a row becomes zero. If this happens with non artificial variable we have a degeneracy case.