Matrix match?

Question

I have the following problem: I have a matrix (NxM) with random
integers. I can move the columns up and down. For example if I have the
following matrix and move down the first column:
-5 9 4 13
0 8 10 -7
3 6 1 15
-4 11 -6 5
then it'll become:
-4 9 4 13
-5 8 10 -7
0 6 1 15
3 11 -6 5
By analogy we do the same for the up movement.

We can also move the rows left and right:
3 -4 2 3 - becomes:
3 3 -4 2

I have another matrix which is a result from the first matrix and up,
down, left and right movements.

The problem is if I have the first matrix and the result matrix how to
find the movements?

Excuse my bad english :)

1. The movements I've described are the only allowed to be applied over the matrixes;
2. I know that there might be a lot of solutions to the problem - there might be different ways to transform from the starting matrix to the result one - I just need a solution (if someone can think of the optimal one - with least number of moves, I'll be very glad)

Answer 1

Sorry cant help

Answer 2

I think you will find no regular method for this matter, since the transform you explained (movements) is of non-linear type and therefore there is no systematic rule to make a reverse transform to get the origin matrix. Also note that there is no relation between your numbers (they could be identical) and therefore any solution for this matter may have several ways, which is completely based on trial & error method.
If there exist a 2-dimensional relation between matrix members then you may find some very complicated solutions in "DSP" theory books that may lead you to the answer (or its nearsome). I neither say I know them, nor can help more, and as I told this might be done provided that a 2-D relationship exists (like illumination relationship between pixels of a photograph).

Answer 3

u only mentioned b elementary row and column transformations. But actually there are many operations that can b applied on matrices.

there can b many ways in which the resultant matrix can b obtained.

its just like roads linking 2 cities. u hav 1 straight path n many other in addition.

also u cannot , just by analysis, decide how a particular matrix was obtained from d initial one. u hav to do this by hit n trial.

Answer 4

What's your resulting matrix? If you list the resulting matrix, I try to find the movements for you. You have to back track and see what has changed in the resulting matrix compared to the original matrix.

Answer 5

I think your problem can be reduced to one of factorizing in a permutation group. I suggest you look at

Egner and Puschel, "Solving Puzzles related to Permutation Groups", in Proceedings of the International Symposium on Symbolic and Algebraic Computation 1998.

http://citeseer.ist.psu.edu/18497.html

and

Minkwitz, "An algorithm for solving the factorization problem in permutation groups", Journal of Symbolic Communication vol. 26, issue 1 (July 1998)

http://www.ingentaconnect.com/content/ap/sy/1998/00000026/00000001/art00202;jsessionid=mjhe4pwlvsw8.alice