# Proof verification for simplex method problems

I was studying simplex method in LPP from "Introduction to Linear Optimization by Bertsimas and Tsitsiklis", and came across this problem:

Consider the simplex method applied to a standard form problem and assume that the rows of the matrix $$A$$ are linearly independent . For each of the statements that follow, give either a proof or a counterexample. Take $$n\geq m$$, where $$A$$ is $$m*n$$ and $$b$$ is $$m*1$$ matrix.

(a) An iteration of the simplex method may move the feasible solution by a positive distance while leaving the cost unchanged.

(b) If there is a nondegenerate optimal basis , then there exists a unique optimal basis.

(c) If $$x$$ is an optimal solution, no more than $$m$$ of its components can be positive.

I tried this question, and was able to solve some of them. But, I'm not sure if my solutions are correct. It'd be really helpful if someone could tell if I solved these correctly and tell the solutions/hints for the unsolved ones.

My try:

I considered a tableau while solving all of these problems.

a) False. Let $$c$$ and $$\bar{c}$$ be the initial and final costs. When we update the tableau, we'll apply row transformation to go from $$c$$ to $$\bar{c}$$. But since $$c=\bar{c}$$, for the cost to remain the same after an iteration, the basic variable that is exiting the basis has to be zero. Let $$k$$ be the index of the variable entering the basis and $$B(l)$$ be that of leaving the basis. When we move from $$x_{B(l)}$$ to $$x_k$$, whatever we multiply by, $$x_{B(l)} (=x_k)$$ will remain the same ($$0$$). So, we are still at the same point.

b) I was unable to understand it clearly. What does "basis" mean? The basis matrix $$B$$ or the vector of basic variables $$x_B$$? I've no idea on how to proceed in any of those two way either.

c) This is true since $$x$$ being an optimal solution is a bfs.

Please note that I don't even need full solutions, even hints will do. Thanks!