Find the affine transformation to minimize the distance between two sets of points Definition: Let $A=\{a_1,\cdots,a_n\}$ and $B=\{b_1,\cdots,b_n\}$ two sets with the same cardinality. Then define the distance between two sets as $$d(A,B):=\min_{\sigma}\sum_i||a_i-b_{\sigma(i)}||,\text{where }\sigma \text{ is a bijection from }\{1,2,\cdots, n\} \text{ to itself}.$$
Problem: Given two sets of points $A$ and $B$ in the Euclidean space with the same cardinality, find the affine transformation ${\bf M}$ such that distance between the sets ${\bf M}(A)$ and $B$ is minimized, where ${\bf M}(A) = \{{\bf M} {\bf p}:{\bf p}\in A\}$.
 A: Here are cases when we can achieve a distance of 0 (which must be the min distance). Fix $n, m, k$ as positive integers.  We have vectors $\{a_1, \ldots, a_n\}$ and $\{b_1, \ldots, b_n\}$ that satisfy
\begin{align*}
&a_i \in \mathbb{R}^m \quad \forall i \in \{1, \ldots, n\}\\
&b_i \in \mathbb{R}^k \quad \forall i \in \{1, \ldots, n\}
\end{align*}
Case 1: $\{a_1, ..., a_n\}$ are linearly independent.
Suppose $\{a_1, ..., a_n\}$ are linearly independent. Then we can construct a $k \times m$ matrix $C$ that satisfies $Ca_i = b_i$ for each $i \in \{1, ..., n\}$ and so $dist(\{C a_i\}_{i=1}^n, \{b_i\}_{i=1}^n)=0$.
Case 2: $\{(a_1;1),..., (a_n;1)\}$ are linearly independent.
For each vector $a_i \in \mathbb{R}^m$ we can create a vector $(a_i;1)\in \mathbb{R}^{m+1}$ by appending a final component of $1$. Suppose $\{(a_1;1), ..., (a_n;1)\}$ are linearly independent. Then we can construct a $k \times (m+1)$ matrix $C$ that satisfies
$$ C(a_i;1) = b_i \quad \forall i \in \{1, \ldots, n\}$$
Let $L$ be the last column of matrix $C$, so that $C=[D : L]$ where $D \sim k \times m$. Then
$$ C(a_i;1) = Da_i + L$$
Consider the affine mapping $M:\mathbb{R}^m\rightarrow\mathbb{R}^k$ by
$$ M(x) = Dx + L$$
Then $M(a_i) = Da_i+L = C(a_i;1) = b_i$ for all $i \in \{1, .., n\}$ and so $dist(\{M(a_1), ..., M(a_n)\}, \{b_1, ..,. b_n\})=0$.
