Linear programming, variable without non-negativity constraint

Question

In a linear programming problem where we have a variable $x_k$ which has no non-negativity constraint, we can replace it by $x_k = u_k - v_k$, where both $u_k$ and $v_k$ have to be $\ge 0$. Can there exist a basic feasible solution where both $u_k$ and $v_k$ are basic variables?

Answer 1

The basis $B$ of a system $Ax\leq b$, $x\geq 0$ corresponds to a basic solution $x_B$, which can be determined by computing $x_B=A_B^{-1}b$, where $A_B$ are the coloumns from $A$ with index in $B$.

By replacing $x_k$ with $u_k$ and $v_k$ we delete the coloumn $k$ and add two new coloumns one for $u_k$ and one for $v_k$. This coloumns are by construction $x_k=u_k-v_k$ identical except for the sign. So the coloumns are linear dependent.

If we now assume that both are in a basis B, we can't construct $A_B^{-1}$ anymore, which makes it impossible to construct a basis solution.

Obviously $u_k$ and $v_k$ can be chosen to be both non zero.