# 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.

## 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$.