4 Permutation Matrices Associated to Bent Functions
93
and the corresponding permutation matrix is
P f 1 =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
The permutation represented by this permutation matrix can also be represented as
a product of cycles as follows:
P = (5)(0, 15, 10)(1, 13, 3, 4, 7, 12)(2, 6, 14, 8, 9, 11),
which leads to a factorization with three sparse matrices.
4.6 Structure of Gibbs Permutation Matrices
In this section, we specify requirements that should be satisfied in order that a (2 n ×
2 n ) permutation matrix, where n is a natural number, be a Gibbs permutation matrix.
Each Gibbs permutation matrix is composed of the following five submatrices:
A =
0 0
0 1
, B =
0 1
0 0
, C =
0 0
1 0
, D =
1 0
0 0
, 0 =
0 0
0 0
.
Except the zero submatrix 0, each submatrix appears 2 (n−2) times in the (2 n × 2 n )
Gibbs permutation matrix.