Sinkhorn Matrix Scaling
Visualize the Sinkhorn-Knopp algorithm scaling a positive matrix to a doubly stochastic matrix.
By Riano · Published · Updated · Report a correction
Sinkhorn Matrix Scaling
Concept Overview
The Sinkhorn-Knopp algorithm is an iterative process used to scale a positive matrix into a doubly stochastic matrix. A matrix is doubly stochastic if all its entries are non-negative, and the sum of the elements in every row and every column equals 1.
The algorithm works by alternately scaling the rows (dividing each element by its row sum) and the columns (dividing each element by its column sum). For matrices with strictly positive entries, this process is guaranteed to converge to a unique doubly stochastic matrix.
Worked Example
Let's trace one cycle of the algorithm manually with the initial matrix A:
- Initial matrix: A = [[1, 2], [3, 4]]
- Step 1: Row Normalization:
Row 1 sum = 1 + 2 = 3
Row 2 sum = 3 + 4 = 7
Matrix after row normalization: [[1/3, 2/3], [3/7, 4/7]] - Step 2: Column Normalization:
Column 1 sum = 1/3 + 3/7 = 16/21
Column 2 sum = 2/3 + 4/7 = 26/21
Matrix after one full cycle:
Row 1: (1/3)/(16/21) = 7/16, (2/3)/(26/21) = 7/13
Row 2: (3/7)/(16/21) = 9/16, (4/7)/(26/21) = 6/13 - Expected result: The resulting matrix is [[7/16, 7/13], [9/16, 6/13]]. Row sums are 203/208 and 213/208. Residual is 5/208.
Interactive Experiment
You can try this in the Sinkhorn Matrix Scaling module.
- Set A11 to 1, A12 to 2, A21 to 3, and A22 to 4.
- Set Cycle limit to 1.
- Click the Finish button to perform one complete cycle.
- Observe that the matrix becomes [[7/16, 7/13], [9/16, 6/13]] with row sums 203/208 and 213/208, and a residual of 5/208.
- Because the residual > 1e-6, it displays "Cycle limit reached, not Converged."
Limitations
There are several notable limitations in this interactive implementation of the Sinkhorn Matrix Scaling algorithm, primarily regarding dimensions and numerical constraints:
- This implementation is strictly limited to 2x2 matrices for educational clarity and visualization constraints.
- Zero or negative entries are outside the domain; Sinkhorn scaling may not converge or may converge to a matrix with zeros if the initial matrix has a certain sparsity pattern.
- Floating-point arithmetic limitations mean convergence is defined as a residual less than or equal to 1e-6, rather than true equality. The fraction display recognizes small rational values for readability; the scientific residual uses unrounded entries. Before the first cycle both cards contain the raw input; an unfinished cursor is labeled in progress, not cycle-limit reached. Reset preserves the matrix and selected limit.
References
Nathanson’s Section 1 defines left row scaling and right column scaling, notes that either half-step need not satisfy the other sum condition, and describes convergence for strictly positive matrices. Our one-cycle 2×2 calculation is worked independently above; a finite cycle limit is not a promise of exact equality.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Sinkhorn Matrix Scaling module.
Try Sinkhorn Matrix Scaling on Riano →