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?