[proofplan] We write the assignment problem in the standard equality-form linear programme $\inf\{\langle C,X\rangle : L(X)=b,\ X\geq 0\}$. The row and column sum constraints determine the [linear map](/page/Linear%20Map) $L$, and computing its adjoint shows that the dual inequalities are exactly $u_i+v_j\leq c_{ij}$. Feasibility and boundedness of the primal allow finite-dimensional linear programming strong duality to be applied, which gives equality of the two optimal values. [/proofplan]

[step:Rewrite the assignment problem as an equality-form linear programme] Let $E := \mathbb{R}^{n \times n}$, equipped with the coordinatewise order $X \geq 0$ meaning $x_{ij} \geq 0$ for every $1 \leq i,j \leq n$. Define the linear functional $\ell_C:E\to\mathbb{R}$ by declaring that, for each $X=(x_{ij})_{1\leq i,j\leq n}\in E$, \begin{align*} \ell_C(X) := \sum_{i=1}^{n}\sum_{j=1}^{n} c_{ij}x_{ij}. \end{align*} Define the constraint space $F := \mathbb{R}^{n} \times \mathbb{R}^{n}$ and the linear map $L:E\to F$ by declaring that, for each $X=(x_{ij})_{1\leq i,j\leq n}\in E$, \begin{align*} L(X) := \left(\left(\sum_{j=1}^{n} x_{ij}\right)_{i=1}^{n},\left(\sum_{i=1}^{n} x_{ij}\right)_{j=1}^{n}\right). \end{align*} Finally define \begin{align*} b := \left((1,\dots,1),(1,\dots,1)\right) \in F. \end{align*} Then $X \in \mathcal{A}_n$ if and only if $X \geq 0$ and $L(X)=b$. Therefore the primal programme is exactly \begin{align*} \inf\{\ell_C(X) : X \in E,\ X \geq 0,\ L(X)=b\}. \end{align*} [/step]

[step:Compute the dual constraints from the adjoint of the row-column sum map]Equip $E$ with the Euclidean pairing \begin{align*} \langle A,X\rangle_E := \sum_{i=1}^{n}\sum_{j=1}^{n} a_{ij}x_{ij} \end{align*} for $A=(a_{ij})_{1 \leq i,j \leq n}, X=(x_{ij})_{1 \leq i,j \leq n} \in E$, and equip $F$ with the Euclidean pairing \begin{align*} \langle (u,v),(r,s)\rangle_F := \sum_{i=1}^{n}u_i r_i + \sum_{j=1}^{n}v_j s_j \end{align*} for $(u,v),(r,s) \in \mathbb{R}^{n}\times \mathbb{R}^{n}$. For $(u,v)\in F$, the adjoint $L^*(u,v)\in E$ is determined by the identity \begin{align*} \langle L^*(u,v),X\rangle_E = \langle (u,v),L(X)\rangle_F \end{align*} for every $X\in E$. The first expansion of the right-hand pairing is \begin{align*} \langle (u,v),L(X)\rangle_F = \sum_{i=1}^{n}u_i\sum_{j=1}^{n}x_{ij}+\sum_{j=1}^{n}v_j\sum_{i=1}^{n}x_{ij}. \end{align*} Reindexing the second finite sum by writing it as a double sum over the same ordered pairs $(i,j)$ gives \begin{align*} \langle (u,v),L(X)\rangle_F = \sum_{i=1}^{n}\sum_{j=1}^{n}(u_i+v_j)x_{ij}. \end{align*} Hence \begin{align*} L^*(u,v) = (u_i+v_j)_{1 \leq i,j \leq n}. \end{align*} For a minimisation problem with constraints $X\geq 0$, the equality-form dual is \begin{align*} \sup\{\langle (u,v),b\rangle_F : (u,v)\in F,\ L^*(u,v)\leq C\}, \end{align*} where $L^*(u,v)\leq C$ is coordinatewise. Since \begin{align*} \langle (u,v),b\rangle_F = \sum_{i=1}^{n}u_i+\sum_{j=1}^{n}v_j \end{align*} and $L^*(u,v)\leq C$ means $u_i+v_j\leq c_{ij}$ for every $i,j$, this is precisely the stated dual programme.[/step]

[guided]The purpose of this step is to identify the dual variables and the dual inequalities without guessing them. The primal has one equality constraint for each row and one equality constraint for each column, so we introduce one unrestricted dual variable $u_i\in\mathbb{R}$ for the $i$th row equation and one unrestricted dual variable $v_j\in\mathbb{R}$ for the $j$th column equation. We use the Euclidean pairing on $E=\mathbb{R}^{n\times n}$: \begin{align*} \langle A,X\rangle_E := \sum_{i=1}^{n}\sum_{j=1}^{n} a_{ij}x_{ij}, \end{align*} and the Euclidean pairing on $F=\mathbb{R}^{n}\times\mathbb{R}^{n}$: \begin{align*} \langle (u,v),(r,s)\rangle_F := \sum_{i=1}^{n}u_i r_i+\sum_{j=1}^{n}v_j s_j. \end{align*} For $X=(x_{ij})\in E$, the constraint map is \begin{align*} L(X)=\left(\left(\sum_{j=1}^{n}x_{ij}\right)_{i=1}^{n},\left(\sum_{i=1}^{n}x_{ij}\right)_{j=1}^{n}\right). \end{align*} Therefore, for $(u,v)\in F$, \begin{align*} \langle (u,v),L(X)\rangle_F = \sum_{i=1}^{n}u_i\sum_{j=1}^{n}x_{ij}+\sum_{j=1}^{n}v_j\sum_{i=1}^{n}x_{ij}. \end{align*} Because all sums are finite, we may rewrite both terms as double sums over the same index set $\{1,\dots,n\}\times\{1,\dots,n\}$: \begin{align*} \langle (u,v),L(X)\rangle_F = \sum_{i=1}^{n}\sum_{j=1}^{n}u_i x_{ij}+\sum_{i=1}^{n}\sum_{j=1}^{n}v_j x_{ij}. \end{align*} Combining the two double sums term by term gives \begin{align*} \langle (u,v),L(X)\rangle_F = \sum_{i=1}^{n}\sum_{j=1}^{n}(u_i+v_j)x_{ij}. \end{align*} By the definition of the adjoint with respect to these pairings, this computation says \begin{align*} L^*(u,v)=(u_i+v_j)_{1\leq i,j\leq n}. \end{align*} Now we translate the standard dual form. The primal is a minimisation problem with non-negative variables $X\geq 0$ and equality constraints $L(X)=b$. Its dual has objective $\langle (u,v),b\rangle_F$ and constraint $L^*(u,v)\leq C$ coordinatewise. Since \begin{align*} b=\left((1,\dots,1),(1,\dots,1)\right), \end{align*} we get \begin{align*} \langle (u,v),b\rangle_F = \sum_{i=1}^{n}u_i+\sum_{j=1}^{n}v_j. \end{align*} The coordinatewise inequality $L^*(u,v)\leq C$ is exactly \begin{align*} u_i+v_j\leq c_{ij} \end{align*} for all $1\leq i,j\leq n$. Thus the abstract linear-programming dual is exactly the dual programme stated in the theorem.[/guided]

[step:Verify feasibility and finiteness of the primal optimum] Define $I_n=(\delta_{ij})_{1\leq i,j\leq n}\in\mathbb{R}^{n\times n}$, where $\delta_{ij}=1$ if $i=j$ and $\delta_{ij}=0$ otherwise. Then $I_n\geq 0$, each row sum of $I_n$ is $1$, and each column sum of $I_n$ is $1$, so $I_n\in\mathcal{A}_n$. Hence the primal feasible set is non-empty. If $X=(x_{ij})\in\mathcal{A}_n$, then $0\leq x_{ij}\leq 1$ for every $i,j$, because $x_{ij}\geq 0$ and $\sum_{j=1}^{n}x_{ij}=1$. Therefore \begin{align*} \ell_C(X) = \sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}x_{ij} \geq -\sum_{i=1}^{n}\sum_{j=1}^{n}|c_{ij}|x_{ij} \geq -\sum_{i=1}^{n}\sum_{j=1}^{n}|c_{ij}|. \end{align*} Thus the primal feasible set is non-empty and the primal objective is bounded below by the finite constant \begin{align*} M_C := -\sum_{i=1}^{n}\sum_{j=1}^{n}|c_{ij}|. \end{align*} [/step]

[step:Apply finite-dimensional strong duality to conclude equality of optimal values] The dual feasible set is also non-empty. Define $u^0=(u_i^0)_{i=1}^{n}\in\mathbb{R}^n$ and $v^0=(v_j^0)_{j=1}^{n}\in\mathbb{R}^n$ by \begin{align*} u_i^0 := \min_{1\leq j\leq n} c_{ij}, \qquad v_j^0 := 0. \end{align*} Then, for every $1\leq i,j\leq n$, the definition of the minimum over the finite set $\{c_{i1},\dots,c_{in}\}$ gives \begin{align*} u_i^0+v_j^0 = \min_{1\leq k\leq n}c_{ik}\leq c_{ij}, \end{align*} so $(u^0,v^0)$ is feasible for the dual. We use the finite-dimensional linear programming strong duality theorem in the following form: for a finite-dimensional equality-form primal minimisation problem with non-negative variables and its adjoint dual, if both programmes are feasible and the primal objective is bounded below, then the primal and dual optimal values are equal. The equality-form primal is \begin{align*} \inf\{\ell_C(X): X\in E,\ X\geq 0,\ L(X)=b\} \end{align*} and its dual is \begin{align*} \sup\{\langle (u,v),b\rangle_F : (u,v)\in F,\ L^*(u,v)\leq C\}. \end{align*} The primal is feasible and bounded below by the previous step, and the dual is feasible by the construction of $(u^0,v^0)$ above. Therefore finite-dimensional linear programming strong duality applies, and the two optimal values are equal. Using the identification of the dual constraints and dual objective computed above, this equality is exactly \begin{align*} \inf_{X\in\mathcal{A}_n}\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}x_{ij} = \sup\left\{\sum_{i=1}^{n}u_i+\sum_{j=1}^{n}v_j : u_i+v_j\leq c_{ij}\ \text{for all }1\leq i,j\leq n\right\}. \end{align*} This proves the theorem. [/step]