Open Collections

Description

An $n\times n$ matrix $S = \bmat s_{i,j} \emat$ with nonnegative coordinates is \emph{doubly stochastic} if all of its row and column sums are equal to 1, that is, if \[ \rowsum_i(S) = \sum_{j=1}^n s_{i,j} = 1 \qquad\text{for $i= 1,\ldots, n$} \] and \[ \colsum_j(S) = \sum_{i=1}^n s_{i,j} = 1 \qquad\text{for $j = 1,\ldots, n$.} \] Let $A = \bmat a_{i,j} \emat$ be an $n\times n$ matrix with positive coordinates. The alternate minimization algorithm of Sinkhorn-Knopp constructs sequences $(X_k)_{k=1}^{\infty}$ and $(Y_k)_{k=1}^{\infty}$ of positive diagonal matrices such that the limit matrix \[ S = \lim_{k\rightarrow \infty} X_k A Y_k \] exists and is doubly stochastic. The matrix $S$ is called the \emph{Sinkhorn-Knopp limit} of $A$. The attempt to compute explicit Sinkhorn-Knopp limits leads to problems involving Gr\" obner bases and algebraic number theory. In special cases we obtain sequences of rational numbers that converge rapidly to cubic irrationalities.