As proved by Cate & Twigg (1977), the number of fixed points (cycles of length 1) of the permutation is precisely , where gcd is the greatest common divisor. For example, with N = M the number of fixed points is simply N (the diagonal of the matrix). If and are coprime, on the other hand, the only two fixed points are the upper-left and lower-right corners of the matrix. The number of cycles of any length k>1 is given by (Cate & Twigg, 1977): where μ is the Möbius function and the sum is over the divisors d of k. Furthermore, the cycle containing a=1 (i.e. the second element of the first row of the matrix) is always a cycle of maximum length L, and the lengths k of all other cycles must be divisors of L (Cate & Twigg, 1977). For a given cycle C, every element has the same greatest common divisor . Let s be the smallest element of the cycle, and . From the definition of the permutation P above, every other element x of the cycle is obtained by repeatedly multiplying s by N modulo MN−1, and therefore every other element is divisible by d. But, since N and are coprime, x cannot be divisible by any factor of larger than d, and hence . This theorem is useful in searching for cycles of the permutation, since an efficient search can look only at multiples of divisors of MN−1 (Brenner, 1973). Laflin & Brebner (1970) pointed out that the cycles often come in pairs, which is exploited by several algorithms that permute pairs of cycles at a time. In particular, let s be the smallest element of some cycle C of length k. It follows that MN−1−s is also an element of a cycle of length k (possibly the same cycle). The length k of the cycle containing s is the smallest k > 0 such that . Clearly, this is the same as the smallest k>0 such that , since we are just multiplying both sides by −1, and . Algorithms The following briefly summarizes the published algorithms to perform in-place matrix transposition. Source code implementing some of these algorithms can be found in the references, below. Accessor transpose Because physically transposing a matrix is computationally expensive, instead of moving values in memory, the access path may be transposed instead. It is trivial