Return to Question

• It is bijective, that means reversible: It is a linear transformation under the matrix [[2,1],[1,1]]. Since it has determinant 1 and and it has only integer entries, the inverse also has integer entries and is given by [[1,-1],[-1,2]], this means it is also bijective on integer coordinates.

• It is a torsion element of the group of bijective maps of N x N images, that means if you apply it sufficiently many times, you will get the original image back: f(f(...f(x)...)) = x The amount of times the map applied to itself results in the identity is guaranteed to be less or equal to 3*N. In the following you can see the image of a cat after a given number of iterated applications of Arnold's cat map, and an animation of what a repeated application looks like:

As image (bottom left is (0,0))

• It is bijective, that means reversible: It is a linear transformation with the matrix [[2,1],[1,1]]. Since it has determinant 1 and and it has only integer entries, the inverse also has only integer entries and is given by [[1,-1],[-1,2]], this means it is also bijective on integer coordinates.

• It is a torsion element of the group of bijective maps of N x N images, that means if you apply it sufficiently many times, you will get the original image back: f(f(...f(x)...)) = x The amount of times the map applied to itself results in the identity is guaranteed to be less or equal to 3*N. In the following you can see the image of a cat after a given number of iterated applications of Arnold's cat map, and an animation of what a repeated application looks like:

As image (bottom left is (0,0)):

• Your program does not necessarily have to deal with images, but 2D-arrays/matrices, strings or similar 2D-structures are acceptable too.

• It does not matter whether your (0,0) point is on the bottom left or on the top left. (Or in any other corner, if this is more convenient in your language.)

• Your program does not necessarily have to deal with images, but 2D-arrays/matrices, strings or similar 2D-structures are acceptable too.

• It does not matter whether your (0,0) point is on the bottom left or on the top left. (Or in any other corner, if this is more convenient in your language.) Please specify what convention you use in your submission.

In matrix form ([1,2,3,4] is the top row, 1 has index (0,0), 2 has index (1,0))

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

maps to:

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

In matrix form ([1,2,3,4] is the top row, 1 has index (0,0), 2 has index (1,0), 5 has index (0,1))

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

maps to:

 1    14    11     8
12     5     2    15
 3    16     9     6
10     7     4    13
          
 --------------------
        
 1     2     3
 4     5     6
 7     8     9

 map to:

 1     8     6
 9     4     2
 5     3     7

As image (bottom left is (0,0))