Exercise 2.7

Question

Supponse that $\{x \in \mathfrak{R}^n \mid \mathbf{a}_i\mathbf{x} \geq b_i,\, i=1,\ldots,m\}$ and $\{x \in \mathfrak{R}^n \mid \mathbf{g}_i\mathbf{x} \geq h_i,\, i=1,\ldots,k\}$ are two representations of the same nonempty polyhedron. Suppose that the vectors $\mathbf{a}_1,\ldots,\mathbf{a}_m$ span $\mathfrak{R}^n$. Show that the same must be true for the vectors $\mathbf{g}_1,\ldots,\mathbf{g}_k$.

Elu Thingol · Accepted Answer

\begin{proof}
Since $\{x \in \mathfrak{R}^n \mid \mathbf{a}_i\mathbf{x} \geq b_i,\, i=1,\ldots,m\}$ is nonempty, it possesses at least one basic feasible solution $\mathbf{x}^*$ (Theorem 2.6). Since $\mathbf{x}^* \in \{x \in \mathfrak{R}^n \mid \mathbf{g}_i\mathbf{x} \geq h_i,\, i=1,\ldots,k\}$, there are $n$ linearly independent constraints in $\{g_i \mid g_i'\mathbf{x}=h_i\}$ that are active at $\mathbf{x}^*$ (Definition 2.9).  By Theorem 2.2., the span of vectors $\{g_i \mid i = 1,\ldots,k\}$ is all of $\mathfrak{R}^n$.
\end{proof}

Prakash Anand · Answer

Assume otherwise the vector $g_{1}, \ldots, g_{k}$ do not span $\mathbb{R}^{n} .$ Then, they are all in a proper subspace of $\mathbb{R}^{n}$. Hence, there exists a non-zero vector $d \in \mathbb{R}^{n}$ such that $d^{\prime} g_{i}=0 \quad \forall i=1, \ldots, k$. Let $x_{0}$ be an element of the polyhedron represented by $\left\{x \in \mathbb{R}^{n} \mid g_{i}^{\prime} x \geq h_{i}, i=1, \ldots, k\right\}$ and $\left\{x \in \mathbb{R}^{n} \mid a_{i}^{\prime} x \geq b_{i}, i=1, \ldots, m\right\}$. Consider the line $x_{0}+\lambda d, \lambda \in \mathbb{R}$. Note that $g_{i}^{\prime}\left(x_{0}+\lambda d\right)=g_{i}^{\prime} x_{0} \geq h_{i} \quad \forall i=1, \ldots, k$. Thus, the line is contained in the polyhedron. Hence, we have $a_{i}^{\prime}(x+\lambda d) \geq b_{i}, \forall \lambda \in \mathbb{R} \forall i=1, \ldots, m$. Clearly, $d$ must be orthogonal to all the vectors $a_{i}$ 's. However, the vectors $a_{1}, \ldots, a_{m}$ span $\mathbb{R}^{n}$, and hence $d=0 .$ Contradiction. We conclude that the vector $g_{1}, \ldots, g_{k}$ also $\operatorname{span} \mathbb{R}^{n} .$

Exercise 2.7

Answers

Comments

Comments

Exercise 2.7

Answers

Comments

Comments

Add answer