[proofplan] The proof proceeds by contradiction. We assume the simplex method cycles under Bland's rule, then derive a contradiction from the structure of the cycle. A variable is called *fickle* if it is basic in some bases of the cycle but not all. Among all fickle variables, we select the one with the largest index $t$. We identify two pivots: one where $t$ leaves the basis (basis $B$, entering variable $s < t$), and one where $t$ enters the basis (basis $\hat{B}$). From the first pivot we extract a direction vector $d$ in $\ker A$, and from comparing the two bases we form the reduced cost difference $\tilde{c} = \hat{c} - \bar{c} \in \operatorname{row}(A)$. Since $d \in \ker A$ and $\tilde{c} \in \operatorname{row}(A)$, we have $\tilde{c}^\top d = 0$. However, a term-by-term sign analysis using Bland's entering and leaving rules shows every term in $\tilde{c}^\top d$ is $\leq 0$ with at least two strictly negative, giving $\tilde{c}^\top d < 0$ — a contradiction. [/proofplan] [step:Assume the simplex method cycles and identify the largest-index fickle variable $t$] Suppose for contradiction that under Bland's rule, the simplex method cycles through a sequence of bases $B_0, B_1, \ldots, B_\kappa = B_0$ with $\kappa \geq 1$. Since the objective value is non-decreasing and the bases repeat, the objective value is constant throughout the cycle. Every pivot in the cycle is therefore degenerate: the step length is $0$ and the basic feasible solution $x^*$ is the same at every step. Call a variable $x_j$ **fickle** if it is basic in some, but not all, bases of the cycle. Since the cycle involves at least two distinct bases, at least one variable changes basis status, so fickle variables exist. Every fickle variable satisfies $x^*_j = 0$ throughout the cycle: if $x_j$ is non-basic at some step, then $x^*_j = 0$ at that step; since $x^*$ is constant, $x^*_j = 0$ at every step. Let $t$ be the fickle variable with the largest index. Since $t$ is fickle, there is a basis in the cycle that contains $t$ and a basis that does not. [guided] Why must every pivot in the cycle be degenerate? The simplex method either increases the objective strictly (non-degenerate pivot) or keeps it the same (degenerate pivot). If the algorithm returns to basis $B_0$ after $\kappa$ steps, the objective value at $B_\kappa = B_0$ equals the value at $B_0$. Since the objective is non-decreasing along the simplex path, every intermediate pivot must have produced zero improvement. Why is every fickle variable zero throughout? If $x_j$ is fickle, then at some step of the cycle $x_j$ is non-basic, hence $x^*_j = 0$. Since all pivots are degenerate with step length $0$, the basic feasible solution $x^*$ never changes. Therefore $x^*_j = 0$ at every step, regardless of whether $j$ is currently basic or non-basic. The definition of $t$ as the largest-index fickle variable is the engine of the proof. Every variable with index $> t$ has the same basis status at every step of the cycle — it is either always basic or always non-basic. This means that such variables are **not fickle**, and we will exploit this to control the signs in the key inner product. [/guided] [/step] [step:Identify two pivots and record the sign conditions from Bland's rules] Since $t$ is fickle, we can find two specific pivots in the cycle: **(1) A pivot where $t$ leaves the basis.** Call the basis at this step $B$, with non-basic set $N$. At this pivot, some variable $s$ enters the basis while $t$ leaves. Denote the reduced costs and updated tableau at $B$ by $\bar{c}$ and $\bar{A}$. Since we are solving a maximisation LP, Bland's entering rule selects $s$ as the smallest-index non-basic variable with $\bar{c}_s > 0$. The variable $s$ is fickle (it changes basis status), so $s \leq t$. Since $s$ enters while $t$ leaves, $s \neq t$, giving: \begin{align*} s < t, \quad \bar{c}_s > 0, \quad \bar{c}_t = 0 \text{ (since } t \in B\text{)}. \end{align*} The pivot element $\bar{A}_{ts} > 0$ (the entry in the $t$-row of the updated column for $s$ must be positive for $t$ to be eligible as the leaving variable). **(2) A pivot where $t$ enters the basis.** Call the basis at this step $\hat{B}$, with non-basic set $\hat{N}$. At this pivot, $t$ enters the basis. Denote the reduced costs at $\hat{B}$ by $\hat{c}$. Since Bland's entering rule selects $t$: \begin{align*} \hat{c}_t > 0, \quad \text{and } \hat{c}_j \leq 0 \text{ for all } j \in \hat{N} \text{ with } j < t. \end{align*} For any fickle variable $j$ with $j < t$: either $j \in \hat{B}$ (so $\hat{c}_j = 0$) or $j \in \hat{N}$ with $j < t$ (so $\hat{c}_j \leq 0$ by Bland's rule). In either case: \begin{align*} \hat{c}_j \leq 0 \quad \text{for every fickle } j \neq t. \end{align*} [guided] Why is $s$ fickle? Variable $s$ enters the basis at this pivot, so $s$ is non-basic at basis $B$ but basic at the next basis. Since the cycle eventually returns to $B$, variable $s$ must leave at some later step. Therefore $s$ is not basic in all bases — it is fickle. Why is $\bar{A}_{ts} > 0$? The simplex method updates the basic variables as $\hat{x}_{B} = \bar{b} - \epsilon \bar{A}_s$, where $\bar{A}_s$ is the updated column for the entering variable $s$ and $\epsilon \geq 0$ is the step length. For basic variable $t$ to leave, it must be a candidate in the minimum ratio test: we need $\bar{A}_{ts} > 0$ so that increasing $\epsilon$ drives $x_t$ toward zero. The sign condition $\hat{c}_j \leq 0$ for fickle $j \neq t$ comes from combining two observations. If $j \in \hat{B}$, then $\hat{c}_j = 0$ by definition of reduced costs. If $j \in \hat{N}$ and $j < t$, then Bland's rule would have chosen $j$ over $t$ if $\hat{c}_j > 0$ (since $j$ has a smaller index). Since $t$ was chosen, $\hat{c}_j \leq 0$. These are all the sign conditions we need. The next steps construct the objects whose inner product yields the contradiction. [/guided] [/step] [step:Extract the direction vector $d$ from the pivot where $t$ leaves] At basis $B$, when variable $s$ enters and $t$ leaves, the simplex method moves along the direction: \begin{align*} d_j = \begin{cases} -\bar{A}_{js} & \text{if } j \in B, \\ 1 & \text{if } j = s, \\ 0 & \text{if } j \in N \setminus \{s\}. \end{cases} \end{align*} Here $\bar{A}_{js}$ is the entry in the $j$-th row of the updated column for $s$ at basis $B$. This direction satisfies $Ad = 0$: indeed, $Ad = A_B(-\bar{A}_s) + A_N e_s = -A_B(A_B^{-1} a_s) + a_s = -a_s + a_s = 0$, where $a_s$ is the $s$-th column of $A$. We record the sign of $d_j$ for each variable: - **$d_t = -\bar{A}_{ts} < 0$** (since $\bar{A}_{ts} > 0$, the pivot element). - **$d_s = 1 > 0$**. - **$d_j = 0$ for $j \in N \setminus \{s\}$** (non-basic variables other than $s$ do not move). - **$d_j \geq 0$ for fickle $j \in B$ with $j \neq t$**: Since $j$ is fickle, $x^*_j = 0$, so $\bar{b}_j = 0$. Thus $j$ is a degenerate basic variable eligible to leave if $\bar{A}_{js} > 0$. But Bland's leaving rule selected $t$ as the leaving variable, and $j < t$ (since $j$ is fickle and $j \neq t$ implies $j < t$ by maximality of $t$). If $\bar{A}_{js} > 0$, then $j$ would have been eligible with $\bar{b}_j / \bar{A}_{js} = 0$ and $j < t$, so Bland's rule would have chosen $j$ over $t$. This contradicts the choice of $t$, so $\bar{A}_{js} \leq 0$, giving $d_j = -\bar{A}_{js} \geq 0$. - **$d_j$ has unknown sign for non-fickle $j \in B$**: If $j \in B$ is not fickle, $j$ has the same basis status at every step, and $x^*_j$ may be positive. We cannot determine the sign of $d_j$ for such variables, but this will not matter. [guided] The direction vector $d$ describes how the variables change in a simplex pivot: the entering variable $x_s$ increases by $\epsilon$, each basic variable $x_j$ changes by $-\bar{A}_{js} \epsilon$, and all other non-basic variables stay at zero. In the current degenerate pivot $\epsilon = 0$, so no actual movement occurs — but the direction $d$ is still well-defined and lies in $\ker A$. The sign $d_j \geq 0$ for fickle $j \in B$, $j \neq t$ is a direct consequence of Bland's **leaving** rule. Here is the reasoning in detail: the minimum ratio test identifies leaving candidates as those $j \in B$ with $\bar{A}_{js} > 0$ and minimal ratio $\bar{b}_j / \bar{A}_{js}$. Since $\bar{b}_j = x^*_j = 0$ for degenerate basics, any degenerate basic with $\bar{A}_{js} > 0$ achieves ratio $0$ (the minimum possible). Bland's rule then picks the smallest index among all such ties. If any fickle $j < t$ had $\bar{A}_{js} > 0$, it would have been chosen instead of $t$, contradicting our setup. So $\bar{A}_{js} \leq 0$ for all such $j$, and $d_j = -\bar{A}_{js} \geq 0$. The sign of $d_j$ for non-fickle basic variables is irrelevant because the corresponding $\tilde{c}_j$ will turn out to be zero, making those terms vanish in the inner product. [/guided] [/step] [step:Form the reduced cost difference $\tilde{c}$ and establish $\tilde{c}^\top d = 0$] Let $\bar{c}$ and $\hat{c}$ denote the vectors of reduced costs at bases $B$ and $\hat{B}$ respectively. Define: \begin{align*} \tilde{c} = \hat{c} - \bar{c}. \end{align*} At any basis with simplex multiplier vector $\pi$, the reduced cost of variable $j$ is $\bar{c}_j = c_j - \pi^\top a_j$, where $\pi^\top = c_B^\top A_B^{-1}$. Let $\bar{\pi}^\top = c_B^\top A_B^{-1}$ and $\hat{\pi}^\top = c_{\hat{B}}^\top A_{\hat{B}}^{-1}$ be the simplex multiplier vectors at $B$ and $\hat{B}$. Then for every variable $j$: \begin{align*} \tilde{c}_j = \hat{c}_j - \bar{c}_j = (c_j - \hat{\pi}^\top a_j) - (c_j - \bar{\pi}^\top a_j) = (\bar{\pi} - \hat{\pi})^\top a_j. \end{align*} Therefore $\tilde{c}^\top = (\bar{\pi} - \hat{\pi})^\top A$, which means $\tilde{c}$ lies in the row space of $A$. Since $d \in \ker A$ (established in the previous step) and the null space of $A$ is orthogonal to the row space of $A$: \begin{align*} \tilde{c}^\top d = 0. \end{align*} We now record the sign of $\tilde{c}_j$ for each variable: - **$\tilde{c}_t = \hat{c}_t - \bar{c}_t = \hat{c}_t - 0 = \hat{c}_t > 0$** (since $t \in B$ gives $\bar{c}_t = 0$, and $\hat{c}_t > 0$ from Bland's entering rule at $\hat{B}$). - **$\tilde{c}_s = \hat{c}_s - \bar{c}_s$**: We have $\hat{c}_s \leq 0$ (since $s$ is fickle and $s \neq t$) and $\bar{c}_s > 0$. Therefore $\tilde{c}_s = \hat{c}_s - \bar{c}_s < 0$. - **$\tilde{c}_j \leq 0$ for fickle $j \in B$ with $j \neq t$**: Since $j \in B$, $\bar{c}_j = 0$. Since $j$ is fickle and $j \neq t$, $\hat{c}_j \leq 0$. Therefore $\tilde{c}_j = \hat{c}_j \leq 0$. - **$\tilde{c}_j = 0$ for non-fickle $j \in B$**: If $j$ is not fickle, then $j$ has the same basis status in every basis of the cycle. Since $j \in B$, $j$ is basic at every step, so $j \in \hat{B}$ as well. Therefore $\bar{c}_j = 0$ and $\hat{c}_j = 0$, giving $\tilde{c}_j = 0$. - **$\tilde{c}_j$ is unconstrained for $j \in N \setminus \{s\}$**: We have no sign information, but $d_j = 0$ for these variables, so the product $\tilde{c}_j d_j = 0$ regardless. [guided] The identity $\tilde{c}^\top d = 0$ is the linchpin of the entire proof. It holds because $\tilde{c}$ and $d$ live in orthogonal subspaces of $\mathbb{R}^n$: $d$ lies in the null space of $A$ (it is a feasible direction of the polytope), while $\tilde{c}$ lies in the row space of $A$ (it is the difference of two vectors of the form $c - A^\top \pi$, and their difference is $A^\top(\bar{\pi} - \hat{\pi})$, a linear combination of the rows of $A$). Let us verify this orthogonality concretely. We have $\tilde{c}^\top d = (\bar{\pi} - \hat{\pi})^\top A d = (\bar{\pi} - \hat{\pi})^\top \cdot 0 = 0$, since $Ad = 0$. The sign analysis of $\tilde{c}_j$ combines information from both bases. The key observations are: - For $t$: the reduced cost at $B$ is zero (basic), at $\hat{B}$ is positive (entering). So $\tilde{c}_t > 0$. - For $s$: the reduced cost at $B$ is positive (entering), at $\hat{B}$ is non-positive (Bland's rule at $\hat{B}$ chose $t$ instead). So $\tilde{c}_s < 0$. - For other fickle basics: zero at $B$ (basic), non-positive at $\hat{B}$ (Bland's rule). So $\tilde{c}_j \leq 0$. - For non-fickle basics: basic at both $B$ and $\hat{B}$, so zero at both. Notice that the sign of $\tilde{c}_j$ for non-basic $j \neq s$ is completely irrelevant: since $d_j = 0$ for these variables, their contribution to $\tilde{c}^\top d$ vanishes regardless. This is why the proof works — we only need sign information where $d_j \neq 0$, and those are precisely the basic variables and the entering variable $s$. [/guided] [/step] [step:Compute $\tilde{c}^\top d$ term by term and reach the contradiction] We now evaluate $\tilde{c}^\top d = \sum_{j=1}^{n} \tilde{c}_j d_j$ by partitioning the sum into five groups: \begin{align*} \tilde{c}^\top d = \underbrace{\tilde{c}_t \, d_t}_{(I)} + \underbrace{\tilde{c}_s \, d_s}_{(II)} + \underbrace{\sum_{\substack{j \in B,\, j \neq t \\ j \text{ fickle}}} \tilde{c}_j \, d_j}_{(III)} + \underbrace{\sum_{\substack{j \in B \\ j \text{ not fickle}}} \tilde{c}_j \, d_j}_{(IV)} + \underbrace{\sum_{\substack{j \in N \\ j \neq s}} \tilde{c}_j \, d_j}_{(V)}. \end{align*} **Term (I):** $\tilde{c}_t > 0$ and $d_t < 0$, so $\tilde{c}_t \, d_t < 0$. **Term (II):** $\tilde{c}_s < 0$ and $d_s > 0$, so $\tilde{c}_s \, d_s < 0$. **Term (III):** For each fickle $j \in B$ with $j \neq t$: $\tilde{c}_j \leq 0$ and $d_j \geq 0$, so $\tilde{c}_j \, d_j \leq 0$. **Term (IV):** For each non-fickle $j \in B$: $\tilde{c}_j = 0$, so $\tilde{c}_j \, d_j = 0$. **Term (V):** For each $j \in N$ with $j \neq s$: $d_j = 0$, so $\tilde{c}_j \, d_j = 0$. Combining: \begin{align*} \tilde{c}^\top d = \underbrace{(\tilde{c}_t \, d_t)}_{< \, 0} + \underbrace{(\tilde{c}_s \, d_s)}_{< \, 0} + \underbrace{(\text{III})}_{\leq \, 0} + \underbrace{(\text{IV})}_{= \, 0} + \underbrace{(\text{V})}_{= \, 0} < 0. \end{align*} But we established that $\tilde{c}^\top d = 0$. This is a contradiction. [guided] Let us verify each sign one final time, since this is the heart of the proof. **Term (I): $\tilde{c}_t \, d_t < 0$.** We have $\tilde{c}_t = \hat{c}_t - \bar{c}_t = \hat{c}_t > 0$, where $\hat{c}_t > 0$ because $t$ enters at $\hat{B}$ (Bland's rule requires positive reduced cost for the entering variable in a maximisation LP), and $\bar{c}_t = 0$ because $t$ is basic at $B$. We have $d_t = -\bar{A}_{ts} < 0$, where $\bar{A}_{ts} > 0$ is the pivot element. Product: strictly negative. **Term (II): $\tilde{c}_s \, d_s < 0$.** We have $\bar{c}_s > 0$ (the variable $s$ enters at $B$, so its reduced cost is positive) and $\hat{c}_s \leq 0$ (since $s$ is fickle, $s < t$, and at $\hat{B}$ Bland's rule chose $t$ as the entering variable, so all non-basic variables with index $< t$ have non-positive reduced cost; if $s$ is basic at $\hat{B}$ then $\hat{c}_s = 0$). Therefore $\tilde{c}_s = \hat{c}_s - \bar{c}_s < 0$. We have $d_s = 1 > 0$. Product: strictly negative. **Term (III): each $\tilde{c}_j \, d_j \leq 0$.** For fickle $j \in B$ with $j \neq t$, necessarily $j < t$ (since $t$ is the largest fickle index). Then $\tilde{c}_j = \hat{c}_j \leq 0$ (same argument as for $s$: fickle variables with index $< t$ have non-positive reduced cost at $\hat{B}$). And $d_j \geq 0$ (Bland's leaving rule at basis $B$: if $d_j < 0$ then $\bar{A}_{js} > 0$ with $\bar{b}_j = 0$, making $j$ eligible to leave; since $j < t$, Bland would have chosen $j$ instead of $t$). Product: non-positive. **Term (IV): $\tilde{c}_j \, d_j = 0$.** Non-fickle variables in $B$ are basic at every step, including at $\hat{B}$. So $\bar{c}_j = 0$ and $\hat{c}_j = 0$, hence $\tilde{c}_j = 0$. **Term (V): $\tilde{c}_j \, d_j = 0$.** Non-basic variables other than $s$ do not move in the pivot, so $d_j = 0$. The two strictly negative terms and the non-positive terms force $\tilde{c}^\top d < 0$, but the orthogonality of the null space and row space forces $\tilde{c}^\top d = 0$. This is the contradiction. [/guided] [/step] [step:Conclude finite termination] The contradiction shows that no cycle of bases can occur under Bland's rule. Since the number of bases is finite (at most $\binom{n}{m}$ choices of $m$ columns from $n$), and the simplex method either visits a new basis at each degenerate pivot or strictly improves the objective at each non-degenerate pivot, the algorithm must terminate after finitely many iterations. At termination, either the [Simplex Optimality Criterion](/theorems/2560) is satisfied (all reduced costs of non-basic variables are non-positive), confirming the current basic feasible solution is optimal, or an unbounded ray is detected (an entering variable has no positive entry in its updated column, so $x_j$ can increase without bound). [guided] The finiteness argument has two components: 1. **No cycling**: we have just proved that under Bland's rule, no basis is visited twice. This eliminates the only mechanism by which the simplex method could fail to terminate. 2. **Finite number of bases**: a basis $B$ is a subset of $m$ column indices from $\{1, \ldots, n\}$ such that $A_B$ is invertible. The total number of such subsets is at most $\binom{n}{m}$, which is finite. Since the algorithm visits a distinct basis at each iteration and there are finitely many bases, it must terminate. The worst-case iteration count under Bland's rule is exponential in $n$ and $m$ (which is why more sophisticated anti-cycling rules or interior-point methods are preferred in practice), but termination is guaranteed. [/guided] [/step]