Matrix rotation and transpose

Why this matters

Grids appear in many programs. A game board is a grid. A picture is a grid of pixels. A seating plan or a table of scores is a grid too. Sometimes you need to turn one of them, such as when a phone turns its screen or an image editor turns a photo.

One way to turn a grid is to build a second grid and copy each value into its new place. That uses twice the memory. Another way is to change the grid where it stands. That is called rotating in place, and this lesson shows how to do it with two simple moves.

The lesson assumes you can read and write a value in a two-dimensional array, which the two-dimensional arrays lesson earlier in this module covers. A grid is written m[i][j], where i is the row and j is the column. Both count from 0.

A matrix is the maths word for a grid of rows and columns. A square matrix has the same number of rows and columns, such as 3 by 3 or 4 by 4. This lesson works on square matrices only.

The idea: two moves

The first move is called a transpose. It flips the grid across its main diagonal, which is the line of cells from the top-left corner to the bottom-right corner. Each cell swaps places with the cell on the other side of that line. Row 1 becomes column 1, row 2 becomes column 2, and so on.

Here is a 3 by 3 grid before and after a transpose.

1 2 3
4 5 6
7 8 9

1 4 7
2 5 8
3 6 9

The second move reverses each row. Reversing a row means its first value goes to the end and its last value goes to the front. Read the first row of the transposed grid, 1 4 7, and reverse it: you get 7 4 1. That row becomes the top row of the turned grid.

This is why the result is a clockwise turn. Picture the grid as a sheet of paper. When you turn the paper a quarter turn clockwise, the bottom-left corner moves to the top-left corner. The left column, read from the bottom up, becomes the top row. After the transpose, the first row is the left column read from the top down. Reversing that row puts the bottom cell first, so the bottom-left value ends up in the top-left corner. Every other cell follows the same pattern.

Worked example 1: a 3 by 3 grid, one step at a time

The program below turns a 3 by 3 grid and prints it after each step. It has three functions: one for the transpose, one for reversing rows, and one that prints the grid.

C++ · editable

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>

using Matrix = std::vector<std::vector<int>>;

void print_matrix(const Matrix& m) {
    for (const auto& row : m) {
        for (std::size_t j = 0; j < row.size(); ++j) {
            std::cout << (j == 0 ? "" : " ") << row[j];
        }
        std::cout << "\n";
    }
}

void transpose(Matrix& m) {
    std::size_t n = m.size();
    for (std::size_t i = 0; i < n; ++i) {
        for (std::size_t j = i + 1; j < n; ++j) {
            std::swap(m[i][j], m[j][i]);
        }
    }
}

void reverse_each_row(Matrix& m) {
    for (auto& row : m) {
        std::ranges::reverse(row);
    }
}

void rotate_clockwise(Matrix& m) {
    transpose(m);
    reverse_each_row(m);
}

int main() {
    Matrix m = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9},
    };

std::cout << "original:\n";
    print_matrix(m);

transpose(m);
    std::cout << "after transpose:\n";
    print_matrix(m);

reverse_each_row(m);
    std::cout << "after reversing each row:\n";
    print_matrix(m);
    return 0;
}

The output is:

original:
1 2 3
4 5 6
7 8 9
after transpose:
1 4 7
2 5 8
3 6 9
after reversing each row:
7 4 1
8 5 2
9 6 3

Some details to notice.

using Matrix = std::vector<std::vector<int>>; gives a short name to a vector of vectors. A vector of vectors is a grid where each row is its own vector. Each row can be read and changed with m[i][j].
The transpose uses two loops. The outer loop picks row i. The inner loop starts at j = i + 1, so it only visits the cells above the diagonal. Each swap exchanges one value with its mirror partner across the diagonal. For a 3 by 3 grid, the swaps are the pairs (0,1) with (1,0), (0,2) with (2,0), and (1,2) with (2,1). That is three swaps.
The diagonal cells, such as m[0][0] and m[1][1], already sit on their mirror position, so the loop leaves them alone.
std::ranges::reverse comes from <algorithm>. It reverses the order of the values in a range, and a row is a range.

The output shows the three stages. The final grid is the original turned a quarter turn clockwise. The top row, 7 4 1, is the left column read from the bottom up.

Worked example 2: checking against a slower method

One correct example does not prove that a method works for every size. A second method that is slow but obviously right gives a way to compare.

The slow method builds a new grid. It uses this rule: the value at row i, column j moves to row j, column n - 1 - i. Here n is the number of rows. For a 3 by 3 grid, the top-left value at (0, 0) moves to (0, 2), the top-right corner. That is what a clockwise turn does to the top-left corner.

The next program fills grids of sizes 1 to 6 with the numbers 1, 2, 3 and so on. It rotates each grid with the fast method and compares the result with the slow method. It then turns a 4 by 4 grid once.

C++ · editable

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>

using Matrix = std::vector<std::vector<int>>;

void reverse_each_row(Matrix& m) {
    for (auto& row : m) {
        std::ranges::reverse(row);
    }
}

void rotate_clockwise(Matrix& m) {
    transpose(m);
    reverse_each_row(m);
}

// Slow but obviously correct: new[j][n-1-i] = old[i][j].
Matrix rotate_clockwise_copy(const Matrix& m) {
    std::size_t n = m.size();
    Matrix out(n, std::vector<int>(n));
    for (std::size_t i = 0; i < n; ++i) {
        for (std::size_t j = 0; j < n; ++j) {
            out[j][n - 1 - i] = m[i][j];
        }
    }
    return out;
}

int main() {
    bool all_ok = true;
    for (std::size_t n = 1; n <= 6; ++n) {
        Matrix m(n, std::vector<int>(n));
        int value = 1;
        for (auto& row : m) {
            for (auto& cell : row) {
                cell = value++;
            }
        }
        Matrix expected = rotate_clockwise_copy(m);
        rotate_clockwise(m);
        std::cout << "n = " << n << ": " << (m == expected ? "match" : "DIFFERENT") << "\n";
        all_ok = all_ok && (m == expected);
    }
    std::cout << "all sizes match: " << std::boolalpha << all_ok << "\n\n";

Matrix four = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16},
    };
    std::cout << "4 by 4 original:\n";
    print_matrix(four);
    rotate_clockwise(four);
    std::cout << "4 by 4 after one clockwise turn:\n";
    print_matrix(four);
    return 0;
}

The output is:

n = 1: match
n = 2: match
n = 3: match
n = 4: match
n = 5: match
n = 6: match
all sizes match: true
 
4 by 4 original:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
4 by 4 after one clockwise turn:
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4

The check m == expected compares every value in the two grids. Because the vectors are compared element by element, one wrong cell makes the result DIFFERENT.

The size 1 case deserves a note. A 1 by 1 grid has nothing to swap and nothing to move, so the answer is the same grid. Test the smallest size too, because a bug can show up only there.

In the 4 by 4 result, the top row 13 9 5 1 is the left column of the original read from the bottom up. That matches the paper-turning picture from earlier.

Worked example 3: counter-clockwise and a half turn

The same two moves in the other order turn the grid the other way. To turn counter-clockwise, reverse each row first, then transpose.

C++ · editable

The output is:

3 by 3 after one counter-clockwise turn:
3 6 9
2 5 8
1 4 7

The top row is now 3 6 9, which is the right column of the original read from the top down. In a counter-clockwise turn, the right edge moves to the top, so that is the expected result.

A half turn is two quarter turns in the same direction. Turning clockwise twice turns the grid upside down and reverses each row. That is a useful way to test the two moves: after two turns, the answer is easy to predict by eye.

Non-square grids

The two moves only give a clean turn for square grids. Take a grid with 2 rows and 3 columns. A transpose gives 3 rows and 2 columns, which is a different shape. A value in that grid has nowhere to go inside the same space. A turn of a non-square grid needs a new grid of a different shape, which is a different method.

So the function should refuse non-square input. The check below looks at every row and compares its length with the number of rows.

C++ · editable

The output is:

error: matrix must be square

The try block runs the call, and the catch block handles the error that the call throws. Without the check, the program would not crash. It would print a wrong grid, as the next section shows.

Common mistakes

Starting the inner loop at 0

The inner loop must start at i + 1. If it starts at 0, every pair of cells is swapped twice, and two swaps cancel each other out. The program below uses the wrong loop on a 3 by 3 grid.

C++ · editable

The output is:

after the wrong loop, first row: 1 2 3

The first row should now start with 1, 4, 7, but it still reads 1 2 3. The program gives no error, so the mistake is easy to miss. A quick test on a 2 by 2 grid, where the expected answer is easy to write down, catches it at once.

Doing the two moves in the wrong order

Transpose first and then reverse each row turns the grid clockwise. Reverse each row first and then transpose turns it counter-clockwise, as worked example 3 shows. Both results are clean turns, just in opposite directions, so swapping the order gives an answer that looks valid. The only way to catch it is to check one case by hand, such as the top row of the result.

Using an int for the loop index

The size of a vector is an unsigned number. Comparing it with an int loop variable makes the compiler warn you. The line below compiles, and the warning appears under -Wall:

for (int i = 0; i < m.size(); ++i) {

warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]

The fix is std::size_t i = 0, which matches the type that size() returns. Treat this warning as a bug report, even when the program seems to work.

Skipping the square check

A 2 by 3 grid has no error when it is passed to the transpose loops, because the loops only use size() as the row count. The program runs and prints a wrong grid:

3 4 1
6 5 2

The grid started as 1 2 3 and 4 5 6. The transpose only swapped cells in the top-left 2 by 2 part, so the third column was not transposed. The result is a grid that looks plausible but is not a turn of the input. The is_square check in the previous section prevents this.

Practice

Exercise 1

Transpose the 2 by 2 grid 1 2 and 3 4. Then turn it clockwise. Write the rows of both results.

Show the answer

After the transpose, the rows are 1 3 and 2 4. After a clockwise turn, the rows are 3 1 and 4 2. The first row of the turned grid is the left column read from the bottom up: 3, then 1.

Exercise 2

Turn this 3 by 3 grid counter-clockwise by hand: 1 2 3, 4 5 6, 7 8 9.

Show the answer

The turned grid has the rows 3 6 9, 2 5 8 and 1 4 7. The top row is the right column of the original read from the top down.

Exercise 3

Turn a 4 by 4 grid, with values 1 to 16 in order, clockwise twice. Write the rows of the result.

Show the answer

The result has the rows 16 15 14 13, 12 11 10 9, 8 7 6 5 and 4 3 2 1. Two clockwise turns make a half turn, which reverses the order of the rows and the order of the values in each row.

Exercise 4

How many swaps does the transpose make for a 5 by 5 grid? Give a formula that works for any size n.

Show the answer

The transpose makes 10 swaps. The inner loop visits the cells above the diagonal, and that count is n times (n minus 1) divided by 2. For n equal to 5, that is 5 times 4 divided by 2, which is 10. The diagonal cells never move.

Exercise 5

Call rotate_clockwise from the square check example on a 2 by 3 grid. What happens, and what is printed?

Show the answer

The function throws std::invalid_argument with the message matrix must be square. The catch block prints error: matrix must be square. The grid is not changed, because the check runs before any swap.

Summary

A clockwise turn of a square grid is a transpose followed by reversing each row.
A counter-clockwise turn is reversing each row followed by a transpose.
The transpose loop starts the inner index at i + 1, so each pair is swapped once.
Compare a fast method with a slow, obviously correct one on several sizes, including 1.
A non-square grid cannot be turned in place with these moves, so check the shape first and throw an error if it is wrong.
Use std::size_t for indexes into a vector, so the compiler does not warn about signed and unsigned comparisons.

Matrix rotation and transpose

Why this matters

The idea: two moves

Worked example 1: a 3 by 3 grid, one step at a time

Worked example 2: checking against a slower method

Worked example 3: counter-clockwise and a half turn

Non-square grids

Common mistakes

Starting the inner loop at 0

Doing the two moves in the wrong order

Using an int for the loop index

Skipping the square check

Practice

Exercise 1

Exercise 2

Exercise 3

Exercise 4

Exercise 5

Summary

Stuck? Ask the tutor