# A Mathematical Design of Genetic Operators onG

Authors: Yourim Yoon; Yong-Hyuk Kim
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We study the space that consists of all nonsingular binary matrices, that is,G
L
n
(
ℤ
2
). The space is quite important in that it is used for the change of basis in binary representation, which is the encoding typically adopted in genetic algorithms. We analyze the properties of G
L
n
(
ℤ
2
) and theoretically design possible encodings and their corresponding recombination operators for evolutionary algorithms. We present approaches based on elementary matrices
of linear algebra as well as typical two-dimensional ones.


---

## Body

## 1. Introduction

Ann
×
n matrix A is called binary if A
∈
M
n
×
n
(
ℤ
2
) [1]. Binary matrices have been widely used to deal with the adjacency of a graph [2–5]. In particular, Anderson and Feil [2] transformed the light bulb puzzle into the problem of solving a linear system A
x
=
b from its graph structure, where A
∈
M
n
×
n
(
ℤ
2
) and x
,
b
∈
ℤ
2
n. Then the solution could be obtained by computing the inverse of A, that is, x
=
A
-
1
b. Binary matrices are also useful in dealing with the cut/cycle subspace of a graph, which is a vector space over ℤ
2 [3, 6]. They can also be used to represent a change of basis of a vector space over ℤ
2 in combinatorial problems [7, 8]. A change of basis plays an important role in the performance of evolutionary algorithms [8–12]. It can be represented as a nonsingular matrix, and hence we need to consider the space composed of all nonsingular binary matrices. In this paper, we investigate the space of nonsingular binary matrices, G
L
n
(
ℤ
2
). Table 1 shows the sizes of spaces according to small n. The size of M
n
×
n
(
ℤ
2
) is 2
n
2. Those of G
L
n
(
ℤ
2
) in Table 1 are obtained by an exhaustive search over M
n
×
n
(
ℤ
2
). Each matrix in M
n
×
n
(
ℤ
2
) is verified whether it is singular or nonsingular by Gauss-Jordan elimination. |
G
L
n
(
ℤ
2
)
| grows exponentially as matrix size n increases.Table 1
The sizes of spacesM
n
×
n
(
ℤ
2
) and G
L
n
(
ℤ
2
) according to matrix size n.
n
|
M
n
×
n
(
ℤ
2
)
|
|
G
L
n
(
ℤ
2
)
|
2
16 (=24)
6
3
512 (=29)
168
4
65,536 (=216)
20,160
5
33,554,432 (=225)
9,999,360In this paper, we focus on the mathematical designs of encodings and their corresponding recombination operators inG
L
n
(
ℤ
2
) for evolutionary algorithms. The remainder of this paper is organized as follows. In Section 2, typical 2D encoding and recombination operators, in which we can intuitively and easily devise, are introduced. In advance of the typical 2D approaches, ones using elementary matrices of linear algebra are presented in Section 3. In Section 3.1, we introduce the elementary matrix of M
n
×
n
(
ℤ
2
) as a preliminary. If we represent a nonsingular binary matrix as a product of elementary matrices, the feasibility of offspring is naturally preserved. As representation based on the product of elementary matrices, we propose the representation by a variable-length linear string in Section 3.2 and that by directed acyclic graph in Section 3.3. When we consider a nonsingular matrix as a product of elementary matrices, the representation is not unique. Moreover, it is not so easy to know how many equivalent representations exist for a nonsingular binary matrix. In Section 3.4, nontrivial equivalences are investigated to help analyze the same genotypes for a phenotype. Finally, we give our conclusions in Section 4.


## 2. Approaches Based on 2D Encoding

The most intuitive and natural representation for a nonsingular binary matrix is 2Dn
×
n binary encoding. Or more simply, we can use just length-n
2 binary linear string. When using linear encoding, we can adopt traditional genetic operators such as n-point crossover and uniform crossover for recombination operators.However, a 2D encoding/crossover pair can reflect more geographical linkages of genes than 1D encoding/crossover pairs [13]. Cohoon and Paris [14] proposed a 2D crossover which chooses a small rectangle from one parent and copies the genes in the rectangle into the offspring, with the rest of the genes copied from the other parent. Anderson et al. [15] suggested the block-uniform crossover on n
×
n grid. It divides the grid into i
×
j blocks at random; each block of one parent is interchanged randomly with the corresponding block of the other parent based on a preassigned percentage.Although 2D encoding can preserve more geographical relationships among the genes, when traditional straight-line-based cutting strategies are used, the power of new-schema creation is far below that of the crossovers on linear encodings [16].Geographic crossover was suggested to resolve this problem [13, 16, 17]. In the case of a 2D encoding, it chooses a number of monotonic lines, divides the chromosomal domain into two equivalence classes, and alternately copies the genes from the two parent chromosomes. Figure 1 shows an example using geographic crossover in 2D encoding of binary matrices. By combining 2D representation and geographic crossover, we can expect both reduced information loss in the stage of encoding and the power of new-schema creation.An example of typical 2D approach.H
(
P
1
,
P
2
)
=
5, H
(
P
1
,
O
)
=
6, and H
(
P
2
,
O
)
=
3, where H is the Hamming distance on typical 2D binary encoding. An offspring that is quite different from parents is generated by recombination operator.
(a)
Parent 1 (P
1)
(b)
Parent 2 (P
2)
(c)
An offspring generated by geographic crossover fromP
1 and P
2 (not invertible, i.e., infeasible)
(d)
Repaired offspringO of (c) (invertible, i.e., feasible)However, an inevitable defect of this typical 2D approach is that it needs feasibility check and repair mechanism. We can see an example case from Figure1(c). In this case, the offspring is not invertible. One of the possible repair mechanisms is finding maximal linearly independent rows (or columns)—this can be conducted by Gauss-Jordan elimination—and replacing linearly dependent rows/columns by other available basis elements (see Figure 1(d)). Algorithm 1 shows the repair mechanism. But it is too time consuming since Gauss-Jordan elimination takes O
(
n
3
) time.Algorithm 1:An algorithm for repairing offspring generated by typical 2D approach.
RepairBinaryMatrix(M
=
(
m
i
j
))
{
// Letm
i be the ith row vector of M, that is, M
T
=
(
m
1
m
2
…
m
n
).
// LetI be the identity matrix, where I
T
=
(
e
1
e
2
…
e
n
).
J
←
{
1,2
,
…
,
n
};
K
←
∅;
R
←
∅;
for  each m
i, i
∈
J // use the process of Gauss-Jordan elimination
if  m
i
≠
0 and m
i is not spanned by R  then
R
←
R
∪
{
m
i
};
K
←
K
∪
{
i
};
// Then,R becomes the set of maximal linearly-independent row vectors.
S
←
∅;
for  each e
i, i
∈
J
if  e
i is not spanned by R  then
S
←
S
∪
{
e
i
};
for each i
∈
J
-
K
r
← any element in S;
S
←
S
-
{
r
};
m
i
←
r; // repairing m
i
return  M
=
(
m
i
j
);
}


## 3. Approaches Based on Elementary Matrices

In this section, we propose novel methods inspired by the fact that all the invertible matrices can be represented as products of elementary matrices [18].


### 3.1. Elementary Matrix inM
n
×
n
(
ℤ
2
)

Before introducing the elementary matrix ofM
n
×
n
(
ℤ
2
), we define elementary row operation.Definition 1.
LetA
∈
M
n
×
n
(
ℤ
2
). Any one of the following two operations on the rows of A is called an  elementary row operation: (i)
interchanging any two rows ofA and
(ii)
adding a row ofA to another row.Elementary row operations are oftype 1 or type 2 depending on whether they are obtained by (i) or (ii) of Definition 1. An n
×
n
elementary matrix over ℤ
2 field is a matrix obtained by performing an elementary row operation on the identity matrix I
n. The elementary matrix is said to be of type 1 or type 2 according to whether the elementary row operation performed on I
n is of type 1 or type 2, respectively. We can easily check the following property.Proposition 2.
For each elementary matrixE
∈
M
n
×
n
(
ℤ
2
), E
2
=
I
n, where I
n is the identity matrix.Proof.
It is trivial for the cases of type 1. Since1
+
1
=
0 and 0
+
0
=
0 in ℤ
2, m
+
m
=
0 for any row vector m. Hence, the identity also holds in the cases of type 2.We defineS
n
i
j as the elementary matrix of type 1 that interchanges the ith row and the jth one (i
≠
j). We also define A
n
i
j as the elementary matrix of type 2 that adds the ith row to the jth one (i
≠
j). For example, consider 3
×
3 cases; that is, n
=
3. There are three elementary matrices of type 1, S
3
12, S
3
13, and S
3
23:
(1)
S
3
12
=
(
0
1
0
1
0
0
0
0
1
)
,
S
3
13
=
(
0
0
1
0
1
0
1
0
0
)
,
S
3
23
=
(
1
0
0
0
0
1
0
1
0
)
.
And there are six elementary matrices of type 2, A
3
12, A
3
13, A
3
21, A
3
23, A
3
31, and A
3
32:
(2)
A
3
12
=
(
1
0
0
1
1
0
0
0
1
)
,
A
3
13
=
(
1
0
0
0
1
0
1
0
1
)
,
A
3
21
=
(
1
1
0
0
1
0
0
0
1
)
,
A
3
23
=
(
1
0
0
0
1
0
0
1
1
)
,
A
3
31
=
(
1
0
1
0
1
0
0
0
1
)
,
A
3
32
=
(
1
0
0
0
1
1
0
0
1
)
.Proposition 3.
The number of elementary matrices inM
n
×
n
(
ℤ
2
) is 3
n
(
n
-
1
)
/
2. In detail, let S
n and A
n be the sets of all elementary matrices of type 1 and of type 2 in M
n
×
n
(
ℤ
2
), respectively. Then, |
S
n
|
=
n
(
n
-
1
)
/
2 and |
A
n
|
=
n
(
n
-
1
).Proof.
SinceS
n
i
j
=
S
n
j
i for each (
i
,
j
) pair, S
n
=
{
S
n
i
j
∣
1
≤
i
<
j
≤
n
}. Since A
n
i
j
≠
A
n
j
i for each (
i
,
j
) pair, A
n
=
{
A
n
i
j
∣
1
≤
i
≤
n
,
1
≤
j
≤
n
,
i
≠
j
}.It is known that every invertible matrix is represented as a product of elementary matrices [18]. Hence, if we represent a solution in G
L
n
(
ℤ
2
) as a product of elementary matrices, we get a big advantage of preserving feasibility.


### 3.2. Variable-Length Linear String

In the case of using elementary matrices, we can consider the representation by variable-length linear string, of which each element is an elementary matrix. MatrixP
1 in Figure 1(a) is S
4
12
A
4
34
S
4
24
A
4
13
S
4
14 when represented as a product of elementary matrices. Similarly, matrix P
2 in Figure 1(b) becomes A
4
34
S
4
12
A
4
24
S
4
14. So their new encodings are given in Figure 2(a).Figure 2
An example of variable-length string.H
(
P
1
,
P
2
)
=
5, (
P
1
,
O
)
=
3, and H
(
P
2
,
O
)
=
2, where H is the Hamming distance on typical 2D binary encoding. d
e
(
P
1
,
P
2
)
=
5, d
e
(
P
1
,
O
)
=
2, and d
e
(
P
2
,
O
)
=
3, where d
e is the edit distance in that insertion, deletion, and replacement have weights of 1, 1, and 2, respectively.As recombination operators for this encoding, any recombinations for variable-length string can be used. Among such recombination operators,geometric crossover [19–24] by sequence alignment [25–27] is expected to be effectively performed. The string can be regarded as a sequence having the fixed number of elementary matrices. Geometric crossover by sequence alignment will be helpful for offspring to preserve features inherent in parents.As a distance for variable-length string, there isedit distance
d
e: the minimum number of insertion, deletion, and replacement of single elementary matrix to transform one string into the other. The geometric crossover associated with this distance is called the homologous geometric crossover [25]: two strings are aligned optimally before recombination. Alignment here means allowing parent strings to be stretched to match better with each other. Formally stretching strings means interleaving “—” anywhere and in any number in the strings to create two stretched strings of the same length that have minimal Hamming distance. In our example, when we recombine S
4
12
A
4
34
S
4
24
A
4
13
S
4
14 and A
4
34
S
4
12
A
4
24
S
4
14, we need to align them optimally first: S
4
12
A
4
34
S
4
24
A
4
13
S
4
14 and -
A
4
34
S
4
12
A
4
24
S
4
14 (see Figure 2(b)). Notice that the Hamming distance between the aligned strings is less than that between the nonaligned ones.After the optimal alignment, one does the normal crossover and produces a newstretched string. The offspring is obtained by removing “—”, so by unstretching the string (see Figure 2
(
c
)). In the example of Figure 2, we can easily check d
e
(
P
1
,
P
2
)
=
d
e
(
P
1
,
O
)
+
d
e
(
O
,
P
2
).Now we assume that insertion, deletion, and replacement have weights of 1, 1, and 2 in edit distanced
e, respectively. Then, when E
1
≠
E
2
∈
M
n
×
n
(
ℤ
2
), d
e
(
E
1
,
E
2
)
=
2 and d
e
(
E
1
E
2
,
E
2
E
2
)
=
d
e
(
E
1
E
2
,
I
n
)
=
2. In general, the following proposition holds.Proposition 4.
LetA, B, C be in G
L
n
(
ℤ
2
). Then d
e
(
A
,
B
)
=
d
e
(
A
C
,
B
C
)
=
d
e
(
C
A
,
C
B
); that is, d
e is translation-invariant.Proof.
LetE be an elementary matrix in M
n
×
n
(
ℤ
2
). By the definition of edit distance d
e, d
e
(
A
E
,
B
E
)
≤
d
e
(
A
,
B
). Here the equality holds when the last elementary matrices of A
E and B
E are aligned. Analogously, we can obtain the inequality of d
e
(
A
E
E
,
B
E
E
)
≤
d
e
(
A
E
,
B
E
). By Proposition 2, d
e
(
A
E
E
,
B
E
E
)
=
d
e
(
A
I
n
,
B
I
n
)
=
d
e
(
A
,
B
), and then d
e
(
A
,
B
)
≤
d
e
(
A
E
,
B
E
). Hence, d
e
(
A
,
B
)
=
d
e
(
A
E
,
B
E
). Since nonsingular binary matrix C can be represented by a product of elementary matrices, by induction, d
e
(
A
,
B
)
=
d
e
(
A
C
,
B
C
). Similarly, we can show that d
e
(
A
,
B
)
=
d
e
(
C
A
,
C
B
).


### 3.3. Directed Acyclic Graph

When the representation by elementary matrices is considered as a sequence of elementary matrices, the representation for a matrix may not be unique. For example,S
4
12
A
4
34
=
A
4
34
S
4
12 and S
4
24
A
4
13
=
A
4
13
S
4
24. Moreover, it is not easy to know how many equivalent representations exist for a nonsingular matrix. However, we could find an obvious equivalence as follows.Proposition 5.
LetC
n
(
i
,
j
) be {
S
n
i
j
,
A
n
i
j
,
A
n
j
i
}. Let E
1
∈
C
n
(
i
1
,
j
1
), E
2
∈
C
n
(
i
2
,
j
2
), and {
i
1
,
j
1
}
∩
{
i
2
,
j
2
}
=
∅. Then, E
1
E
2
=
E
2
E
1.Proof.
LetM
=
(
m
i
j
) be an n
×
n binary matrix in which m
i is the ith row vector. It is enough to show that E
1
E
2
M = E
2
E
1
M. E
1
M changes only two row vectors m
i
1 and m
j
1 of M, and E
2
M changes only two row vectors m
i
2 and m
j
2 of M. Since {
i
1
,
j
1
}
∩
{
i
2
,
j
2
}
=
∅ by assumption, the i
1th and j
1th row vectors of E
2
M are the same as m
i
1 and m
j
1, respectively, and the i
2th and j
2th row vectors of E
1
M are the same as m
i
2 and m
j
2, respectively. Also, E
1
E
2
M does not change the i
2th and j
2th row vectors of E
2
M. Analogously, E
2
E
1
M does not change the i
1th and j
1th row vectors of E
1
M. The i
1th and j
1th row vectors of E
1
E
2
M and E
2
E
1
M are the same as those of E
1
M, respectively, and the i
2th and j
2th row vectors of E
1
E
2
M and E
2
E
1
M are the same as those of E
2
M, respectively. Hence, E
1
E
2
M = E
2
E
1
M.Figure3 shows the noninterchangeability among the sets C
4
(
i
,
j
)s. Each set C
4
(
i
,
j
) has only one interchangeable set among the total 6 sets. It seems that such interchangeable cases are rare. However, it is not true for large n. For arbitrary chosen elementary matrices E
1 and E
2, the probability of E
1
E
2
=
E
2
E
1 is as follows:
(3)
P
(
E
1
E
2
=
E
2
E
1
)
=
{
(
n
-
2
)
(
n
-
3
)
n
(
n
-
1
)
,
if
n
>
3
,
0
,
if
n
≤
3
.
Figure 4 shows the probabilities of E
1
E
2
=
E
2
E
1 according to matrix size n. We can see that P
(
E
1
E
2
=
E
2
E
1
) is close to 1 for sufficiently large n. It means that the cases of E
1
E
2
=
E
2
E
1 have very frequently appeared for large n.Figure 3
Noninterchangeability of4
×
4 cases (n
=
4). Each edge means noninterchangeability between both classes.Figure 4
P
(
E
1
E
2
=
E
2
E
1
) according to matrix size n.Based on the equivalence of Proposition5, we can represent an invertible matrix by using a directed acyclic graph (DAG) with elementary matrices as its vertices. Each edge means noninterchangeability between two elementary matrices. Consider A
=
E
1
E
2
⋯
E
m
∈
G
L
n
(
ℤ
2
). We assume that the DAG structure of A is as follows:Then,E
1
E
2
⋯
E
m is a topological order of the above DAG. The following is also another topological order of the above DAGWhen we use this DAG representation for nonsingular binary matrices, we can apply known DAG recombination such as [28] or design geometric operators based on the similarity of DAGs [29].Figure5 shows the DAG representation of parents given in Figure 2  and an offspring generated by a simple DAG recombination. We can see that DAG representation reflects the similarity of parents more than that based on variable-length string.An example of directed acyclic graph.H
(
P
1
,
P
2
)
=
5, H
(
P
1
,
O
)
=
3, and H
(
P
2
,
O
)
=
3, where H is the Hamming distance on typical 2D binary encoding.
(a)
DAG representation of parents given in Figure2
(
a
)
(b)
An offspringO generated by a simple DAG recombination
(c)
Matrix form of the offspringO


### 3.4. Nontrivial Equivalences

We could also find more sophisticated equivalences. One class of them is about the exchange of two elementary matrices.Proposition 6 (exchange rules).
For eachi, j, k such that i
≠
j, j
≠
k, and k
≠
i, the following five exchange rules hold. (i)A
n
i
k
A
n
j
k
=
A
n
j
k
A
n
i
k, (ii)A
n
i
j
A
n
i
k
=
A
n
i
k
A
n
i
j, (iii)S
n
i
j
A
n
i
k
=
A
n
j
k
S
n
i
j, (iv)S
n
i
j
A
n
k
i
=
A
n
k
j
S
n
i
j, and (v)S
n
i
j
S
n
j
k
=
S
n
j
k
S
n
i
k
=
S
n
i
k
S
n
i
j.Proof.
LetM
=
(
m
i
j
) be an n
×
n binary matrix in which m
i is the ith row vector; that is, M
T
=
(
m
1
m
2
⋯
m
n
).(i)
It is enough to show that thekth row vector of A
n
i
k
A
n
j
k
M is the same as that of A
n
j
k
A
n
i
k
M. First, consider the left side: (
A
n
j
k
M
)
T
=
(
m
1
⋯
m
k
-
1
m
j
+
m
k
m
k
+
1
⋯
m
n
). (
A
n
i
k
A
n
j
k
M
)
T
=
(
m
1
⋯
m
k
-
1
m
i
+
m
j
+
m
k
m
k
+
1
⋯
m
n
). Now, consider the right side: (
A
n
i
k
M
)
T
=
(
m
1
⋯
m
k
-
1
m
i
+
m
k
m
k
+
1
⋯
m
n
). (
A
n
j
k
A
n
i
k
M
)
T
=
(
m
1
⋯
m
k
-
1
m
i
+
m
j
+
m
k
m
k
+
1
⋯
m
n
).
(ii)
It is enough to show that thejth and kth row vectors of A
n
i
j
A
n
i
k
M are the same as those of A
n
i
k
A
n
i
j
M. Without loss of generality, we assume that j
<
k. First, consider the left side: (
A
n
i
k
M
)
T
=
(
m
1
⋯
m
k
-
1
m
i
+
m
k
m
k
+
1
⋯
m
n
). (
A
n
i
j
A
n
i
k
M
)
T
=
(
m
1
⋯
m
j
-
1
m
i
+
m
j
m
j
+
1
⋯
m
k
-
1
m
i
+
m
k
m
k
+
1
⋯
m
n
). Now, consider the right side: (
A
n
i
j
M
)
T
=
(
m
1
⋯
m
j
-
1
m
i
+
m
j
m
j
+
1
⋯
m
n
). (
A
n
i
k
A
n
i
j
M
)
T
=
(
m
1
⋯
m
j
-
1
m
i
+
m
j
m
j
+
1
⋯
m
k
-
1
m
i
+
m
k
m
k
+
1
⋯
m
n
).
(iii)
It is enough to show that theith, jth, and kth row vectors of S
n
i
j
A
n
i
k
M are the same as those of A
n
j
k
S
n
i
j
M. Without loss of generality, we assume that i
<
j
<
k. First, consider the left side: (
A
n
i
k
M
)
T
=
(
m
1
⋯
m
k
-
1
m
k
+
m
i
m
k
+
1
⋯
m
n
). (
S
n
i
j
A
n
i
k
M
)
T
=
(
m
1
⋯
m
i
-
1
m
j
m
i
+
1
⋯
m
j
-
1
m
i
m
j
+
1
⋯
m
k
-
1
m
i
+
m
k
m
k
+
1
⋯
m
n
). Now, consider the right side: (
S
n
i
j
M
)
T
=
(
m
1
⋯
m
i
-
1
m
j
m
i
+
1
⋯
m
j
-
1
m
i
m
j
+
1
⋯
m
n
). (
A
n
j
k
S
n
i
j
M
)
T
=
(
m
1
⋯
m
i
-
1
m
j
m
i
+
1
⋯
m
j
-
1
m
i
m
j
+
1
⋯
m
k
-
1
m
i
+
m
k
m
k
+
1
⋯
m
n
).
(iv)
It is enough to show that theith, jth, and kth row vectors of S
n
i
j
A
n
k
i
M are the same as those of A
n
k
j
S
n
i
j
M. Without loss of generality, we assume that i
<
j
<
k. First, consider the left side: (
A
n
k
i
M
)
T
=
(
m
1
⋯
m
i
-
1
m
i
+
m
k
m
i
+
1
⋯
m
n
). (
S
n
i
j
A
n
k
i
M
)
T
=
(
m
1
⋯
m
i
-
1
m
j
m
i
+
1
⋯
m
j
-
1
m
i
+
m
k
m
j
+
1
⋯
m
n
). Now, consider the right side: (
S
n
i
j
M
)
T
=
(
m
1
⋯
m
i
-
1
m
j
m
i
+
1
⋯
m
j
-
1
m
i
m
j
+
1
⋯
m
n
). (
A
n
k
j
S
n
i
j
M
)
T
=
(
m
1
⋯
m
i
-
1
m
j
m
i
+
1
⋯
m
j
-
1
m
i
+
m
k
m
j
+
1
⋯
m
n
).
(v)
It is enough to check theith, jth, and kth row vectors of S
n
i
j
S
n
j
k
M, S
n
j
k
S
n
i
k
M, and S
n
i
k
S
n
i
j
M. We can easily check that the ith, jth, and kth row vectors of S
n
i
j
S
n
j
k
M are m
k, m
i, and m
j, respectively. Similarly, the ith, jth, and kth row vectors of S
n
j
k
S
n
i
k
M and S
n
i
k
S
n
i
j
M are the same as those of S
n
i
j
S
n
j
k
M.Another class is about the compaction of three elementary matrices into two ones.Proposition 7 (compaction rules).
For eachi, j, k such that i
≠
j, j
≠
k, and k
≠
i, the following two compaction rules hold. (i)A
n
i
k
A
n
j
k
A
n
i
j
=
A
n
i
j
A
n
j
k and (ii)A
n
k
j
A
n
k
i
A
n
j
i
=
A
n
j
i
A
n
k
j.Proof.
LetM
=
(
m
i
j
) be an n
×
n binary matrix in which m
i is the ith row vector; that is, M
T
=
(
m
1
m
2
⋯
m
n
).(i)
It is enough to show that theith, jth, and kth row vectors of A
n
i
k
A
n
j
k
A
n
i
j
M are the same as those of A
n
i
j
A
n
j
k
M. Without loss of generality, we assume that i
<
j
<
k. First, consider the left side: (
A
n
i
j
M
)
T
=
(
m
1
⋯
m
j
-
1
m
i
+
m
j
m
j
+
1
⋯
m
n
). (
A
n
j
k
A
n
i
j
M
)
T
=
(
m
1
⋯
m
j
-
1
m
i
+
m
j
m
j
+
1
⋯
m
k
-
1
m
i
+
m
j
+
m
k
m
k
+
1
⋯
m
n
). Since m
i
+
m
i
=
0, (
A
n
i
k
A
n
j
k
A
n
i
j
M
)
T
=
(
m
1
⋯
m
j
-
1
m
i
+
m
j
m
j
+
1
⋯
m
k
-
1
m
j
+
m
k
m
k
+
1
⋯
m
n
). Now, consider the right side: (
A
n
j
k
M
)
T
=
(
m
1
⋯
m
k
-
1
m
j
+
m
k
m
k
+
1
⋯
m
n
). (
A
n
i
j
A
n
j
k
M
)
T
=
(
m
1
⋯
m
j
-
1
m
i
+
m
j
m
j
+
1
⋯
m
k
-
1
m
j
+
m
k
m
k
+
1
⋯
m
n
).
(ii)
It is enough to show that theith, jth, and kth row vectors of A
n
k
j
A
n
k
i
A
n
j
i
M are the same as those of A
n
j
i
A
n
k
j
M. First, consider the left side: (
A
n
j
i
M
)
T
=
(
m
1
⋯
m
i
-
1
m
i
+
m
j
m
i
+
1
⋯
m
n
). (
A
n
k
i
A
n
j
i
M
)
T
=
(
m
1
⋯
m
i
-
1
m
i
+
m
j
+
m
k
m
i
+
1
⋯
m
n
). (
A
n
k
j
A
n
k
i
A
n
j
i
M
)
T
=
(
m
1
⋯
m
i
-
1
m
i
+
m
j
+
m
k
m
i
+
1
⋯
m
j
-
1
m
j
+
m
k
m
j
+
1
⋯
m
n
). Now, consider the right side: (
A
n
k
j
M
)
T
=
(
m
1
⋯
m
j
-
1
m
j

+

m
k
m
j
+
1
⋯
m
n
). (
A
n
j
i
A
n
j
k
M
)
T
=
(
m
1
⋯
m
i
-
1
m
i
+
m
j
+
m
k
m
i
+
1
m
j
-
1
m
j
+
m
k
m
j
+
1
⋯
m
n
).The encodings of matricesP
1 and P
2 given in Figure 2 can be reduced to other forms by using the presented propositions as follows:
(4)
P
1
=
S
4
12
A
4
34
S
4
24
A
4
13
S
4
14
=
A
4
34
S
4
12
_
S
4
24
A
4
13
S
4
14
(
∵
Proposition
5
)
=
A
4
34
S
4
12
A
4
13
S
4
24
_
S
4
14
(
∵
Proposition
5
)
=
A
4
34
A
4
23
S
4
12
_
S
4
24
S
4
14
(
∵
Proposition
6
(
iii
)
)
=
A
4
34
A
4
23
S
4
24
S
4
14
_
S
4
14
(
∵
Proposition
6
(
v
)
)
=
A
4
34
A
4
23
S
4
24
E
_
(
∵
Proposition
2
)
=
A
4
34
A
4
23
S
4
24
,
(5)
P
2
=
A
4
34
S
4
12
A
4
24
S
4
14
=
A
4
34
S
4
12
S
4
14
A
4
21
_
(
∵
Proposition
6
(
iv
)
)
=
A
4
34
S
4
14
S
4
42
_
A
4
21
(
∵
Proposition
6
(
v
)
)
=
A
4
34
S
4
14
S
4
24
_
A
4
21
(
∵
S
n
i
j

=

S
n
j
i
by
the
definition
of
S
n
i
j
)
=
A
4
34
S
4
14
S
4
24
A
4
21
.From the reduction, the edit distance between both parents decreases by 2. This reduction process can be understood as a kind of normalization [23]. Figure 6 shows a recombination example with the reduced encodings of parents. It shows that reduced encodings can produce more similar offspring to parents.Figure 6
Another example of variable-length string.H
(
P
1
,
P
2
)
=
5, H
(
P
1
,
O
)
=
1, and H
(
P
2
,
O
)
=
4, where H is the Hamming distance on typical 2D binary encoding d
e
(
P
1
,
P
2
)
=
3, d
e
(
P
1
,
O
)
=
1, and d
e
(
P
2
,
O
)
=
2, where d
e is the edit distance in that insertion, deletion, and replacement have weights of 1, 1, and 2, respectively.


## 3.1. Elementary Matrix inM
n
×
n
(
ℤ
2
)

Before introducing the elementary matrix ofM
n
×
n
(
ℤ
2
), we define elementary row operation.Definition 1.
LetA
∈
M
n
×
n
(
ℤ
2
). Any one of the following two operations on the rows of A is called an  elementary row operation: (i)
interchanging any two rows ofA and
(ii)
adding a row ofA to another row.Elementary row operations are oftype 1 or type 2 depending on whether they are obtained by (i) or (ii) of Definition 1. An n
×
n
elementary matrix over ℤ
2 field is a matrix obtained by performing an elementary row operation on the identity matrix I
n. The elementary matrix is said to be of type 1 or type 2 according to whether the elementary row operation performed on I
n is of type 1 or type 2, respectively. We can easily check the following property.Proposition 2.
For each elementary matrixE
∈
M
n
×
n
(
ℤ
2
), E
2
=
I
n, where I
n is the identity matrix.Proof.
It is trivial for the cases of type 1. Since1
+
1
=
0 and 0
+
0
=
0 in ℤ
2, m
+
m
=
0 for any row vector m. Hence, the identity also holds in the cases of type 2.We defineS
n
i
j as the elementary matrix of type 1 that interchanges the ith row and the jth one (i
≠
j). We also define A
n
i
j as the elementary matrix of type 2 that adds the ith row to the jth one (i
≠
j). For example, consider 3
×
3 cases; that is, n
=
3. There are three elementary matrices of type 1, S
3
12, S
3
13, and S
3
23:
(1)
S
3
12
=
(
0
1
0
1
0
0
0
0
1
)
,
S
3
13
=
(
0
0
1
0
1
0
1
0
0
)
,
S
3
23
=
(
1
0
0
0
0
1
0
1
0
)
.
And there are six elementary matrices of type 2, A
3
12, A
3
13, A
3
21, A
3
23, A
3
31, and A
3
32:
(2)
A
3
12
=
(
1
0
0
1
1
0
0
0
1
)
,
A
3
13
=
(
1
0
0
0
1
0
1
0
1
)
,
A
3
21
=
(
1
1
0
0
1
0
0
0
1
)
,
A
3
23
=
(
1
0
0
0
1
0
0
1
1
)
,
A
3
31
=
(
1
0
1
0
1
0
0
0
1
)
,
A
3
32
=
(
1
0
0
0
1
1
0
0
1
)
.Proposition 3.
The number of elementary matrices inM
n
×
n
(
ℤ
2
) is 3
n
(
n
-
1
)
/
2. In detail, let S
n and A
n be the sets of all elementary matrices of type 1 and of type 2 in M
n
×
n
(
ℤ
2
), respectively. Then, |
S
n
|
=
n
(
n
-
1
)
/
2 and |
A
n
|
=
n
(
n
-
1
).Proof.
SinceS
n
i
j
=
S
n
j
i for each (
i
,
j
) pair, S
n
=
{
S
n
i
j
∣
1
≤
i
<
j
≤
n
}. Since A
n
i
j
≠
A
n
j
i for each (
i
,
j
) pair, A
n
=
{
A
n
i
j
∣
1
≤
i
≤
n
,
1
≤
j
≤
n
,
i
≠
j
}.It is known that every invertible matrix is represented as a product of elementary matrices [18]. Hence, if we represent a solution in G
L
n
(
ℤ
2
) as a product of elementary matrices, we get a big advantage of preserving feasibility.


## 3.2. Variable-Length Linear String

In the case of using elementary matrices, we can consider the representation by variable-length linear string, of which each element is an elementary matrix. MatrixP
1 in Figure 1(a) is S
4
12
A
4
34
S
4
24
A
4
13
S
4
14 when represented as a product of elementary matrices. Similarly, matrix P
2 in Figure 1(b) becomes A
4
34
S
4
12
A
4
24
S
4
14. So their new encodings are given in Figure 2(a).Figure 2
An example of variable-length string.H
(
P
1
,
P
2
)
=
5, (
P
1
,
O
)
=
3, and H
(
P
2
,
O
)
=
2, where H is the Hamming distance on typical 2D binary encoding. d
e
(
P
1
,
P
2
)
=
5, d
e
(
P
1
,
O
)
=
2, and d
e
(
P
2
,
O
)
=
3, where d
e is the edit distance in that insertion, deletion, and replacement have weights of 1, 1, and 2, respectively.As recombination operators for this encoding, any recombinations for variable-length string can be used. Among such recombination operators,geometric crossover [19–24] by sequence alignment [25–27] is expected to be effectively performed. The string can be regarded as a sequence having the fixed number of elementary matrices. Geometric crossover by sequence alignment will be helpful for offspring to preserve features inherent in parents.As a distance for variable-length string, there isedit distance
d
e: the minimum number of insertion, deletion, and replacement of single elementary matrix to transform one string into the other. The geometric crossover associated with this distance is called the homologous geometric crossover [25]: two strings are aligned optimally before recombination. Alignment here means allowing parent strings to be stretched to match better with each other. Formally stretching strings means interleaving “—” anywhere and in any number in the strings to create two stretched strings of the same length that have minimal Hamming distance. In our example, when we recombine S
4
12
A
4
34
S
4
24
A
4
13
S
4
14 and A
4
34
S
4
12
A
4
24
S
4
14, we need to align them optimally first: S
4
12
A
4
34
S
4
24
A
4
13
S
4
14 and -
A
4
34
S
4
12
A
4
24
S
4
14 (see Figure 2(b)). Notice that the Hamming distance between the aligned strings is less than that between the nonaligned ones.After the optimal alignment, one does the normal crossover and produces a newstretched string. The offspring is obtained by removing “—”, so by unstretching the string (see Figure 2
(
c
)). In the example of Figure 2, we can easily check d
e
(
P
1
,
P
2
)
=
d
e
(
P
1
,
O
)
+
d
e
(
O
,
P
2
).Now we assume that insertion, deletion, and replacement have weights of 1, 1, and 2 in edit distanced
e, respectively. Then, when E
1
≠
E
2
∈
M
n
×
n
(
ℤ
2
), d
e
(
E
1
,
E
2
)
=
2 and d
e
(
E
1
E
2
,
E
2
E
2
)
=
d
e
(
E
1
E
2
,
I
n
)
=
2. In general, the following proposition holds.Proposition 4.
LetA, B, C be in G
L
n
(
ℤ
2
). Then d
e
(
A
,
B
)
=
d
e
(
A
C
,
B
C
)
=
d
e
(
C
A
,
C
B
); that is, d
e is translation-invariant.Proof.
LetE be an elementary matrix in M
n
×
n
(
ℤ
2
). By the definition of edit distance d
e, d
e
(
A
E
,
B
E
)
≤
d
e
(
A
,
B
). Here the equality holds when the last elementary matrices of A
E and B
E are aligned. Analogously, we can obtain the inequality of d
e
(
A
E
E
,
B
E
E
)
≤
d
e
(
A
E
,
B
E
). By Proposition 2, d
e
(
A
E
E
,
B
E
E
)
=
d
e
(
A
I
n
,
B
I
n
)
=
d
e
(
A
,
B
), and then d
e
(
A
,
B
)
≤
d
e
(
A
E
,
B
E
). Hence, d
e
(
A
,
B
)
=
d
e
(
A
E
,
B
E
). Since nonsingular binary matrix C can be represented by a product of elementary matrices, by induction, d
e
(
A
,
B
)
=
d
e
(
A
C
,
B
C
). Similarly, we can show that d
e
(
A
,
B
)
=
d
e
(
C
A
,
C
B
).


## 3.3. Directed Acyclic Graph

When the representation by elementary matrices is considered as a sequence of elementary matrices, the representation for a matrix may not be unique. For example,S
4
12
A
4
34
=
A
4
34
S
4
12 and S
4
24
A
4
13
=
A
4
13
S
4
24. Moreover, it is not easy to know how many equivalent representations exist for a nonsingular matrix. However, we could find an obvious equivalence as follows.Proposition 5.
LetC
n
(
i
,
j
) be {
S
n
i
j
,
A
n
i
j
,
A
n
j
i
}. Let E
1
∈
C
n
(
i
1
,
j
1
), E
2
∈
C
n
(
i
2
,
j
2
), and {
i
1
,
j
1
}
∩
{
i
2
,
j
2
}
=
∅. Then, E
1
E
2
=
E
2
E
1.Proof.
LetM
=
(
m
i
j
) be an n
×
n binary matrix in which m
i is the ith row vector. It is enough to show that E
1
E
2
M = E
2
E
1
M. E
1
M changes only two row vectors m
i
1 and m
j
1 of M, and E
2
M changes only two row vectors m
i
2 and m
j
2 of M. Since {
i
1
,
j
1
}
∩
{
i
2
,
j
2
}
=
∅ by assumption, the i
1th and j
1th row vectors of E
2
M are the same as m
i
1 and m
j
1, respectively, and the i
2th and j
2th row vectors of E
1
M are the same as m
i
2 and m
j
2, respectively. Also, E
1
E
2
M does not change the i
2th and j
2th row vectors of E
2
M. Analogously, E
2
E
1
M does not change the i
1th and j
1th row vectors of E
1
M. The i
1th and j
1th row vectors of E
1
E
2
M and E
2
E
1
M are the same as those of E
1
M, respectively, and the i
2th and j
2th row vectors of E
1
E
2
M and E
2
E
1
M are the same as those of E
2
M, respectively. Hence, E
1
E
2
M = E
2
E
1
M.Figure3 shows the noninterchangeability among the sets C
4
(
i
,
j
)s. Each set C
4
(
i
,
j
) has only one interchangeable set among the total 6 sets. It seems that such interchangeable cases are rare. However, it is not true for large n. For arbitrary chosen elementary matrices E
1 and E
2, the probability of E
1
E
2
=
E
2
E
1 is as follows:
(3)
P
(
E
1
E
2
=
E
2
E
1
)
=
{
(
n
-
2
)
(
n
-
3
)
n
(
n
-
1
)
,
if
n
>
3
,
0
,
if
n
≤
3
.
Figure 4 shows the probabilities of E
1
E
2
=
E
2
E
1 according to matrix size n. We can see that P
(
E
1
E
2
=
E
2
E
1
) is close to 1 for sufficiently large n. It means that the cases of E
1
E
2
=
E
2
E
1 have very frequently appeared for large n.Figure 3
Noninterchangeability of4
×
4 cases (n
=
4). Each edge means noninterchangeability between both classes.Figure 4
P
(
E
1
E
2
=
E
2
E
1
) according to matrix size n.Based on the equivalence of Proposition5, we can represent an invertible matrix by using a directed acyclic graph (DAG) with elementary matrices as its vertices. Each edge means noninterchangeability between two elementary matrices. Consider A
=
E
1
E
2
⋯
E
m
∈
G
L
n
(
ℤ
2
). We assume that the DAG structure of A is as follows:Then,E
1
E
2
⋯
E
m is a topological order of the above DAG. The following is also another topological order of the above DAGWhen we use this DAG representation for nonsingular binary matrices, we can apply known DAG recombination such as [28] or design geometric operators based on the similarity of DAGs [29].Figure5 shows the DAG representation of parents given in Figure 2  and an offspring generated by a simple DAG recombination. We can see that DAG representation reflects the similarity of parents more than that based on variable-length string.An example of directed acyclic graph.H
(
P
1
,
P
2
)
=
5, H
(
P
1
,
O
)
=
3, and H
(
P
2
,
O
)
=
3, where H is the Hamming distance on typical 2D binary encoding.
(a)
DAG representation of parents given in Figure2
(
a
)
(b)
An offspringO generated by a simple DAG recombination
(c)
Matrix form of the offspringO


## 3.4. Nontrivial Equivalences

We could also find more sophisticated equivalences. One class of them is about the exchange of two elementary matrices.Proposition 6 (exchange rules).
For eachi, j, k such that i
≠
j, j
≠
k, and k
≠
i, the following five exchange rules hold. (i)A
n
i
k
A
n
j
k
=
A
n
j
k
A
n
i
k, (ii)A
n
i
j
A
n
i
k
=
A
n
i
k
A
n
i
j, (iii)S
n
i
j
A
n
i
k
=
A
n
j
k
S
n
i
j, (iv)S
n
i
j
A
n
k
i
=
A
n
k
j
S
n
i
j, and (v)S
n
i
j
S
n
j
k
=
S
n
j
k
S
n
i
k
=
S
n
i
k
S
n
i
j.Proof.
LetM
=
(
m
i
j
) be an n
×
n binary matrix in which m
i is the ith row vector; that is, M
T
=
(
m
1
m
2
⋯
m
n
).(i)
It is enough to show that thekth row vector of A
n
i
k
A
n
j
k
M is the same as that of A
n
j
k
A
n
i
k
M. First, consider the left side: (
A
n
j
k
M
)
T
=
(
m
1
⋯
m
k
-
1
m
j
+
m
k
m
k
+
1
⋯
m
n
). (
A
n
i
k
A
n
j
k
M
)
T
=
(
m
1
⋯
m
k
-
1
m
i
+
m
j
+
m
k
m
k
+
1
⋯
m
n
). Now, consider the right side: (
A
n
i
k
M
)
T
=
(
m
1
⋯
m
k
-
1
m
i
+
m
k
m
k
+
1
⋯
m
n
). (
A
n
j
k
A
n
i
k
M
)
T
=
(
m
1
⋯
m
k
-
1
m
i
+
m
j
+
m
k
m
k
+
1
⋯
m
n
).
(ii)
It is enough to show that thejth and kth row vectors of A
n
i
j
A
n
i
k
M are the same as those of A
n
i
k
A
n
i
j
M. Without loss of generality, we assume that j
<
k. First, consider the left side: (
A
n
i
k
M
)
T
=
(
m
1
⋯
m
k
-
1
m
i
+
m
k
m
k
+
1
⋯
m
n
). (
A
n
i
j
A
n
i
k
M
)
T
=
(
m
1
⋯
m
j
-
1
m
i
+
m
j
m
j
+
1
⋯
m
k
-
1
m
i
+
m
k
m
k
+
1
⋯
m
n
). Now, consider the right side: (
A
n
i
j
M
)
T
=
(
m
1
⋯
m
j
-
1
m
i
+
m
j
m
j
+
1
⋯
m
n
). (
A
n
i
k
A
n
i
j
M
)
T
=
(
m
1
⋯
m
j
-
1
m
i
+
m
j
m
j
+
1
⋯
m
k
-
1
m
i
+
m
k
m
k
+
1
⋯
m
n
).
(iii)
It is enough to show that theith, jth, and kth row vectors of S
n
i
j
A
n
i
k
M are the same as those of A
n
j
k
S
n
i
j
M. Without loss of generality, we assume that i
<
j
<
k. First, consider the left side: (
A
n
i
k
M
)
T
=
(
m
1
⋯
m
k
-
1
m
k
+
m
i
m
k
+
1
⋯
m
n
). (
S
n
i
j
A
n
i
k
M
)
T
=
(
m
1
⋯
m
i
-
1
m
j
m
i
+
1
⋯
m
j
-
1
m
i
m
j
+
1
⋯
m
k
-
1
m
i
+
m
k
m
k
+
1
⋯
m
n
). Now, consider the right side: (
S
n
i
j
M
)
T
=
(
m
1
⋯
m
i
-
1
m
j
m
i
+
1
⋯
m
j
-
1
m
i
m
j
+
1
⋯
m
n
). (
A
n
j
k
S
n
i
j
M
)
T
=
(
m
1
⋯
m
i
-
1
m
j
m
i
+
1
⋯
m
j
-
1
m
i
m
j
+
1
⋯
m
k
-
1
m
i
+
m
k
m
k
+
1
⋯
m
n
).
(iv)
It is enough to show that theith, jth, and kth row vectors of S
n
i
j
A
n
k
i
M are the same as those of A
n
k
j
S
n
i
j
M. Without loss of generality, we assume that i
<
j
<
k. First, consider the left side: (
A
n
k
i
M
)
T
=
(
m
1
⋯
m
i
-
1
m
i
+
m
k
m
i
+
1
⋯
m
n
). (
S
n
i
j
A
n
k
i
M
)
T
=
(
m
1
⋯
m
i
-
1
m
j
m
i
+
1
⋯
m
j
-
1
m
i
+
m
k
m
j
+
1
⋯
m
n
). Now, consider the right side: (
S
n
i
j
M
)
T
=
(
m
1
⋯
m
i
-
1
m
j
m
i
+
1
⋯
m
j
-
1
m
i
m
j
+
1
⋯
m
n
). (
A
n
k
j
S
n
i
j
M
)
T
=
(
m
1
⋯
m
i
-
1
m
j
m
i
+
1
⋯
m
j
-
1
m
i
+
m
k
m
j
+
1
⋯
m
n
).
(v)
It is enough to check theith, jth, and kth row vectors of S
n
i
j
S
n
j
k
M, S
n
j
k
S
n
i
k
M, and S
n
i
k
S
n
i
j
M. We can easily check that the ith, jth, and kth row vectors of S
n
i
j
S
n
j
k
M are m
k, m
i, and m
j, respectively. Similarly, the ith, jth, and kth row vectors of S
n
j
k
S
n
i
k
M and S
n
i
k
S
n
i
j
M are the same as those of S
n
i
j
S
n
j
k
M.Another class is about the compaction of three elementary matrices into two ones.Proposition 7 (compaction rules).
For eachi, j, k such that i
≠
j, j
≠
k, and k
≠
i, the following two compaction rules hold. (i)A
n
i
k
A
n
j
k
A
n
i
j
=
A
n
i
j
A
n
j
k and (ii)A
n
k
j
A
n
k
i
A
n
j
i
=
A
n
j
i
A
n
k
j.Proof.
LetM
=
(
m
i
j
) be an n
×
n binary matrix in which m
i is the ith row vector; that is, M
T
=
(
m
1
m
2
⋯
m
n
).(i)
It is enough to show that theith, jth, and kth row vectors of A
n
i
k
A
n
j
k
A
n
i
j
M are the same as those of A
n
i
j
A
n
j
k
M. Without loss of generality, we assume that i
<
j
<
k. First, consider the left side: (
A
n
i
j
M
)
T
=
(
m
1
⋯
m
j
-
1
m
i
+
m
j
m
j
+
1
⋯
m
n
). (
A
n
j
k
A
n
i
j
M
)
T
=
(
m
1
⋯
m
j
-
1
m
i
+
m
j
m
j
+
1
⋯
m
k
-
1
m
i
+
m
j
+
m
k
m
k
+
1
⋯
m
n
). Since m
i
+
m
i
=
0, (
A
n
i
k
A
n
j
k
A
n
i
j
M
)
T
=
(
m
1
⋯
m
j
-
1
m
i
+
m
j
m
j
+
1
⋯
m
k
-
1
m
j
+
m
k
m
k
+
1
⋯
m
n
). Now, consider the right side: (
A
n
j
k
M
)
T
=
(
m
1
⋯
m
k
-
1
m
j
+
m
k
m
k
+
1
⋯
m
n
). (
A
n
i
j
A
n
j
k
M
)
T
=
(
m
1
⋯
m
j
-
1
m
i
+
m
j
m
j
+
1
⋯
m
k
-
1
m
j
+
m
k
m
k
+
1
⋯
m
n
).
(ii)
It is enough to show that theith, jth, and kth row vectors of A
n
k
j
A
n
k
i
A
n
j
i
M are the same as those of A
n
j
i
A
n
k
j
M. First, consider the left side: (
A
n
j
i
M
)
T
=
(
m
1
⋯
m
i
-
1
m
i
+
m
j
m
i
+
1
⋯
m
n
). (
A
n
k
i
A
n
j
i
M
)
T
=
(
m
1
⋯
m
i
-
1
m
i
+
m
j
+
m
k
m
i
+
1
⋯
m
n
). (
A
n
k
j
A
n
k
i
A
n
j
i
M
)
T
=
(
m
1
⋯
m
i
-
1
m
i
+
m
j
+
m
k
m
i
+
1
⋯
m
j
-
1
m
j
+
m
k
m
j
+
1
⋯
m
n
). Now, consider the right side: (
A
n
k
j
M
)
T
=
(
m
1
⋯
m
j
-
1
m
j

+

m
k
m
j
+
1
⋯
m
n
). (
A
n
j
i
A
n
j
k
M
)
T
=
(
m
1
⋯
m
i
-
1
m
i
+
m
j
+
m
k
m
i
+
1
m
j
-
1
m
j
+
m
k
m
j
+
1
⋯
m
n
).The encodings of matricesP
1 and P
2 given in Figure 2 can be reduced to other forms by using the presented propositions as follows:
(4)
P
1
=
S
4
12
A
4
34
S
4
24
A
4
13
S
4
14
=
A
4
34
S
4
12
_
S
4
24
A
4
13
S
4
14
(
∵
Proposition
5
)
=
A
4
34
S
4
12
A
4
13
S
4
24
_
S
4
14
(
∵
Proposition
5
)
=
A
4
34
A
4
23
S
4
12
_
S
4
24
S
4
14
(
∵
Proposition
6
(
iii
)
)
=
A
4
34
A
4
23
S
4
24
S
4
14
_
S
4
14
(
∵
Proposition
6
(
v
)
)
=
A
4
34
A
4
23
S
4
24
E
_
(
∵
Proposition
2
)
=
A
4
34
A
4
23
S
4
24
,
(5)
P
2
=
A
4
34
S
4
12
A
4
24
S
4
14
=
A
4
34
S
4
12
S
4
14
A
4
21
_
(
∵
Proposition
6
(
iv
)
)
=
A
4
34
S
4
14
S
4
42
_
A
4
21
(
∵
Proposition
6
(
v
)
)
=
A
4
34
S
4
14
S
4
24
_
A
4
21
(
∵
S
n
i
j

=

S
n
j
i
by
the
definition
of
S
n
i
j
)
=
A
4
34
S
4
14
S
4
24
A
4
21
.From the reduction, the edit distance between both parents decreases by 2. This reduction process can be understood as a kind of normalization [23]. Figure 6 shows a recombination example with the reduced encodings of parents. It shows that reduced encodings can produce more similar offspring to parents.Figure 6
Another example of variable-length string.H
(
P
1
,
P
2
)
=
5, H
(
P
1
,
O
)
=
1, and H
(
P
2
,
O
)
=
4, where H is the Hamming distance on typical 2D binary encoding d
e
(
P
1
,
P
2
)
=
3, d
e
(
P
1
,
O
)
=
1, and d
e
(
P
2
,
O
)
=
2, where d
e is the edit distance in that insertion, deletion, and replacement have weights of 1, 1, and 2, respectively.


## 4. Conclusions

We presented several ideas to deal with the space of nonsingular binary matrices,G
L
n
(
ℤ
2
), in evolutionary algorithms. This space is important in that it is used for the change of basis of standard binary encoding. As typical approaches, we represented a matrix in G
L
n
(
ℤ
2
) just as an array of matrix elements. Two-dimensional n
×
n binary encoding or length-n
2 binary linear string can be used in these approaches. However, these approaches need the feasibility check of offspring together with their repair mechanism. We illustrated this nature by an example.We presented some novel methods using elementary matrices, which have an advantage of preserving feasibility. An invertible matrix can be represented as a product of elementary matrices. Variable-length linear string and DAG (directed acyclic graph) representation are proposed to represent each nonsingular binary matrix that could be understood as a product of elementary matrices. Different products of elementary matrices often represent the same matrix, so we tried to get more information about the relation between representations with the same phenotype by finding some nontrivial equivalences.Future work will be directed to apply these results to the problem of finding good bases of binary encoding in evolutionary algorithms.



---

*Source: 540936-2014-01-09.xml*