How to check whether a permutation is linear? [closed]

savecancel

The question is not well defined.

There are some standard guesses on the road, that make the word "linear" get a sense. This should come in the question. However, since there was a chance to "guess the linearity" in the more complicated example of the permutation mapping (0,1,...,255) to (0,29,142,...) i'll post the code that recovers "linearly" the map.

(Note: There is also a first guess that 256 was a typo, so that we are working over an algebraic structure with $256$ instead of $257$ elements. Both numbers are prime powers and there are chances in both cases to give a sense to the word "linear". There will be further guesses. I am not complaining, but if this is not the answer to the question, this is because the question is interpretable.)

The code in the sequel will do the following:

Let $F$ be the field with two elements. In sage it is GF(2). Let $V=F^{\times 8}$ be the canonical vector space of dimension $8$ over $F$, its elements are column vectors with eight components, the zero of $F$ and the one of $F$. We will identify the set ${0,1,2,\dots,255}$ with the underlying set of $V$ (built out of $V$ by the forgetful functor) in the following way:

Take an integer number in the first set, take its coefficients in base two, they are $0$ or $1$ (in $\mathbb Z$), fill in the data to a vector with eight components, map then on components $0_{\mathbb Z}\to 0_F$ and $1_{\mathbb Z}\to 1_F$.

The sage code for this, starting with $99\in\mathbb Z$ would be:

sage: 99.digits( base=2 )
[1, 1, 0, 0, 0, 1, 1]
sage: 99.digits( base=2, padto=8 )    # even better for us
[1, 1, 0, 0, 0, 1, 1, 0]
sage: vector( GF(2), 99.digits( base=2, padto=8 ) )    # element in vector space
(1, 1, 0, 0, 0, 1, 1, 0)

Conversely, from the above vector we have to lift the components from GF(2) to the integers, applying ZZ on the zero or one of the GF(2), then to use the "right two-powers" to get the number between $0$ and $255$. The function encode will do this in the sequel, we have to write it.

Note that this bijection (at sets level) is not canonical, it is our choice / our guess, the question has to make it specific.

OK, the code now, half of it is copy-pasted:

L = (0, 29, 142, 147, 199, 218, 73, 84, 227, 254, 109, 112, 36, 57, 170, 183, 113, 108, 255, 226, 182, 171, 56, 37, 146, 143, 28, 1, 85, 72, 219, 198, 184, 165, 54, 43, 127, 98, 241, 236, 91, 70, 213, 200, 156, 129, 18, 15, 201, 212, 71, 90, 14, 19, 128, 157, 42, 55, 164, 185, 237, 240, 99, 126, 220, 193, 82, 79, 27, 6, 149, 136, 63, 34, 177, 172, 248, 229, 118, 107, 173, 176, 35, 62, 106, 119, 228, 249, 78, 83, 192, 221, 137, 148, 7, 26, 100, 121, 234, 247, 163, 190, 45, 48, 135, 154, 9, 20, 64, 93, 206, 211, 21, 8, 155, 134, 210, 207, 92, 65, 246, 235, 120, 101, 49, 44, 191, 162, 238, 243, 96, 125, 41, 52, 167, 186, 13, 16, 131, 158, 202, 215, 68, 89, 159, 130, 17, 12, 88, 69, 214, 203, 124, 97, 242, 239, 187, 166, 53, 40, 86, 75, 216, 197, 145, 140, 31, 2, 181, 168, 59, 38, 114, 111, 252, 225, 39, 58, 169, 180, 224, 253, 110, 115, 196, 217, 74, 87, 3, 30, 141, 144, 50, 47, 188, 161, 245, 232, 123, 102, 209, 204, 95, 66, 22, 11, 152, 133, 67, 94, 205, 208, 132, 153, 10, 23, 160, 189, 46, 51, 103, 122, 233, 244, 138, 151, 4, 25, 77, 80, 195, 222, 105, 116, 231, 250, 174, 179, 32, 61, 251, 230, 117, 104, 60, 33, 178, 175, 24, 5, 150, 139, 223, 194, 81, 76)

F = GF(2)
A = matrix( F, 8,8 )

for k in [0..7]:
    A[ : , k ] = column_matrix( F, L[ 2**k ].digits( base=2, padto=8 ) )
print "The matrix A is:"
print A

def encode( c ):
    return sum( [ 2^k * ZZ( c[k] )
                  for k in range(len(c)) ] )

LL = [ encode( A * vector( F, ZZ(j).digits( base=2, padto=8 ) ) )
       for j in range(256) ]
print "Is the constructed list recovering L? %s" % ( LL == list(L) )

Running it we get:

The matrix A is:
[1 0 1 1 1 0 0 0]
[0 1 1 1 0 0 0 1]
[1 1 1 0 0 0 1 1]
[1 1 0 0 0 1 1 1]
[1 0 0 0 1 1 1 0]
[0 0 0 1 1 1 0 1]
[0 0 1 1 1 0 1 1]
[0 1 1 1 0 1 1 1]
Is the constructed list recovering L? True

So in a very conventional way, up to a guessed bijection, the permutation is induced by multiplication with the (symmetric!) matrix $A$ above.

Note:

sage: A.det()
1
sage: A.multiplicative_order()
85

so we expect that the given permutation splits into some cycles of length $85$. (And the $0$ remains $0$.) Indeed, the corresponding permutation can be easily associated, this time using the world of permutations, which want integers $1,2,\dots, 256$, and its order and cycles can be required. Here is the small dialog:

sage: S = SymmetricGroup( 256 )
sage: s = S( [ k+1 for k in L ] )
sage: s.order()
85
sage: for c in s.cycles():
....:     print "Found cycle of order %s" % c.order()
....:     
Found cycle of order 85
Found cycle of order 85
Found cycle of order 85

(A last check: $1+85+85+85=256$. The $1$-cycle corresponds to the zero.)

Note: I tried also to even realize the "linear map" over a ring (or field for optimists), but the natural identification of the above vector space with the polynomial ring $F[X]$ modulo some polynomial could not be performed. The modulus polynomial $f$ should be then recovered from $29=L[1]$ and $72=L[L[1]]$. So that $f$ decodes $29$ and $f^2$ decodes $72$. But then $f^3$... For instance:

sage: R.<X> = PolynomialRing( GF(2) )
sage: f   = R( 29.digits( base=2 ) )
sage: ff  = R( 72.digits( base=2 ) )
sage: fff = R( 63.digits( base=2 ) )
sage: (f^2 - ff).factor()
(X + 1) * (X^7 + X^6 + X^5 + X^4 + X^2 + X + 1)
sage: (f^3 - fff).factor()
X * (X + 1) * (X^5 + X^3 + 1) * (X^5 + X^3 + X^2 + X + 1)

So it seems i am missing the final, ultimative guess.