AlgoScope

Matrix

structurebeginnerTime O(rows x cols)Space O(rows x cols)

A matrix is a flat block of memory that you address with two indices. Row-major order puts row 0 first, so (r, c) lives at r x cols + c. Once that is clear, transpose is a swap across the diagonal, a 2D prefix sum is the 1D idea with one overlap to subtract, and an adjacency matrix is a graph written as a grid of 0s and 1s. A multigraph, with parallel edges and self loops, needs the same grid to count rather than flag: cell (u, v) holds the number of edges between u and v, and a loop adds 2 to its diagonal cell so that the degree is still the row sum.

012301230000000000000000

A multigraph allows more than one edge between the same two vertices, and edges from a vertex to itself. A plain adjacency matrix cannot say that, so each cell counts edges instead of flagging one: cell (u, v) is the number of edges between u and v, and cell (u, u) counts a self loop twice, because a loop touches its vertex at both ends. The degree of u is then still the sum of row u.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 6, with their answers.

  1. Edge 0-1. What changes?

    • (0, 1) and (1, 0) go up by 1
    • (0, 1) and (1, 0) become 1
    • Only (0, 1) goes up

    Answer: (0, 1) and (1, 0) go up by 1. The cells count edges, so a parallel edge adds one more rather than staying at 1.

  2. Edge 0-1. What changes?

    • (0, 1) and (1, 0) go up by 1
    • (0, 1) and (1, 0) become 1
    • Only (0, 1) goes up

    Answer: (0, 1) and (1, 0) go up by 1. The cells count edges, so a parallel edge adds one more rather than staying at 1.

  3. Edge 1-2. What changes?

    • (1, 2) and (2, 1) go up by 1
    • (1, 2) and (2, 1) become 1
    • Only (1, 2) goes up

    Answer: (1, 2) and (2, 1) go up by 1. The cells count edges, so a parallel edge adds one more rather than staying at 1.

  4. Edge 2-2 is a self loop. What changes?

    • (2, 2) goes up by 2
    • (2, 2) goes up by 1
    • Nothing: loops are ignored

    Answer: (2, 2) goes up by 2. A loop contributes 2 to its vertex's degree, so the diagonal cell counts it twice.

  5. Edge 2-3. What changes?

    • (2, 3) and (3, 2) go up by 1
    • (2, 3) and (3, 2) become 1
    • Only (2, 3) goes up

    Answer: (2, 3) and (3, 2) go up by 1. The cells count edges, so a parallel edge adds one more rather than staying at 1.

  6. Edge 0-1. What changes?

    • (0, 1) and (1, 0) go up by 1
    • (0, 1) and (1, 0) become 1
    • Only (0, 1) goes up

    Answer: (0, 1) and (1, 0) go up by 1. The cells count edges, so a parallel edge adds one more rather than staying at 1.

How it runs, step by step

  1. A multigraph allows more than one edge between the same two vertices, and edges from a vertex to itself. A plain adjacency matrix cannot say that, so each cell counts edges instead of flagging one: cell (u, v) is the number of edges between u and v, and cell (u, u) counts a self loop twice, because a loop touches its vertex at both ends. The degree of u is then still the sum of row u.

    Building a 4 by 4 multigraph matrix from 6 edges.

  2. Edge 0-1: cells (0, 1) and (1, 0) go from 0 to 1, the same as in a simple graph. 1 of 6 edges placed.

    Edge 0 to 1, count 1.

  3. Edge 0-1 again: a parallel edge. Cells (0, 1) and (1, 0) go up to 2; a 0 or 1 matrix would have lost this edge. 2 of 6 edges placed.

    Edge 0 to 1, count 2.

  4. Edge 1-2: cells (1, 2) and (2, 1) go from 0 to 1, the same as in a simple graph. 3 of 6 edges placed.

    Edge 1 to 2, count 1.

  5. Edge 2-2 is a self loop: cell (2, 2) goes up by 2, because the loop leaves 2 and arrives at 2, and the degree counts both ends. 4 of 6 edges placed.

    Self loop at 2.

  6. Edge 2-3: cells (2, 3) and (3, 2) go from 0 to 1, the same as in a simple graph. 5 of 6 edges placed.

    Edge 2 to 3, count 1.

  7. Edge 0-1 again: a parallel edge. Cells (0, 1) and (1, 0) go up to 3; a 0 or 1 matrix would have lost this edge. 6 of 6 edges placed.

    Edge 0 to 1, count 3.

  8. 6 edges, 2 of them parallel to an earlier one and 1 self loop. Degrees by row sum: 0 has 3, 1 has 4, 2 has 4, 3 has 1, total 12 = 2 x 6, so the handshake lemma still holds. Multigraphs are where road networks, circuits and Euler tours live; the counting matrix and a list of edge objects both represent them, a set of neighbours cannot.

    Degrees 3, 4, 4, 1.

Remember

  • Row-major: (r, c) is flat index r x cols + c. Walk rows in the inner loop and memory is touched in order.
  • 2D prefix sum: own value plus above plus left minus the diagonal, and any rectangle is four lookups.
  • An adjacency matrix costs V squared cells no matter how few edges there are.

Topics covered

Related

Where this is used

Scientific computingNumPy strides and the BLAS memory order

NumPy stores an array row-major by default and keeps a stride per axis, so .T moves no data at all: it swaps the two strides and returns a view of the same buffer. LAPACK and Fortran BLAS want column-major, and the .T of a row-major array is exactly that, so the transposed view can go straight to a solver while the original array is the one that has to be copied or passed with a transpose flag. Knowing which layout you are holding is the difference between a free transpose and a full copy of the matrix.

Computer visionIntegral images in OpenCV

cv2.integral builds a 2D prefix sum of an image, and the Haar cascade detector then reads any rectangle sum in four lookups, so one feature costs a fixed handful of reads however large its boxes are. Because the cost does not grow with the rectangle, the cascade can test thousands of candidate windows at every scale per frame. The same table came out of graphics texture filtering, under the name summed-area table, before vision borrowed it.

DatabasesParquet and columnar databases

A table is a matrix and the storage engine gets to pick the traversal order. Row-major formats keep each record contiguous, which suits fetching whole rows; Parquet and ClickHouse store column-major, so a query over 2 of 50 columns reads two dense runs instead of touching every record. The compression win follows from the same choice, because a column holds one type and its values repeat.

GraphsWhy graph libraries default to lists, not matrices

An adjacency matrix answers "is there an edge u to v" in one lookup, which is exactly what dense algorithms like Floyd-Warshall need. SciPy's csgraph and NetworkX still default to sparse or list forms, because a social graph of a million vertices with ten edges each would need a trillion cells to hold ten million edges. The matrix earns its place when the graph is small or dense, or when you want to multiply it: raising it to the power k counts the walks of length k between every pair.

Why it works this way

In Java and Kotlin a 2D array is not one flat block

Array<IntArray> is an array of references, so every row is a separate object and the rows can sit anywhere on the heap. The r x cols + c model still describes the logic, but the contiguity guarantee only holds inside a single row. When layout actually matters, allocate one IntArray(rows * cols) and do the index arithmetic yourself, which is what C, Fortran and NumPy hand you for free.

Why the inner loop should walk a row, not a column

A cache line pulls in roughly 64 bytes at once, about 16 ints. Walking a row consumes all 16; walking a column uses one and throws away the rest, then fetches a fresh line on every step. The operation count is identical either way, so a column-order traversal of a large matrix can run several times slower for reasons the code does not show. Reordering the loops of a matrix multiply from i-j-k to i-k-j is the same fix.

Why transpose starts at c = r + 1, and why it needs a square

Starting at c = 0 visits every pair twice and swaps it straight back, so the loop runs and the matrix is unchanged. Starting one past the diagonal touches each pair once, and the diagonal never moves because (r, r) would swap with itself. The trick also depends on rows == cols: a 3 x 5 matrix transposes to 5 x 3, so the shape itself changes and the index map stops being a set of two-element swaps. For rectangular input you write into a new matrix or follow the permutation cycles of the index map, which is a much harder job.

Why the 2D prefix sum subtracts the diagonal term

The block above and the block to the left both already cover the region up and to the left of the current cell, so adding the two counts that overlap twice; subtracting p[r-1][c-1] once removes the extra copy. The extra zero row and column exist so that r-1 and c-1 are always in range and no boundary check is needed. The price is an off-by-one in the query: the rectangle from (r1, c1) to (r2, c2) reads p at r2+1 and c2+1.

Read more

Next up