4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.