Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 38 / 5 / c / Solution

For an explicit algorithm, keep an unnormalized residual $R$, initially $A$, whose row and column sums all equal a common mass $\tau$, initially one. While $\tau >0$, find a perfect matching in its positive support, form its permutation matrix $P$, and subtract $\alpha P$, where $\alpha$ is the smallest selected entry. Record $(\alpha ,P)$ and replace $\tau$ by $\tau -\alpha$.

If the residual mass is positive, the same proof of the Hall marriage theorem condition applies after division by $\tau$. Every subtraction removes at least one positive entry and creates no new positive entries. Before the last subtraction, any positive-mass residual has at least $n$ positive entries; the last step removes all its entries. If $r$ is the initial number of positive entries, thenSince the residual ultimately vanishes, summing the recorded subtractions gives $A=\sum {\alpha }_i{P}_i$, and the row sums give $\sum {\alpha }_i=1$.

A perfect matching can be found by at most $n$ searches for an augmenting path in a matching, each costing $O(n^2)$ in a graph with at most $n^2$ edges. Thus each iteration costs $O(n^3)$, including forming the support and updating the residual, and there are $O(n^2)$ iterations. HenceThis bound uses exact real arithmetic. For rational input, a common denominator lets all residual subtractions be performed on integers of polynomial bit length, giving a polynomial bit-time implementation as well.