Algorithm for finding a permutation matrix of a matrix

Question

I see some similar questions:

• Generate permutation matrix from permutation vector
• https://math.stackexchange.com/questions/345166/what-is-the-name-for-a-non-square-permutation-matrix

Given elements:

elems =  [1,2,3,4] # dimensions 1x4

If I have a vector:

M = [4,2,3,1] # dimensions 1x4

I know there is some permutation matrix p that I can multiply elems * p = M, which in this case would be:

p = 
[ 
  0 0 0 1
  0 1 0 0 
  0 0 1 0 
  1 0 0 0 
] # dimensions 4x4

# eg: 
# elems * P = M
  1x4   4x4 = 1x4

Now, for my question, I am interested in what it would look like in the case when M is a non-vector, non-square matrix, like:

M' = [ 
  4 2 3 1 
  4 3 2 1
  1 2 3 4
] # dimensions 3x4

For the same

elems' = [
 1 2 3 4
 1 2 3 4
 1 2 3 4
] # where this is now tripled to be conformant dimensions
# dimensions 3x4
#
# meaning P is still 4x4

You can see M_prime and elems_prime in this case are still just permutations, but now multivariate, rather than just a single vector as originally.

I know I am not able to just do the following kind of thing, because the matrix is not square, and thus not invertible:

elems' * P = M'
         P = elems'^-1 * M'

# eg: 
# elems' * P = M'
  3x4   4x4  = 3x4

When I try, in R at least, I see:

> P <- ginv(elems_prime) %*% M_prime
     [,1]       [,2]       [,3]       [,4]
[1,]  0.1 0.07777778 0.08888889 0.06666667
[2,]  0.2 0.15555556 0.17777778 0.13333333
[3,]  0.3 0.23333333 0.26666667 0.20000000
[4,]  0.4 0.31111111 0.35555556 0.26666667

Does this give me back M'?

> elems_prime %*% P
     [,1]     [,2]     [,3] [,4]
[1,]    3 2.333333 2.666667    2
[2,]    3 2.333333 2.666667    2
[3,]    3 2.333333 2.666667    2

!= M' # No, does not.

So this is not right.

My questions are:

1. What is the right P that would correctly permute the elems' matrix into the M' matrix?
2. What is the name of the algorithm to find it? (implementation in R, Haskell, or pseudocode is great)
3. Is there a way to restrict the values of P to be integers, preferably 0 or 1?

for R reproducibility

> dput(elems_prime)
structure(c(1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4), .Dim = 3:4)
> dput(M_prime)
structure(c(4, 4, 1, 2, 3, 2, 3, 2, 3, 1, 1, 4), .Dim = 3:4)

Answer 1

Notice that column space of M' is of higher order than the column space of elem'. This implies that there does not exist a linear mapping from elem' to M' because a linear mapping cannot increase the row or column space of a matrix (useful to think about this as a transformation of basis).

It follows that the any M' generated by elem' * P can have rank of at most 1, leaving only the conventional permutation matrices as candidates for P'

It is an entirely different question if we look at going from M' back to elem, and this asymmetry is also noteworthy.