RELATIVE RESIDUAL BOUNDS FOR THE EIGENVALUES OF A HERMITIAN SEMIDEFINITE MATRIX

ZLATKO DRMAČ^{∗} AND VJERAN HARI^{†}

Abstract. Let H be a Hermitian matrix, X an orthonormal matrix and M = X^{∗}HX. Then the eigenvalues of M approximate some eigenvalues of H with an absolute error bounded by ∥R∥_{2}, R = HX −XM. This work contains estimates of |λ−μ|/|μ| and |λ−μ|/|λ|, where μ, λ is a matching pair of the eigenvalues of M and H, when H is semidefinite. The general bound is expressed in terms of sines of the canonical angles between certain subspaces associated with H and X. A more refined “quadratic” bound, which uses the relative distances between eigenvalues, is also proved.

Key words. residual bounds, relative error, eigenvalue location

AMS subject classifications. 65F15, 65G05

0. Introduction. Let H ∈ C^{n×n} be Hermitian, X ∈ C^{n×m} orthonormal and

M = X^{∗}HX, R = HX − XM.

Let X = R(X) be the range of X and σ(H) = {λ_{j}}, σ(M) = {μ_{k}} the spectra of H, M, respectively. For the eigenvalues of H and M we assume

λ_{1} ≥ ⋯ ≥ λ_{n} and μ_{1} ≥ ⋯ ≥ μ_{m},

respectively. If X is an invariant subspace of H, then R = 0 and σ(M) ⊆ σ(H). If X is close to an invariant subspace of H, then R is close to 0 and each eigenvalue of M is close to an eigenvalue of H. This claim is quantified by the following classical results.

Theorem 0.1 (Kahan, [8]). There are eigenvalues λ_{j_{k}}, k = 1, …, m of H such that

| λ_{j_{k}} − μ_{k} |≤ ∥R∥_{2}, k = 1, …, m. (1)

Theorem 0.2 (Sun, [13]). Let Y = R(Y) be an invariant subspace of H with orthonormal basis Y ∈ C^{n×m}. Let λ_{j_{1}} ≥ ⋯ ≥ λ_{j_{m}} be the eigenvalues of Y^{∗}HY, and Λ_{Y} = diag (λ_{j_{1}}, …, λ_{j_{m}}), Λ_{X} = diag (μ_{1}, …, μ_{m}). If for some α, β ∈ R and δ_{0} > 0

σ(M) ⊂ [α, β], σ(H) \ σ(Y^{∗}HY) ⊂ (−∞, α − δ_{0}] ⋃ [β + δ_{0}, +∞) (or vice versa)

and if ρ ≡ ∥R∥_{2}/δ_{0} < 1, then for any unitarily invariant norm ∥ · ∥

∥Λ_{Y} − Λ_{X} ∥ ≤ \frac{1}{\sqrt{1 − ρ^{2}}} \frac{∥R∥_{2}∥R∥}{δ_{0}}.

Furthermore, if δ ≡ min{|μ − λ| : μ ∈ σ(M), λ ∈ σ(H) \ σ(Y^{∗}HY)} > 0, and ρ_{F} ≡ ∥R∥_{F} /δ < 1, then

∥Λ_{Y} − Λ_{X} ∥_{F} ≤ \frac{1}{\sqrt{1 − ρ_{F}^{2}}} \frac{∥R∥_{F}^{2}}{δ} . (2)

∗ Department of Computer Science, University of Colorado, Boulder CO 80309–0430, USA. (zlatko@cs.colorado.edu) The research of this author was supported by National Science Foundation grant ASC–9357812, and Department of Energy Grant DE–FG03–94ER25215.

† Department of Mathematics, University of Zagreb, Bijenička 30, 41000 Zagreb, Croatia.

(hari@math.hr)

In the above estimates ∥ · ∥_{2} and ∥ · ∥_{F} denote the spectral and the Frobenius matrix norms, respectively. Theorem 0.1 is a corollary of a more general result [8] that treats the case of an arbitrary m × m Hermitian matrix in place of M and an arbitrary n × m full column rank matrix instead of X. For other bounds of this kind see [10], [3], [12], [11], [2]. All these results estimate absolute distance between two matching eigenvalues of M and H. The bounds use the norm of the residual (thus, an absolute measure of R) and the (absolute) distance δ between σ(M) and the “non-matching” part of σ(H). Often the assumptions of Theorem 0.2 are not met (see Example 2.4 below). Note also that the bound in (2) becomes large (and thus useless) if δ gets tiny enough.

Our aim is to bound |λ_{j_{k}} − μ_{k}|/|μ_{k}| and consequently |λ_{j_{k}} − μ_{k}|/|λ_{j_{k}}|, where μ_{k} , λ_{j_{k}}, k = 1, …, m are appropriately matching pairs of eigenvalues. Note that the appropriate relative error bounds derived from Theorem 0.1 and Theorem 0.2 can become useless for small or close eigenvalues.

We seek bounds dependent on relative quantities such as (canonical) angles between subspaces and relative distances between eigenvalues. The first such estimates were proved in [6] and the following two theorems summarize them.

Theorem 0.3. Let H be nonsingular and Y = HX, Z = H^{−1}X. There are at least m eigenvalues λ_{j_{k}}, k = 1, …, m of H for which

\frac{|λ_{j_{k}} − μ_{k}|}{|λ_{j_{k}}|} ≤ ∥(I − P_{X})P_{Y,Z} + P_{X} (I − P_{Y,Z})∥_{2}, k = 1, …, m (3)

holds, provided that the right hand side is less than one. Here P_{X} denotes the orthogonal projector on X and P_{Y,Z} is the projector on Y along Z^{⊥}. Furthermore, the right hand side in (3) is bounded by sin ξ + tan ζ, where ξ is the maximal acute angle between X and Y, and ζ is the maximal acute angle between Y and Z.

In Theorem 0.3 Z^{⊥} denotes the orthogonal complement of Z. By an abuse of notation we have denoted by H the operator whose matrix in the standard basis is H. This will be repeated with the matrix L below.

Theorem 0.4. Let H = LL^{∗} be positive definite, Y_{L} = L^{∗}X, Z_{L} = L^{−1}X and let ψ be the maximal acute angle between Y_{L} and Z_{L}. Then there are at least m eigenvalues λ_{j_{k}}, k = 1, …, m of H for which

\frac{|λ_{j_{k}} − μ_{k}|}{λ_{j_{k}}} ≤ \frac{sin ψ}{1 − sin ψ} , k = 1, …, m (4)

holds, provided that sin ψ/(1 − sin ψ) is less than one.

If X is invariant for H from Theorem 0.4, we have LL^{∗}X ⊆ X, that is Y_{L} ⊆ Z_{L}. Since Y_{L} and Z_{L} have the same dimension, we have Y_{L} = Z_{L} and ψ = 0. Note that converse is also true, hence we have ψ = 0 iff μ_{k} = λ_{j_{k}}, k = 1, …, m. The bounds (3), (4) are derived using the backward perturbation δH = RX^{∗} + XR^{∗}, relative eigenvalue perturbation estimates from [4], [14], [5], and special geometric structure of the operators δHH^{−1} and L^{−1}δHL^{−∗}.

In this paper we derive new bounds for |λ_{j_{k}} − μ_{k}|/|μ_{k}| provided the matrix H is semidefinite. One of them is similar to that of Theorem 0.4, but uses another pair of subspaces and a slightly different angle function. The others assume sufficiently small canonical angles between subspaces, but in return deliver bounds which are quadratic in the sine of the maximal angle between subspaces.

1. Relative estimates for semidefinite matrices. Here we derive a new relative a posteriori bound for the eigenvalues of a Hermitian semidefinite matrix H obtained from the subspace X ⊂ C^{n}. For obvious reasons (replacing H by −H if needed) we can assume that H is positive semidefinite. Hence, in the sequel, all the results are stated for positive semidefinite H.

Let H = LL^{∗} be any factorization of H. If X is invariant for H we have

(L^{∗}x | L^{∗}y) = (LL^{∗}x | y) = (Hx | y) = 0, x ∈ X , y ∈ X^{⊥},

where (a | b) = b^{∗}a for a, b ∈ C^{n}. Hence for the subspaces

Y_{L} = L^{∗}X , U_{L} = L^{∗}X^{⊥}

we have Y_{L} ⊆ U_{L}^{⊥} and U_{L} ⊆ Y_{L}^{⊥}. This indicates that, at least if L is square and nonsingular, the maximal canonical angle between subspaces Y_{L} and U_{L}^{⊥} as well as between U_{L} and Y_{L}^{⊥} is zero. Note that Y_{L}, Y_{L}^{⊥}, U_{L} and U_{L}^{⊥} are subspaces of C^{r} where r is the number of columns of L. Since L can be rectangular and rank deficient, the dimensions of Y_{L} and U_{L}^{⊥} (Y_{L}^{⊥} and U_{L}) can differ. Therefore, we shall use the angle function ^{}(M_{1}, M_{2}) between arbitrary subspaces M_{1} and M_{2} of C^{r}, defined by (see [15])

(M_{1}, M_{2}) = sin^{−1} min {∥ (I − P_{M_{2}}) P_{M_{1}}∥_{2} , ∥ (I − P_{M_{1}}) P_{M_{2}}∥_{2}} .

Here P_{M_{i}} is the orthogonal projector onto M_{i}, i = 1, 2. ¿From the definition one obtains ^{}(M_{1}, M_{2}) = ^{}(M_{2}^{⊥}, M_{1}^{⊥}). Hence for our pairs of subspaces we have (Y_{L}, U_{L}^{⊥}) = ^{}(Y_{L}^{⊥}, U_{L}) =: ϕ_{L}. Let us yet show that ϕ_{L} actually does not depend on L but H. Indeed, let H = L_{1}L_{1}^{∗} be another factorization, where L_{1} has the same number of columns^{1} as L. Then we must have L_{1} = LQ for some unitary Q. This implies Y_{L_{1}} = L_{1}^{∗}X = Q^{∗}L^{∗}X = Q^{∗}Y_{L} and hence Y_{L_{1}}^{⊥} = Q^{∗}Y_{L}^{⊥}. In the same way one obtains U_{L_{1}} = Q^{∗}U_{L} and U_{L_{1}}^{⊥} = Q^{∗}U_{L}^{⊥}. Since the angle function is unitarily invariant (see [15]) we have ^{}(Y_{L_{1}}, U_{L_{1}}^{⊥}) = ^{}(Q^{∗}Y_{L}, Q^{∗}U_{L}^{⊥}) = ^{}(Y_{L}, U_{L}^{⊥}) and similarly ^{}(Y_{L_{1}}^{⊥}, U_{L_{1}}) = ^{}(Y_{L}^{⊥}, U_{L}). Thus, ϕ_{L_{1}} = ϕ_{L} =: ϕ_{H}. Since H is fixed, in the sequel we write ϕ = ϕ_{H}.

Let X ∈ C^{n×m}, X_{⊥} ∈ C^{n×(n−m)} be any orthonormal bases of X, X^{⊥}. Let M = X^{∗}HX, N = X_{⊥}^{∗}HX_{⊥} be restrictions of H on X, X^{⊥}, respectively. Since every transition to new orthonormal bases X′, X′_{⊥} induces unitary matrices U, V such that X′ = XU, X′_{⊥} = X_{⊥}V, we have M′ = X′^{∗}HX′ = U^{∗}MU, N′ = X′_{⊥}^{∗}HX′_{⊥} = V^{∗}NV. This shows that the eigenvalues of M and N depend only on H and X.

Theorem 1.1. Suppose H ∈ C^{n×n} is Hermitian positive semidefinite and X is an m - dimensional subspace of C^{n}. Let μ_{1} ≥ ⋯ ≥ μ_{m} and η_{m+1} ≥ ⋯ ≥ η_{n} be the eigenvalues of the restrictions of H on X and X^{⊥}, respectively. Let H = LL^{∗} and ϕ = ^{}(L^{∗}X , (L^{∗}X^{⊥})^{⊥}). If ϕ < π/2, there is an ordering λ_{j_{1}},…, λ_{j_{n}} of the eigenvalues of H such that

\frac{| μ_{k} − λ_{j_{k}} |}{| μ_{k} |} ≤ sin ϕ,  k = 1, …, dim (L^{∗}X) ,
μ_{k} = λ_{j_{k}} = 0,  k = dim (L^{∗}X) + 1, …, m,
\frac{| η_{k} − λ_{j_{k}} |}{| η_{k} |} ≤ sin ϕ,  k = m + 1, …, m + dim (L^{∗}X^{⊥}) ,
η_{k} = λ_{j_{k}} = 0,  k = m + dim (L^{∗}X^{⊥}) + 1, …, n.

1 If L_{1} has less (more) columns than L, an appropriate number of zero columns can be appended to L_{1} (L).

Proof. Let us select orthonormal bases X, X_{⊥} of X, X^{⊥}, respectively, such that

M = X^{∗}HX = [ \begin{matrix}O \\ & Λ_{1} \end{matrix} ] \begin{matrix}m − r_{M} \\ r_{M} \end{matrix} , N = X_{⊥}^{∗}HX_{⊥} = [ \begin{matrix}Λ_{2} \\ & O \end{matrix} ] \begin{matrix}r_{N} \\ n − m − r_{N} \end{matrix} ,

where r_{M} = rank (M), r_{N} = rank (N), Λ_{1} = diag (μ_{1}, …, μ_{r_{M}}) and Λ_{2} = diag (η_{m+1}, …, η_{m+r_{N}}). Since [X, X_{⊥}]^{∗}H[X, X_{⊥}] is positive semidefinite, we have

[X, X_{⊥}]^{∗}H[X, X_{⊥}] [ O ; Ĥ ; O ] \begin{matrix}m − r_{M} \\ r_{M} + r_{N} \\ n − m − r_{N} \end{matrix} , Ĥ = [ \begin{matrix}Λ_{1} & K^{∗} \\ K & Λ_{2} \end{matrix} ] \begin{matrix}r_{M} \\ r_{N} \end{matrix} .

Note that Ĥ has full rank. Therefore, Ĥ and Λ_{1}⊕Λ_{2} are positive definite. By the inertia theorem ([12, Theorem 4.1]) we conclude that Ĥ_{S} = (Λ_{1} ⊕ Λ_{2})^{− \frac{1}{2}} Ĥ (Λ_{1} ⊕ Λ_{2})^{− \frac{1}{2}} is also positive definite. Hence

Ĥ = (Λ_{1} ⊕ Λ_{2})^{\frac{1}{2}} ĤS^{\frac{1}{2}} ĤS^{\frac{1}{2}} (Λ_{1} ⊕ Λ_{2})^{\frac{1}{2}}

and

Ĥ′ = ĤS^{\frac{1}{2}} (Λ_{1} ⊕ Λ_{2})^{\frac{1}{2}} (Λ_{1} ⊕ Λ_{2})^{\frac{1}{2}} ĤS^{\frac{1}{2}} = ĤS^{\frac{1}{2}} (Λ_{1} ⊕ Λ_{2}) ĤS^{\frac{1}{2}}

have the same eigenvalues, counting multiplicities. Since rank(H) = r_{M} + r_{N}, they are exactly the positive eigenvalues of H. Since Ĥ′ is related to Λ_{1} ⊕ Λ_{2} via the congruence transformation with ĤS^{\frac{1}{2}} we can apply Ostrowski’s theorem (see [9] or [7, Theorem 4.5.9]) to Ĥ′. We obtain λ_{i}(Ĥ′) = θ_{i}λ_{i} (Λ_{1} ⊕ Λ_{2}) , i = 1, …, n (5) with 1 − ∥K_{S}∥_{2} ≤ λ_{r_{M} +r_{N}} (Ĥ_{S}) ≤ θ_{i} ≤ λ_{1}(Ĥ_{S}) ≤ 1 + ∥K_{S}∥_{2}, (6) where K_{S} = Λ_{2}^{− \frac{1}{2}} KΛ_{1}^{− \frac{1}{2}} . Here λ_{i}(·) denotes the ith largest eigenvalue of a matrix. Note, if we prove ∥K_{S}∥_{2} = sin ϕ, (7) then the relations (5) and (6) will imply all the assertions of the theorem.

To prove (7) we use partitions: X = [X_{1}, X_{2}], X_{⊥} = [X_{⊥,1}, X_{⊥,2}], where X_{2} ∈ C^{n×r_{M}}, X_{⊥,1} ∈ C^{n×r_{N}}. Then we have

(8)  K_{S} = Λ_{2}^{− \frac{1}{2}} KΛ_{1}^{− \frac{1}{2}} = Λ_{2}^{− \frac{1}{2}} X_{⊥,1}^{∗}HX_{2}Λ_{1}^{− \frac{1}{2}} = Λ_{2}^{− \frac{1}{2}} X_{⊥,1}^{∗}LL^{∗}X_{2}Λ_{1}^{− \frac{1}{2}}
= (L^{∗}X_{⊥,1}Λ_{2}^{− \frac{1}{2}} )^{∗} (L^{∗}X_{2}Λ_{1}^{− \frac{1}{2}} ) = U^{∗}Y.

Note that

Y^{∗}Y = Λ_{1}^{− \frac{1}{2}} X_{2}^{∗}LL^{∗}X_{2}Λ_{1}^{− \frac{1}{2}} = Λ_{1}^{− \frac{1}{2}} X_{2}^{∗}HX_{2}Λ_{1}^{− \frac{1}{2}} = Λ_{1}^{− \frac{1}{2}} Λ_{1}Λ_{1}^{− \frac{1}{2}} = I_{r_{M}} ,
U^{∗}U = Λ_{2}^{− \frac{1}{2}} X_{⊥,1}^{∗}LL^{∗}X_{⊥,1}Λ_{2}^{− \frac{1}{2}} = Λ_{2}^{− \frac{1}{2}} X_{⊥,1}^{∗}HX_{⊥,1}Λ_{2}^{− \frac{1}{2}} = Λ_{2}^{− \frac{1}{2}} Λ_{2}Λ_{2}^{− \frac{1}{2}} = I_{r_{N}} ,
R (Y) = R (L^{∗}X_{2}Λ_{1}^{− \frac{1}{2}} ) = R (L^{∗}X_{2}) ⊆ R (L^{∗}X) =: Y_{L},
R (U) = R (L^{∗}X_{⊥,1}Λ_{2}^{− \frac{1}{2}} ) = R (L^{∗}X_{⊥,1}) ⊆ R (L^{∗}X_{⊥}) =: U_{L}.

Since 0 = X_{1}^{∗}HX_{1} = X_{1}^{∗}LL^{∗}X_{1} = (L^{∗}X_{1})^{∗} L^{∗}X_{1} we have L^{∗}X_{1} = 0. Similarly, we obtain L^{∗}X_{⊥,2} = 0. Thus dim (R (L^{∗}X_{2})) = dim (Y_{L}), dim (R (L^{∗}X_{⊥,1})) = dim (U_{L}), whence R (Y) = Y_{L} and R (U) = U_{L}. We have shown that Y and U are orthonormal bases for Y_{L} and U_{L}, respectively. Since Y_{L} = L^{∗}X, U_{L} = L^{∗}X^{⊥}, we have

sin ϕ = sin^{}(Y_{L}, U_{L}^{⊥}) = min {∥P_{U_{L}}P_{Y_{L}}∥_{2} , ∥P_{Y_{L}^{⊥}}P_{U_{L}^{⊥}}∥_{2}} .

Using [15, Section 2.] we can choose an orthogonal basis of C^{n} such that matrix representations of (the linear operators defined by) P_{U_{L}}P_{Y_{L}}, P_{Y_{L}^{⊥}}P_{U_{L}^{⊥}} with respect to that basis are block diagonal matrices with nonzero blocks of the size 2 × 2. Furthermore, if cos ξ_{1} ≥ ⋯ ≥ cos ξ_{ℓ} are the nonzero singular values of K_{S}, then the nontrivial diagonal blocks of P_{U_{L}}P_{Y_{L}} and P_{Y_{L}^{⊥}}P_{U_{L}^{⊥}} in the new basis have forms

cos ξ_{i}[ \begin{matrix}cos ξ_{i} & sin ξ_{i} \\ 0 & 0 \end{matrix} ] and cos ξ_{i}[ \begin{matrix}0 & − sin ξ_{i} \\ 0 & cos ξ_{i} \end{matrix} ],

respectively. Hence sin ϕ = cos ξ_{1} = ∥K_{S}∥_{2}. This proves the relation (7) and completes the proof of the theorem.

We call the reader’s attention to the beautiful dualities in Theorems 0.4 and 1.1. Theorem 0.4 can be applied to H^{−1} with the same right-hand side in (4). This is in accordance with the fact that H and H^{−1} have the same invariant subspaces. Similarly, in Theorem 1.1 the subspace X can be replaced by X^{⊥} without changing the bound. This corresponds to the fact that X and X^{⊥} are complementary and one is H–invariant iff the other is such. In fact, in the case of positive definite H, Theorem 0.4 follows from Theorem 1.1, because in that case (L^{∗}X^{⊥})^{⊥} = L^{−1}X. In the semidefinite case one can easily show that (L^{∗}X^{⊥})^{⊥} = {x : Lx ∈ X }.

2. Quadratic residual bounds. In this section we show how to replace the linear bound of Theorem 1.1 by a bound of order sin^{2} ϕ. Our estimate will differ from that of Theorem 0.2 because we use the relative gap in the spectrum and estimate the relative distance between the spectrum of M and the matching part of the spectrum of H. Note an important restriction in Theorem 0.2. It lies in the definitions of δ_{0} and δ – if an eigenvalue of H is approximated by some μ_{j}, then the whole eigenspace of H corresponding to that eigenvalue has to be approximated by some subspace of X. Such a condition is unlikely to be met in applications and fortunately it can be removed.

In the following theorem which refines Theorem 1.1, σ_{min}(·) denotes the smallest singular value of a matrix and ∥ · ∥ denotes any unitarily invariant matrix norm. We let Sin Φ denote the diagonal matrix with sines of the canonical angles between L^{∗}X and (L^{∗}X^{⊥})^{⊥} as diagonal elements. It is actually the diagonal matrix in the singular value decomposition of K_{S} = U^{∗}Y from the proof of Theorem 1.1. To simplify notation, for a given nonzero eigenvalue λ of H we shall choose the bases X and X^{⊥} so that

Λ_{1} = Ξ_{λ} ⊕ Ξ̂_{λ} , Λ_{2} = Ω_{λ} ⊕ Ω̂_{λ}, (9)

where the diagonals of Ξ_{λ} and Ω_{λ} approximate λ in the sense of Theorem 1.1. Note that the diagonals of Λ_{1} and Λ_{2} need not be anymore in the monotone ordering.

Theorem 2.1. Let H, X and ϕ < π/2 be as in Theorem 1.1. Let λ > 0 be an eigenvalue of H of multiplicity n(λ). Let the orthonormal bases of X and X^{⊥} be so chosen that (9) holds. Suppose there exist constants α > sin ϕ and β > sin ϕ such that

(10)  ∥λΞ_{λ}^{−1} − I∥_{2} ≤ sin ϕ , σ_{min} (λΞ̂_{λ}^{−1} − I) ≥ α ,
(11)  ∥λΩ_{λ}^{−1} − I∥_{2} ≤ sin ϕ , σ_{min} (λΩ̂_{λ}^{−1} − I) ≥ β .

If Ξ_{λ} ⊕ Ω_{λ} is of order n(λ), then

∥I − λΞ_{λ}^{−1}∥ ≤ \frac{1}{1 − \frac{sin^{2} ϕ}{αβ}} \frac{∥ Sin Φ∥_{2}∥ Sin Φ∥}{β},

∥I − λΩ_{λ}^{−1}∥ ≤ \frac{1}{1 − \frac{sin^{2} ϕ}{αβ}} \frac{∥ Sin Φ∥_{2}∥ Sin Φ∥}{α}.

Proof. Without loss of generality we can assume

H = [ \begin{matrix}Λ_{1} & K^{∗} \\ K & Λ_{2} \end{matrix} ],

where Λ_{1} and Λ_{2} are given by (9). Otherwise one can work with Ĥ from the proof of Theorem 1.1. Since λ is fixed we omit it as matrix subscript. By the Sylvester’s law of inertia, the matrix

H_{S}(λ) = (Λ_{1} ⊕ Λ_{2})^{−1/2}(H − λI)(Λ_{1} ⊕ Λ_{2})^{−1/2}

has rank n − n(λ). It has the following block structure

H_{S}(λ) = [ \begin{matrix}I − λΞ^{−1} & O & (K_{S}^{(1,1)})^{∗} & (K_{S}^{(2,1)})^{∗} \\ O & I − λΞ̂^{−1} & (K_{S}^{(1,2)})^{∗} & (K_{S}^{(2,2)})^{∗} \\ K_{S}^{(1,1)} & K_{S}^{(1,2)} & I − λΩ^{−1} & O \\ K_{S}^{(2,1)} & K_{S}^{(2,2)} & O & I − λΩ̂^{−1} \end{matrix} ] .

For technical reasons we replace H_{S}(λ) by a similar matrix

Ĥ_{S}(λ) = Π^{τ} H_{S}(λ)Π = [ \begin{matrix}I − λΞ^{−1} & (K_{S}^{(1,1)})^{∗} & O & (K_{S}^{(2,1)})^{∗} \\ K_{S}^{(1,1)} & I − λΩ^{−1} & K_{S}^{(1,2)} & O \\ O & (K_{S}^{(1,2)})^{∗} & I − λΞ̂^{−1} & (K_{S}^{(2,2)})^{∗} \\ K_{S}^{(2,1)} & O & K_{S}^{(2,2)} & I − λΩ̂^{−1} \end{matrix} ] ,

where Π denotes an appropriate permutation matrix. Since the spectral norm of a submatrix is not larger than the norm of the whole matrix, the assumptions (10) and (11) imply

(12) σ_{min} ((I − λΞ̂^{−1}) ⊕ (I − λΩ̂^{−1})) ≥ min{α, β} > sin ϕ
= ∥ Sin Φ∥_{2} ≥ ∥K_{S}∥_{2} ≥ max_{1≤i,j≤2} ∥K_{S}^{(i,j)}∥_{2},

where K_{S} = Λ_{2}^{−1/2}KΛ_{1}^{−1/2}. Hence the matrix

C = [ \begin{matrix}I − λΞ̂^{−1} & (K_{S}^{(2,2)})^{∗} \\ K_{S}^{(2,2)} & I − λΩ̂^{−1} \end{matrix} ] = [ \begin{matrix}C_{11} & C_{12} \\ C_{21} & C_{22} \end{matrix} ], C_{12} = C_{21}^{∗},

and its diagonal blocks C_{11} and C_{22} are nonsingular. Therefore (see [7, Sect. 0.7.3])

C^{−1} = [ \begin{matrix}[C_{11} − C_{12}C_{22}^{−1}C_{21}]^{−1} & C_{11}^{−1}C_{12} [C_{21}C_{11}^{−1}C_{12} − C_{22}]^{−1} \\ [C_{21}C_{11}^{−1}C_{12} − C_{22}]^{−1} C_{21}C_{11}^{−1} & [C_{22} − C_{21}C_{11}^{−1}C_{12}]^{−1} \end{matrix} ],

provided that all matrices in brackets are nonsingular. However, this follows since these matrices are (signed) Shur complements of C_{11} and C_{22} in C. By the last assumption, C is of order n − n(λ) what is also the rank of Ĥ_{S}(λ). Since C is nonsingular its Schur complement in Ĥ_{S}(λ) must be zero (cf. [10, pp. 183]). Hence

[ \begin{matrix}I − λΞ^{−1} & (K_{S}^{(1,1)})^{∗} \\ K_{S}^{(1,1)} & I − λΩ^{−1} \end{matrix} ] = [ \begin{matrix}O & (K_{S}^{(2,1)})^{∗} \\ K_{S}^{(1,2)} & O \end{matrix} ]C^{−1}[ \begin{matrix}O & (K_{S}^{(1,2)})^{∗} \\ K_{S}^{(2,1)} & O \end{matrix} ]. (13)

The rest of the proof is obvious. Indeed, using (13) and the structure of C^{−1} we obtain

I − λΞ^{−1} = (K_{S}^{(2,1)})^{∗}[I − λΩ̂^{−1} − K_{S}^{(2,2)}(I − λΞ̂^{−1})^{−1}(K_{S}^{(2,2)})^{∗}]^{−1}K_{S}^{(2,1)},
I − λΩ^{−1} = K_{S}^{(1,2)}[I − λΞ̂^{−1} − (K_{S}^{(2,2)})^{∗}(I − λΩ̂^{−1})^{−1}K_{S}^{(2,2)}]^{−1}(K_{S}^{(1,2)})^{∗}.

Applying an arbitrary unitarily invariant matrix norm to the expressions on the leftand right-hand sides and using its relation to the spectral norm (cf. [12, Theorem 3.9.]), we obtain

∥I − λΞ^{−1}∥ ≤ \frac{∥K_{S}^{(2,1)}∥_{2}∥K_{S}^{(2,1)}∥}{β − \frac{∥K_{S}^{(2,2)}∥_{2}^{2}}{α}} = \frac{1}{1 − \frac{∥K_{S}^{(2,2)}∥_{2}^{2}}{αβ}} \frac{∥K_{S}^{(2,1)}∥_{2}∥K_{S}^{(2,1)}∥}{β},

∥I − λΩ^{−1}∥ ≤ \frac{∥K_{S}^{(1,2)}∥_{2}∥K_{S}^{(1,2)}∥}{α − \frac{∥K_{S}^{(2,2)}∥_{2}^{2}}{β}} = \frac{1}{1 − \frac{∥K_{S}^{(2,2)}∥_{2}^{2}}{αβ}} \frac{∥K_{S}^{(1,2)}∥_{2}∥K_{S}^{(1,2)}∥}{α}.

Since for any unitarily invariant norm (cf. [12, Corollary 3.8])

max_{1≤i,j≤2} ∥K_{S}^{(i,j)}∥ ≤ ∥K_{S}∥ = ∥ Sin Φ∥,

the proof is completed.

If the matrices Ξ̂_{λ} and Ω_{λ} in Theorem 2.1 are void, i.e. in the proof of Theorem 2.1 Λ_{1} = Ξ_{λ} and Λ_{2} = Ω̂_{λ}, then the assertion of the theorem reduces to

(14) ∥I − λΞ_{λ}^{−1}∥ ≤ \frac{∥ Sin Φ∥_{2}∥ Sin Φ∥}{β}.

This is the first assertion of Theorem 2.1 with simplified bound.

Specifying ∥·∥ to be the spectral and the Frobenius norm, we obtain the following useful relative a posteriori estimates.

Corollary 2.2. Let L denote the set of all λ ∈ σ(H) for which the assumptions of Theorem 2.1 hold. For λ ∈ L let Ξ_{λ}, Ω_{λ}, α_{λ} and β_{λ} be as in Theorem 2.1. If α = min_{λ∈L} α_{λ}, β = min_{λ∈L} β_{λ} then

max_{λ∈L} max_{μ∈σ(Ξ_{λ})} \frac{|μ − λ|}{|μ|} ≤ \frac{1}{1 − \frac{sin^{2} ϕ}{αβ}} \frac{sin^{2} ϕ}{β},

max_{λ∈L} max_{η∈σ(Ω_{λ})} \frac{|η − λ|}{|η|} ≤ \frac{1}{1 − \frac{sin^{2} ϕ}{αβ}} \frac{sin^{2} ϕ}{α},

\sqrt{∑_{λ∈L} ∑_{μ∈σ(Ξ_{λ})} (\frac{μ − λ}{μ})^{2}} ≤ \frac{1}{1 − \frac{sin^{2} ϕ}{αβ}} \frac{∥ Sin Φ∥_{F}^{2}}{β} ,

\sqrt{∑_{λ∈L} ∑_{η∈σ(Ω_{λ})} (\frac{η − λ}{η})^{2}} ≤ \frac{1}{1 − \frac{sin^{2} ϕ}{αβ}} \frac{∥ Sin Φ∥_{F}^{2}}{α} .

Remark 2.3. One can easily check that the assumptions (10) and (11) of Theorem 2.1 are satisfied if e.g. for some λ ∈ σ(H)

sin ϕ ≤ \frac{1}{3} min_{λ_{i}≠λ} \frac{|λ_{i} − λ|}{λ_{i} + λ} ≡ δ_{λ}.

In such a case α and β in Theorem 2.1 can be replaced by δ_{λ}.

Example 2.4. Let

H = [ \begin{matrix}10^{10} & 1 & 10^{−13} \\ 1 & 2 · 10^{−5} & 10^{−7} \\ 10^{−13} & 10^{−7} & 10^{−5} \end{matrix} ], X = [ \begin{matrix}0 \\ 1 \\ 0 \end{matrix} ] , X^{⊥} = [ \begin{matrix}1 & 0 \\ 0 & 0 \\ 0 & 1 \end{matrix} ] .

Then

M = [2 · 10^{−5}] , R = [10^{−7} 0 1]^{∗} .

Thus, the result of Theorem 0.1 is not useful because ∥R∥_{2} ≈ 1. Since

H_{S} = diag (H_{ii}^{−1/2})Hdiag (H_{ii}^{−1/2}) = I + E, ∥E∥_{∞} < 10^{−2},

we know from the theory of Barlow and Demmel [1] that

1 − 10^{−2} < \frac{H_{jj}}{λ_{j}} < 1 + 10^{−2}, j = 1, 2, 3,

where λ_{1} ≥ λ_{2} ≥ λ_{3} are the eigenvalues of H. This means that in this example the separation δ from Theorem 0.2 is of order 10^{−5} and that Theorem 0.2 is not applicable. On the other side, both Theorem 0.4 and Theorem 1.1 ensure that for some j_{0} ∈ {1, 2, 3} (check that j_{0} = 2) holds |λ_{j_{0}} −2·10^{−5}|/λ_{j_{0}} < 7.5·10^{−3}. Note that N = (X^{⊥})^{∗}HX^{⊥} is scaled diagonally dominant in the sense of [1] and its diagonal elements approximate the eigenvalues of N to fifteen significant digits. Hence one can check that the eigenvalue λ_{j_{0}} is well separated (in the relative sense) from the spectrum of N. An easy calculation shows that we can take β = 0.9. Since ϕ is the angle between two one dimensional subspaces, the relation (14) and an easy calculation yield |λ_{j_{0}} − 2 · 10^{−5}|/λ_{j_{0}} < 6.2 · 10^{−5}. Note that |λ_{j_{0}} − 2 · 10^{−5}|/λ_{j_{0}} ≈ |λ_{j_{0}} − 2 · 10^{−5}|/2 · 10^{−5} ≈ 4.5 · 10^{−5}.

Acknowledgement . We would like to thank professor N. J. Higham, Manchester, and anonymous referees for detailed and constructive comments. We also thank professor Ji–guang Sun, Umeå, for calling our attention to [13].

REFERENCES

[1] J. Barlow and J. Demmel, Computing accurate eigensystems of scaled diagonally dominant matrices, SIAM J. Num. Anal., 27 (1990), pp. 762–791.

[2] Z.-H. Cao, J.-J. Xie, and R.-C. Li, A sharp version of Kahan’s theorem on clustered eigenvalues, Computer Science Division Technical Report UCB//CSD-94-857, University of California, Berkeley, CA 94720, 1994.

[3] F. Chatelin, Spectral Approximation of Linear Operators, Academic Press, New York, 1983.

[4] J. Demmel and K. Veselić, Jacobi’s method is more accurate than QR, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 1204–1245.

[5] Z. Drmač, Computing the Singular and the Generalized Singular Values, PhD thesis, Lehrgebiet Mathematische Physik, Fernuniversität Hagen, 1994.

[6] , On relative residual bounds for the eigenvalues of a Hermitian matrix, technical report, Department of Mathematics, University of Hagen, Germany, 1994. LAA, to appear.

[7] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 1990.

[8] W. Kahan, Inclusion theorems for clusters of eigenvalues of Hermitian matrices, tech. report, Computer Science Department, University of Toronto, Toronto, Ontario, Canada, 1967.

[9] A. M. Ostrowski, A quantitative formulation of sylvester’s Law of Inertia, Proc. National Acad. Sciences (USA), 45 (1959), pp. 740–744.

[10] B. N. Parlett, The Symmetric Eigenvalue Problem, Prentice–Hall Inc., Englewood Cliffs, N. J., 1980.

[11] G. W. Stewart, Two simple residual bounds for the eigenvalues of a Hermitian matrix, SIAM J. Matrix Anal. Appl., 12 (1991), pp. 205–208.

[12] G. W. Stewart and J. g. Sun, Matrix Perturbation Theory, Academic Press, 1990.

[13] J.-G. Sun, Eigenvalues of Rayleigh quotient matrices, Numer. Math., 59 (1991), pp. 603–614.

[14] K. Veselić and I. Slapničar, Floating-point perturbations of Hermitian matrices, Linear Algebra Appl., 195 (1993), pp. 81–116.

[15] P. A. Wedin, On angles between subspaces of a finite dimensional inner product space, in Matrix Pencils Proceedings of a Conference, Springer Verlag, 1982.