CODEWITHSUNDEEP
ralgorithmmatrixpermutation
Mittenchops
Mittenchops

Reputation: 19664

Algorithm for finding a permutation matrix of a matrix

I see some similar questions:

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)

Upvotes: 5

Views: 1560

Answers (2)

Jared Goguen
Jared Goguen

Reputation: 9010

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.

Upvotes: 1

btilly
btilly

Reputation: 46409

When M is not a vector, this is not possible.

Here is why. In general if we multiple a nxm matrix times a mxp matrix we get a nxp matrix. Here elems is a vector that is a 1x4 matrix, so elems * P has to be a 1x? matrix of some sort. By making P longer, you can make M longer, but you'd have to change elems to make M taller.

Incidentally in linear algebra it is standard to flip vectors to be columns and put the matrices on their left. The reason for that is that the matrix represents a linear function, and that puts the matrix in the same place where the linear function goes. So it is very nice when going from functional notation to matrix notation. Also if you've got to write a square matrix anyways, it takes less room on the page to write a vertical vector on the right rather than a horizontal one on the left...

Upvotes: 0

Related Questions