Exercise 2.8

Question

Consider the standard form polyhedron $\left\{\mathbf{x} \mid \mathbf{A}\mathbf{x} = \mathbf{b},\, \mathbf{x}\geq \mathbf{0}ight\}$, and assume that the rows of the matrix $\mathbf{A}$ are linearly independent. Let $\mathbf{x}$ be a basic solution, and let $J=\{i \mid x_i 
eq 0\}$. Show that a basis is associated with the basic solution $\mathbf{x}$ if and only if every column $\mathbf{A}_i$, $i\in J$, is in the basis.

Elu Thingol · Accepted Answer

\begin{proof}
We demonstrate that the implications hold in both directions.
\begin{itemize}
\item[$\implies$] Let $\mathbf{B} = \begin{bmatrix} A_{B(1)} & \cdots & A_{B(m)} \end{bmatrix}$ be a basis associated with $\mathbf{x}$. Then, any index $i \in \{1,\ldots,n\} \setminus \{B(1),\ldots,B(m)\}$ is associated with a zero component $x_i = 0$ by definition. Therefore, $J \subseteq \{1,\ldots,n\}$ must be a subset of the rest, i.e. of $\{B(1),\ldots,B(m)\}$.

\item[$\impliedby$] Suppose that every column $A_{i}$ associated with a non-zero component $x_i$, $i \in J$, is contained in some matrix $\mathbf{B} = \begin{bmatrix} A_{B(1)} & \cdots & A_{B(m)} \end{bmatrix}$. For all the columns $A_{j}$ not contained in $\mathbf{B}$ we must have $x_j = 0$, thus fulfilling property (b) from Theorem 2.4. Furthermore, $\mathbf{A}$ has full row rank, meaning any $m$ columns of $\mathbf{A}$ are linearly independent. Thus, $\mathbf{B}$ is a basic solution associated with $\mathbf{x}$.
\end{itemize}
\end{proof}

Prakash Anand · Answer

extbf{Proof}:
ewline

$\Rightarrow$:

If a basis is associated with the basic solution $\mathbf{x}$, for any $i$ s.t. the $i$-th column is not in the basis, we set $x_i=0$. So if $x_i\ge 0$, the $i$-th column has to be in the basis.
ewline

$\Leftarrow$:

If every column $\mathbf{A}_i,i\in J$ is in the basis, all columns $\left\{x_iight\}$ that are not in the basis have $x_i=0$. Therefore, the basis is associated with the solution.

Exercise 2.8

Answers

Comments

Comments

Exercise 2.8

Answers

Comments

Comments

Add answer