Expert: Paul Klarreich - 6/12/2006

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 column:
4
-3
5
1
And I move it down then it'll become:
1
4
-3
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 :)

Answer
Hi, Nikolay,

You wrote:
Subject:  Matrix state solver
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

column:
4
-3
5
1
And I move it down then it'll become:
1
4
-3
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 :)
--------------------------------
I am not sure exactly what you mean by 'move the columns up and down'.  You seem to be rotating the elements WITHIN the column.  Now do you mean that given a matrix such as the following(which I have deliberately written without any repeated elements):

-5   9   4   13
0    8  10   -7
3    6   1   15
-4  11  -6    5

that you will rotate the elements in a column, to produce:


-4   9   4   13
-5    8  10   -7
0    6   1   15
3  11  -6    5

or will you rotate the entire matrix along with the elements, to produce:

-4  11  -6    5
-5   9   4   13
0    8  10   -7
3    6   1   15

There is a difference, as you can see.  If you rotate all the rows as you rotate the elements, the row, say, that begins with  -4  does not change.

So what kind of problem is this?
A. Some kind of puzzle where you are asked to find a sequence of row and column rotations that changes one matrix into another?  In that case, you have a lot of research to do, because many matrices are not like my example -- they have repeated elements.  Also, I think the answers might not be unique.  If you start with:

...  5  ...  ...
... ... ...  ...
... ... ...  ...
... ... ...  ...

and end up with

... ... ...  ...
... ... ...  ...
... ...  5   ...
... ... ...  ...

you can probably find more than one way to rotate that 5 into the (3,3) position.  This looks like a problem for computer solution.

B. An issue of linear algebra, which is usually connected with using the matrix to solve linear systems.  In this case, rotating the entire matrix is usually what is done, because:

  --- A rotation of the entire row set does not change the solution set.
  --- A rotation of the entire column set will just rotate the variables in the solution set.