= 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, then
$$
\boxed{k\leq r-n+1\leq n^2-n+1.}
$$
Since the residual ultimately vanishes, summing the recorded subtractions gives $A=\sum\alpha_iP_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. Hence
$$
\boxed{\text{running time }O(n^5)\text{ arithmetic/comparison operations}.}
$$
This 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.
Back to article page
