Exercise 2.3 (Basic feasible solutions in standard form polyhedra with upper bounds)

Proof. We demonstrate both directions.

• Consider some $x\in {\Re }^n:Ax=b$ and suppose that there are indices $B(1),\dots ,B(m)$ that satisfy (a) and (b) in the statement of the theorem. Let $I:=\{1,\dots ,n\}\setminus \{B(1),\dots ,B(m)\}$ be the set of non-active indices, let $U:=I\setminus \{i\in I\mid x_i=u_i\}$ be the set of the indices where $x$ hits the upper bound and let $N:=I\setminus \{i\in I\mid x_i=0\}$ be the set of the indices where $x$ hits the lower bound. The active constraints and $Ax=b$ imply that

  $$\sum _{i=1}^m{A}_{B(i)}{x}_{B(i)}=\sum _{i=1}^n{A}_i{x}_i-0\sum _{i\in N}{A}_i{x}_i-\sum _{i\in U}{A}_i{x}_i=b-\sum _{i\in U}{A}_i{x}_i.$$

  Since the columns $A_{B(i)}$, $i=1,\dots ,m$ are linearly independent by the theorem hypothesis, by Theorem 1.2 (e,f), $x_{B(1)},\dots ,x_{B(m)}$ are uniquely determined. In other words, the system of equations formed by the active constraints

  $$\left[\begin{array}{ccc}\hfill |\hfill & \hfill \hfill & \hfill |\hfill \\ \hfill A_{B(1)}\hfill & \hfill \text{…}\hfill & \hfill A_{B(m)}\hfill \\ \hfill |\hfill & \hfill \hfill & \hfill |\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_{B(1)}\hfill \\ \hfill ⋮\hfill \\ \hfill x_{B(m)}\hfill \end{array}\right]=b-\sum _{i\in U}{A}_i{x}_i$$

  has a unique solution. By Theorem 2.2, this is equivalent to saying that there are $n$ linearly independent active constraints. Coupled with the fact that all of the equality constraints are active by hypothesis, this implies that $x$ is a basic solution.

• For the converse, we assume that $x$ is a basic solution of $P=\left\{x\in {\Re }^n\mid Ax=b,0\le x\le u\right\}$; we will show that conditions (a) and (b) in the statement of the theorem are satisfied. Just as in the previous part, we partition the index into

  $$\begin{array}{llll}\hfill U& :=\left\{1\le i\le n\mid x_i=u_i\right\}& \hfill & \\ \hfill N& :=\left\{1\le i\le n\mid x_i=0\right\}& \hfill & \end{array}$$

  and denote the elements that are not indexed by either of these sets by $x_{B(1)},\dots ,x_{B(n)}$ for some $k\in 𝔑$. We then have

  $$\sum _{i=1}^k{A}_{B(i)}{x}_{B(i)}=\sum _{i=1}^n{A}_i{x}_i-0\sum _{i\in N}{A}_i{x}_i-\sum _{i\in U}{A}_i{x}_i=b-\sum _{i\in U}{A}_i{x}_i.$$

  Since $x$ is a basic solution, there are $n$ linearly independent constraints and by Theorem 2.2, the system of equations

  $$\left[\begin{array}{ccc}\hfill |\hfill & \hfill \hfill & \hfill |\hfill \\ \hfill A_{B(1)}\hfill & \hfill \text{…}\hfill & \hfill A_{B(m)}\hfill \\ \hfill |\hfill & \hfill \hfill & \hfill |\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_{B(1)}\hfill \\ \hfill ⋮\hfill \\ \hfill x_{B(m)}\hfill \end{array}\right]=b-\sum _{i\in U}{A}_i{x}_i$$

  results in a unique solution. It follows that the columns $A_{B(1)},\dots ,A_{B(k)}$ are linearly independent. [If they were not, we could find scalars ${\lambda }_1,\dots ,{\lambda }_k$, no all of them zero, such that ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=1}^k{A}_{B(i)}{\lambda }_i=0$. This would imply that ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=1}^k{A}_{B(i)}(x_{B(i)}+{\lambda }_i)=b-{\sum }_{i\in U}{A}_i{x}_i$, contradicting the uniqueness of the solution.]
  We have shown that the columns $A_{B(1)},\dots ,A_{B(k)}$ are linearly independent and this implies that $k\le m$. Since $A$ has $m$ linearly independent rows, it also has $m$ linearly independent columns, which span ${\Re }^m$. It follows [cf. Theorem 1.3(b)] that we can find $m-k$ additional columns $A_{B(k+1)},\dots ,A_{B(m)}$ so that the columns $A_{B(i)}$, $i=1,\dots ,m$ are linearly independent. In addition, if $i\ne B(1),\dots ,B(m)$, then $i\ne B(1),\dots ,B(k)$ (because $k\le m$), and we either have $x_i=0$ or $x_i=u_i$. Therefore, both conditions (a) and (b) in the statement of the theorem are satisfied.