Approximating a matrix so that 1) all rows sum to one and 2) all values have max 6 digits.

Question

Let consider a big matrix with values ranging from 0 to 1 (included). Each row sums to values that are lower than 1, extremely close to 1 but not exactly 1.

I'd like to make sure that 1) each row sums to 1 and 2) no element has more than 6 digits. The goal is to find a method that minimizes the approximation. We may for example want to minimize the sum of the squared differences between original values of the matrix and the values at the end.

---

Coded in R: let mat be the matrix of interest. I first multiplied each element by the sum of its row to make sure each row sums up to 1

mat = mat / rowSums(mat)

Then, I wanted to make sure than no value has more than 6 digits. So I rounded all values

mat = round(mat,6)

As a result of this last operation, all rows don't sum to exactly 1 anymore! If I were to do the opposite, that is rounding in first place:

mat = round(mat,6)
mat = mat / rowSums(mat)

I would then have values that have more than 6 digits!

What is the most (or one of the most) optimal way to make sure that all rows sum up to 1 and that no values has more than 6 digits with as little approximation as possible?

If needed I welcome people to define "as little approximation as possible" as the technic that minimizes the sum of squared differences between original values of mat and the values at the end.

Answer 1

This is a wonderful problem! It turns out that it is equivalent to a problem in voting theory called apportionment. This has a long and colorful history, with high stakes riding on every twist and turn. The short answer is: there is no unique "best" answer, but there are many good answers.

Consider a single row of the matrix, scaled to sum to 1 but not rounded. Suppose for the sake of argument that there are 50 columns. This corresponds to 50 states in the U.S. Together, there needs to be exactly five million representatives in the House of Representatives. (note: in real life, 435). The values in our row represent the fraction of the total U.S. population living in each state. In an ideal world, we could just multiply all the fractions by 100,000, and the result would be the number of representatives that state gets. 100,000 per state on average, 50 states, five million total representatives.

However the results after multiplying by 100,000 are not integers, and we require an integer number of representatives. Hence we need to do some rounding, but with the added restriction that the total is five million on the nose. Which way do we round? Always round to the closest integer? Well that won't always give five million (what you discovered).

My suggestion, as a simple answer, is this. Round all entries down. This will give a total that is less than five million. Then, subtract the rounded entries from the original row. This will give each row a new number less than 1. Sort the entries from high to low, i.e. from most deserving of being rounded up to least deserving. Then award an extra representative to just enough of the top of the list, to make the total exactly five million.

In the context of the original problem, let $r$ be a row of the original matrix, and $r_f$ be the row of the floor of $r$, to 6 decimal places, in each entry. Add up the entries of $r_f$, subtract from $1$, and multiply by $10^6$. Call this $n$. $n$ is how many entries need to be rounded up instead of down. Set $r_d-=r-r_f$. Find the indices of the $n$ largest entries of $r_d$, and add $10^{-6}$ to those indices in $r_f$. This is your desired row.