How to rotate a matrix by 45 degrees?

Assume you have a 2D matrix.

Ignore the blue squares. The first image represents the initial matrix and the second represents the matrix rotated by 45 degrees.

For example, let's consider a random cell from the first image. a32 (row 3, column 2) Let x be the row and y be the column, so x = 3 and y = 2.

The formula of this rotation is : RM[x + y - 1][n - x + y] = M[x][y], where RM means rotated matrix, M the initial matrix, and n the dimension of the initial matrix (which is n x n).

So, a32, from the third row and second column will get to the fourth row and the fourth column.

The problem is, I don't really understand this forumla. Can you help me? And how do you rotate by 45 degrees a matrix that is not square shaped? (a rectangle shaped one)

Any help is much appreciated. Thank you very much!

Solution 1:

Consider the column and row numbers of a cell to be the coordinates of a point in a Cartesian plane. In your illustration, these could be the coordinates of the center of the cell. You need to transform the coordinates in order to rotate the set of cells in the plane. But your transformation also needs to increase the distance between centers of cells by a factor of $\sqrt{2}$, because as you can see in your figure, instead of moving just one unit right to get from $a_{11}$ to $a_{12}$, now it is one unit right and one unit down. So what you need is not just a rotation; it is a rotation with dilation.

The formula for doing a rotation of angle $\theta$ and dilation by factor $k$ around the point $(0,0)$ is

$$ \left( \begin{array}{c} x \\ y \end{array} \right) \rightarrow k \left( \begin{array}{cc} \cos \theta & \sin \theta \\ -sin\theta & \cos\theta \end{array} \right) \left( \begin{array}{c} x \\ y \end{array} \right). $$

In your case, for a $45$-degree rotation, $\theta$ is either $\pi/4$ or $-\pi/4$ (depending on the direction of rotation) and $k = \sqrt{2}$. It turns out to be $\pi/4$ for what you're doing, but you could figure out which angle is correct by trial and error. So $\sin\theta = \cos\theta = \sqrt{2}/2$, and if you plug all these numbers into the formula and distribute the factor over the $2\times2$ array, you get

$$ \left( \begin{array}{c} x \\ y \end{array} \right) \rightarrow \left( \begin{array}{cc} 1 & 1 \\ -1 & 1 \end{array} \right) \left( \begin{array}{c} x \\ y \end{array} \right) = \left( \begin{array}{c} x + y \\ -x + y \end{array} \right). $$

If you just apply that transformation, it says to copy the contents of cell $M[x][y]$ to the new location $RM[x+y][-x+y]$. This would solve your problem, except that it copies $M[1][1]$ to $RM[0][2]$, which we don't normally consider to be a valid matrix cell. In fact, it copies all the cells below $M[1][1]$ even further to the left: if the original matrix has $n$ rows, this rotation will copy the first column of $M$ to the $n$ “columns” to the left of the first column of $RM$. It also copies all cells to rows numbered $2$ or greater, and you want to put a non-zero cell on row $1$.

To fix these defects in the new array, you need to move everything one row up and $n$ columns to the right, that is, subtract one from the row number and add $n$ to the column number. So instead of $RM[x+y][-x+y]$, you want to copy cell $M[x][y]$ to cell $RM[x+y+1][-x+y+n]$. That's one way to derive your formula.

Or you could observe that the “rotation” of the matrix preserves collinearity and relative distances, so it must be a linear transformation, and work out the coefficients of two linear functions of $x$ and $y$ that move $a_{11}$ and $a_{12}$ where they need to go.

As for what to do with a rectangular matrix, notice the phrase “if the original matrix has $n$ rows” in the text above. The “rotation” formula does not depend on the number of columns; more columns (or fewer) will just cause the new matrix to extend farther (or less far) to the lower right where there are always positive row and column numbers. Just set $n$ in the formula to the number of rows you find in $M$, and you'll be OK.

Solution 2:

Let me explain it in my words.First of all, that is not exactly the mathematical definition of rotation, it is looking more like an image processing operator with predefined pixels position (matrix cells). We have to define a couple of thinks:

• the center of rotation: let say it the the cell of indexes ic and jc (for center). It happens to be the exact middle cell in the example, thanks to the odd size of the square matrix. It wont be the same for even sized matrix, and will get a little more tricky for rectangular matrix. Let us not think about angle not multiple of 45 degrees.

• position relative to the center of rotation: Let's add new indexes that define the offset with respect to the center of rotation; for the cell (i,j), this offset is (i-ic, j-jc).

Now, if you think about it, you will find that for a 45 degrees rotation, rows above the center (row with index i less than ic) shift to the right by (ic-i) cells. For rows bellows ic (i>ic) they shift to the left by (i-ic) cells. A general formula for the shift is simply -(i-ic) with right shift for positive number and left shift for negative. This is a shift in column, so an offset in rows induces a shift in column.

for columns we will have something similar, an offset in column will induce shift in rows. The shift in this case is (j-jc), no negative sign. Now, positive shift means shift down and negative means shift up.

Now, let suppose that we can guess the position of the rotated center irc, jrc, the offset of cell (i,j) in the rotated matrix is simply:

• ir - irc = i - ic + (j-jc) = i + j - (ic + jc)
• jr - jrc = j - jc - (i-ic) = j - i + (ic - jc)

So you get

• ir = i + j + irc - (ic + jc)
• jr = j - i + jrc + (ic - jc)

It is simple to determine the position of the center, it is the position that guarantees the min col is 1 and the min row is 1 (in one based indexation).

It is easy to check that the formula hold for your example. n = 2k+1 and ic = jc = k+1.