Generating Conditional Random Matrices

Question

How we can generate a matrix with columns and rows with the sum of 1.

import numpy as np
import random
class city:

    def  __init__(self):
        self.distance()

    def  distance(self):
        self.A = np.array([[ 0,  10,    20,  30],[10,   0,    25,  20],[20,  25,      0,  15],[30,  20,    15,   0]])
        self.B =(np.random.randint(0, self.A.shape[0], size=self.A.shape[0]) == np.arange(self.A.shape[0]).reshape(-1, 1)).astype(int)
        return self.B

Answer 1

As far as I can tell, you want a generator for random doubly stochastic matrices (DSM).

If you don't need any additional properties for the distribution of the generated matrices, the algorithm of choice still seems to be Sinkhorn-Knopp. Here, we alternatingly rescale row and columns so that the values conform to the sum criterion:

def gen_doubly_stochastic(size, max_error=None):
    if max_error is None:
        max_error = 1024 * np.finfo(float).eps

    m = np.matrix(np.random.random((size, size)))
    error = float('Inf')
    while error > max_error:
        m = np.divide(m, m.sum(axis=0), order='C')
        m = np.divide(m, m.sum(axis=1), order='K')

        error = max(
            np.max(np.abs(1 - m.sum(axis=0))),
            np.max(np.abs(1 - m.sum(axis=1)))
        )
    return m

Following the original paper, the iteration converges pretty rapidly towards an approximated solution.

Alternatively, one can make use of the property that any n x n DSM can be expressed as a linear combination of n random permutation matrices (see e.g. Is there a better way to randomly generate a Doubly Stochastic Matrix), with the sum of the linear coefficients summing up to 1:

def gen_doubly_stochastic_permute(size):
    m = np.zeros((size, size))
    I = np.identity(size)

    # n random coefficients
    coeffs = np.random.random(size)
    # enforce coefficient sum == 1
    coeffs /= np.sum(coeffs)

    # index array for identity permutation
    values = np.array(range(0, size))
    for c in coeffs:
        # generate new random permutation in place
        np.random.shuffle(values)
        # add scaled permutation matrix
        m += c * I[values, :]
    return m