Database Reference
In-Depth Information
finite-dimensional spectral theory is that the eigenvalues of a matrix
A
are,
respecting multiplicities, precisely the roots of the
characteristic polynomial
χ
B
ðÞ:¼
det
A λ
ð
I
Þ:
It turns out that the characteristic polynomial of a rank-1 modification of a
diagonal matrix has a closed-form representation.
n
.
Proposition 8.3 Let
Λ
:
¼
diag(
λ
1
,
...
,
λ
n
) be a real diagonal matrix and
x
∈ R
+
xx
T
is given by
Then the characteristic polynomial of
Λ
¼
det
Þ
1
x
Λ þ xx
T
1
þ x
T
det
λ
I
ð
Λ λ
I
Þ
ð
Λ λ
I
!
!
Y
1
þ
X
n
i¼
1
λ
i
λ
n
x
i
λ
i
λ
¼
ð
Þ
:
i¼
1
A proof may be found in, e.g., [GE94].
For the sake of simplicity, our discussion is restricted to the case where:
1.
λ
n
are distinct.
2. The spectra of
λ
1
,
...
,
+
xx
T
are disjoint.
Λ
and
Λ
For a more general treatment, please consult [BNS78].
If the second of the above conditions holds, then
λ
+
xx
T
if
is an eigenvalue of
Λ
and only if
1
Λ λ
1
þ x
T
I
x ¼
0
:
ð
8
:
16
Þ
Hence, the eigenvalues of the rank-1 modification may be obtained by solving
the secular equation (
8.16
). To do so, we may exploit the following insight.
Proposition 8.4 (cf. [GE94]) The eigenvalues
λ
1
... λ
n
of
+
xx
T
satisfy the
Λ
interlacing property
λ
i
λ
i
λ
i
1
,
i ¼
2,
...
,
n
:
By virtue of this observation, we are given intervals in which precisely one
eigenvalue is located. How should we proceed to solve (
8.16
)? The most straight-
forward way consists in deploying a bisection method. Since Proposition 8.4 pro-
vides suitable initializations, such a method is guaranteed to converge. The rate,
however, is only
q
-linear. A method exhibiting
q
-quadratic convergence is
Newton-Raphson. Unfortunately, we are not in a position to guarantee convergence
thereof because it may “leap” over the singularities and thus out of the search
intervals in an early stage. A more sophisticated method, again, has been proposed
in [BNS78]: the rational function on the right-hand side of (
8.16
) is iteratively
approximated by low-degree rational functions the roots of which are available in
