Exercise 3.29 (Basic points are affinely independent)

Question

Consider the simplex method, viewed in terms of column geometry. Show that the $m+1$ basic points $\left(\mathbf{A}_{i}, c_{i}\right)$, as defined in Section 3.6, are affinely independent.

Elu Thingol · Accepted Answer

\begin{proof}
Assume for the sake of contradiction that the basic points $(\mathbf{A}_i,c_i)$, $i=1,\ldots,m,m+1$ are affinely dependent. By Definition 3.6, the points $(\mathbf{A}_i - \mathbf{A}_{m+1},c_i-c_{m+1})$, $i=1,\ldots,m$ must then be linearly dependent.

In other words, there is a nontrivial collection of scalars $a_1,\ldots,a_m \in \mathfrak{R}$ such that 
$$\sum_{i=1}^{m} a_i (\mathbf{A}_i - \mathbf{A}_{m+1},c_i-c_{m+1}) = \mathbf{0}.$$

Looking at the first $m$ coordinates of our points, we in particular see that
$$\sum_{i=1}^{m} a_i \mathbf{A}_i - \sum_{i=1}^{m} a_i \mathbf{A}_{m+1} = \mathbf{0}.$$

In particular, we have found a nontrivial collection $a_1,\ldots,a_m,\sum_{i=1}^{m} a_i \in \mathfrak{R}$ of $m+1$ scalars under which a linear combination of the basic columns of the linear programming problem in (3.6) becomes zero
$$\sum_{i=1}^{m} a_i (\mathbf{A}_i,1) - \left(\sum_{i=1}^{m} a_i\right) (\mathbf{A}_{m+1},1) = \mathbf{0}.$$

This is a contradiction to the fact that the associated $m+1$ basic columns $(\mathbf{A}_i,1)$, $i=1,\ldots,m+1$, are linearly independent.
\end{proof}

Exercise 3.29 (Basic points are affinely independent)

Answers

Comments

Exercise 3.29 (Basic points are affinely independent)

Answers

Comments

Add answer