Finding the Closest Permutation Matrix Given Two Vectors

Question

You are given two vectors $\vec{a},\vec{b} \in \mathbb{R}^{n}$. Is there a method to find a permutation matrix $M \in \mathbb{R}^{n\times n}$ such that $M\vec{a}=\vec{b}$? Let us break this down into two cases:

1. The vectors are indeed related by a permutation of their elements, such that: $\vec{b} = M \vec{a}$. In fact, it is possible that there are many permutation matrices which satisfy this equation. For example, let $\vec{a}=(3,1,0,0)^\top$ and $\vec{b}=(0,3,1,0)^\top$, then we would like something of the form of the "shift matrix": $$ M_1 = \begin{bmatrix} 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ \end{bmatrix}. $$ Although it is indeed also possible that $$ M_2 = \begin{bmatrix} 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ \end{bmatrix} $$ as we only have information about the images of the first two basis vectors. Is there a general algorithm that provides the "solution set" to this type of problem?
2. Now for the real problem I would like to solve. There is no permutation matrix $M$ such that $\vec{b} \not = M \vec{a}$. We wish to find an $M$ nonetheless, by finding the "closest" such permutation matrix: $\operatorname*{argmin}_M ||\vec{b}-M\vec{a}||$.

Any tips or insights would be greatly appreciated.

Answer 1

For the first question: If $\vec a=(a_1,\ldots,a_n)$ and $\vec b=(b_1,\ldots,b_n)$, we need to find the image of every basis vector $\vec e_i$. For $\vec e_1$, you can pick any $j$ with $b_j=a_1$ and then map $\vec e_1\mapsto \vec e_j$ (i.e., $M\vec e_1=\vec e_j$, i.e., the $(j,1)$ entry of $M$ is $1$, or the value of the desired permutation $\pi$ evaluated at $1$ is $\pi(1)=j$). Continue with this method, but avoid repetition, i.e., when looking for $M\vec e_i$, pick any $j$ with $b_j=a_i$, but only among those indices you haven't picked yet.

For the second question: We mainly have to decide which value in $\vec a$ to associate with which value in $\vec b$. And then, in case of repeated values on either side, their corresponding indices may be permuted at will. First let us find one such association that is optimal.

Claim. If permutation $\pi$ minimizes $f(\pi):=\sum_i(a_i-b_{\pi(i)})^2$, then there exists a permutation $\sigma$ such that $$\tag1a_{\sigma(1)}\le a_{\sigma(2)}\le\ldots\le a_{\sigma(n)}$$ and $$\tag2b_{\pi(\sigma(1))}\le b_{\pi(\sigma(2))}\le\ldots\le a_{\pi(\sigma(n))}$$

Proof. There are certainly sorting permutaions $\sigma$ that guarantee $(1)$. But for each such $\sigma$, there may exist indices $\ell$ with $b_{\pi(\sigma(\ell))}>b_{\pi(\sigma(\ell+1))}$ (whereas of course $a_{\sigma(\ell)}\ge a_{\sigma(\ell+1)}$). Among all $\sigma$ with $(1)$, consider one that minimzes the number of such bad indices $\ell$. If no suc $\ell $ exists, w are done. So assume otherwise. Let $j=\sigma(\ell)$, $k=\sigma(\ell+1)$, $\pi'=\pi\circ (j\;k)$. Then $$\begin{align} f(\pi')-f(\pi)&=(a_j-b_{\pi'(j)})^2+(a_k-b_{\pi'(k)})^2-(a_j-b_{\pi(j)})^2-(a_k-b_{\pi(k)})^2\\ &=(a_j-b_{\pi(k)})^2+(a_k-b_{\pi(j)})^2-(a_j-b_{\pi(j)})^2-(a_k-b_{\pi(k)})^2\\ &=-2a_jb_{\pi(k)}-2a_kb_{\pi(j)}+2a_jb_{\pi(j)}+2a_kb_{\pi(k)}\\ &=2(a_j-a_k)(b_{\pi(j)}-b_{\pi(k)})\\ &\le 0\end{align}$$ with equality iff $a_j=a_k$. By minimality of $f(\pi)$, we conclude that $a_j=a_k$. But them $\sigma':=(j\;k)\circ \sigma$ is a permutation that sorts $\vec a$ and has one less bad index than $\sigma$, contradicting our choice of $\sigma$. Hence the claim follows. $\square$

Now to find all optimal permutatons, you may permute arbitrarily among indices where components of $\vec a$ are the same, or similarly for components of $\vec b$. Note that considering only permutations among the components of $\vec a$ or only permutations among the components of $\vec b$ will not necessarily give you all optimal solutions. On the other hand, permuting both with $ßvec a$ and within $\vec b$ may count some solutions repeatedly, namely when ranges of equal value "overlap" in the sorted order of the components of $\vec a$ resp $\vec b$.