94
R. S. Stankovi´ c et al.
Being a permutation matrix, the single non-zero element should be in each
row and column which determines the possible distribution of these submatrices
within a Gibbs permutation matrix. Therefore, the following requirements should
be satisfied:
1. No two identical submatrices can appear in the same row or column except for
the submatrix 0. Therefore, no AA, or BB, or CC, or DD in the same row or
column,
2. No two A and C in the same row,
3. No two B and D in the same row,
4. No two A and B in the same column,
5. No two C and D in the same column,
6. Allowed combinations of submatrices are A, B, and C, D for rows and A, C, and
B, D for columns.
An additional requirement is that each four of these different non-zero submatrices should be placed in such a way that form vertices of a rectangle. In each
rectangle, the position of the vertices should be such that the componentwise sum
of binary representations of the coordinates should be the zero 2(n − 1)-tuple. In
other words, if a i,j , b i,j , c i,j , and d i,j are elements of the submatrices A, B, C, and
D, then it should be
a 00 ⊕ b 00 ⊕ c 00 ⊕ d 00 = 0,
a 01 ⊕ b 01 ⊕ c 01 ⊕ d 01 = 0,
a 10 ⊕ b 10 ⊕ c 10 ⊕ d 10 = 0,
a 11 ⊕ b 11 ⊕ c 11 ⊕ d 11 = 0.
These requirements specified above determine the structure of the Gibbs permutation matrices and they are necessary and sufficient conditions for a (2 n × 2 n )
permutation matrix to be a Gibbs permutation matrix.
Example 4.7 Figure 4.1 shows a permutation matrix for the function specified by
the (0, 1) → (1, −1) encoded function vector
F 2 = [1, 1, 1, −1, 1, −1, 1, 1, 1, −1, −1, −1, 1, 1, −1, 1]
T ,
with rectangles. The coordinates of matrix elements in their vertices are
a 00 = 000|011, b 00 = 001|000, c 00 = 100|001, d 00 = 101|010,
a 01 = 000|100, b 01 = 001|111, c 01 = 100|110, d 01 = 101|101,
a 10 = 010|011, b 10 = 011|000, c 10 = 110|001, d 10 = 111|010,
a 00 = 010|100, b 11 = 011|111, c 11 = 110|110, d 11 = 111|101.
R. S. Stankovi´ c et al.
Being a permutation matrix, the single non-zero element should be in each
row and column which determines the possible distribution of these submatrices
within a Gibbs permutation matrix. Therefore, the following requirements should
be satisfied:
1. No two identical submatrices can appear in the same row or column except for
the submatrix 0. Therefore, no AA, or BB, or CC, or DD in the same row or
column,
2. No two A and C in the same row,
3. No two B and D in the same row,
4. No two A and B in the same column,
5. No two C and D in the same column,
6. Allowed combinations of submatrices are A, B, and C, D for rows and A, C, and
B, D for columns.
An additional requirement is that each four of these different non-zero submatrices should be placed in such a way that form vertices of a rectangle. In each
rectangle, the position of the vertices should be such that the componentwise sum
of binary representations of the coordinates should be the zero 2(n − 1)-tuple. In
other words, if a i,j , b i,j , c i,j , and d i,j are elements of the submatrices A, B, C, and
D, then it should be
a 00 ⊕ b 00 ⊕ c 00 ⊕ d 00 = 0,
a 01 ⊕ b 01 ⊕ c 01 ⊕ d 01 = 0,
a 10 ⊕ b 10 ⊕ c 10 ⊕ d 10 = 0,
a 11 ⊕ b 11 ⊕ c 11 ⊕ d 11 = 0.
These requirements specified above determine the structure of the Gibbs permutation matrices and they are necessary and sufficient conditions for a (2 n × 2 n )
permutation matrix to be a Gibbs permutation matrix.
Example 4.7 Figure 4.1 shows a permutation matrix for the function specified by
the (0, 1) → (1, −1) encoded function vector
F 2 = [1, 1, 1, −1, 1, −1, 1, 1, 1, −1, −1, −1, 1, 1, −1, 1]
T ,
with rectangles. The coordinates of matrix elements in their vertices are
a 00 = 000|011, b 00 = 001|000, c 00 = 100|001, d 00 = 101|010,
a 01 = 000|100, b 01 = 001|111, c 01 = 100|110, d 01 = 101|101,
a 10 = 010|011, b 10 = 011|000, c 10 = 110|001, d 10 = 111|010,
a 00 = 010|100, b 11 = 011|111, c 11 = 110|110, d 11 = 111|101.