Information Technology Reference
In-Depth Information
(
)
Proof of Lemma 22
If
p
is a scalar multiple of a single nonzero minor, then we
already have the lemma from Proposition 23. Hence, let us assume that there are at
least two distinct minors participating in the linear combination
p
X
. Without loss
of generality, assume that the first row occurs in some of the minors, and does not in
others. That is,
(
X
)
⊨
⊨
+
p
(
X
)
=
c
i
M
i
c
j
M
j
i
:
Row
1
∗
M
i
j
:
Row
1
∗
M
j
=
x
11
M
1
+···+
x
1
n
M
n
+
M
(expanding along the first row)
.
To understand a random evaluation of
p
(
X
)
, let us first set rows 2
,...,
n
to random
values, and then setting row 1 to random values.
x
11
M
1
+···+
x
1
n
M
n
+
M
∅=
some
M
i
P
A
[
p
(
A
)
∅=
0
]ↆ
Pr
[
0
|
∅=
0
]
some
M
i
×
Pr
[
∅=
0
]
Note that once we have set rows 2
,...,
n
to random values,
p
(
X
)
reduces to a linear
polynomial in
{
x
11
,...,
x
1
n
}
. Further, a random evaluation of any nonconstant linear
polynomial is zero with probability exactly
1
q
. Hence,
1
−
x
11
M
1
+···+
x
1
n
M
n
+
M
∅=
some
M
i
P
A
[
p
(
A
)
∅=
0
]ↆ
Pr
[
0
|
∅=
0
]
some
M
i
×
Pr
[
∅=
0
]
⊣
1
⊤
1
q
some
M
i
=
−
·
Pr
[
∅=
0
]
.
Now comes Koutis' Trick: the term
1
q
1
some
M
i
−
·
Pr
[
∅=
0
]
is exactly the
probability that
x
11
M
1
+···+
x
1
n
M
n
is nonzero! Hence,
x
11
M
1
+···+
x
1
n
M
n
+
M
∅=
P
A
[
p
(
A
)
∅=
0
]=
Pr
[
0
]
x
11
M
1
+···+
x
1
n
M
n
∅=
ↆ
Pr
[
0
]
⊨
∅=
.
=
Pr
c
i
M
i
0
i
:
Row
1
∗
M
i
which is just the linear combination obtained by only considering those minors that
contain the first row. Repeating this process for other rows/columns until only one
minor remains, we have
q
−
2
P
A
[
p
(
A
)
∅=
0
]ↆ
P
A
[
det
(
A
)
∅=
0
]=
1
(
by Proposition 23
).
∈
q
−
