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.

A 3 x 4 matrix is 3 rows of 4 values, but memory is one flat line. Row-major order stores row 0, then row 1, and so on, so cell (r, c) sits at flat index r x 4 + c. Walk it in that order.

Check your understanding

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

Cell (0, 1) in a 3 x 4 matrix. Which flat index?
- 1
- 3
Answer: 1. 0 full rows of 4 come first, then 1 more: 1.
Cell (0, 2) in a 3 x 4 matrix. Which flat index?
- 2
- 6
Answer: 2. 0 full rows of 4 come first, then 2 more: 2.
Cell (0, 3) in a 3 x 4 matrix. Which flat index?
- 3
- 9
Answer: 3. 0 full rows of 4 come first, then 3 more: 3.
Cell (1, 0) in a 3 x 4 matrix. Which flat index?
- 4
- 1
Answer: 4. 1 full rows of 4 come first, then 0 more: 4.
Cell (1, 1) in a 3 x 4 matrix. Which flat index?
- 5
- 4
- 2
Answer: 5. 1 full rows of 4 come first, then 1 more: 5.
Cell (1, 2) in a 3 x 4 matrix. Which flat index?
- 6
- 7
- 3
Answer: 6. 1 full rows of 4 come first, then 2 more: 6.
Cell (1, 3) in a 3 x 4 matrix. Which flat index?
- 7
- 10
- 4
Answer: 7. 1 full rows of 4 come first, then 3 more: 7.
Cell (2, 0) in a 3 x 4 matrix. Which flat index?
- 8
- 2
Answer: 8. 2 full rows of 4 come first, then 0 more: 8.
Cell (2, 1) in a 3 x 4 matrix. Which flat index?
- 9
- 5
- 3
Answer: 9. 2 full rows of 4 come first, then 1 more: 9.
Cell (2, 2) in a 3 x 4 matrix. Which flat index?
- 10
- 8
- 4
Answer: 10. 2 full rows of 4 come first, then 2 more: 10.
Cell (2, 3) in a 3 x 4 matrix. Which flat index?
- 11
- 5
Answer: 11. 2 full rows of 4 come first, then 3 more: 11.

How it runs, step by step

A 3 x 4 matrix is 3 rows of 4 values, but memory is one flat line. Row-major order stores row 0, then row 1, and so on, so cell (r, c) sits at flat index r x 4 + c. Walk it in that order.
Walking a 3 by 4 matrix in row-major order and naming the flat index of each cell.
(0, 0) holds 1. Flat index 0 x 4 + 0 = 0.
Cell 0, 0 is flat index 0.
(0, 1) holds 2. Flat index 0 x 4 + 1 = 1.
Cell 0, 1 is flat index 1.
(0, 2) holds 3. Flat index 0 x 4 + 2 = 2.
Cell 0, 2 is flat index 2.
(0, 3) holds 4. Flat index 0 x 4 + 3 = 3.
Cell 0, 3 is flat index 3.
(1, 0) holds 5. Flat index 1 x 4 + 0 = 4.
Cell 1, 0 is flat index 4.
(1, 1) holds 6. Flat index 1 x 4 + 1 = 5.
Cell 1, 1 is flat index 5.
(1, 2) holds 7. Flat index 1 x 4 + 2 = 6.
Cell 1, 2 is flat index 6.
(1, 3) holds 8. Flat index 1 x 4 + 3 = 7.
Cell 1, 3 is flat index 7.
(2, 0) holds 9. Flat index 2 x 4 + 0 = 8.
Cell 2, 0 is flat index 8.
(2, 1) holds 10. Flat index 2 x 4 + 1 = 9.
Cell 2, 1 is flat index 9.
(2, 2) holds 11. Flat index 2 x 4 + 2 = 10.
Cell 2, 2 is flat index 10.
(2, 3) holds 12. Flat index 2 x 4 + 3 = 11.
Cell 2, 3 is flat index 11.
12 cells, flat indices 0 to 11. Walking row by row touches memory in order, which is why row-major loops run faster than column-major ones on a row-major matrix.
All 12 cells visited in row-major order.

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

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.

Row- and column-major orderWikipedia
Summed-area tableWikipedia
Adjacency matrixWikipedia
In-place matrix transpositionWikipedia
The N-dimensional array: internal memory layoutNumPy