Row- and column-major order

The terms row-major and column-major stem from the terminology related to ordering objects. A general way to order objects with many attributes is to first group and order them by one attribute, and then, within each such group, group and order them by another attribute, etc. If more than one attribute participates in ordering, the first would be called major and the last minor. If two attributes participate in ordering, it is sufficient to name only the major attribute.

In the case of arrays, the attributes are the indices along each dimension. For matrices in mathematical notation, the first index indicates the row, and the second indicates the column, e.g., given a matrix ${\displaystyle A}$, the entry ${\displaystyle a_{1,2}}$ is in its first row and second column. This convention is carried over to the syntax in programming languages,[2] although often with indexes starting at 0 instead of 1.[3]

Even though the row is indicated by the first index and the column by the second index, no grouping order between the dimensions is implied by this. The choice of how to group and order the indices, either by row-major or column-major methods, is thus a matter of convention. The same terminology can be applied to even higher dimensional arrays. Row-major grouping starts from the leftmost index and column-major from the rightmost index, leading to lexicographic and colexicographic (or colex) orders, respectively.

For example, the array

${\displaystyle A=a_{y,x}={\begin{bmatrix}\color {Blue}a_{11}&\color {Blue}a_{12}&\color {Blue}a_{13}\\\color {Orange}a_{21}&\color {Orange}a_{22}&\color {Orange}a_{23}\end{bmatrix}}}$

could be stored in two possible ways:

Address	Row-major order	Column-major order
0	${\displaystyle \color {Blue}a_{11}}$	${\displaystyle \color {Blue}a_{11}}$
1	${\displaystyle \color {Blue}a_{12}}$	${\displaystyle \color {Orange}a_{21}}$
2	${\displaystyle \color {Blue}a_{13}}$	${\displaystyle \color {Blue}a_{12}}$
3	${\displaystyle \color {Orange}a_{21}}$	${\displaystyle \color {Orange}a_{22}}$
4	${\displaystyle \color {Orange}a_{22}}$	${\displaystyle \color {Blue}a_{13}}$
5	${\displaystyle \color {Orange}a_{23}}$	${\displaystyle \color {Orange}a_{23}}$

Programming languages handle this in different ways. In C, multidimensional arrays are stored in row-major order, and the array indexes are written  row-first (lexicographical access order):

C: row-major order (lexicographical access order), zero-based indexing

Address x + N_x*y	Access A[y][x]	Value ${\displaystyle a_{y,x}}$
0	A[0][0]	${\displaystyle a_{11}}$
1	A[0][1]	${\displaystyle a_{12}}$
2	A[0][2]	${\displaystyle a_{13}}$
3	A[1][0]	${\displaystyle a_{21}}$
4	A[1][1]	${\displaystyle a_{22}}$
5	A[1][2]	${\displaystyle a_{23}}$

On the other hand, in Fortran, arrays are stored in column-major order, while the array indexes are still written row-first (colexicographical access order):

Fortran: column-major order (colexicographical access order), one-based indexing

Address y + N_y*(x-1)	Access A(y,x)	Value ${\displaystyle a_{y,x}}$
1	A(1,1)	${\displaystyle a_{11}}$
2	A(2,1)	${\displaystyle a_{21}}$
3	A(1,2)	${\displaystyle a_{12}}$
4	A(2,2)	${\displaystyle a_{22}}$
5	A(1,3)	${\displaystyle a_{13}}$
6	A(2,3)	${\displaystyle a_{23}}$

Note how the use of A[i][j] with multi-step indexing as in C, as opposed to a neutral notation like A(i,j) as in Fortran, almost inevitably implies row-major order for syntactic reasons, so to speak, because it can be rewritten as (A[i])[j], and the A[i] row part can even be assigned to an intermediate variable that is then indexed in a separate expression. (No other implications should be assumed, e.g., Fortran is not column-major simply because of its notation, and even the above implication could intentionally be circumvented in a new language.)

To use column-major order in a row-major environment, or vice versa, for whatever reason, one workaround is to assign non-conventional roles to the indexes (using the first index for the column and the second index for the row), and another is to bypass language syntax by explicitly computing positions in a one-dimensional array. Of course, deviating from convention probably incurs a cost that increases with the degree of necessary interaction with conventional language features and other code, not only in the form of increased vulnerability to mistakes (forgetting to also invert matrix multiplication order, reverting to convention during code maintenance, etc.), but also in the form of having to actively rearrange elements, all of which have to be weighed against any original purpose such as increasing performance. Running the loop row-wise is preferred in row-major languages like C and vice versa for column-major languages.

Programming languages or their standard libraries that support multi-dimensional arrays typically have a native row-major or column-major storage order for these arrays.

Row-major order is used in C/C++/Objective-C (for C-style arrays), PL/I,[4] Pascal,[5] Speakeasy, and SAS.[6]

Column-major order is used in Fortran, MATLAB,[7] GNU Octave, Julia,[8] S, S-PLUS,[9] R,[10] Scilab,[11] Yorick, and Rasdaman.[12]

As exchanging the indices of an array is the essence of array transposition, an array stored as row-major but read as column-major (or vice versa) will appear transposed (as long as the matrix is square). As actually performing this rearrangement in memory is typically an expensive operation, some systems provide options to specify individual matrices as being stored transposed. The programmer must then decide whether or not to rearrange the elements in memory, based on the actual usage (including the number of times that the array is reused in a computation).

For example, the Basic Linear Algebra Subprograms functions are passed flags indicating which arrays are transposed.[23]

The concept generalizes to arrays with more than two dimensions.

For a d-dimensional ${\displaystyle N_{1}\times N_{2}\times \cdots \times N_{d}}$ array with dimensions N_k (k=1...d), a given element of this array is specified by a tuple ${\displaystyle (n_{1},n_{2},\ldots ,n_{d})}$ of d (zero-based) indices ${\displaystyle n_{k}\in [0,N_{k}-1]}$.

In row-major order, the last dimension is contiguous, so that the memory-offset of this element is given by:

$${\displaystyle n_{d}+N_{d}\cdot (n_{d-1}+N_{d-1}\cdot (n_{d-2}+N_{d-2}\cdot (\cdots +N_{2}n_{1})\cdots )))=\sum _{k=1}^{d}\left(\prod _{\ell =k+1}^{d}N_{\ell }\right)n_{k}}$$

In column-major order, the first dimension is contiguous, so that the memory-offset of this element is given by:

$${\displaystyle n_{1}+N_{1}\cdot (n_{2}+N_{2}\cdot (n_{3}+N_{3}\cdot (\cdots +N_{d-1}n_{d})\cdots )))=\sum _{k=1}^{d}\left(\prod _{\ell =1}^{k-1}N_{\ell }\right)n_{k}}$$

where the empty product is the multiplicative identity element, i.e., ${\textstyle \prod _{\ell =1}^{0}N_{\ell }=\prod _{\ell =d+1}^{d}N_{\ell }=1}$.

For a given order, the stride in dimension k is given by the multiplication value in parentheses before index n_k in the right-hand side summations above.

More generally, there are d! possible orders for a given array, one for each permutation of dimensions (with row-major and column-order just 2 special cases), although the lists of stride values are not necessarily permutations of each other, e.g., in the 2-by-3 example above, the strides are (3,1) for row-major and (1,2) for column-major.

• Array data structure
• Matrix representation
• Vectorization (mathematics), the equivalent of turning a matrix into the corresponding column-major vector
• CSR format, a technique for storing sparse matrices in memory
• Morton order, another way of mapping multidimensional data to a one-dimensional index, useful in tree data structures

• Donald E. Knuth, The Art of Computer Programming Volume 1: Fundamental Algorithms, third edition, section 2.2.6 (Addison-Wesley: New York, 1997).