One class of permutations of the integers in the set S n = {0, 1, 2, .

Question:

One class of permutations of the integers in the set Sn = {0, 1, 2, . . . , 2n − 1} is defined by matrix multiplication over GF (2). For each integer x in Sn, we view its binary representation as an n-bit vector

where


If A is an n × n matrix in which each entry is either 0 or 1, then we can define a permutation mapping each value x in Sn to the number whose binary representation is the matrix-vector product Ax. Here, we perform all arithmetic over GF (2): all values are either 0 or 1, and with one exception the usual rules of addition and multiplication apply. The exception is that 1 + 1 = 0. You can think of arithmetic over GF (2) as being just like regular integer arithmetic, except that you use only the least significant bit. As an example, for S2 = {0, 1, 2, 3}, the matrix

defines the following permutation μA: μA(0) = 0, μ(1) = 3, μA(2) = 2, μA(3) = 1. To see why μA(3) = 1, observe that, working in GF (2),

which is the binary representation of 1.

For the remainder of this problem, we work over GF (2), and all matrix and vector entries are 0 or 1. We define the rank of a 0-1 matrix (a matrix for which each entry is either 0 or 1) over GF(2) the same as for a regular matrix, but with all arithmetic that determines linear independence performed over GF(2). We define the range of an n × n 0-1 matrix A by

so that R (A) is the set of numbers in Sn that we can produce by multiplying each value x in Sn by A.

a. If r is the rank of matrix A, prove that |R (A)| = 2r. Conclude that A defines a permutation on Sn only if A has full rank.

For a given n × n matrix A and a given value y ∈ (R.A), we define the preimage of y by

so that P (A, y) is the set of values in Sn that map to y when multiplied by A.

b. If r is the rank of n × n matrix A and y ∈ R (A), prove that |P (A, y)| = 2nr.

Let 0 ≤ m ≤ n, and suppose we partition the set Sn into blocks of consecutive numbers, where the ith block consists of the 2m numbers i2m, i2m + 1, i2m + 2, . . . , (i + 1)2m − 1. For any subset S ⊆ Sn, define B (S, m) to be the set of size-2m blocks of Sn containing some element of S. As an example, when n = 3, m = 1, and S = {1, 4, 5}, then B (S, m) consists of blocks 0 (since 1 is in the 0th block) and 2 (since both 4 and 5 are in block 2).

c. Let r be the rank of the lower left (n−m) × m submatrix of A, that is, the matrix formed by taking the intersection of the bottom n−m rows and the leftmost m columns of A. Let S be any size-2m block of Sn, and let S' = {y : y = Ax for some x ∈ S}. Prove that |B (S' , m)| = 2r and that for each block in B (S' , m), exactly 2mr numbers in S map to that block.

Because multiplying the zero vector by any matrix yields a zero vector, the set of permutations of Sn defined by multiplying by n × n 0-1 matrices with full rank over GF (2) cannot include all permutations of Sn. Let us extend the class of permutations defined by matrix-vector multiplication to include an additive term, so that x ∈ Sn maps to Ax + c, where c is an n-bit vector and addition is performed over GF (2). For example, when

and

we get the following permutation πA, c : πA, c (0) = 2, πA, c (1) = 1, πA, c (2) = 0, πA, c (3) = 3. We call any permutation that maps x ∈ Sn to Ax + c, for some n × n 0-1 matrix A with full rank and some n-bit vector c, a linear permutation.

d. Use a counting argument to show that the number of linear permutations of Sn is much less than the number of permutations of Sn.

e. Give an example of a value of n and a permutation of Sn that cannot be achieved by any linear permutation.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Introduction to Algorithms

ISBN: 978-0262033848

3rd edition

Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

Question Posted: