Nov 23 2018
How do you rotate a square matrix counter-clockwise? That's easy enough: you map the cell located at to the cell located at , where is the length of a side of the square matrix.
Today I stumbled across another way to do this. The idea is to flatten the matrix out and derive a linear map between the 1D indices of the flattened matrix and the 1D indices of the flattened rotated matrix. The relation is . That is, given an index into the flattened version of the original matrix, the corresponding index in the flattened version of the rotated matrix will be .
The index is an integer between and , because it is an index into the flattening of a square matrix of side . In fact, . Intuitively, we make r jumps of stride n, and then offset ourselves by c to get to the cell located at . Note that and are integers lying in .
How do we derive the relation ? By trial and error. My starting point was to take a 4x4 matrix and rotate it to the left, and to observe that there was an even spacing between the values of the 1D indices in the output - and that that spacing was equal to itself. It was natural to guess that there was a modulo involved, but that failed very quickly. I then tried , and it worked!
Why does this work? The derivation is straightforward. We relate 2D coordinates in a square matrix to the index of the corresponding cell in the flattened version: . We already know how to map 2D coordinates between matrices when one is a left-rotation of the other. So we just need to derive a relation between the 1D indices, and we're done.
The second line above comes from the formula for mapping a 2D coordinate to a 1D one in the flattened array. Here the coordinate is , which is where goes after we rotate the matrix.
...and we're done.