3.4.1. Making \(\boldsymbol{s}\) Non-Basic

If \(s\) is not a basic variable of \(Q'\), we can set \(Q'' = Q'\) and \(B'' = B'\). If \(s\) is a basic variable, then assume it is the basic variable corresponding to the \(k\)th constraint in \(Q'\) and let \(z_j\) be a non-basic variable whose coefficient in this constraint is non-zero. By the following lemma, such a variable must exist:

Lemma 3.4: If \(s\) is the basic variable corresponding to the \(k\)th equality constraint of \(Q'\), then there exists a non-basic variable \(z_j\) that has a non-zero coefficient in this constraint.

Proof: The \(k\)th equality constraint of \(Q'\) is of the form

\[b'_k = \sum_{j=1}^{m+n} a'_{kj}z_j + s\tag{3.2}\]

because \(s\) is the basic variable corresponding to this constraint and thus has coefficient \(1\).

For any \(i\), the \(i\)th equality constraint of \(Q\) is of the form

\[b_i = \sum_{j=1}^{m+n} a_{ij}z_j - s.\]

Since the set of equality constraints of \(Q'\) is obtained from the set of equality constraints of \(Q\) using elementary row operations—remember, we solve \(Q\) using the Simplex Algorithm—(3.2) is a linear combination of the equality constraints of \(Q\). Specifically, we have

\[\begin{aligned} b'_k &= \sum_{i=1}^m \lambda_ib_i\\ a'_{kj} &= \sum_{i=1}^m \lambda_ia_{ij} \quad \forall 1 \le j \le m + n\\ 1 &= -\sum_{i=1}^m \lambda_i, \end{aligned}\]

for an appropriate vector of coefficients \((\lambda_1, \ldots, \lambda_m)\). The last equality holds because \(s\) has coefficient \(1\) in (3.2) and coefficient \(-1\) in all equality constraints of \(Q\). This last equality implies that there exists an index \(i\) such that \(\lambda_i < 0\). If \(z_{j_i}\) is the basic variable of \(Q\) corresponding to the \(i\)th equality constraint of \(Q\), we have

\[a'_{kj_i} = \sum_{h=1}^m \lambda_ha_{hj_i} = \lambda_i\]

because \(a_{ij_i} = 1\) and \(a_{hj_i} = 0\) for all \(h \ne i\). Thus, \(z_{j_i}\) has a non-zero coefficient in (3.2). Since every basic variable of \(Q'\) other than \(s\) must have coefficient \(0\) in (3.2), \(z_{j_i}\) must be a non-basic variable of \(Q'\). ▨

We now have the basic variable corresponding to the \(k\)th equality constraint of \(Q'\), \(s\), and a non-basic variable with non-zero coefficient in this constraint, \(z_j\). We apply a pivoting operation to remove \(s\) from the basis and add \(z_j\) to the basis. Since \(\tilde s = 0\) in the BFS \(\bigl(\tilde z, \tilde s\bigr)\) of \(Q'\), this does not change the BFS, that is, \(\bigl(\tilde z, \tilde s\bigr)\) is also a BFS of \(Q''\): the pivoting operation is degenerate.