[proofplan] The update changes row potentials on $S$ and column potentials on $T$, so each reduced cost is controlled by the location of its row and column relative to $S$ and $T$. We compute the updated reduced cost in the four possible cases and use the definition of $\delta$ exactly in the only case where a reduced cost can decrease. The absence of equality edges from $S$ to $J \setminus T$ makes $\delta$ positive, and an edge attaining the minimum becomes a new equality edge. Finally, the matched-edge closure property of the alternating search tree ensures that every matched edge whose column lies in $T$ has its row in $S$; all other matched equality edges with column outside $T$ cannot start in $S$ because there is no equality edge from $S$ to $J \setminus T$. [/proofplan] [step:Show that the update size is positive and attained by an edge from $S$ to $J \setminus T$] Let $C=(C_{ij})_{i,j\in J}$ denote the cost matrix. For each pair $(i,j) \in J \times J$, define the reduced cost with respect to $u,v$ by \begin{align*} r_{ij} := C_{ij} - u_i - v_j. \end{align*} Let $M \subset J \times J$ be the matching in the Hungarian state from which the maximal alternating search tree $(S,T)$ is formed; a matched equality edge means an edge $(i,j) \in M$ satisfying $r_{ij}=0$. By the definition of an alternating search tree, the matched-edge closure property holds: whenever $(i,j) \in M$ and $j \in T$, one has $i \in S$. Since $S \neq \varnothing$ and $J \setminus T \neq \varnothing$, define $A \subset \mathbb{R}$ to be the finite set \begin{align*} A := \{r_{ij} : i \in S,\ j \in J \setminus T\}. \end{align*} This set is nonempty. Define the update size $\delta \in \mathbb{R}$ by \begin{align*} \delta := \min A = \min \{r_{ij} : i \in S,\ j \in J \setminus T\}. \end{align*} Since $A$ is finite and nonempty, this minimum is attained: there exist $i_0 \in S$ and $j_0 \in J \setminus T$ such that $\delta = r_{i_0j_0}$. Because there is no equality edge from $S$ to $J \setminus T$, every reduced cost $r_{ij}$ with $i \in S$ and $j \in J \setminus T$ satisfies $r_{ij} \neq 0$. Feasibility gives $r_{ij} \geq 0$ for all such pairs, so in fact $r_{ij} > 0$ for all $i \in S$ and $j \in J \setminus T$. Therefore $\delta > 0$. [/step] [step:Compute the updated reduced costs in the four possible cases] Fix arbitrary $i,j \in J$. Define the updated reduced cost with respect to $u',v'$ by \begin{align*} r_{ij}' := C_{ij} - u_i' - v_j'. \end{align*} By the definitions of $u_i'$ and $v_j'$, the value of $r_{ij}'$ is determined by whether $i$ lies in $S$ and whether $j$ lies in $T$. If $i \in S$ and $j \in T$, then $u_i' = u_i + \delta$ and $v_j' = v_j - \delta$. Substituting these definitions and cancelling the added row-potential term against the subtracted column-potential term gives $r_{ij}' = C_{ij} - u_i - v_j = r_{ij}$. If $i \in J \setminus S$ and $j \in J \setminus T$, then $u_i' = u_i$ and $v_j' = v_j$, so $r_{ij}' = C_{ij} - u_i - v_j = r_{ij}$. If $i \in S$ and $j \in J \setminus T$, then $u_i' = u_i + \delta$ and $v_j' = v_j$, so \begin{align*} r_{ij}' = C_{ij} - (u_i + \delta) - v_j = r_{ij} - \delta. \end{align*} By the definition of $\delta$ as the minimum of $r_{ab}$ over $a \in S$ and $b \in J \setminus T$, we have $\delta \leq r_{ij}$. Hence $r_{ij}' \geq 0$ in this case. If $i \in J \setminus S$ and $j \in T$, then $u_i' = u_i$ and $v_j' = v_j - \delta$, so \begin{align*} r_{ij}' = C_{ij} - u_i - (v_j - \delta) = r_{ij} + \delta. \end{align*} Since $r_{ij} \geq 0$ and $\delta > 0$, this gives $r_{ij}' \geq 0$. These four cases cover all pairs $(i,j) \in J \times J$, so $r_{ij}' \geq 0$ for every $i,j \in J$. [guided] The only danger in the Hungarian update is that increasing $u_i$ for rows in $S$ may decrease some reduced costs. We therefore compute exactly how each reduced cost changes. Fix arbitrary $i,j \in J$. The old reduced cost and updated reduced cost are the [real numbers](/page/Real%20Numbers) \begin{align*} r_{ij} := C_{ij} - u_i - v_j, \qquad r_{ij}' := C_{ij} - u_i' - v_j'. \end{align*} If $i \in S$ and $j \in T$, then the update adds $\delta$ to the row potential and subtracts $\delta$ from the column potential. These two changes cancel: \begin{align*} r_{ij}' = C_{ij} - u_i' - v_j' = C_{ij} - (u_i + \delta) - (v_j - \delta) = C_{ij} - u_i - v_j = r_{ij}. \end{align*} Thus no reduced cost changes on $S \times T$. If $i \in J \setminus S$ and $j \in J \setminus T$, neither potential changes. Therefore $r_{ij}' = C_{ij} - u_i - v_j = r_{ij}$. If $i \in S$ and $j \in J \setminus T$, then only the row potential changes. This is the case where a reduced cost decreases: \begin{align*} r_{ij}' = C_{ij} - (u_i + \delta) - v_j = r_{ij} - \delta. \end{align*} The definition of $\delta$ was chosen precisely to control this case: \begin{align*} \delta = \min \{ r_{ab} : a \in S,\ b \in J \setminus T \}. \end{align*} Since the fixed pair $(i,j)$ belongs to $S \times (J \setminus T)$, we have $\delta \leq r_{ij}$. Hence \begin{align*} r_{ij}' = r_{ij} - \delta \geq 0. \end{align*} Finally, if $i \in J \setminus S$ and $j \in T$, then only the column potential decreases. Since reduced cost is $C_{ij} - u_i - v_j$, decreasing $v_j$ increases the reduced cost: \begin{align*} r_{ij}' = C_{ij} - u_i - (v_j - \delta) = r_{ij} + \delta. \end{align*} Feasibility of the old potentials gives $r_{ij} \geq 0$. We also record why $\delta > 0$ within this guided argument. The set of values $r_{ab}$ with $a \in S$ and $b \in J \setminus T$ is finite and nonempty, so its minimum is attained. There is no equality edge from $S$ to $J \setminus T$, meaning none of these reduced costs is $0$; feasibility gives all of them are at least $0$, so all of them are strictly positive. Therefore their minimum $\delta$ is strictly positive. Hence $r_{ij}' = r_{ij} + \delta \geq 0$. The four alternatives $i \in S$ or $i \in J \setminus S$, and $j \in T$ or $j \in J \setminus T$, exhaust $J \times J$. Therefore every updated reduced cost is non-negative. [/guided] [/step] [step:Create a new equality edge from $S$ to $J \setminus T$] Let $i_0 \in S$ and $j_0 \in J \setminus T$ be chosen so that $\delta = r_{i_0j_0}$. For this pair the computation in the case $S \times (J \setminus T)$ gives \begin{align*} r_{i_0j_0}' = r_{i_0j_0} - \delta = 0. \end{align*} Thus $(i_0,j_0)$ is an equality edge with respect to the updated potentials. Since $\delta > 0$, the old reduced cost satisfies $r_{i_0j_0} = \delta > 0$, so this equality edge was not present before the update. [/step] [step:Verify that matched equality edges remain equality edges] Let $(i,j) \in M$ be an arbitrary matched equality edge, so by definition $r_{ij} = 0$. If $j \in T$, then the matched-edge closure property of the alternating search tree gives $i \in S$. Hence $(i,j) \in S \times T$, and the computation above gives \begin{align*} r_{ij}' = r_{ij} = 0. \end{align*} If $j \in J \setminus T$, then no equality edge runs from $S$ to $J \setminus T$. Since $(i,j)$ is a matched equality edge and $j \in J \setminus T$, it follows that $i \notin S$. Hence $(i,j) \in (J \setminus S) \times (J \setminus T)$, and the computation above gives \begin{align*} r_{ij}' = r_{ij} = 0. \end{align*} Thus every matched equality edge in $M$ remains an equality edge with respect to $u',v'$. [guided] We prove the matched-edge preservation by separating according to whether the column of the matched edge lies in the tree. Let $(i,j) \in M$ be a matched equality edge, so $r_{ij}=0$. First suppose $j \in T$. Since $(S,T)$ is an alternating search tree for the matching $M$, its matched-edge closure property says that any matched edge whose column lies in $T$ has its row in $S$. Therefore $i \in S$, so $(i,j) \in S \times T$. In the computation of updated reduced costs on $S \times T$, the increase of $u_i$ by $\delta$ and the decrease of $v_j$ by $\delta$ cancel, giving \begin{align*} r_{ij}' = r_{ij} = 0. \end{align*} Now suppose $j \in J \setminus T$. If $i$ belonged to $S$, then $(i,j)$ would be an equality edge from $S$ to $J \setminus T$, because $r_{ij}=0$. This contradicts the hypothesis that there is no equality edge from $S$ to $J \setminus T$. Hence $i \in J \setminus S$, so $(i,j) \in (J \setminus S) \times (J \setminus T)$. In this case neither potential changes, and therefore \begin{align*} r_{ij}' = r_{ij} = 0. \end{align*} These two cases cover every matched equality edge in $M$, so every matched equality edge remains an equality edge after the update. [/guided] Combining this with the non-negativity of all updated reduced costs and the creation of an equality edge from $S$ to $J \setminus T$ proves the theorem. [/step]