We present a global spectral bound for the Sinkhorn‑Knopp (SK) algorithm. Let $A$ be a row‑stochastic non‑negative $n\times n$ matrix that admits a finite doubly stochastic scaling $B$. Define
$$ g = 1 - s2(B)^2 > 0,\qquad D = \min{|(u,v)|\infty : B = \operatorname{diag}(e^u) A \operatorname{diag}(e^{-v})}.$$
Starting from the standard initialization, SK reaches a total marginal $\ell_1$ error $\varepsilon$ in
$$O\!\left(\frac{D + \log n + \log(1/\varepsilon)}{g}\right)$$
iterations. A scale‑invariant potential contracts globally according to the spectrum of $B$. The linear dependence on $D$ is unavoidable in the fixed‑gap regime: we construct strictly positive inputs with constant input and endpoint spectral gaps but $D = \Theta(n)$, yielding an $\Omega(n)$ iteration lower bound at error $n^{-2}$. Our upper bound therefore gives $O(n)$ iterations on this family.
We also provide spectral certificates for scalability and short scaling distance. For a row‑stochastic input $A$ with positive column sums $c_j$, set
$$K = \frac{\max_j c_j}{\min_j c_j},\qquad \sigma = s_2\!\left(A\operatorname{diag}(c)^{-1/2}\right).$$
The input‑only condition $\sqrt{K}\,\sigma < 1$ guarantees that $A$ can be scaled to a doubly stochastic matrix, and the scaling distance is bounded by $O\bigl(\frac{\sqrt{K}\,\sigma}{1-\sqrt{K}\,\sigma}\bigr)$. Experiments confirm that the empirical behavior matches the theoretical predictions.
Review: By linking the convergence of SK to the spectral gap of the target scaling, the paper delivers a tight iteration bound and shows that linear dependence on $D$ is intrinsic in the fixed‑gap setting. The spectral certificates offer a practical test for doubly stochastic scalability, contributing both theoretical insight and algorithmic guidance.