Rotating a matrix cannot be done with matrix multiplication

Note that this is different from rotation matrices in our previous discussion on transformation matrices. We were rotating (3D) objects and vertices (points) then. We’re talking about rotating a matrix here.

I read this article by Raymond Chen discussing the rotation of a 2 dimensional array (which is equivalent to a matrix in our case). In it, he stated:

The punch line for people who actually know matrix algebra: Matrix multiplication doesn’t solve the problem anyway.

Yeah, I’m one of those people.

I’ve never quite thought about it before, so I decided to explore it further. Why can’t matrix multiplication be used?

Before we go into that, let’s look at a reference link in the above article from which this whole topic came about. In it, Chris Williams (the author) gave some code for rotating a matrix. I’m not sure what he referred to by “left” and “right” turn because I feel it’s a bit ambiguous.

Duty calls by XKCD

Anyway, the code on the left turn is wrong. This is what’s given:

' For LEFT turns

For Y = 0 to 3

    For X = 0 to 3

        Destination(Y,X) = Source(X,Y)

    Next

Next

That is the algorithm for transposing a matrix.

He also gave code for the “right” turns, which is correct. I prefer to have “messy” indices on the right side of the assignment. To each his own…

Anyway, here’s what I came up with:

const int cnSize = 4;
int[,] Source = new int[cnSize, cnSize];
int[,] Destination = new int[cnSize, cnSize];
int i, j;

Console.WriteLine("Source matrix:");
for (i = 0; i < cnSize; ++i)
{
    for (j = 0; j < cnSize; ++j)
    {
        Source[i, j] = i * cnSize + (j + 1);
        Console.Write("{0:d2} ", Source[i, j]);
        Destination[i, j] = -1;
    }
    Console.WriteLine();
}
Console.WriteLine();

Console.WriteLine("Using given 'clockwise turn' formula");
// given left turn
for (j = 0; j < cnSize; ++j)
{
    for (i = 0; i < cnSize; ++i)
    {
        Destination[j, i] = Source[i, j];
    }
}
for (i = 0; i < cnSize; ++i)
{
    for (j = 0; j < cnSize; ++j)
    {
        Console.Write("{0:d2} ", Destination[i, j]);
    }
    Console.WriteLine();
}
Console.WriteLine();

Console.WriteLine("Using corrected 'clockwise turn' formula");
// correct given left turn
for (j = 0; j < cnSize; ++j)
{
    for (i = 0; i < cnSize; ++i)
    {
        Destination[j, cnSize - 1 - i] = Source[i, j];
    }
}
for (i = 0; i < cnSize; ++i)
{
    for (j = 0; j < cnSize; ++j)
    {
        Console.Write("{0:d2} ", Destination[i, j]);
    }
    Console.WriteLine();
}
Console.WriteLine();

Console.WriteLine("Using given 'anticlockwise turn' formula");
// given right turn
for (j = 0; j < cnSize; ++j)
{
    for (i = 0; i < cnSize; ++i)
    {
        Destination[cnSize - 1 - j, i] = Source[i, j];
    }
}
for (i = 0; i < cnSize; ++i)
{
    for (j = 0; j < cnSize; ++j)
    {
        Console.Write("{0:d2} ", Destination[i, j]);
    }
    Console.WriteLine();
}
Console.WriteLine();

Console.WriteLine("End of program");
Console.ReadLine();

I said you'd have to get used to nested for loops, didn't I? *smile* The output looks like this:

Rotating a matrix

Ok, back to the issue at hand. Let me phrase the question as "Is there a general transformation matrix that rotates a square matrix with size N (N > 1) clockwise?" I'm going to try answering that question using proof by contradiction.

Suppose there is such a transformation matrix. Without loss of generality, we'll assume N to be 2. So there is a 2 by 2 matrix A such that

[ A(0,0)  A(0,1) ]  [ a  b ]  =  [ c  a ]
[ A(1,0)  A(1,1) ]  [ c  d ]     [ d  b ]

Let's look at the top left and top right entries of the resulting matrix, which gives us two simultaneous equations:
A(0,0)a + A(0,1)c = c
A(0,0)b + A(0,1)d = a

Taking the 1st equation, we have
A(0,0)a = c - A(0,1)c

Dividing both sides by a, we have
A(0,0) = (c/a) * (1 - A(0,1))

You might find this ok, but take a look at the (c/a) part. This assumes that a is non-zero. Think about that. Our general transformation matrix assumes that the top left entry "a" to be rotated is non-zero. Hmm... Let's continue for a bit.

Substituting the value of A(0,0) into the 2nd equation, we have
b*(c/a)*(1 - A(0,1)) + A(0,1)d = a

Do the algebraic simplifications, and we'll get this
A(0,1) = (a^2 - bc) / (da - bc)

Take a look at the denominator. This assumes that (da - bc) is non-zero. If you have some knowledge of matrices, this is the determinant of the matrix.

So, our general transformation matrix assumes that the top left entry is non-zero and the determinant of the 2 by 2 matrix to be rotated is non-zero. Do you see problems yet? And we're not even looking at the other 2 simultaneous equations yet...

We have arrived at a contradiction. Our "general" transformation matrix isn't general at all. There are hidden assumptions. This means there's no such general transformation matrix for rotating a matrix.

Q.E.D.

I feel my proof given above is kinda weak. Maybe you can come up with a stronger proof?

Comments

  1. Shorter proof:

    [ A(0,0) A(0,1) ] [ 1 0 ] = [ 0 1 ]
    [ A(1,0) A(1,1) ] [ 0 1 ] [ 1 0 ]

    Therefore, A =

    [ 0 1 ]
    [ 1 0 ]

    but this doesn’t work for the matrix

    [ 0 1 ] [ 2 0 ] != [ 0 2 ]
    [ 1 0 ] [ 0 1 ] != [ 1 0 ]

  2. Vincent Tan says:

    Raymond – I was never much of a student of empirical proofs… Fondness of elaborate math arguments have blinded me!

    Matthew – Thank you for sharing your proof. Much more refined than mine. Can’t believe I went into simultaneous equations and such…

  3. I do think (but haven’t proved to myself) that you should be able to do this with something like a similarity transform with “permutation-like” matrices (despite the fact that neither will be square and it may not follow all the rules of a permutation)

  4. Rhttp://www.theonion.com/content/news_in_photos/a_long_elaborate_history says:

    Raymond Chen revived this thread on his blog, so I just got here, over a year too late.

    In any case, look at the second equation you wrote: A(0,0)b + A(0,1)d = a. This means that our matrix A generates a from b and d, “withoug even knowing” what a was in the first place. In other words, even if we change a (the top-left element of our original matrix), the top-right element of the rotated matrix will not change.

    Here’s a more formal way of looking at it, that generalizes to N*N matrices: Suppose we have our original matrix A, and the “operation matrix” O (which we’d like to be a “rotation matrix”). Write OA=B. Then, assuming O is constant, B[N,1] doesn’t depend on A[1,1] at all: B[N,1] is the result of multiplying the first row of O by the LAST COLUMN of A.

  5. Sorry, I don’t know how that Onion link got accidentally pasted instead of my name…

  6. Hi Roie, your analysis is sound.

    And the Onion link’s fine… ooh Egyptians fail terribly at constructing monumental cubes… :)

Trackbacks

  1. [...] do I mean by messy indices on the right? Variable assignment. I mentioned something of this in the matrix rotation article, and I want to talk more on it here. And I will tell you why I prefer them on the right side of the [...]