Prove an artificial variable that leaves the basis will never return.

Question

This is in the context of the Big M Method in the simplex algorithm in linear programming.

Prove an artificial variable that leaves the basis will never return.

I have no idea how to start this. Anyone know any books with these kinds of questions(and proofs hopefully)?

The closest I could find is "Topics in Linear Programming and Games Theory edited by Lakshmisree Bandopadhyaya" which seems to have a multivariate (i.e. vector) version of a question I had previously:

The vector which leaves basis at one iteration cannot return to basis the next iteration.

Answer 1

Suppose you have a maximization problem. When a variable x enters basis and y leaves out of basis, it means that increasing x would increase the output of the objective function. But the objective function has the coefficients of -M for artificial variables. So we cannot increase objective function value by increasing the artificial variable as it will decrease the current objective function output by a value of -M and become infeasible. Hence why the artificial variables cannot enter your basis once they originally left