Row and columnmajor order
In computing, rowmajor order and columnmajor order are methods for storing multidimensional arrays in linear storage such as random access memory.
The difference between the orders lies in which elements of an array are contiguous in memory. In rowmajor order, the consecutive elements of a row reside next to each other, whereas the same holds true for consecutive elements of a column in columnmajor order. While the terms allude to the rows and columns of a twodimensional array, i.e. a matrix, the orders can be generalized to arrays of any dimension by noting that the terms rowmajor and columnmajor are equivalent to lexicographic and colexicographic orders, respectively.
Data layout is critical for correctly passing arrays between programs written in different programming languages. It is also important for performance when traversing an array because modern CPUs process sequential data more efficiently than nonsequential data. This is primarily due to CPU caching which exploits spatial locality of reference.^{[1]} In addition, contiguous access makes it possible to use SIMD instructions that operate on vectors of data. In some media such as magnetictape data storage, accessing sequentially is orders of magnitude faster than nonsequential access.^{[citation needed]}
Explanation and example
The terms rowmajor and columnmajor 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 [math]\displaystyle{ A }[/math], the entry [math]\displaystyle{ a_{1,2} }[/math] 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 rowmajor or columnmajor methods, is thus a matter of convention. The same terminology can be applied to even higher dimensional arrays. Rowmajor grouping starts from the leftmost index and columnmajor from the rightmost index, leading to lexicographic and colexicographic (or colex) orders, respectively.
For example, the array
 [math]\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} }[/math]
could be stored in two possible ways:
Address  Rowmajor order  Columnmajor order 

0  [math]\displaystyle{ \color{Blue} a_{11} }[/math]  [math]\displaystyle{ \color{Blue} a_{11} }[/math] 
1  [math]\displaystyle{ \color{Blue} a_{12} }[/math]  [math]\displaystyle{ \color{Orange} a_{21} }[/math] 
2  [math]\displaystyle{ \color{Blue} a_{13} }[/math]  [math]\displaystyle{ \color{Blue} a_{12} }[/math] 
3  [math]\displaystyle{ \color{Orange} a_{21} }[/math]  [math]\displaystyle{ \color{Orange} a_{22} }[/math] 
4  [math]\displaystyle{ \color{Orange} a_{22} }[/math]  [math]\displaystyle{ \color{Blue} a_{13} }[/math] 
5  [math]\displaystyle{ \color{Orange} a_{23} }[/math]  [math]\displaystyle{ \color{Orange} a_{23} }[/math] 
Programming languages handle this in different ways. In C, multidimensional arrays are stored in rowmajor order, and the array indexes are written rowfirst (lexicographical access order):
Addressx + N_x*y

AccessA[y][x]

Value [math]\displaystyle{ a_{y,x} }[/math] 

0  A[0][0]

[math]\displaystyle{ a_{11} }[/math] 
1  A[0][1]

[math]\displaystyle{ a_{12} }[/math] 
2  A[0][2]

[math]\displaystyle{ a_{13} }[/math] 
3  A[1][0]

[math]\displaystyle{ a_{21} }[/math] 
4  A[1][1]

[math]\displaystyle{ a_{22} }[/math] 
5  A[1][2]

[math]\displaystyle{ a_{23} }[/math] 
On the other hand, in Fortran, arrays are stored in columnmajor order, while the array indexes are still written rowfirst (colexicographical access order):
Addressy + N_y*(x1)

AccessA(y,x)

Value [math]\displaystyle{ a_{y,x} }[/math] 

1  A(1,1)

[math]\displaystyle{ a_{11} }[/math] 
2  A(2,1)

[math]\displaystyle{ a_{21} }[/math] 
3  A(1,2)

[math]\displaystyle{ a_{12} }[/math] 
4  A(2,2)

[math]\displaystyle{ a_{22} }[/math] 
5  A(1,3)

[math]\displaystyle{ a_{13} }[/math] 
6  A(2,3)

[math]\displaystyle{ a_{23} }[/math] 
Note how the use of A[i][j]
with multistep indexing as in C, as opposed to a neutral notation like A(i,j)
as in Fortran, almost inevitably implies rowmajor 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 columnmajor simply because of its notation, and even the above implication could intentionally be circumvented in a new language.)
To use columnmajor order in a rowmajor environment, or vice versa, for whatever reason, one workaround is to assign nonconventional 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 onedimensional 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 rowwise is preferred in rowmajor languages like C and vice versa for columnmajor languages.
Programming languages and libraries
Programming languages or their standard libraries that support multidimensional arrays typically have a native rowmajor or columnmajor storage order for these arrays.
Rowmajor order is used in C/C++/ObjectiveC (for Cstyle arrays), PL/I,^{[4]} Pascal,^{[5]} Speakeasy,^{[citation needed]} and SAS.^{[6]}
Columnmajor order is used in Fortran, MATLAB,^{[7]} GNU Octave, Julia,^{[8]} S, SPLUS,^{[9]} R,^{[10]} Scilab,^{[11]} Yorick, and Rasdaman.^{[12]}
Neither rowmajor nor columnmajor
A typical alternative for dense array storage is to use Iliffe vectors, which typically store pointers to elements in the same row contiguously (like rowmajor order), but not the rows themselves. They are used in (ordered by age): Java,^{[13]} C#/CLI/.Net, Scala,^{[14]} and Swift.
Even less dense is to use lists of lists, e.g., in Python,^{[15]} and in the Wolfram Language of Wolfram Mathematica.^{[16]}
An alternative approach uses tables of tables, e.g., in Lua.^{[17]}
External libraries
Support for multidimensional arrays may also be provided by external libraries, which may even support arbitrary orderings, where each dimension has a stride value, and rowmajor or columnmajor are just two possible resulting interpretations.
Rowmajor order is the default in NumPy^{[18]} (for Python).
Columnmajor order is the default in Eigen^{[19]} and Armadillo(both for C++).
A special case would be OpenGL (and OpenGL ES) for graphics processing. Since "recent mathematical treatments of linear algebra and related fields invariably treat vectors as columns," designer Mark Segal decided to substitute this for the convention in predecessor IRIS GL, which was to write vectors as rows; for compatibility, transformation matrices would still be stored in vectormajor (=rowmajor) rather than coordinatemajor (=columnmajor) order, and he then used the trick "[to] say that matrices in OpenGL are stored in columnmajor order".^{[20]} This was really only relevant for presentation, because matrix multiplication was stackbased and could still be interpreted as postmultiplication, but, worse, reality leaked through the Cbased API because individual elements would be accessed as M[vector][coordinate]
or, effectively, M[column][row]
, which unfortunately muddled the convention that the designer sought to adopt, and this was even preserved in the OpenGL Shading Language that was later added (although this also makes it possible to access coordinates by name instead, e.g., M[vector].y
). As a result, many developers will now simply declare that having the column as the first index is the definition of columnmajor, even though this is clearly not the case with a real columnmajor language like Fortran.
Torch (for Lua) changed from columnmajor^{[21]} to rowmajor^{[22]} default order.
Transposition
As exchanging the indices of an array is the essence of array transposition, an array stored as rowmajor but read as columnmajor (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]}
Address calculation in general
The concept generalizes to arrays with more than two dimensions.
For a ddimensional [math]\displaystyle{ N_1 \times N_2 \times \cdots \times N_d }[/math] array with dimensions N_{k} (k=1...d), a given element of this array is specified by a tuple [math]\displaystyle{ (n_1, n_2, \ldots, n_d) }[/math] of d (zerobased) indices [math]\displaystyle{ n_k \in [0,N_k  1] }[/math].
In rowmajor order, the last dimension is contiguous, so that the memoryoffset of this element is given by: [math]\displaystyle{ n_d + N_d \cdot (n_{d1} + N_{d1} \cdot (n_{d2} + N_{d2} \cdot (\cdots + N_2 n_1)\cdots))) = \sum_{k=1}^d \left( \prod_{\ell=k+1}^d N_\ell \right) n_k }[/math]
In columnmajor order, the first dimension is contiguous, so that the memoryoffset of this element is given by: [math]\displaystyle{ n_1 + N_1 \cdot (n_2 + N_2 \cdot (n_3 + N_3 \cdot (\cdots + N_{d1} n_d)\cdots))) = \sum_{k=1}^d \left( \prod_{\ell=1}^{k1} N_\ell \right) n_k }[/math] where the empty product is the multiplicative identity element, i.e., [math]\displaystyle{ \prod_{\ell=1}^{0} N_\ell = \prod_{\ell=d+1}^{d} N_\ell = 1 }[/math].
For a given order, the stride in dimension k is given by the multiplication value in parentheses before index n_{k} in the righthand side summations above.
More generally, there are d! possible orders for a given array, one for each permutation of dimensions (with rowmajor and columnorder just 2 special cases), although the lists of stride values are not necessarily permutations of each other, e.g., in the 2by3 example above, the strides are (3,1) for rowmajor and (1,2) for columnmajor.
See also
 Array data structure
 Matrix representation
 Vectorization (mathematics), the equivalent of turning a matrix into the corresponding columnmajor vector
 CSR format, a technique for storing sparse matrices in memory
 Morton order, another way of mapping multidimensional data to a onedimensional index, useful in tree data structures
References
 ↑ "Cache Memory". http://pld.cs.luc.edu/courses/264/spr19/notes/cache.html.
 ↑ "Arrays and Formatted I/O". http://www.fortrantutorial.com/arraysformattedio/index.php.
 ↑ "Why numbering should start at zero". https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html.
 ↑ "Language Reference Version 4 Release 3". IBM. https://www.ibm.com/support/knowledgecenter/SSQ2R2_9.0.0/com.ibm.ent.pl1.zos.doc/topics/lrm.pdf. "Initial values specified for an array are assigned to successive elements of the array in rowmajor order (final subscript varying most rapidly)."
 ↑ "ISO/IEC 7185:1990(E)". http://www.pascalcentral.com/docs/iso7185.pdf. "An arraytype that specifies a sequence of two or more indextypes shall be an abbreviated notation for an arraytype specified to have as its indextype the first indextype in the sequence and to have a componenttype that is an arraytype specifying the sequence of indextypes without the first indextype in the sequence and specifying the same componenttype as the original specification."
 ↑ "SAS® 9.4 Language Reference: Concepts, Sixth Edition". SAS Institute Inc.. September 6, 2017. p. 573. http://documentation.sas.com/api/docsets/lrcon/9.4/content/lrcon.pdf. "From right to left, the rightmost dimension represents columns; the next dimension represents rows. [...] SAS places variables into a multidimensional array by filling all rows in order, beginning at the upper left corner of the array (known as rowmajor order)."
 ↑ MATLAB documentation, MATLAB Data Storage (retrieved from Mathworks.co.uk, January 2014).
 ↑ "Multidimensional Arrays". https://docs.julialang.org/en/v1/manual/arrays/.
 ↑ (Spiegelhalter Thomas): Spiegelhalter, David; Thomas, Andrew; Best, Nicky; Lunn, Dave (January 2003), "Formatting of data: SPlus format", WinBUGS User Manual (Version 1.4 ed.), Cambridge, UK: MRC Biostatistics Unit, Institute of Public Health, http://www.mrcbsu.cam.ac.uk/bugs/winbugs/manual14.pdf
 ↑ An Introduction to R, Section 5.1: Arrays (retrieved March 2010).
 ↑ "FFTs with multidimensional data". https://wiki.scilab.org/howto/FFTMultidimensionalData. "Because Scilab stores arrays in column major format, the elements of a column are adjacent (i.e. a separation of 1) in linear format."
 ↑ "Internal array representation in rasdaman". https://rasdaman.org/wiki/RasdamanInternalArrayRepresentation.
 ↑ "Java Language Specification". Oracle. https://docs.oracle.com/javase/specs/jls/se7/html/jls10.html.
 ↑ "object Array". http://www.scalalang.org/api/current/#scala.Array$.
 ↑ "The Python Standard Library: 8. Data Types". https://docs.python.org/3.6/library/datatypes.html.
 ↑ "Vectors and Matrices". http://reference.wolfram.com/language/tutorial/VectorsAndMatrices.html.
 ↑ "11.2 – Matrices and MultiDimensional Arrays". http://www.lua.org/pil/11.2.html.
 ↑ "The Ndimensional array (ndarray)". http://docs.scipy.org/doc/numpy/reference/arrays.ndarray.html.
 ↑ "Eigen: Storage orders". https://eigen.tuxfamily.org/dox/group__TopicStorageOrders.html. "If the storage order is not specified, then Eigen defaults to storing the entry in columnmajor."
 ↑ "Column Vectors Vs. Row Vectors". http://steve.hollasch.net/cgindex/math/matrix/columnvec.html.
 ↑ "Tensor". http://torch5.sourceforge.net/manual/torch/index6.html.
 ↑ "Tensor". https://github.com/torch/torch7/blob/master/doc/tensor.md#storagestorage.
 ↑ "BLAS (Basic Linear Algebra Subprograms)". http://www.netlib.org/blas/.
Sources
 Donald E. Knuth, The Art of Computer Programming Volume 1: Fundamental Algorithms, third edition, section 2.2.6 (AddisonWesley: New York, 1997).
Original source: https://en.wikipedia.org/wiki/Row and columnmajor order.
Read more 