In the previous chapter we ran the simplex method through dictionaries: rewrite, pivot, repeat. That view is good for intuition. In this chapter we work out the linear algebra behind it. Every dictionary you wrote is a statement about matrices: choosing a basis means selecting an invertible submatrix $A_B$, pivoting means changing that submatrix, and the objective row of a dictionary is a vector of reduced costs computed from $A_B^{-1}$. Making this precise explains why the method works, and it is how simplex is implemented in software, where solvers manipulate basis matrices rather than rewrite equations.

Learning Outcomes

• Explore how a system of equations can be rewritten via partitioning the variables

• See how we can also partition the matrix and rewrite the equation in a new format that solves for basic variables

• Familiarize with matrix notation

• Define terminology of a basic solution and a basic feasible solution

We will now explore ways to represent solutions to this linear system of equations. This is meant to give the theoretical backbone of the simplex algorithm.

We consider a linear system

where $A\in {ℝ}^{m\times n}$, $x\in {ℝ}^n$, and $b\in {ℝ}^m$. Explicitly,

We assume:

• $\text{rank}(A)=m$, i.e., the rows of $A$ are linearly independent (full row rank);

• $m\le n$, so the system is not overdetermined.

If $A$ lacked full row rank, some equations would be redundant and removable without changing the solution set. When $m>n$, the system is typically overdetermined and inconsistent; if consistent, it can be reduced to $m\le n$ via row operations.

Under these assumptions, $Ax=b$ represents a system of $m$ independent equations in $n$ unknowns with a feasible (possibly infinite) solution space.

A small bakery produces two products: loaves of bread (denoted by $x$) and cakes (denoted by $y$). Each loaf of bread contributes $2 in profit, while each cake contributes $3 in profit. The bakery must operate under the following daily constraints:

• Oven Time: The total number of bread loaves and cakes baked each day cannot exceed 9, due to limited oven time. This gives the constraint:

  $$x+y\le 9.$$

• Flour Supply: Bread uses more flour than cake. Each loaf uses 2 units of flour and each cake uses 1 unit. The bakery has a maximum of 16 units of flour available each day, leading to:

  $$2x+y\le 16.$$

• Sugar Supply: Cakes use more sugar than bread. Each loaf uses 1 unit of sugar and each cake uses 2 units. The daily sugar supply is limited to 14 units, so:

  $$x+2y\le 14.$$

• Non-negativity: The bakery cannot produce a negative number of items, so:

  $$x\ge 0,y\ge 0.$$

Model:

The bakery wants to determine how many loaves of bread ($x$) and cakes ($y$) to produce each day in order to maximize total profit. The resulting linear program is:

$$\begin{array}{ccc}\hfill \max & 2x+3y\hfill & \hfill \\ \hfill \text{ s.t. }& x+y\le 9\hfill & \hfill \text{(hours)}& \hfill \\ \hfill & 2x+y\le 16\hfill & \hfill \text{(flour)}& \hfill \\ \hfill & x+2y\le 14\hfill & \hfill \text{(sugar)}& \hfill \\ \hfill & x\ge 0,y\ge 0.\hfill \end{array}$$

We begin by adding slack variables $s_1,s_2,s_3$ to convert the inequalities to equalities:

$$\begin{array}{ccc}\hfill \max & 2x+3y\hfill & \hfill \\ \hfill \text{ s.t. }& x+y+s_1=9\hfill & \hfill \text{(hours)}& \hfill \\ \hfill & 2x+y+s_2=16\hfill & \hfill \text{(flour)}& \hfill \\ \hfill & x+2y+s_3=14\hfill & \hfill \text{(sugar)}& \hfill \\ \hfill & x,y,s_1,s_2,s_3\ge 0\hfill \end{array}$$

It will be useful to also understand standard form from the matrix perspective.

In matrix-vector notation, define:

$$x=\left[\begin{array}{c}\hfill x\hfill \\ \hfill y\hfill \\ \hfill s_1\hfill \\ \hfill s_2\hfill \\ \hfill s_3\hfill \end{array}\right],c=\left[\begin{array}{c}\hfill 2\hfill \\ \hfill 3\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \end{array}\right],A=\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 2\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill 2\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right],b=\left[\begin{array}{c}\hfill 9\hfill \\ \hfill 16\hfill \\ \hfill 14\hfill \end{array}\right]$$

The standard form linear program is then:

$$\begin{array}{ccc}\hfill \max & c^{\top }x\hfill & \hfill \\ \hfill \text{ s.t. }& Ax=b,\hfill \\ \hfill & x\ge 0\hfill \end{array}$$

We extract submatrices of $A$ by selecting columns corresponding to specific variable sets. For a set $I$, we let $A_I$ denote the submatrix of $A$ corresponding to the columns in $I$.

This implies:

So,

Definition 8.1: Basis

Given a matrix $A$ of full row rank $m$, a basis $B$ is an index set of $m$ of the $n$ columns such that the corresponding $m$ columns of the matrix $A$ are linearly independent. We then form the submatrix $A_B$ that contains only those columns of $A$.

The remaining $n-m$ columns are referred to as the nonbasic columns, which form the matrix $A_N$.

Given a basis $B$ and the nonbasic set $N$, this partitions the variable vector $x$ into two sets:

where:

• $x_B$ consists of the basic variables, associated with the basis matrix $A_B$,

• $x_N$ consists of the nonbasic variables, associated with the nonbasic matrix $A_N$.

Rewriting the system $Ax=b$ in terms of these partitions gives:

If the basis matrix $A_B$ is invertible, we can express $x_B$ in terms of $x_N$:

Definition 8.2: Basic solution and Basic Feasible Solution (BFS)

A basic solution is obtained by setting $x_N=0$, yielding:

A basic feasible solution (BFS) is a basic solution that satisfies the nonnegativity constraint $x_B\ge 0$, ensuring that all basic variables are nonnegative.

Consider the following system:

Here, the matrix $A$ and the variable vector $x$ are:

Selecting $B=\{1,2\}$ as the basis, the corresponding submatrix is:

If $A_B$ is invertible, we compute:

Setting $x_3=0$ (i.e., $x_N=0$), we solve for $x_B$:

Since $x_B\ge 0$, this is a basic feasible solution.

Consider a linear program in inequality form:

We introduce slack variables $s_1,s_2\ge 0$ to convert inequalities into equalities:

The augmented system has:

Choosing the slack variables as the basis ($B=\{s_1,s_2\}$), the basis matrix is:

Since $A_B$ is the identity matrix, its inverse is itself, and we obtain:

Since $x_B\ge 0$, this is a basic feasible solution.

To convert the given problem into standard form, we introduce slack variables $s_1,s_2$ to convert the inequalities into equalities.

Now the system is in standard form:

A basis consists of any two linearly independent columns from $A$. We select three different bases:

• Basis 1: $B=\{x_1,x_2\}$ (Feasible) The basis matrix is:

  $$A_B=\left[\begin{array}{cc}\hfill 1\hfill & \hfill 2\hfill \\ \hfill 5\hfill & \hfill 3\hfill \end{array}\right].$$

  Computing $A_B^{-1}$:

  $$A_B^{-1}=\frac{1}{(1)(3)-(2)(5)}\left[\begin{array}{cc}\hfill 3\hfill & \hfill -2\hfill \\ \hfill -5\hfill & \hfill 1\hfill \end{array}\right]=\frac{1}{3-10}\left[\begin{array}{cc}\hfill 3\hfill & \hfill -2\hfill \\ \hfill -5\hfill & \hfill 1\hfill \end{array}\right]=\frac{1}{-7}\left[\begin{array}{cc}\hfill 3\hfill & \hfill -2\hfill \\ \hfill -5\hfill & \hfill 1\hfill \end{array}\right]=\left[\begin{array}{cc}\hfill -3∕7\hfill & \hfill 2∕7\hfill \\ \hfill 5∕7\hfill & \hfill -1∕7\hfill \end{array}\right].$$

  Computing the basic solution:

  $$x_B=A_B^{-1}b=\left[\begin{array}{cc}\hfill -3∕7\hfill & \hfill 2∕7\hfill \\ \hfill 5∕7\hfill & \hfill -1∕7\hfill \end{array}\right]\left[\begin{array}{c}\hfill 16\hfill \\ \hfill 45\hfill \end{array}\right]=\left[\begin{array}{c}\hfill (-3∕7)(16)+(2∕7)(45)\hfill \\ \hfill (5∕7)(16)+(-1∕7)(45)\hfill \end{array}\right]$$

  $$=\left[\begin{array}{c}\hfill -48∕7+90∕7\hfill \\ \hfill 80∕7-45∕7\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 42∕7\hfill \\ \hfill 35∕7\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 6\hfill \\ \hfill 5\hfill \end{array}\right].$$

  Since $x_B=(6,5)$ contains no negative values, this basis indeed yields a feasible solution.

• Basis 2: $B=\{x_1,s_2\}$ (Infeasible) The basis matrix (the columns of $x_1$ and $s_2$) is:

  $$A_B=\left[\begin{array}{cc}\hfill 1\hfill & \hfill 0\hfill \\ \hfill 5\hfill & \hfill 1\hfill \end{array}\right].$$

  Computing $A_B^{-1}$:

  $$A_B^{-1}=\frac{1}{(1)(1)-(0)(5)}\left[\begin{array}{cc}\hfill 1\hfill & \hfill 0\hfill \\ \hfill -5\hfill & \hfill 1\hfill \end{array}\right]=\left[\begin{array}{cc}\hfill 1\hfill & \hfill 0\hfill \\ \hfill -5\hfill & \hfill 1\hfill \end{array}\right].$$

  Computing the basic solution:

  $$x_B=\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill s_2\hfill \end{array}\right]=A_B^{-1}b=\left[\begin{array}{cc}\hfill 1\hfill & \hfill 0\hfill \\ \hfill -5\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill 16\hfill \\ \hfill 45\hfill \end{array}\right]=\left[\begin{array}{c}\hfill (1)(16)+(0)(45)\hfill \\ \hfill (-5)(16)+(1)(45)\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 16\hfill \\ \hfill -80+45\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 16\hfill \\ \hfill -35\hfill \end{array}\right].$$

  Since $s_2=-35<0$, this basis is infeasible. The corresponding point is $(x_1,x_2)=(16,0)$, which violates the constraint $5x_1+3x_2\le 45$.

• Basis 3: $B=\{s_1,s_2\}$ (Feasible) The basis matrix is:

  $$A_B=\left[\begin{array}{cc}\hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill \end{array}\right].$$

  Since this is the identity matrix, its inverse is itself. Thus, the basic solution is:

  $$x_B=\left[\begin{array}{c}\hfill s_1\hfill \\ \hfill s_2\hfill \end{array}\right]=A_B^{-1}b=\left[\begin{array}{c}\hfill 16\hfill \\ \hfill 45\hfill \end{array}\right].$$

  Since all basic variables are nonnegative, this is a feasible solution.

Learning Outcomes

• Define reduced costs at a basic feasible solution

• Establish optimality conditions via the reduced costs

The objective function of the linear program is given by:

Substituting the partitioned variables $x_B$ and $x_N$,

Expressing $x_B$ in terms of $x_N$, using the basic solution $x_B=A_B^{-1}b-A_B^{-1}{A}_N{x}_N$, we rewrite the objective function as:

Expanding and regrouping terms:

Definition 8.3: Reduced Costs

The term $c_N^{\top }-c_B^{\top }{A}_B^{-1}{A}_N$ represents the reduced costs.

This is explained as the objective rewritten from the viewpoint of a basic feasible solution. In particular, these are the coefficients on the non-basic variables.

Definition 8.4: Revised Simplex Dictionary at basis $B$

The revised simplex dictionary at a basis $B$ is

Here is an example: the same linear program written first at the slack basis and then at the basis $\{x,y\}$.

Theorem 8.5: Optimality Condition in Simplex Method

Given a linear program in standard form:

let $B$ be a basis corresponding to a basic feasible solution $x_B=A_B^{-1}b$, with nonbasic variables $x_N=0$.

If all reduced costs satisfy:

then the current basic feasible solution is optimal.

Example 8.6: Verifying Optimality Using Reduced Costs

We aim to verify that the basic feasible solutions $(6,5)$ and $(0,8)$ are optimal for the following linear program:

Solution

Checking Optimality of $(6,5)$

Step 1 — Identify the Basis.  At the point $(x,y)=(6,5)$, we see that $(s_1,s_2)=0$. Thus, we can choose $B=\{x_1,x_2\}$ and $N=\{s_1,s_2\}$, so:

$$A_B=\left[\begin{array}{cc}\hfill 1\hfill & \hfill 2\hfill \\ \hfill 5\hfill & \hfill 3\hfill \end{array}\right],c_B^{\top }=\left[\begin{array}{cc}\hfill 2\hfill & \hfill 5\hfill \end{array}\right].$$

The nonbasic variables are $s_1,s_2$, so:

$$A_N=\left[\begin{array}{cc}\hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill \end{array}\right],c_N^{\top }=\left[\begin{array}{cc}\hfill 0\hfill & \hfill 0\hfill \end{array}\right].$$

Step 2 — Compute $A_B^{-1}$. 

$$A_B^{-1}=\frac{1}{(1)(3)-(2)(5)}\left[\begin{array}{cc}\hfill 3\hfill & \hfill -2\hfill \\ \hfill -5\hfill & \hfill 1\hfill \end{array}\right]=\left[\begin{array}{cc}\hfill -3∕7\hfill & \hfill 2∕7\hfill \\ \hfill 5∕7\hfill & \hfill -1∕7\hfill \end{array}\right].$$

Thus, the system can be written as

$$x_B=A_B^{-1}b-A_B^{-1}{A}_N{x}_N,$$

that is

$$[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \end{array}]=\left[\begin{array}{c}\hfill 6\hfill \\ \hfill 5\hfill \end{array}\right]-\left[\begin{array}{cc}\hfill -3∕7\hfill & \hfill 2∕7\hfill \\ \hfill 5∕7\hfill & \hfill -1∕7\hfill \end{array}\right]\left[\begin{array}{c}\hfill s_1\hfill \\ \hfill s_2\hfill \end{array}\right],$$

(8.10)

or equivalently

$$[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \end{array}]=\left[\begin{array}{c}\hfill 6\hfill \\ \hfill 5\hfill \end{array}\right]-s_1\left[\begin{array}{c}\hfill -3∕7\hfill \\ \hfill 5∕7\hfill \end{array}\right]-s_2\left[\begin{array}{c}\hfill 2∕7\hfill \\ \hfill -1∕7\hfill \end{array}\right]$$

(8.11)

Step 3 — Compute Reduced Costs. 

$$A_B^{-1}{A}_N=\left[\begin{array}{cc}\hfill -3∕7\hfill & \hfill 2∕7\hfill \\ \hfill 5∕7\hfill & \hfill -1∕7\hfill \end{array}\right].$$

$$c_N^{\top }-c_B^{\top }{A}_B^{-1}{A}_N=\left[\begin{array}{cc}\hfill 0\hfill & \hfill 0\hfill \end{array}\right]-\left[\begin{array}{cc}\hfill 2\hfill & \hfill 5\hfill \end{array}\right]\left[\begin{array}{cc}\hfill -3∕7\hfill & \hfill 2∕7\hfill \\ \hfill 5∕7\hfill & \hfill -1∕7\hfill \end{array}\right].$$

Computing:

$$\left[\begin{array}{cc}\hfill 0\hfill & \hfill 0\hfill \end{array}\right]-\left[\begin{array}{cc}\hfill (2)(-\frac{3}{7})+(5)(\frac{5}{7})\hfill & \hfill (2)(\frac{2}{7})+(5)(-\frac{1}{7})\hfill \end{array}\right]=\left[\begin{array}{cc}\hfill 0\hfill & \hfill 0\hfill \end{array}\right]-\left[\begin{array}{cc}\hfill \frac{19}{7}\hfill & \hfill -\frac{1}{7}\hfill \end{array}\right]=\left[\begin{array}{cc}\hfill -\frac{19}{7}\hfill & \hfill \frac{1}{7}\hfill \end{array}\right].$$

The reduced cost on $s_2$ is positive ($\frac{1}{7}>0$), so $(6,5)$ is not optimal: increasing $s_2$ improves the objective.

Verifying Optimality of $(0,8)$

Step 1 — Identify the Basis. 

At the point $(x_1,x_2)=(0,8)$ we have $s_1=16-2(8)=0$ and $s_2=45-3(8)=21$, so the basic variables are $x_2$ and $s_2$. We choose $B=\{x_2,s_2\}$, so:

$$A_B=\left[\begin{array}{cc}\hfill 2\hfill & \hfill 0\hfill \\ \hfill 3\hfill & \hfill 1\hfill \end{array}\right],c_B^{\top }=\left[\begin{array}{cc}\hfill 5\hfill & \hfill 0\hfill \end{array}\right].$$

The nonbasic variables are $x_1,s_1$, so:

$$A_N=\left[\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 5\hfill & \hfill 0\hfill \end{array}\right],c_N^{\top }=\left[\begin{array}{cc}\hfill 2\hfill & \hfill 0\hfill \end{array}\right].$$

Step 2 — Compute $A_B^{-1}$. 

$$A_B^{-1}=\frac{1}{(2)(1)-(0)(3)}\left[\begin{array}{cc}\hfill 1\hfill & \hfill 0\hfill \\ \hfill -3\hfill & \hfill 2\hfill \end{array}\right]=\left[\begin{array}{cc}\hfill \frac{1}{2}\hfill & \hfill 0\hfill \\ \hfill -\frac{3}{2}\hfill & \hfill 1\hfill \end{array}\right].$$

As a check, $A_B^{-1}b=\left(\frac{16}{2},-\frac{3}{2}(16)+45\right)=(8,21)$, matching $(x_2,s_2)=(8,21)\ge 0$: a basic feasible solution.

Step 3 — Compute Reduced Costs. 

$$A_B^{-1}{A}_N=\left[\begin{array}{cc}\hfill \frac{1}{2}\hfill & \hfill 0\hfill \\ \hfill -\frac{3}{2}\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 5\hfill & \hfill 0\hfill \end{array}\right]=\left[\begin{array}{cc}\hfill \frac{1}{2}\hfill & \hfill \frac{1}{2}\hfill \\ \hfill \frac{7}{2}\hfill & \hfill -\frac{3}{2}\hfill \end{array}\right].$$

$$c_N^{\top }-c_B^{\top }{A}_B^{-1}{A}_N=\left[\begin{array}{cc}\hfill 2\hfill & \hfill 0\hfill \end{array}\right]-\left[\begin{array}{cc}\hfill 5\hfill & \hfill 0\hfill \end{array}\right]\left[\begin{array}{cc}\hfill \frac{1}{2}\hfill & \hfill \frac{1}{2}\hfill \\ \hfill \frac{7}{2}\hfill & \hfill -\frac{3}{2}\hfill \end{array}\right]=\left[\begin{array}{cc}\hfill 2\hfill & \hfill 0\hfill \end{array}\right]-\left[\begin{array}{cc}\hfill \frac{5}{2}\hfill & \hfill \frac{5}{2}\hfill \end{array}\right]=\left[\begin{array}{cc}\hfill -\frac{1}{2}\hfill & \hfill -\frac{5}{2}\hfill \end{array}\right].$$

Since both reduced costs are negative, this confirms that $(0,8)$ is an optimal solution.

Conclusion

• $(6,5)$ is not necessarily optimal because it has a positive reduced cost.

• $(0,8)$ is optimal because all reduced costs are nonpositive.

Exercise 8.7: Basis matrix and basic solution

$\star$  Consider the system from Example 1,

and take the basis $B=\{x_2,x_3\}$.

1.

Write down the basis matrix $A_B$ and compute $A_B^{-1}$.

2.

Compute the basic solution $x_B=A_B^{-1}b$ with $x_1=0$.

3.

Is this basic solution a basic feasible solution?

Exercise 8.8: A basic solution that is not feasible

Exercise 8.9: A fourth basis for the three-bases example

Exercise 8.10: Reduced costs at two bases

Exercise 8.11: Which bases are feasible?

$\star \star$  For the $2\times 4$ system

there are $\left(\genfrac{}{}{0.0pt}{}{4}{2}\right)=6$ ways to choose two columns.

1.

Verify that every one of the six column pairs is linearly independent, so each choice is a basis.

2.

For each basis, compute the basic solution and classify it as feasible or infeasible.

3.

Give an example of a $2\times 4$ matrix in which some pair of columns does not form a basis.

Exercise 8.12: Rebuilding a dictionary from the formula

Exercise 8.13: Reduced costs of basic variables

$\star \star$  The reduced-cost vector of the nonbasic variables is $c_N^{\top }-c_B^{\top }{A}_B^{-1}{A}_N$. Apply the same formula to the basic columns: show that

so every basic variable has reduced cost exactly zero. Explain what this says about the dictionary at basis $B$: why can a basic variable never appear in the objective row?

Exercise 8.14: Reduced-cost signs and the entering rule

Exercise 8.15: Strictly negative reduced costs imply a unique optimum

$\star \star \star$  Let $B$ be a basis of an LP in standard form whose basic solution $\overline{x}=(A_B^{-1}b,0)$ is feasible, and suppose every reduced cost is strictly negative:

Prove that $\overline{x}$ is the unique optimal solution of the LP. (This is an argument, not a computation. Suggested route: take any feasible $x\ne \overline{x}$, write $c^{\top }x=c^{\top }\overline{x}+(c_N^{\top }-c_B^{\top }{A}_B^{-1}{A}_N)x_N$, and consider the two cases $x_N=0$ and $x_N\ne 0$.)

Solution