Re-allocating cells in rows in columns to equal given row and column sums

Question

Suppose I have a matrix which looks like: $$ \left[\begin{array}{cccc} a_{11} & a_{12} & ... & a_{1n}\\ a_{21}\\ .\\ a_{n1} & & & a_{nn} \end{array}\right] $$ where $a_{ij}$ denotes the value of $a$ in row $i$ and column $j.$ For each row $i,$ I have a given constraint on its sum. So, the sum of the first row should be: $$ \sum_{j}x_{1j}=R_{1} $$ Similarly, we have it for all other $n-1$ rows. Moreover, I have another constraint, which for the first column is: $$ \sum_{i}x_{i1}=C_{1} $$ These also make up a total of $n$ column constraints. So, I have $n$ row constraints and $n$ column constraints in this example. As of now, there is no guarantee that these constraints are being met. Is there any well known algorithm ( a least squares type?) to re-allocate cells in a manner which doesnt change original data much, but still meets the constraints? This could take the form of, say: $$ \text{min}\sum_{ij}\left(a_{ij}-\epsilon\right)^{2} $$ s.t. the $2N$ row and column constraints? Is there a closed form solution for this? Many thanks!

Answer 1

This is called matrix balancing and can be solved via iterative proportional fitting.

See Schneider and Zenios, A Comparative Study of Algorithms for Matrix Balancing, Operations Research 38 (1990).

Here are two informative blog posts:

• https://blogs.sas.com/content/iml/2020/09/08/matrix-balancing.html
• https://blogs.sas.com/content/iml/2020/09/10/iterative-proportional-fitting-sas.html