Information Technology Reference
In-Depth Information
[
GK
]
k
q
ʳ
n
,A
(
)
≥
·
.
C
s
(5.1)
n
2
q
n
2
n
A
= F
\
E
E
·
ʲ
·
< ʲ <
where
for some set
of size at most
s
for some 0
1.
[
GK
]
5.7.3 Lower Bounding
for
Det
n
and
Perm
n
k
,A
We now wish to show that
M
k
(
has large rank. The original proof of
Grigoriev and Karpinski is tailored specifically for the determinant, and does not
extend directly to the permanent. The following argument is a proof communicated
by Srikanth Srinivasan [
Sri13
] that involves an elegant trick that he attributes to
[
Kou08
]. The following proof is presented for the determinant, but immediately
extends to the permanent as well.
Note that if we were to just consider
M
k
(
Det
n
;
A)
, it would have been easy to show
that the rank is full by looking at just those evaluation points that keep exactly one
(
Det
n
)
minor nonzero (set the main diagonal of the minor to ones, and
every other entry to zero). Hence,
M
k
(
n
−
k
)
×
(
n
−
k
)
has the identity matrix
embedded inside
and hence must be full rank. However, we are missing a few of the evaluations (since
asmallset
Det
n
)
of evaluations is removed) and we would still like to show that the
matrix continues to have full column-rank.
E
Lemma 22
Let p
(
X
)
be a nonzero linear combination of r
×
r minors of the matrix
X
=
((
x
ij
))
. Then,
Pr
A
∗F
q
[
p
(
A
)
∅=
0
]ↆ
ˇ(
1
).
n
2
This immediately implies that for every linear combinations of the columns of
M
k
(
, a constant fraction of the coordinates have nonzero values. Since we are
removingmerely a set
Det
n
)
q
n
2
, theremust continue to exist coordinates
that are nonzero. In other words, no linear combination of columns of
M
k
(
E
of size
(
1
−
o
(
1
))
Det
n
;
A)
results in the zero vector.
The proof of the above lemma would be an induction on the number of minors
contributing to the linear combination. As a base case, we shall use a well-known
fact about
Det
n
and
Perm
n
of random matrices.
Proposition 23
If A is a random n
×
n matrix with entries from a fixed finite field
F
q
, then for q
∅=
2
we have
q
−
2
Pr
[
det
(
A
)
∅=
0
]ↆ
=
ˇ(
1
).
−
q
1
We shall defer the proof of this proposition for later, and proceed with the proof
of Lemma 22.
