Exercise 2.27 from Bazaraa (LP) Consider the system $Ax=b$ where $A=[a_1,a_2,...,a_n]$ is an $m \times n$ matrix of rank $m$.
Let $x$ be any solution of this system.
Starting with $x$, construct a basic solution.
There is a hint also.
Suppose $x_1,...,x_p \neq 0$ and $x_p+1,...,x_n=0$.
If $p>m$ represent one of the columns $a_j$ for $j=1,...,p$ as a linear combination of the remaining vectors. This results in a new solution having a smaller number of nonzero variables. Repeat the process.
Ok. I will repeat the process until $p=m$. But in each iteration, how will the remaining non-zero variables change? I do not know how to figure out that. Could you please help.
 A: Warm-up
If you're very good in linear algebra, you can skip this.
\begin{array}{c|rrrr}
i & 1 & 2 & 3 & 4 \\ \hline
x_i & 1 & 2 & 3 & 4 \\
y_i & 5 & 7 & 8 & 6 \\ \hline
\dfrac{x_i}{y_i} & \boxed{\dfrac15} & \dfrac27 & \dfrac38 & \dfrac46
\end{array}
We choose the $\boxed{\mathrm{minimum}\;\dfrac{x_i}{y_i}}$.
\begin{align}
& (1,2,3,4) - \boxed{\dfrac15} (5,7,8,6) \\
=& (1,2,3,4) - (1,\dfrac75,\dfrac85,\dfrac65) \\
=& (\boxed0,\dfrac35,\dfrac75,\dfrac{14}{5})
\end{align}
Theoretical stuff
Suppose that $x$ is a non-basic feasible solution to $Ax = b$, $p > m$, and we try to make $x_j = 0$.  (In other words, make the one of these $p$ non-zero component of $x$ zero.)  This can be repeated until $p = m$, so that $x$ is a BFS.
Vectors $a_1,\dots,a_p$ (taken from columns of $A$) are linearly dependent, so $\exists\,y_1,\dots,y_p \in \Bbb R$ such that not all of $y_1,\dots,y_p$ are zero and $$\sum_{i = 1}^p y_i a_i = 0.$$  We can also write $\begin{bmatrix} a_1 & \cdots & a_p \end{bmatrix} y = 0$.  From the quesiton, $x_{p+1},...,x_n=0$, so we also have $\begin{bmatrix} a_1 & \cdots & a_p \end{bmatrix} \begin{bmatrix} x_1 & \cdots & x_p \end{bmatrix}^T = b$.


*

*Want: One of $x_1,\dots,x_p$ becomes zero.

*Try: Set a constant $\epsilon$ so that $x_j - \epsilon y_j = 0$ for a pariticular index $j \in \{1,\dots,p\}$ in $\begin{bmatrix} a_1 & \cdots & a_p \end{bmatrix} \begin{bmatrix} x_1 - \epsilon y_1 & \cdots & x_p - \epsilon y_p \end{bmatrix}^T = b$.


Since in the question, you've never required that $x_i \ge 0 \forall i$, we can set $\epsilon$ to $\dfrac{x_j}{y_j}$ if $y_j \ne 0$.  (The existence of $y_j \ne 0$ is guaranteed by the assumption that $a_1,\dots,a_p$ are linearly dependent.)

If you want all decision variables $x_i \ge 0$, which is something necessary for the simplex method to work, then you need $\epsilon$ so that $x_j - \epsilon y_j \ge 0 \forall j$ (if $y_j > 0$, this is equivalen to $\epsilon \le \dfrac{x_j}{y_j}$), and $x_k - \epsilon y_k = 0$ for some index $k \in \{1,\dots,p\}$.  We set $\epsilon$ to $\min\left\{\dfrac{x_i}{y_i}:y_i>0,i \in \{1,\dots,p\}\right\}$, and we see that the index $k$ such that $\dfrac{x_k}{y_k} = \min\left\{\dfrac{x_i}{y_i}:y_i>0,i \in \{1,\dots,p\}\right\}$ satisfies $x_k - \epsilon y_k = 0$.
