hp
toc

Visualizing cycles in row-major transposition encodings

2021-01-23, post № 239

mathematics, programming, c++, shell, #matrix, #encoding, #permutation, #rainbow

A matrix A\in \mathcal{D}^{h\times w} of discretely representable entries \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})-bytes long array. Such a representation, however, is disruptive to the matrix’ two-dimensional nature: whilst horizontally neighboring elements remain neighbors, vertically neighboring entries are torn apart by insertion of w non-neighboring elements. As such, on matrices naturally defined operations get distorted by this encoding.
One such inherently two-dimensional operation is matrix transposition. In the realm of matrices, \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\}).
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-dimensional 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, 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 generated images, one may notice how some dimensions require only a few cycles to span the entire permutation. For studying the number of required cycles — notationally \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 is symmetric in its arguments. In the case of square dimensions 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)

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

Implementation

Computation of the permutations, \mu-table and creation of source .ppm files is implemented 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

Jonathan Frech's blog; built 2024/08/31 22:59:44 CEST