Information Technology Reference
In-Depth Information
5 The Number of Linearly Independent Equations in XL
In this section we will estimate the number of linearly independent equations
one generates with the XL-method. As we will see, the linear dependencies we
can identify is governed by products of polynomials from
F
, and the number of
dependencies is calculated by counting the number of such products. We multiply
each
f
i
with all monomials of degree
D
m
(including the monomial 1, which
keeps the original polynomials) to form the set
U
D
.
Let
H
0
be the matrix whose rows are the coecient vectors of all polynomials
in
U
D
.Thecolumnsof
H
0
are indexed by all monomials of degree
≤
D
m
+
D
e
.
To avoid confusion in the generalization that follows, the rows of
H
0
are indexed
by
≤
m
)is1if
m
occurs as a term
m
·
r
(
f
i
), instead of
m
[
f
i
]. The entry (
m
·
r
(
f
i
)
,
in
m
·
f
i
and 0 otherwise.
We will now recursively construct a sequence of binary matrices
H
i
,i
≥
1. The
i
s
), where
j
=1
e
j
=
i
+1and
r
(
f
e
1
i
1
f
e
2
f
e
s
rows of
H
i
will be indexed by
m
·
···
m
i
2
is a monomial with deg(
D
e
.Thecolumnsof
H
i
will have the same
indices as the rows of
H
i−
1
. The degree of
m
)
≤
D
m
−
i
·
m
needs to be non-negative, so the
D
D
e
final
H
i
we construct is for
i
=
. When writing
g
·
r
(
···
) for a polynomial
g
=
m
1
+
...
+
m
k
, we will mean the sum
m
1
·
r
(
···
)+
...
+
m
k
·
r
(
···
). The row
r
(
f
e
1
i
1
f
e
2
f
e
s
m
·
···
i
s
) will contain a 1 in all columns that occur as terms in the
i
2
following sum:
s
f
e
j
−
1
i
j
1mod2
r
(
f
e
1
i
1
f
e
s
m
·
(
f
i
j
+(
e
i
j
−
···
···
i
s
)
.
(3)
j
=1
r
(
f
e
1
i
1
f
e
2
f
e
s
The rest of the entries in row
i
s
) will contain 0.
Let
v
be a binary vector indexed by the rows of
H
i
.If
v
·
m
·
···
i
2
H
i
=
0
,
v
identifies a
linear dependency between the rows of
H
i
. With the matrices
H
i
,i
=0
,...,
D
D
e
defined, we are ready to prove the first result.
D
D
e
Theorem 1.
H
i
·
H
i−
1
=[
0
]
, the all-zero matrix for
i
=1
,...,
. That is,
each row of
H
i
identifies a linear dependency among the rows of
H
i−
1
.
Proof.
The row
m
· r
(
f
e
1
i
1
f
e
2
···f
e
s
i
s
)in
H
i
contains a 1 in the columns indexed
by the terms in the following sum
i
2
s
f
e
j
−
1
i
j
1mod2
r
(
f
e
1
i
1
f
e
s
m
·
(
f
i
j
+(
e
i
j
−
···
···
i
s
)
.
(4)
j
=1
If
e
j
=1,itmeansthat
f
e
j
−
1
). Assume
without loss of generality that
e
t
+1
=
...
=
e
s
=1,andthat
e
j
>
1
,j
=1
,...,t
.
We need to show that (4) is the all-zero vector when the terms are regarded as
rows in
H
i−
1
. We substitute
r
(
f
e
1
vanishes from the expression
r
(
···
i
j
f
e
j
−
1
i
j
f
e
s
i
s
) with the expression given
by (3) to find which columns in
H
i−
1
that contain a 1 in the rows found in (4).
···
···
i
1
