Digital Signal Processing Reference
In-Depth Information
which gives us the variation in eigenvalues (
15.65
), while looking outside the diagonal
in (
15.69
), one immediately gets matrix
B
(
15.66
) as indeed (
15.69
) becomes in this
case for row
i
, column
j
:
a
t
i
0
=
d
ii
b
ij
−
d
jj
b
ij
−
A
t
j
.
(15.71)
When
d
ii
=
d
jj
, this leads to (
15.67
), as claimed.
Case 2
some eigenvalues have geometric multiplicity greater than one. Assume now
without loss of generality that
g
(
d
kk
)
=
2, with
d
kk
=
d
ll
,forsome1
≤
k
=
l
≤
d
.
(
15.71
) shows that
t
k
t
l
A
t
l
=
A
t
k
=
0, which implies that
A
projects vectors into
the space spanned by eigenvectors
{
t
i
}
i
=
k
,
l
, so that
{
t
k
,
t
l
}
generates the null space
of
A
. Picking
i
=
k
,
l
or
j
=
k
,
l
in (
15.71
) implies
∀
i
,
j
=
k
,
l
:
b
kj
=
b
lj
=
b
ik
=
b
il
=
0. Hence, in columns
k
or
l
,
B
may only have non-zero values in rows
k
or
l
.
But looking at (
15.70
) shows that
0, implying
d
kk
=
d
ll
.
λ
kk
=
λ
ll
=
d
kk
=
d
ll
=
It is immediate to check from (
15.63
) that
t
k
and
t
l
are also eigenvectors of
a
A
.
To finish-up, looking at (
15.68
) brings that if the remaining unknowns in columns
k
or
l
in
B
are non-zero, then
t
k
and
t
l
are collinear, which is impossible.
Θ
−
Armed with this Lemma, we can prove the following Theorem, in which we
use the decomposition
A
=
i
=
1
a
i
a
i
a
i
, where
a
i
denotes an eigenvalue with
eigenvector
a
i
.
Theorem 4.
Define
e
(
Θ
)>
0
as the minimum difference between distinct eigenval-
, and d
the number of distinct eigenvalues of
ues of
Θ
Θ
. Then, under the first-order
shift setting, the following holds on
ς
(
15.61
):
ad
2
Tr
4
3
(
A
)
ς
≤
.
(15.72)
e
(
Θ
)
v
i
the eigenvector in column
i
of
V
in (
15.63
). The general
term of
V
T
in row
i
, column
j
is:
Proof sketch:
We denote
v
i
t
j
, but it comes from the definition of
B
t
i
+
k
b
ki
t
k
, which yields
v
i
b
ji
v
i
=
t
j
=
=
in (
15.68
) that
if
i
j
(and 1
otherwise); so:
F
V
T
V
T
ς
=
I
−
(
)
·
(
)
=
B
·
B
F
a
t
i
A
t
j
d
ii
−
4
=
,
d
jj
π(
i
,
j
)
where
π(
i
,
j
)
is the Boolean predicate
(
g
(
d
ii
)
=
1
)
∧
(
g
(
d
jj
)
=
1
)
∧
(
i
=
j
)
.
We finally get:
