[igraph] Finding stochastic submatrices

[Moses Boudourides]

Hello,

I was wondering if you know an algorithm which selects stochastic
submatrices from an arbitrary binary matrix.

Actually my problem is the following: Say I have a binary nxm matrix A
= {Aij}, where Aij = 1 or 0, for all i = 1, ..., n and j = 1, ..., m.
Then I'd like to find a subset, say, I of {1, 2, ..., n} and a subset,
say, J of {1, 2, ..., m} such that the matrix B = {Aij} formed by
restricting i \in I and j \in J has all the sums of its rows and the
sums of its columns equal to 1. (For a square matrix, this is called
stochastic, but I keep the same name, although my case could be
non-square.)

Any suggestions how to do this in Python or R igraph?

Best,

--Moses