Matrix rotation and transpose in Python

Why this matters

Many programs store data in a grid. A picture is a grid of color values. A board game is a grid of squares. A spreadsheet is a grid of cells. Sometimes you need to turn the whole grid a quarter turn, for example to rotate a photo on a phone or to turn a chess-like board so that the player sits on the other side.

The naive way to do this is to build a second grid and copy each value into its new place. That works, but it doubles the memory. This lesson shows a method that rotates a square grid in place. "In place" means the values move inside the same lists, so no second grid is needed.

The method has two steps, and both are simple loops. The first step is called a transpose. The second step reverses each row. Together they give a clockwise rotation.

The previous lessons covered two-dimensional lists and spiral traversal. Copying a jagged grid, where rows have different lengths, is covered in a later lesson. This lesson uses only square grids, where the number of rows equals the number of columns.

The idea: a grid with rows and columns

A matrix is a grid of numbers with rows going across and columns going down. In Python, a matrix is a list of lists. The outer list holds the rows, and each inner list is one row.

Take this grid:

1 2 3
4 5 6
7 8 9

It has three rows and three columns. The value 6 sits in row 1 and column 2, counting from zero. In code, you write the row first and the column second, so the value 6 is grid[1][2].

Output:

6

The number of rows is len(grid), which is 3. The number of columns is len(grid[0]), which is also 3. A grid is square when these two numbers are equal.

Two words are used in this lesson. A transpose is a flip across the main diagonal, the line of cells from the top left to the bottom right. A rotation turns the whole grid around its center.

What a clockwise turn does to a grid

Before writing code, look at what a quarter turn to the right does. Hold the grid in front of you and turn it so the top edge moves to the right side. In a small 2 by 2 grid, the value in the top left moves to the top right, and the value in the top right moves to the bottom right.

Before        After clockwise turn
1 2           3 1
3 4           4 2

The first column, read from bottom to top, becomes the first row. In the example the first column is 1 then 3. Read it from the bottom up, and you get 3 then 1. That is the first row after the turn.

This rule holds for any square size. The first column of the original, read from the bottom up, is the first row of the result. The second column, read from the bottom up, is the second row of the result. The last column becomes the last row.

Knowing this rule lets you check any result by hand. Pick a value, find its column in the original, and check that it lands in the row with that column's number.

Step one: transpose

A transpose swaps the value at [row][col] with the value at [col][row]. The row number and the column number trade places.

Here is a 3 by 3 example. The value 2 is in row 0 and column 1. After the transpose, it should be in row 1 and column 0. The value 4 is in row 1 and column 0, and it should move to row 0 and column 1. The two values trade places.

Output:

[1, 4, 7]
[2, 5, 8]
[3, 6, 9]

The first row of the result is the first column of the original. The second row is the second column, and the third row is the third column. Rows became columns, which is what the word transpose means.

The loop does the real work. The outer loop i goes through the rows, and the inner loop j starts at i + 1. That start is deliberate. Each swap touches two cells. If the inner loop started at 0, the pair at [1][0] and [0][1] would be swapped twice, once when i is 0 and again when i is 1, and the grid would come back unchanged.

Starting j at i + 1 means each pair is swapped once. The diagonal cells, where the row and column are equal, are never touched, because j never equals i. A value on the diagonal stays where it is, which is correct, since a diagonal value is in the same place after a transpose.

The line m[i][j], m[j][i] = m[j][i], m[i][j] does the swap in one step. Python builds both values on the right side first and then assigns them, so no temporary variable is needed.

The transpose is one step. It does not rotate the grid yet. It flips the grid across the diagonal, so the first row became the first column. A rotation needs one more step.

Step two: reverse each row

After the transpose, row i holds the original column i, read from top to bottom. A clockwise rotation needs that column read from bottom to top. Reversing each row gives exactly that order.

So the full method is: transpose, then reverse every row. The method row.reverse() reverses one list in place, so the loop over the rows is short.

Output:

[7, 4, 1]
[8, 5, 2]
[9, 6, 3]

Check it against the rule from earlier. The first column of the original is 1, 4, 7. Read from the bottom up it is 7, 4, 1, and that is the first row of the result. The third column is 3, 6, 9, and read from the bottom up it is 9, 6, 3, which is the last row. The rule works.

The method reverse_each_row uses row.reverse(), which does the same job as the two-index swap loop from the first lesson of this module. If you want to see the swap version, write a loop with left and right indexes that moves inward, exactly as in the reversal lesson. The result is the same.

Each function is a short loop, and the two together rotate the grid. You can test the pair on any square grid by checking the rule for two or three values.

Worked example: a 2 by 2 grid

The smallest useful case is a 2 by 2 grid. Trace it by hand before you run it.

Start with [[1, 2], [3, 4]]. For a 2 by 2 grid the transpose loop has only one swap. When i is 0, j is 1, so the program swaps [0][1] with [1][0]. The value 2 and the value 3 trade places. The grid becomes [[1, 3], [2, 4]].

Now reverse each row. Row 0 is [1, 3], which becomes [3, 1]. Row 1 is [2, 4], which becomes [4, 2]. The final grid is [[3, 1], [4, 2]].

Output:

[[3, 1], [4, 2]]

This matches the hand trace. The value 1 was in the top left and is now in the top right. The value 4 was in the bottom right and is now in the bottom left. Each value moved a quarter turn.

Worked example: four quarter turns

A full turn is four quarter turns. If you rotate a grid four times, every value should return to where it started. This is a good test, because it checks the whole method on a larger grid, and it is easy to predict the answer.

The next program rotates a 4 by 4 grid four times and prints the grid after each turn.

Output:

after turn 1 :
[13, 9, 5, 1]
[14, 10, 6, 2]
[15, 11, 7, 3]
[16, 12, 8, 4]
after turn 2 :
[16, 15, 14, 13]
[12, 11, 10, 9]
[8, 7, 6, 5]
[4, 3, 2, 1]
after turn 3 :
[4, 8, 12, 16]
[3, 7, 11, 15]
[2, 6, 10, 14]
[1, 5, 9, 13]
after turn 4 :
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 10, 11, 12]
[13, 14, 15, 16]

The last grid equals the first. Each turn moves the top row to the right side, and four turns bring it back to the top. The turns also give a useful check. After one turn, the top row is the original first column read from the bottom up: 13, 9, 5, 1. This matches the rule.

Counter-clockwise rotation

A turn to the left, which is counter-clockwise, is also useful. It can be built from the same loops in the opposite order. First transpose. Then reverse the order of the rows, so the first row becomes the last row.

Reversing the order of rows is different from reversing each row. Reversing the order swaps whole rows. The function below uses the same transpose and then swaps the top and bottom rows, then the second and second-last, and so on.

Output:

[3, 6, 9]
[2, 5, 8]
[1, 4, 7]

Compare this with the clockwise result, [7, 4, 1], [8, 5, 2], [9, 6, 3]. The counter-clockwise version is the opposite turn: it undoes the clockwise one. Keep this in mind when the problem asks for a specific direction.

The line m[top], m[bottom] = m[bottom], m[top] swaps the references to the rows. It does not copy the numbers inside each row. Swapping two references is cheap, and it is safe here because every row keeps its length. A short alternative is m[:] = [list(r) for r in zip(*m)][::-1], which builds a new list of rows, but it copies every value.

Common mistakes

Swapping every cell in the grid. A beginner may write the transpose loop with j starting at 0. The loop then swaps each pair twice, and the grid does not change. This is the most common bug in this lesson. The program below shows it. It prints the same grid it started with.

Output:

[[1, 2], [3, 4]]

The fix is range(i + 1, n) for the inner loop. Each pair is then swapped once.

Reversing columns instead of rows. Some people swap the top and bottom values inside each column. That flips the grid upside down, which is a different move from a rotation. The next program flips each column of a 2 by 2 grid, and the result is the upside-down grid.

Output:

[[3, 4], [1, 2]]

The clockwise rotation of this grid is [[3, 1], [4, 2]], so the flip is wrong. Use reverse_each_row after the transpose, as shown earlier.

Using the wrong size for a non-square grid. The method works in place only for a square grid. A grid with 2 rows and 3 columns cannot be transposed inside the same lists, because the transpose would need 3 rows. The loops use one size for both directions, so if the size is taken from the wrong dimension, Python stops with an index error. This program takes the size from the number of columns in a 2 by 3 grid.

def transpose_using_column_count(m):
    n = len(m[0])
    for i in range(n):
        for j in range(i + 1, n):
            m[i][j], m[j][i] = m[j][i], m[i][j]
 
g = [[1, 2, 3], [4, 5, 6]]
transpose_using_column_count(g)
print(g)

Traceback (most recent call last):
  File "main.py", line 8, in <module>
    transpose_using_column_count(g)
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^^^
  File "main.py", line 5, in transpose_using_column_count
    m[i][j], m[j][i] = m[j][i], m[i][j]
                       ~^^^
IndexError: list index out of range

The last frame shows the failing line. The first failing step is i equal to 0 and j equal to 2, where m[j][i] asks for m[2], a third row in a grid that has only two. The fix is to check that the grid is square before rotating. If the grid is not square, the rotation needs a new list, which is a different method.

Forgetting the row reversal. After the transpose alone, the grid is flipped across the diagonal, not rotated. A program that stops after the transpose gives [1, 4, 7] as the first row for the 3 by 3 example, which is the wrong answer for a clockwise turn. Check the first row against the rule: it should be the first column read from the bottom up.

Mixing up the clockwise and counter-clockwise steps. Reversing each row after a transpose gives a clockwise turn. Reversing the order of the rows after a transpose gives a counter-clockwise turn. Swapping the two steps by mistake gives a result that looks plausible, so test it on a grid with distinct values.

Passing the size in from outside. A function that takes n as a separate argument can be called with a wrong n, and then the loops read past the end of the grid. Read the size inside the function with len(m), so the size always matches the grid it receives.

Practice

Try each one before you read the answer. Save each program as main.py and run it with python3 main.py.

1. Write a function transpose(m) that works on a square grid. Test it with the 3 by 3 grid [[1, 2, 3], [4, 5, 6], [7, 8, 9]]. Predict the first row of the result before you run it.

Show the answer

The first row of the result is the first column of the original, which is 1, 4, 7. The function is the one shown earlier in this lesson, with n = len(m) and an inner loop that starts at i + 1. The result is [1, 4, 7], [2, 5, 8], [3, 6, 9].

2. Using only the transpose and the row reversal, rotate the 2 by 2 grid [[5, 6], [7, 8]] clockwise. Write the result as two rows. Check your answer with the rule that the first column, read from the bottom up, becomes the first row.

Show the answer

The first column is 5, 7. Read from the bottom up it is 7, 5, so the first row of the result is [7, 5]. The second column is 6, 8, which read from the bottom up is 8, 6, so the second row is [8, 6]. The result is [7, 5] and [8, 6].

3. A 5 by 5 grid is stored as a list of lists called board. The value at row 0, column 4 is 99. After one clockwise rotation, which row and column hold the value 99? Explain your answer with the rule, then check it with code.

Show the answer

A value at [row][col] moves to [col][n - 1 - row] after a clockwise turn, where n is the size of the grid. Here row is 0, col is 4, and n is 5. The new position is [4][4], which is row 4, column 4, the bottom right corner. This is the place the top right corner moves to in a clockwise turn.

Output:

99 at 4 4

4. Write a function that rotates a square grid counter-clockwise by building it from transpose and reverse_row_order. Test it on the 4 by 4 grid [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]. Print the first row of the result.

Show the answer

The first row of a counter-clockwise turn is the last column of the original, read from the top down. The last column is 4, 8, 12, 16, so the first row of the result is [4, 8, 12, 16].

def rotate_counter_clockwise(m):
    transpose(m)
    reverse_row_order(m)

The functions transpose and reverse_row_order are the ones from the counter-clockwise section. Calling rotate_counter_clockwise on the grid and printing grid[0] gives [4, 8, 12, 16].

5. Explain in plain words why the transpose loop uses range(i + 1, n) and not range(n), using a 2 by 2 grid as the example.

Show the answer

With the inner loop starting at 0, the program swaps [0][1] with [1][0] when i is 0, and then it swaps them again when i is 1 and j is 0. Two swaps of the same pair put the values back where they started, so the grid does not change. With the inner loop starting at i + 1, the pair is swapped once and the transpose is correct.

Summary

• A square grid is a list of rows, and grid[row][col] reads one cell.
• A transpose swaps [row][col] with [col][row], and the inner loop must start at i + 1 so each pair is swapped once.
• A clockwise rotation is a transpose followed by reversing each row.
• A counter-clockwise rotation is a transpose followed by reversing the order of the rows.
• Four clockwise turns return every value to its start, which is a useful test.
• The in-place method needs a square grid, and a size mistake shows up as an IndexError.