  For a given nonnegative matrix $A=(A_{ij})$, the matrix scaling problem asks
whether $A$ can be scaled to a doubly stochastic matrix $D_1AD_2$ for some
positive diagonal matrices $D_1,D_2$.The Sinkhorn algorithm is a simple
iterative algorithm, which repeats row-normalization $A_{ij} \leftarrow
A_{ij}/\sum_{j}A_{ij}$ and column-normalization $A_{ij} \leftarrow
A_{ij}/\sum_{i}A_{ij}$ alternatively. By this algorithm, $A$ converges to a
doubly stochastic matrix in limit if and only if the bipartite graph associated
with $A$ has a perfect matching. This property can decide the existence of a
perfect matching in a given bipartite graph $G$, which is identified with the
$0,1$-matrix $A_G$.Linial, Samorodnitsky, and Wigderson showed that $O(n^2 \log
n)$ iterations for $A_G$ decide whether $G$ has a perfect matching. Here $n$ is
the number of vertices in one of the color classes of $G$. In this paper, we
show an extension of this result:If $G$ has no perfect matching, then a
polynomial number of the Sinkhorn iterations identifies a Hall blocker -- a
vertex subset $X$ having neighbors $\Gamma(X)$ with $|X| > |\Gamma(X)|$.
Specifically, we show that $O(n^2 \log n)$ iterations can identify one Hall
blocker, and that further polynomial iterations can also identify all
parametric Hall blockers $X$ of maximizing $(1-\lambda) |X| - \lambda
|\Gamma(X)|$ for $\lambda \in [0,1]$.The former result is based on an
interpretation of the Sinkhorn algorithm as alternating minimization for
geometric programming. The latter is on an interpretation as alternating
minimization for KL-divergence (Csisz\'{a}r and Tusn\'{a}dy 1984, Gietl and
Reffel 2013) and its limiting behavior for a nonscalable matrix (Aas 2014). We
also relate the Sinkhorn limit with parametric network flow, principal
partition of polymatroids, and the Dulmage-Mendelsohn decomposition of a
bipartite graph.
