Skip to content

Volume ITechnology

4.0.23 — Matrix Basics: Transpose, Add, Multiply, Diagonals ​

Classic · Easy to Medium · LeetCode 867 (Transpose Matrix), LeetCode 1572 (Matrix Diagonal Sum)

The problem ​

A matrix is a grid of numbers with rows and columns. In Python it is a list of rows, and each row is a list.

python
m = [[1, 2, 3],
     [4, 5, 6]]      # 2 rows, 3 columns
print(m[1][2])       # → 6

m[r][c] is row r, column c, both counted from 0. So m[1][2] is the second row, third column.

  1. Transpose it: turn rows into columns.
  2. Add two matrices.
  3. Multiply two matrices.
  4. Add up the two diagonals of a square matrix.

First, a common mistake: building an empty grid ​

Many matrix answers start by making an empty grid. There is a wrong way that looks right.

python
bad = [[0] * 3] * 2
bad[0][0] = 9
print(bad)    # → [[9, 0, 0], [9, 0, 0]]

Changing one cell changed both rows. Why? [0] * 3 makes one row. Then [row] * 2 makes a list holding the same row object twice, not two separate rows. Both entries point to the same list in memory. Changing it through one name shows through the other.

Numbers are safe to repeat with *, because a number cannot be changed in place. Lists can be changed, so repeating a list repeats the same list. The fix is to build each row separately.

python
good = [[0] * 3 for _ in range(2)]    # a new row each time round the loop
good[0][0] = 9
print(good)   # → [[9, 0, 0], [0, 0, 0]]

This bug is worth naming in any interview that involves a grid. It shows you understand how Python stores lists.

1. Transpose ​

The transpose flips the matrix across its main diagonal, the line from top-left to bottom-right. Row r becomes column r. So the value at m[r][c] moves to t[c][r]. A 2 × 3 matrix becomes 3 × 2.

1 2 3        1 4
4 5 6   →    2 5
             3 6
python
def transpose(m: list[list[int]]) -> list[list[int]]:
    rows, cols = len(m), len(m[0])
    t = [[0] * rows for _ in range(cols)]      # (1)
    for r in range(rows):
        for c in range(cols):
            t[c][r] = m[r][c]                  # (2)
    return t

print(transpose([[1, 2, 3], [4, 5, 6]]))   # → [[1, 4], [2, 5], [3, 6]]

(1) The result has cols rows and rows columns. The shape flips.

(2) Row and column swap places.

The Python one-liner is [list(row) for row in zip(*m)]. zip(*m) hands zip every row as a separate argument. zip then pairs up the first items of every row, then the second items, and so on. Those groups are exactly the columns.

In place, for a square matrix ​

A square matrix keeps its shape when transposed, so it can be done without a new grid. Swap each element above the diagonal with its mirror below.

python
def transpose_square(m: list[list[int]]) -> None:
    n = len(m)
    for r in range(n):
        for c in range(r + 1, n):                  # (1)
            m[r][c], m[c][r] = m[c][r], m[r][c]

sq = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
transpose_square(sq)
print(sq)   # → [[1, 4, 7], [2, 5, 8], [3, 6, 9]]

(1) Start c at r + 1. Then each pair is visited once, from the upper side only. If c started at 0, every pair would be swapped twice, which puts everything back where it started. That is the classic bug: the code runs and the matrix comes out unchanged.

Transpose followed by reversing each row rotates a square matrix 90° clockwise. That is 4.28.1 Rotate Image.

2. Add two matrices ​

Add the cells in matching positions. The two matrices must have the same shape.

python
def add(a: list[list[int]], b: list[list[int]]) -> list[list[int]]:
    if len(a) != len(b) or len(a[0]) != len(b[0]):
        raise ValueError("shapes differ")
    return [[a[r][c] + b[r][c] for c in range(len(a[0]))] for r in range(len(a))]

print(add([[1, 2], [3, 4]], [[10, 20], [30, 40]]))   # → [[11, 22], [33, 44]]

3. Multiply two matrices ​

What multiplication means ​

Matrix multiplication is not cell by cell. Each cell of the result combines a whole row of the first matrix with a whole column of the second. Multiply them pair by pair and add up.

C[i][j] = \sum_{k} A[i][k] \times B[k][j]

Read it aloud: "cell i, j of the result is the sum, over every k, of row i's k-th value times column j's k-th value."

For that to work, a row of A and a column of B must be the same length. So the number of columns of A must equal the number of rows of B. An m \times p matrix times a p \times n matrix gives an m \times n matrix.

Worked by hand:

\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \times \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix}

  • Top-left: row 1 of A with column 1 of B. 1 \times 5 + 2 \times 7 = 19.
  • Top-right: row 1 with column 2. 1 \times 6 + 2 \times 8 = 22.
  • Bottom-left: row 2 with column 1. 3 \times 5 + 4 \times 7 = 43.
  • Bottom-right: row 2 with column 2. 3 \times 6 + 4 \times 8 = 50.

Why is it defined this odd way? A matrix describes a change to a list of numbers. A rotation of a picture is one example. Multiplying two matrices gives the single matrix that does both changes, one after the other. Row-times-column is exactly what makes that true. Volume II, Part 4 explains it in full.

python
def multiply(a: list[list[int]], b: list[list[int]]) -> list[list[int]]:
    m, p, n = len(a), len(b), len(b[0])
    if len(a[0]) != p:
        raise ValueError("columns of a must equal rows of b")   # (1)
    c = [[0] * n for _ in range(m)]
    for i in range(m):              # (2) each row of a
        for j in range(n):          # (3) each column of b
            total = 0
            for k in range(p):      # (4) walk along both together
                total += a[i][k] * b[k][j]
            c[i][j] = total
    return c

print(multiply([[1, 2], [3, 4]], [[5, 6], [7, 8]]))    # → [[19, 22], [43, 50]]
print(multiply([[1, 2, 3]], [[1], [2], [3]]))          # → [[14]]

(1) Check the shapes first. Multiplying mismatched shapes would crash with an IndexError part way through, or worse, silently use the wrong numbers.

(2) Pick a row of the result.

(3) Pick a column of the result.

(4) k moves along row i of a and down column j of b at the same time. Each step multiplies one pair.

The second example multiplies a 1 × 3 by a 3 × 1, giving a 1 × 1: 1 \times 1 + 2 \times 2 + 3 \times 3 = 14.

Order matters. A \times B is usually not equal to B \times A. Often only one of them is even allowed by the shapes. This is unlike ordinary numbers, and interviewers like to check that you know it.

The cost. Three nested loops of sizes m, n and p. For two n \times n matrices that is n^3 multiplications. For n = 1000, a billion. Cleverer methods exist. Volker Strassen showed in 1969 that you can do it in about n^{2.81}. In real code, a library like NumPy runs this on fast, hand-tuned machine code, thousands of times faster than Python loops.

4. Diagonal sums ​

The main diagonal runs top-left to bottom-right. Its cells have r == c. The other diagonal runs top-right to bottom-left. Its cells have r + c == n - 1.

python
def diagonal_sum(m: list[list[int]]) -> int:
    n = len(m)
    total = 0
    for i in range(n):
        total += m[i][i]               # main diagonal
        total += m[i][n - 1 - i]       # other diagonal
    if n % 2 == 1:
        total -= m[n // 2][n // 2]     # (1)
    return total

print(diagonal_sum([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))   # → 25

(1) When n is odd, the two diagonals cross in the centre cell. It was added twice, so take it off once. For the 3 × 3 example: main 1 + 5 + 9, other 3 + 5 + 7, total 30, minus the centre 5, gives 25.

This is LeetCode 1572. Spiral order, a common follow-up, is 4.28.2.

Complexity ​

TaskTimeExtra memory
TransposeO(mn)O(mn), or O(1) in place for square
AddO(mn)O(mn)
Multiply (m \times p by p \times n)O(mnp)O(mn)
Diagonal sumO(n)O(1)

What the interviewer will push on ​

These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.

"What does [[0] * 3] * 2 do?" It makes one row and puts that same row in the list twice. Changing one row changes both. Build each row on its own: [[0] * 3 for _ in range(2)].

"Your in-place transpose gives back the same matrix. Why?" The inner loop probably starts at 0. Then each pair is swapped twice, which puts it back. Start the inner loop at r + 1.

"When can two matrices be multiplied?" When the number of columns of the first equals the number of rows of the second. The answer has the rows of the first and the columns of the second.

"Is A \times B the same as B \times A?" Usually not. Often only one of the two is even allowed by the shapes.

"How fast is matrix multiplication?" The simple method is O(n^3) for two n \times n matrices. Faster methods exist, starting with Strassen's in 1969.

One thing to volunteer: "In real code I would use NumPy's a @ b. It is many times faster than Python loops."

Next: 4.0.24 Bubble Sort. The first of the seven sorting algorithms every computer-science course teaches.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet