= Solution
The assignment constraint <matrix> has one row for each outgoing sum and one for each incoming sum. The column for $x_{ij}$ has a one in outgoing row $i$ and incoming row $j$. Negate all incoming rows. Each column now has exactly one $+1$ and one $-1$, the <oriented incidence matrix>[node-arc incidence matrix] of the directed bipartite <graph> from row vertices to column vertices.
Here is a direct proof that this signed <matrix> is <totally unimodular matrix>[totally unimodular]. Consider any square submatrix and induct on its size. If a column has no nonzero entry, its <determinant> is zero. If a column has one nonzero entry, expansion along it reduces the <determinant> to plus or minus a smaller subdeterminant, hence to $0,1$ or $-1$. If every column has two nonzero entries, they have opposite signs, so each column sum is zero. The rows are then dependent and the <determinant> is zero. The size-one case is immediate, completing the induction.
Negating rows only changes signs of square subdeterminants. Thus the original assignment <matrix> is also a \b[<totally unimodular matrix>]. This proves the <total unimodularity of directed incidence matrices> argument directly in the required setting.
The integrality theorem for totally unimodular systems says that $\{x\geq0:Ax=b\}$ has integral vertices when $A$ is totally unimodular and $b$ is integral. Redundant equalities cause no problem. Here the row sums also force $x_{ij}\leq1$, so every integral feasible vertex is a binary assignment. The bounded nonempty LP relaxation has an optimal vertex, and therefore an optimal assignment. Hence \b[the <assignment problem> can be solved by <linear programming> without a binary search]; dedicated methods such as the <Hungarian algorithm> also exploit its polynomial-time structure. Multiple optimal assignments can have fractional <convex combinations>, so the conclusion concerns an optimal integral vertex, not every optimal LP point.
Back to article page
