## Questioning assumptions

With the explosion of information due to the Internet, we should be more wary of the trustworthiness of the source, and even the veracity of the information. I also tell you about the Barber Paradox and a brief explanation of “proof by contradiction”.

## 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");
```

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?