Editing Transpose (section)

=== Implementation of matrix transposition on computers ===
{{See also|In-place matrix transposition}}
[[File:Row_and_column_major_order.svg|thumb|upright|Illustration of [[row- and column-major order]] ]]
On a [[computer]], one can often avoid explicitly transposing a matrix in [[Random access memory|memory]] by simply accessing the same data in a different order. For example, [[software libraries]] for [[linear algebra]], such as [[BLAS]], typically provide options to specify that certain matrices are to be interpreted in transposed order to avoid the necessity of data movement.

However, there remain a number of circumstances in which it is necessary or desirable to physically reorder a matrix in memory to its transposed ordering. For example, with a matrix stored in [[row- and column-major order|row-major order]], the rows of the matrix are contiguous in memory and the columns are discontiguous. If repeated operations need to be performed on the columns, for example in a [[fast Fourier transform]] algorithm, transposing the matrix in memory (to make the columns contiguous) may improve performance by increasing [[memory locality]].

Ideally, one might hope to transpose a matrix with minimal additional storage. This leads to the problem of transposing an ''n''&nbsp;×&nbsp;''m'' matrix [[in-place]], with [[Big O notation|O(1)]] additional storage or at most storage much less than ''mn''. For ''n''&nbsp;≠&nbsp;''m'', this involves a complicated [[permutation]] of the data elements that is non-trivial to implement in-place. Therefore, efficient [[in-place matrix transposition]] has been the subject of numerous research publications in [[computer science]], starting in the late 1950s, and several algorithms have been developed.