Finding the least squares solution to a matrix with some constraints. I am currently attempting to solve a coding challenge using linear algebra. I have just finished a course on linear algebra and am unsure whether what I am attempting to do is within the realm of linear algebra, but have given it a go.
I am working with an $m\times n$ matrix with integer entries, e.g.
$
\begin{pmatrix}
1 & 4 & 2 & 5\\
5 & 3 & 1 & 5
\end{pmatrix}
$
.
Each row has a mean $\mu_i$, and each entry has an error $e_{i,j}$ that is the difference between the mean of the entry's row and the entry itself $x_{i,j}$. $$ \sum^{i} \sum^j e_{i,j}^2 = \sum^{i} \sum^j (\mu_i - x_{i,j})^2 $$ represents the total sum of squares.
I am attempting to find a matrix consisting of only integers with the lowest possible sum of squares, such that the sum of each column and the sum of each row is the same as they were in the original matrix.
I have tried using the formula I learnt for computing the least squares solution (for $Ax = b, \hat{x} = (A^TA)^{-1}Ab$), however I was unable to apply this.
Extra example:
$$
\text{Before}\\
\begin{pmatrix}
3 & 7\\
6 & 3
\end{pmatrix}
\begin{array}\\
\mu_1 = 5\\
\mu_2 = 4.5
\end{array}\\
\sum^i \sum^j e_{i,j}^2 = 12.5\\
$$
$$
\text{After}\\
\begin{pmatrix}
5 & 5\\
4 & 5
\end{pmatrix}\\
\sum^i \sum^j e_{i,j}^2 = \frac{1}{2}\\
$$
 A: Without the integer constraint, this is indeed a least squares problem, but of a different kind than you are probably used to. We can solve it as follows:
Let $v_X$ denote the vectorized version of your matrix $X$. For instance, in the $2 \times 4$ case, $v_X$ is the column-vector $v_X = (x_{11},x_{21},x_{12},\dots,x_{24})$.   Let $R_i$ denote the sum of of the $i$th row of the original matrix, and let $C_j$ denote the sum of the $j$th column. Let $e$ denote the column-vector of ones, $e = (1,\dots,1)$.
With the properties of vectorization noted in the linked page, we find that the constraints on the row and column sums can be written as the equation $Pv_X = s$, where
$$
Q = \pmatrix{I_{n \times n} \otimes e^T\\e^T \otimes I_{m \times m}} , \quad s = (R_1,\dots,R_m,C_1,\dots,C_n),
$$
and $\otimes$ denotes a Kronecker product. On the other hand, let $M$ denote the matrix whose columns are all of the form $(\mu_1,\dots,\mu_m)$.  We can write the optimization problem at hand as follows:
$$
\min_{v_X} \|v_X - v_M\| \quad \text{such that } \quad Qv_X = s
$$
Now, let's make the substitution $w = v_X - v_M$. We note that
$$
Qv_X = s \implies Q(v_M + w) = s \implies Qw = s - Qv_M
$$
The optimization problem now reads
$$
\min_{w} \|w\| \quad \text{such that } \quad Qw = (s - Qv_M).
$$
Now, this is an application of "least squares" that you're probably not used to: rather than selecting a solution to an overdetermined system by minimizing the (least squares) size of the error of the output, we select a solution to an underdetermined system by minimizing the size of the the input!
Long story short: the answer to this question will be $w = Q^+(s - Qv_M)$, where $Q^+$ denotes the Moore-Penrose pseudoinverse of $A$.
Good online explanations are hard to come by, but you might find these notes to be helpful.
