Jonathan. Frech’s WebBlog

Visualizing cycles in row-major transposition encodings (#239)

Jonathan Frech

A matrix $A\in \mathcal{D}^{h\times w}$$A\in \mathcal{D}^{h\times w}$ of discretely representable entries $\mathcal{D}$$\mathcal{D}$ may be linearly layed out in memory using row-major order, concatenating successive rows into a contiguous $(h\cdot w \cdot\texttt{sizeof}\,\mathcal{D})$$(h\cdot w \cdot\texttt{sizeof}\,\mathcal{D})$-bytes long array. Such a rep­re­sent­ation, however, is disruptive to the matrix’ two-di­men­sion­al nature: whilst horizontally neighboring elements remain neighbors, vertically neighboring entries are torn apart by insertion of $w$$w$ non-neighboring elements. As such, on matrices naturally defined operations get distorted by this encoding.
One such inherently two-di­men­sion­al operation is matrix transposition. In the realm of matrices, $\mathcal{D}^{h\times w}\neq\mathcal{D}^{w\times h}$$\mathcal{D}^{h\times w}\neq\mathcal{D}^{w\times h}$ are for nonsquare dimensions semantically different, being mapped to one another by transposition. Projecting onto their encoding, this semantic is lost and one is left with a permutation on memory $\bullet^\top\in\mathrm{Sym}(\{1,\dots,hw\})$$\bullet^\top\in\mathrm{Sym}(\{1,\dots,hw\})$.
To visualize this permutation, its cycle decomposition is computed of which each cycle is given a color of the rainbow dyeing this cycle’s corresponding two-di­men­sion­al pixels when interpreting its path on the underlying array in the semantics of the original matrix.

Initial transposition cycles

Above listed are all visualizations for $1\leq h\leq 8,1\leq w\leq 16$$1\leq h\leq 8,1\leq w\leq 16$, shuffled. Whilst some behave extremely regularly — for example square matrices’ transposition permutations decompose into transpositions —, others are wildly intricate. Each of them adheres to a rotational symmetry; the top left and bottom right are fixed points.

-=-

Number of cycles required

When looking at the gen­er­ated images, one may notice how some dimensions require on­ly a few cycles to span the en­tire permutation. For studying the num­ber of required cycles — notationally $\mu(h,w)$$\mu(h,w)$ —, the following table is computed:

h\w |   1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16  
---------------------------------------------------------------------------------------------------
  1 |   1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16   
  2 |   2     3     3     4     4     3     3     6     4     3     7     4     4     5     3     8   
  3 |   3     3     6     4     5     3     8     4    11     3    10     6     5     7    10     4   
  4 |   4     4     4    10     4     4     8     8    10    10     8     4    16    10     4    24   
  5 |   5     4     5     4    15     4     5    12    13     4     9     4    13     6     5     4   
  6 |   6     3     3     4     4    21     3     4     4     3    11     4    12     3     3    16   
  7 |   7     3     8     8     5     3    28     6     7     7    22     4    21     3    14    16   
  8 |   8     6     4     8    12     4     6    36     4     8     6    12     8    12    22    20

$\mu$$\mu$ is symmetric in its arguments. In the case of square dimensions $h=w=k$$h=w=k$ one immediately sees

$$\mu(k,k)=k^2-\mathrm{A000217}(k-1)=k^2-\sfrac 12\,k(k-1)=\sfrac 12\,(k^2+k)$$$$\mu(k,k)=k^2-\mathrm{A000217}(k-1)=k^2-\sfrac 12\,k(k-1)=\sfrac 12\,(k^2+k)$$

and the largest non-square-di­men­sion­al value of $\mu$$\mu$ in the above table is $\mu(16,4)=24$$\mu(16,4)=24$ with accompanying visulization pngs/h004-w016.png.

Implementation

Computation of the permutations, $\mu$$\mu$-table and creation of source .ppm files is im­ple­ment­ed in C++. Targeting the web necessitates usage of another image file format, thus zsh glue together with ImageMagick is used for .png conversion.

Source files: visualizing-cycles-in-row-major-transposition-encodings.cpp, visualizing-cycles-in-row-major-transposition-encodings.zsh