In-situ transposition of m X n matrix

[all at abouthugo.de]

SeqFans,

the problem of the in-situ transposition of a rectangular matrix without
using additional memory locations has been discussed since the late 50s
of the
last century, see e.g.

P. F. Windley, Transposing Matrices in a  digital computer. Computer J.
2, April 1959,
Pages 47-48
The Computer Journal, Volume 2, Issue 1, pp. 47-48: Abstract.
http://www3.oup.co.uk/computer_journal/hdb/Volume_02/Issue_01/

University Mathematical Laboratory, Cambridge, UK

Abstract:
In November 1957 the problem of transposing a matrix in the store of a
computer
was given as an exercise to students taking the Cambridge University
Diploma
in Numerical Analysis and Automatic Computing. The best solution
received was due
to the author, who describes it in this paper, together with some of the
other
methods suggested.

Ignoring the now relevant problem of cache usage in modern processors
the solution requires the determination of the cycle structure of the
permutation
mapping. The theory behind is simple and has been discussed in several
newsgroups discussions, see e.g.
Dave Rusin, <a
href="http://www.mathforum.org/discuss/sci.math/a/m/133543/133544">
Problem with permutation cycles.</a> Posting in newsgroup sci.math

or in
Donald E. Knuth, The Art of Computer Programming, Vol. 1 (3rd ed.)
Fundamental
Algorithms. Addison-Wesley 1997. 
Ch. 1.3.3 Exercise 12: Transposing a rectangular matrix. p. 182, answer
p. 523

Several implementations of transposition algorithms trying to create the
permutation cycles have been published, e.g.

J. Boothroyd, Algorithm 302, Tranpose vector stored array.
Communications of the ACM,
Vol. 10, No. 5, May 1967, Pages 292-293

S. Laflin, M. A. Brebner, Algorithm 380; In-situ tranposition of a
rectangular matrix.
[F1], Communications of the ACM, Vol. 13, No. 5, May 1970, Pages 324-326

file	380
for	matrix transpose
title	In-situ Transposition of a Rectangular Matrix
by	S. Laflin and M. A. Brebner
ref	Comm. ACM 13,5 (May 1970) 324
http://www.netlib.org/toms/380


Norman Brenner, Algorithm 467, Matrix transposition n place [F1]
Communications of the ACM, Vol. 16, Issue 11, Nov 1973, Pages 692-694

Esco G. Cate, David W. Twigg, Algorithm 513 Analysis of In-Situ
Transposition.
ACM Transactions on Mathematical Software, Vol. 3, No. 1, March 1977,
Pages 104-110

file	513
keywords  transposition in place, matrix transposition, permutation
gams	D1b3
title	TRANS
for	in-situ matrix transposition
alg	makes use of the cyclic structure of the transposition mapping
by	E.G. Cate and D.W. Twigg
ref	ACM TOMS 3 (1977) 104-110
#	revision of algorithm 380
http://www.netlib.org/toms/513


The question on the structure of the permutation cycles comes up in
mathematical, graphics and programming newsgroups in regular intervals.

It might therefore be useful to have a few related sequences in the
OEIS. 
- Number of non-singleton cycles: A093055
- Lenght of longest cycle (the lengths of other cycles are divisors of
l_max)
  A093056
- Number of elements that remain fixed besides from first and last:
A093057

Example for 3X7 Matrix written as one-dimensional vector
1st line: before transposition, 2nd line: after transposition

(1  2  3  4  5  6  7)(8  9 10 11 12 13 14)(15 16 17 18 19 20 21)
(1  8 15)(2  9 16)(3 10 17)(4 11 18)(5 12  19)(6 13 20)(7 14 21)

The following exchange cycles have to be performed:
2->4->10->8->2, 3->7->19->15->3, 5->13->17->9->5, 6->16->6,
12->14->20->18->12
11 fixed
4 cycles of length 4 + 1 cycle of length 2
A093055(17)=b(7,3)=5, length of longest cycle: A093056(17)=4,
number of fixed elements besides first and last: A093057(17)=1

Lower triangle T(j,k) read by rows, excluding first row and column
k>1,j>=k
e.g.
a(1)=T(2,2),
a(2)=T(3,2),a(3)=T(3,3),
a(4)=T(4,2),a(5)=T(4,3),a(6)=T(4,4),
a(7)=T(5,2),.......

A093055
Number of cycles with length>1 (non-singleton cycles)
in the in-situ transposition of a rectangular mXn matrix.

 1
 1  3
 2  2  6
 2  2  2 10
 1  1  2  2 15
 1  5  4  2  1 21
 4  2  6 10  2  4 28
 2  8  8  8  2  4  2 36
 1  1  6  2  1  3  6  2 45
 5  7  6  6  5 19  4  8  1 55
 2  4  2  2  2  2 10  2  4  2 66
 2  2 12  8 10 14  6  8  6  2  4 78
 3  5  8  4  1  1 10  6  3  7  2  4 91
 1  7  2  2  1 11 14 12  1  5  2  2  5 105
 6  2 20  2 10 12 18 14 12 22  2 12  6  2 120

Numbers of cycles of length k:
P(k) = (1/k) sum_(d|k) ( mue(k/d) * gcd(n^d-1,m*n-1),
where the sum runs over all divisors d of k and mue is the
Moebius function (from Cate/Twigg article)

Formula for A093055?

A093056
Length of longest cycle in the in situ-transposition of a rectangular
mXn matrix.

 2
 4  2
 3  5  2
 6  6  9  2
10 16 11 14  2
12  4  9 16 40  2
 4 11  5  4 23 20  2
 8  3  6  5 26 15 35  2
18 28  6 42 58 22 13 44  2
 6  8  7 18 12  6 28 21 108 2
11 12 23 29 35 41 12 53 48 65  2
20 18  4 16 10 12 17 14 21 70 60  2
18  8 10 22 82 96 12 50 46 48 83 45  2
28 10 29 36 88 12 8 11 148 40 89 96 90  2
 5 23  3 39  9  9  7 15 13 15 95 33 37 119 2

Formula for A093056?

A093057
Number of matrix elements remaining at fixed position in the in-situ
transposition
of a rectangular m X n matrix (singleton cycles).
Elements (1,1) and (m,n) which always remain at their old position are
not counted.

 0
 0  1
 0  0  2
 0  1  0  3
 0  0  0  0  4
 0  1  2  1  0  5
 0  0  0  0  0  0  6
 0  1  0  3  0  1  0  7
 0  0  2  0  0  2  0  0  8
 0  1  0  1  4  1  0  1  0  9
 0  0  0  0  0  0  0  0  0  0 10
 0  1  2  3  0  5  0  3  2  1  0 11
 0  0  0  0  0  0  0  0  0  0  0  0 12
 0  1  0  1  0  1  6  1  0  1  0  1  0 13
 0  0  2  0  4  2  0  0  2  4  0  2  0  0 14

Formula for T(m,n)=gcd(m-1,n-1)-1


I'll submit the 3 sequences during the next days.
Any comments and suggestions are welcome.

Hugo Pfoertner