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.
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:
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
5 Responses to “Rotating a matrix cannot be done with matrix multiplication”
Leave a Reply
Hi I'm Vincent and am currently an IT Analyst, working mainly with .NET technologies (love C#!). Here, I write about mathematics, programming and any curiosities that flit through my mind (
Twitter
FriendFeed
Facebook
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 ]
Here’s the proof I came up with:
http://blogs.msdn.com/matthew_van_eerde/archive/2008/09/12/rotating-a-matrix-redux.aspx
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…
[...] 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 [...]
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)