Row-Major vs Column-Major Storage and Address Arithmetic

Why linearization is needed

Memory is one-dimensional, but arrays are not. To store a 2-D matrix $A$ with $r$ rows and $c$ columns, the compiler must pick an order in which to flatten the cells into consecutive addresses. There are two standard choices.

• Row-major (C, C++, Python/NumPy default, Pascal): rows are laid down one after another — $A[0][0], A[0][1], \dots, A[0][c-1], A[1][0], \dots$ The last index varies fastest.
• Column-major (Fortran, MATLAB, R, Julia): columns are laid down one after another — $A[0][0], A[1][0], \dots, A[r-1][0], A[0][1], \dots$ The first index varies fastest.

Address formulas

Let $b$ be the base address, $s$ the size of one element (in bytes), and assume 0-based indices.

$\text{row-major:}\quad \text{addr}(A[i][j]) = b + (i\cdot c + j)\cdot s$

$\text{column-major:}\quad \text{addr}(A[i][j]) = b + (j\cdot r + i)\cdot s$

The quantity multiplied by $s$ is the linear index. With 1-based indices and lower bounds $L_1, L_2$, replace $i\to(i-L_1)$ and $j\to(j-L_2)$.

How to read a problem

The diagnostic trick: pick two cells, see which index changed, and measure the address gap (the stride).

So: a big jump when the row index moves $\Rightarrow$ row-major; a big jump when the column index moves $\Rightarrow$ column-major.

Mini-example

Suppose $\text{addr}(A[0][1]) = \mathtt{7A00}_{16}$ and $\text{addr}(A[1][1]) = \mathtt{7A10}_{16}$. Only the row index changed ($0\to1$), and the address advanced by $\mathtt{7A10}-\mathtt{7A00} = \mathtt{10}_{16} = 16$ bytes. Jumping a full row width when the first index increments is the row-major signature, so the matrix is stored row-major. (Had the same 16-byte jump come from changing the column index, it would have been column-major.)

Generalizing to $k$ dimensions

For dimensions $d_0 \times d_1 \times \dots \times d_{k-1}$, row-major weights each index by the product of all later dimension sizes:

$\text{linear index} = \sum_{t=0}^{k-1} i_t \cdot \!\!\prod_{u=t+1}^{k-1}\!\! d_u .$

Column-major instead weights each index by the product of all earlier dimension sizes.

Exam trick: Always ask which index moved and how big the gap is before deciding. A small one-element stride means that index varies fastest (last index in row-major, first in column-major); a large stride means you crossed a whole row or column. Also watch for 1-based indexing and a nonzero base — subtract the lower bound before plugging into the formula.