Given $d_{ij}\in\mathbb{R}$, $1\leq i<j\leq n$, I'm considering the problem of finding $a\in\mathbb{R}^n$ such that $a_1=0$ and $$ a_i-a_j\approx d_{ij}. $$ I need to formulate this problem as a least square problem, in the context of linear systems.
The way i'm thinking is like that:
Defining $E_{ij}$ as the column matrix with all entrys $0$, except $1$ at the row $i$ and $-1$ at the row $j$, we have that $$ E_{ij}^Ta=d_{ij}. $$ So, we have $$ \begin{bmatrix} E_{12}^T \\ E_{13}^T \\ \vdots \\ E_{1n}^T \end{bmatrix} a= \begin{bmatrix} d_{12} \\ d_{13} \\ \vdots \\ d_{1n} \end{bmatrix}. $$ In general, for every $1\leq k < n$, we have a system of $n-k$ equations: $$ \begin{bmatrix} E_{k\,k+1}^T \\ E_{k\,k+2}^T \\ \vdots \\ E_{kn}^T \end{bmatrix} a= \begin{bmatrix} d_{k\,k+1} \\ d_{k\,k+2} \\ \vdots \\ d_{kn} \end{bmatrix}. $$ So, there are $n-1$ systems of equations for $a$. How exactly can I use least squares to find the best estimative for $a$?
There's a nice way to formulate this problem using vectorization and the Kronecker product. If $D$ denotes the matrix with entries $d_{ij}$ and $e$ denotes the vector $(1,\dots,1) \in \Bbb R^n$, then the desired outcome can be written as $$ ae^T - ea^T \approx D. $$ Using the properties of vectorization, we can write $$ \operatorname{vec}(ae^T - ea^T) = (e\otimes I_n - I_n \otimes e)a, $$ where vec denotes column-major vectorization (as in the wiki page), $\otimes$ denotes a Kronecker product, and $I_n$ denotes the identity matrix. With that, you are looking for a least squares solution to the equation $Ma = \operatorname{vec}(D)$ , where $M = e \otimes I_n - I_n \otimes e$.
Notably, $M$ does not have linearly independent columns. One convenient approach is to use the Moore Penrose pseudoinverse to get the least squares solution $a = M^+\operatorname{vec}(D)$.
You have found that $$ M^TM = (2n I_n - ee^T). $$ This matrix is positive semidefinite with eigenvalue $0$ of multiplicity $1$ and $2n$ of multiplicity $n-1$. It follows that its pseudoinverse is given by $(M^TM)^+ = \frac 1{(2n)^2}M^TM$. Thus, we have $$ M^+ = (M^TM)^+M^T = \frac{M^TMM^T}{4n^2}, $$ which we can plug into $a = M^+ \operatorname{vec}(D)$.