How to find a matrix such that each row and col sums to 1

Question

I'm interested in finding a "soft" permutation matrix relating two equal sized sets $\{a_1, \dots, a_n\}$ and $\{b_1, \dots, b_n\}$. I have a distance function $d(a_i, b_j)$, so I can construct a distance matrix $D$ such that $D_{ij} = d(a_i, b_j)$. However, the rows and columns of $D$ do not sum to one, and the elements of $D$ may not be within $[0, 1]$.

How can I find a matrix where the relative distances are preserved, but the rows and columns sum to one, and each element is within $[0,1]$?

Answer 1

Assuming you want to start with some general matrix and end up with one that preserves some of the structure of the initial matrix but also meets your requirements, you can apply iterative proportional fitting to get what you want:

1. Calculate the row sums $R_i$ and scale each element in a row by that value, i.e. $M_{ij} \rightarrow \frac{1}{R_i} M_{ij}$.

2. Calculate the column sums $C_j$ and scale each element in a column by that value, i.e. $M_{ij} \rightarrow \frac{1}{C_j} M_{ij}$.

3. Repeat steps 1 & 2 until the matrix is no longer changing much in each iteration.

There are more complicated methods, but IPF should give you reasonable results a lot of the time.

Answer 2

A direct approach would be to start from any non-singular matrix $A$, and orthogonalize it using the well-known Gram-Schmidt orthogonalization method (which is straight forward, and easy to code).

Then the elements of the sought matrix are just the square of the elements of the orthogonal matrix obtained above.

This way the sum of any column and any row will be $1$, and all the entries are in the range $[0, 1]$.