Can we solve for perm. matrix P in: aP = b? Where a and b are row vectors.

Question

Can we solve $\boldsymbol{aP} = \boldsymbol{b}$ where $\boldsymbol{a}$ and $\boldsymbol{b}$ are each $1 \times n$ row vectors and are known, and $\boldsymbol{P}$ is an $n \times n$ permutation matrix that is unknown?

Answer 1

No, It is not possible in general.

Consider $P=\begin{bmatrix}a&b\\c&d\end{bmatrix}$

$a=(1,1)$ and $b=(2,2)$

Now solving $$a{P}=b$$ amounts to solving the following equation $$a+c=2$$ $$b+d=2$$

That means $a+b+c+d=4$.

This is a contradiction as by definition a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere.

So sum of all entries of a $n\times n$ permutation matrix is $n$.

So for a $2\times 2$ Permutation matrix sum of all entries is equal to $2$.