Information Technology Reference
In-Depth Information
which is the desired conclusion.
The proof also holds for Toeplitz matrices (each element on a diagonal of the matrix
is the same) because we reasoned only about the value of elements in the upper right-hand
corner of submatrices that are on different diagonals.
The Kronecker product of matrices is used in Section
10.13.5
to derive a lower bound on
the space-time product for matrix inversion.
DEFINITION
10.12.2
The
Kronecker product
of two
n × n
matrices
A
and
B
is the
n
2
×
n
2
matrix
C
, denoted
C
=
A
⊗
B
, obtained by replacing the entry
a
i
,
j
of
A
with the matrix
a
i
,
j
B
.
AKroneckerproduct
C
=
A
⊗
B
of matrices
A
and
B
is shown below:
⎡
⎤
5
6
10
12
A
=
12
34
,
B
=
56
78
,
⎣
⎦
7
8
14
16
C
=
15
18
20
24
21
24
28
32
The following property of the Kronecker product of two
γ
-nice matrices is used to derive
the space-time lower bounds stated in Theorem
10.13.5
.
LEMMA
10.12.2
If
A
and
B
are both
n × nγ
-nice matrices for some
0
≤ γ ≤
1
/
2
,then
C
=
A
n
2
γ
2
-ok matrix.
Proof
Number the rows and columns of
A
,
B
,and
C
consecutively from 0. For a matrix
E
, extend the notation
e
i
,
j
for the entry in the
i
th row and
j
th column of
E
to
e
I
,
J
,by
which we denote the submatrix of
E
consisting of the intersection of the rows in the set
I
and columns in the set
J
.Thus,if
I
=
⊗
B
is an
n
2
×
,then
e
I
,
J
=
e
i
,
j
.
To s h ow t h a t
C
is
γ
2
-ok, we must show that every
p
{
i
}
and
J
=
{
j
}
×
q
submatrix
S
of
C
satisfying
has rank at least
γ
2
p
. Such a matrix
S
can be represented
as
S
=
c
I
,
J
for index sets
I
and
J
,where
p
=
γ
2
n
2
γ
2
n
2
p
≤
and
q
≥
n
−
γ
2
n
2
γ
2
n
2
|
I
|≤
and
q
=
|
J
|≥
n
−
.
We assume that
γn
1, since otherwise the result holds trivially.
The
r
th
block row
of
C
is the submatrix
[
a
r
,0
B
,
a
r
,1
B
,
...
,
a
r
,
n−
1
B
]
containing rows
numbered
I
r
=
≥
and all
n
2
columns.
{
rn
,
rn
+
1,
...
,
rn
+
n
−
1
}
Let
Δ
r
=
I
∩{
rn
,
rn
+
1,
...
,
rn
+
n
−
1
}
betheindicesoftherowsof
S
that fall into
the
r
th block row. Choose a set
Γ
⊂{
0, 1, 2,
...
,
n
−
1
}
of size
|
Γ
|
=
γn
that maximizes
the sum
T
=
r∈
Γ
|
γp
because the lower bound is achieved if the rows
of
S
are uniformly distributed over the rows of
C
and
T
is larger if they are not.
Let
Λ
r
=Δ
r
if
Δ
r
|
.Then,
T
≥
|
Δ
r
|≤
γn
and let
Λ
r
consist of the smallest
γn
indices in
Δ
r
|
Λ
r
|≥|
Δ
r
|
γ
because
Δ
r
is chosen from a set of size
n
.Callrowsof
C
otherwise. Clearly,
with indices in
r∈
Γ
Λ
r
blue rows
. There must be at least
γ
2
p
blue rows because, if not,
γ
2
p>
r∈
Γ
|
γ
2
p
r∈
Γ
|
Λ
r
|≥
Δ
r
|
γ
=
γT
≥
which is a contradiction.
We now show that the blue rows of
S
are linearly independent. Suppose not. Then
there exist constants
{
α
r
,
s
|
r
∈
Γ
,
s
∈
Δ
r
}
not all of which are zero such that the linear
Search WWH ::
Custom Search