## Fast algorithm for generating doubly-stochasstic matrices

version 1.0.0.0 (1.36 KB) by
A simple and fast algorithm for generating doubly-stochasstic matrices

Updated 14 Sep 2006

A simple and fast algorithm for generating doubly-stochasstic matrices.
(matrices, where the sum of each column and each row is exactly 1).
Each matrix is chosen uniformly from the space of all NxN doubly-stochasstic
matrices.
Note: the generated matrices are indeed doubly-stochastic, but it's not
proved / checked yet that the algoithm indeed gnereate the matrices UAR.

Simple algorithm for generating doubly-stochastic matrices
(matrices, where the sum of each column and each row is exactly 1).
The algorithm:
1. set an NxN matrix TM s.t TM[i,j] = 1/N for each 1<=i,j<=N.
2. for X number of iterations:
3. Draw i1, j1, i2, j2 UAR on [1,...,N].
4. Draw d UAR on (0, min {TM[i1, j1], TM[i2, j2]}).
5. M[i1,j1] <= M[i1,j1] - d;
6. M[i2,j2] <= M[i2,j2] - d;
7. M[i1,j2] <= M[i1,j2] + d;
8. M[i2,j1] <= M[i2,j1] + d;

### Cite As

Itamar Cohen (2021). Fast algorithm for generating doubly-stochasstic matrices (https://www.mathworks.com/matlabcentral/fileexchange/12267-fast-algorithm-for-generating-doubly-stochasstic-matrices), MATLAB Central File Exchange. Retrieved .

##### MATLAB Release Compatibility
Created with R14SP1
Compatible with any release
##### Platform Compatibility
Windows macOS Linux