On the Subdifferentiability of Functions of a Matrix Spectrum II: Subdifferential Formulas

James V. Burke^{∗} and Michael L. Overton^{†}

Abstract

Variational properties for the spectral radius and spectral abscissa of an analytic matrix valued mapping A: C^{s} ↦ C^{n×n} are considered. A notion of directional differentiability is introduced that allows us to exploit the perturbation results of Part I of this study. Lower bounds for the directional derivative are established which yield formulas for the directional derivative when a natural nondegeneracy condition is satisfied. These formulas are interpreted in the extreme cases where the eigenvalues attaining either the spectral radius or the spectral abscissa are nonderogatory or semisimple (nondefective). We conclude by investigating the relationship with the proximal normal subdifferential. In particular, it is shown that the proximal normal subdifferential is always nonempty.

1 Introduction

In this article, we develop a few of the variational properties of the spectral radius, ρ, and the spectral abscissa, α, for the analytic matrix valued mapping A: C^{s} ↦ C^{n×n}. The mappings ρ and α are given by the formulas

ρ(z) := max{|λ|: λ ∈ Σ(z)},

and

α(z) := max{Re λ : λ ∈ Σ(z)},

where the multifunction Σ: C^{s} ↦ C^{n×n} is the spectrum of A(z), i.e. the roots of the characteristic polynomial

P (z, λ) = det(λI − A(z)).

∗Department of Mathematics, University of Washington. The work of this author was supported in part by National Science Foundation Grant DMS-88-03206

†Computer Science Department, Courant Institute of Mathematical Sciences, New York University. The work of this author was supported in part by National Science Foundation Grant CCR-88-02408.

As discussed in Part I [3], the mappings α and ρ, although continuous, are not, in general, lipschitzian near values of z for which P has multiple roots. The nonlipschitzian behavior arises from the bifurcation of these multiple roots. Along analytic curves in C^{s} these roots are algebroidal functions and as such can be described as the branches of an analytic function with each branch being representable as a power series in fractional powers of the perturbation. It is these classical results that inspire us to introduce a notion of directional differentiability which depends in an essential way on the underlying analyticity of A.

For f: C^{s} ↦ IR, define f^{h}(z; ·): C^{s} ↦ IR ∪ {±∞} by

f^{h}(z; d) := inf_{γ∈Γ(z,d)} lim inf_{ϵ↓0} \frac{f(γ(ϵ)) − f(z)}{ϵ},  (1)

where

Γ(z, d) := {γ: C ↦ C^{s} : γ is analytic , γ(0) = z, and γ′(0) = d}.  (2)

The notation ϵ ↓ 0 implies that only real (and positive) values of ϵ are to be considered. The superscript h in (1) is used to emphasize that f^{h}(z; d) depends only on the analytic (holomorphic) curves in C^{s} that pass through z. At first glance it may appear that this notion of directional differentiability is not sufficiently robust to capture the full range of first order variational behavior that is possible for nonlipschitzian functions. However, as we hope to demonstrate, it is sufficiently robust for the analysis of the functions ρ and α. In order to see why this is so, we need to recall certain properties of the Puiseux-Newton series expansions for the roots of P, which were introduced by way of example in the discussion following Lemma 1 in Part I of this study. Here we provide a little more detail.

Let z, d be in C^{s} and choose γ ∈ Γ(z, d). The roots of P (γ(ϵ), λ) are given by series expansions in fractional powers of ϵ, that is, Puiseux-Newton series of the form

λ(ϵ) := λ_{0} + κϵ^{p} + ⋯,  (3)

where p := q/r ≥ 1/n for some pair of relatively prime integers q and r. Associated with each such value of p there are r series of the form (3) yielding roots of P (γ(ϵ), λ) with κ taking the values

η^{1/r}ω^{j} for j = 1, ⋯, r,

for some η ∈ C where η^{1/r} is the principal rth root of η and ω is the principal rth root of unity. An immediate consequence of this type of splitting of the roots of P is that, when evaluating the directional derivative (1) for the spectral abscissa and radius, one can replace the limit infimum in the definition with a limit. Moreover, again in the case of ρ and α, this directional derivative always exists, possibly taking the value +∞ but never the value −∞. This structure also indicates why the spectral radius and abscissa are Hölder continuous of order at least 1/n. Thus, a natural extension to (1) would be to consider Hölder type directional derivatives based on fractional powers of ϵ. Although it is possible to pursue such an approach using the techniques developed in Part 1 of this study, we do not do so here.

2 The Directional Derivative

In this section, we apply Lemmas 4 and 5 of Part I of this study to obtain information about the directional derivative defined in (1) for the spectral abscissa and radius. We continue to assume that A: C^{s} ↦ C^{n×n} is an analytic matrix function and z_{0} ∈ C^{s}. Also let A(z_{0}) have the block diagonal decomposition

A(z_{0}) = A^{(0)} = P DP^{−1}, D = Diag(D_{1},…, D_{m}),  (4)

where m is the number of distinct eigenvalues of A(z_{0}) and the kth diagonal block D_{k} is upper triangular with constant diagonal λ_{k}, i.e.

D_{k} = λ_{k}I + N_{k},

with N_{k} strictly upper triangular and hence nilpotent. Let n_{k} denote the order of D_{k}, i.e., the multiplicity of the eigenvalue λ_{k}. Suppose

\frac{∂A}{∂z_{l}} (z_{0}) = A_{l}^{(1)}, for l = 1, ⋯, s,

and let B_{1l},…, B_{ml} be the corresponding diagonal blocks of P^{−1}A_{l}^{(1)}P for l = 1, ⋯, s. With this notation established, we have the following results.

Theorem 1 Choose d ∈ C^{s}. If for some k ∈ A(z_{0}) := {k : λ_{k} ∈ Σ(z_{0}), Re λ_{k} = α(z_{0})} any one of the conditions

Re ∑_{l=1}^{s}(tr N_{k}B_{kl})d_{l} ≤ 0, Im ∑_{l=1}^{s}(tr N_{k}B_{kl})d_{l} = 0,  (5)

∑_{l=1}^{s}(tr N_{k}^{j−1}B_{kl})d_{l} = 0, j = 3,…, n_{k},  (6)

is violated, then

α^{h}(z_{0}; d) = +∞ ;  (7)

otherwise,

α^{h}(z_{0}; d) ≥ ϕ(z_{0}, d),  (8)

where

ϕ(z_{0}, d) := max \{\frac{Re ∑_{l=1}^{s}(tr B_{kl})d_{l}}{n_{k}} : k ∈ A(z_{0})\} .  (9)

Moreover, if conditions (5) and (6) hold and the vectors

{[tr N_{k}^{j−1}B_{k1}, ⋯, tr N_{k}^{j−1}B_{ks}]^{T} : j = 1,…, n_{k}, k ∈ A_{1}(z_{0}, d)}

are linearly independent, where A_{1}(z_{0}, d) is the set of indices in A(z_{0}) which achieve the maximum in (9), then equality holds in (8).

Partial Proof We will establish the first statement by applying Lemma 4 of Part I, using the correspondence between A^{(1)} in Part I and ∑_{l=1}^{s} d_{l}A_{l}^{(1)} here. It follows immediately that (7) holds if (5) or (6) is violated. Indeed, if for some k ∈ A(z_{0}) one of the conditions (5) or (6) fail to hold, then for every γ ∈ Γ(z_{0}, d) the inequality

Re (λ(ϵ) − λ_{k}) ≤ δϵ + o(ϵ)

fails to hold for every δ ∈ R, for some branch λ(ϵ) of the splitting of λ_{k} along the curve γ. Consequently, the limit defining α^{h}(z_{0}; d) is +∞ for every γ ∈ Γ(z_{0}, d) and so α^{h}(z_{0}; d) = +∞. On the other hand, if δ > α^{h}(z_{0}; d), then there is a γ ∈ Γ(z_{0}, d) such that

lim_{ϵ↓0} \frac{α(γ(ϵ)) − α(z_{0})}{ϵ} < δ,

or equivalently,

Re (λ(ϵ) − λ_{k}) < δϵ for ϵ ∈ [0, ϵ_{0}],

for some ϵ_{0} > 0, for every branch λ(ϵ) of the splitting of λ_{k} along the curve γ ,and for every k ∈ A(z_{0}). Now by applying Lemma 4 of Part I to this inequality for each k ∈ A(z_{0}) and then letting δ ↓ α^{h}(z_{0}; d), we obtain inequality (8). The proof of the last statement requires the implicit function theorem and is given in [4].

Theorem 2 Choose d ∈ C^{s} and set

R(z_{0}) := {k : |λ_{k}|= ρ(z_{0})}.

We will consider two cases; ρ(z_{0}) = 0 and ρ(z_{0}) ≠ 0.

1) Let us assume that ρ(z_{0}) = 0 so that m = 1 and λ_{1} = 0. If any one of the conditions

∑_{l=1}^{s}(tr N_{1}^{j−1}B_{1l})d_{l} = 0, j = 2,…, n_{k},  (10)

is violated, then

ρ^{h}(z_{0}; d) = +∞ ;

otherwise,

ρ^{h}(z_{0}; d) ≥ ξ(z_{0}, d),  (11)

where

ξ(z_{0}, d) := \frac{1}{n} |∑_{l=1}^{s}(tr B_{1l})d_{l}| .

Moreover, if condition (10) holds and the vectors

{[tr N_{1}^{j−1}B_{11}, ⋯, tr N_{1}^{j−1}B_{1s}]^{T} : j = 1,…, n}

are linearly independent, then equality holds in (11).

2) Let us assume that ρ(z_{0}) ≠ 0. If for some k ∈ R(z_{0}) any one of the conditions

Re \overline{λ}_{k}^{2} ∑_{l=1}^{s}(tr N_{k}B_{kl})d_{l} ≤ 0, Im \overline{λ}_{k}^{2} ∑_{l=1}^{s}(tr N_{k}B_{kl})d_{l} = 0,  (12)

∑_{l=1}^{s}(tr N_{k}^{j−1}B_{kl})d_{l} = 0, j = 3,…, n_{k},  (13)

is violated, then

ρ^{h}(z_{0}; d) = +∞ ;

otherwise,

ρ^{h}(z_{0}; d) ≥ ψ(z_{0}, d),  (14)

where

ψ(z_{0}, d) := max\{\frac{1}{n_{k}ρ(z_{0})}[Re (\overline{λ}_{k} ∑_{l=1}^{s}(tr B_{kl})d_{l})+ |∑_{l=1}^{s}(tr N_{k}B_{kl})d_{l}|] : k ∈ R(z_{0})\}.

(15)

Moreover, if conditions (12) and (13) hold and the vectors

{[tr N_{k}^{j−1}B_{k1}, ⋯, tr N_{k}^{j−1}B_{ks}]^{T} : j = 1,…, n_{k}, k ∈ R_{1}(z_{0}, d)}

are linearly independent, where R_{1}(z_{0}, d) is the set of indices in R(z_{0}) achieving the maximum in (15), then equality holds in (14).

Partial Proof First consider ρ(z_{0}) = 0. It follows immediately from Lemma 5 of Part I that (10) must hold for j = 2 as well as j = 3, ⋯, n, if the directional derivative is to be finite valued. Now assume that (10) holds and suppose δ ≥ ρ^{h}(z_{0}; d). Then there is a γ ∈ Γ(z_{0}, d) such that

|∑ λ(ϵ)|≤ ∑ |λ(ϵ)|< nδϵ ,

where the sum is taken over all branches λ(ϵ). Letting δ ↓ 0 yields (11) in view of Lemma 3 in Part I.

Next assume that ρ(z_{0}) ≠ 0. The proof of inequality (14) is a straight forward application of Lemma 5 in Part I. Observe that if for some k ∈ R(z_{0}) one of the conditions (12) or (13) fail to hold, then for every γ ∈ Γ(z_{0}, d) the inequality

|λ(ϵ)| − |λ_{k}|≤ δϵ + o(ϵ)

fails to hold for every δ ∈ R, for some branch λ(ϵ) of the splitting of λ_{k} along the curve γ. Consequently, the limit defining ρ^{h}(z_{0}; d) is +∞ for every γ ∈ Γ(z_{0}, d) and so ρ^{h}(z_{0}; d) = +∞. On the other hand, if δ > ρ^{h}(z_{0}; d), then there is a γ ∈ Γ(z_{0}, d) such that

lim_{ϵ↓0} \frac{ρ(γ(ϵ)) − ρ(z_{0})}{ϵ} < δ,

or equivalently,

|λ(ϵ)| − |λ_{k}|< δϵ for ϵ ∈ [0, ϵ_{0}],

for some ϵ_{0} > 0, for every branch λ(ϵ) of the splitting of λ_{k} along the curve γ ,and for every k ∈ R(z_{0}). Now by applying Lemma 5 of Part I to this inequality for each k ∈ A(z_{0}) and then letting δ ↓ ρ^{h}(z_{0}; d), we obtain inequality (14).

The proofs of equality in both cases makes use of the implicit function theorem and are given in [4].

3 The Nonderogatory and Semisimple Cases

In this section we consider two cases that illustrate the results in Theorems 1 and 2. Let λ_{k} ∈ Σ(z_{0}) have multiplicity n_{k}. Then λ_{k} is said to be nonderogatory if it possesses only a single eigenvector. The nonderogatory multiple eigenvalues are, in a quantifiable sense, the most generic kind of multiple eigenvalue [1]. The eigenvalue λ_{k} is said to be semisimple if it is associated with n_{k} independent eigenvectors.

Now suppose A(z_{0}) has block diagonal form as described in the previous section. Then λ_{k} is semisimple if and only if N_{k} = 0, and λ_{k} is nonderogatory if and only if N_{k}^{n_{k}−1} ≠ 0. Therefore, if λ_{k} is derogatory, then for some j_{0} < n_{k} we have that N_{k}^{j} = 0 for j ≥ j_{0}. This observation is significant in the interpretation of Theorems 1 and 2. These theorems provide formulas for the directional derivatives α^{h}(z_{0}; d) and ρ^{h}(z_{0}; d) when it is known that vectors given by

[tr N_{k}^{j−1}B_{k1}, ⋯, tr N_{k}^{j−1}B_{ks}]^{T} , for j = 1,…, n_{k}

are linearly independent. However these vectors cannot be linearly independent if the eigenvalue λ_{k} is derogatory since in this case N_{k}^{j−1} = 0 for at least one value of j satisfying 1 ≤ j ≤ n_{k}. Thus the formulas that are provided in Theorems 1 and 2 are at best sharp only in the nonderogatory case. Such an outcome could have been predicted from the outset. As has been indicated, our results are derived from results for polynomials and are extended to matrices by application to the characteristic polynomial. Such results are most applicable to nonderogatory eigenvalues since the multiplicity of these eigenvalues in the characteristic polynomial agrees with their multiplicity in the minimal polynomial. In this case, the characteristic polynomial accurately reflects the behavior of the eigenvalue. This is not true for derogatory eigenvalues.

It is instructive to see just how far off these lower bounds can be by considering the semisimple case. Semisimple and nonderogatory eigenvalues lie at opposite structural extremes whenever n_{k} > 1 (of course, if n_{k} = 1, then the eigenvalue is both semisimple and nonderogatory). Thus, we would expect the lower bounds for the directional derivatives α^{h}(z_{0}; d) and ρ^{h}(z_{0}; d) to be most inaccurate in this case. By employing the resolvent theory for linear operators [5] to the semisimple case, one can obtain precise formulas for the required directional derivatives. This is done in [7, Lemma 3.5]. As an immediate consequence of this result we obtain the following theorem.

Theorem 3 Suppose A(z_{0}) and R(z_{0}) contain only semisimple eigenvalues of A(z_{0}). Let d ∈ C^{s} and denote by λ′_{kl}, for l = 1,…, n_{k}, the eigenvalues of ∑_{l=1}^{s} B_{kl}d_{l} for each k ∈ A(z_{0}).

1) The spectral abscissa: The ordinary directional derivative α′(z_{0}; d) exists and satisfies

α′(z_{0}; d) = α^{h}(z_{0}; d) = max_{k∈A(z_{0})} max_{1≤l≤n_{k}}{Re λ′_{kl}}.  (16)

2) The spectral radius: The ordinary directional derivative ρ′(z_{0}; d) exists and satisfies

ρ′(z^{0}; d) = ρ^{h}(z_{0}; d) = \{ \begin{matrix}max_{k∈R(z_{0})} max_{1≤l≤n_{k}} |λ′_{kl}| & if ρ(z_{0}) = 0, \\ \frac{1}{ρ(z_{0})} max_{k∈R(z_{0})} max_{1≤l≤n_{k}} Re \overline{λ}_{k}λ′_{kl} & if ρ(z_{0}) ≠ 0. \end{matrix}

(17)

Let us suppose that both A(z_{0}) and R(z_{0}) contain the single element k and that the associated eigenvalue λ_{k} is semisimple. Regarding the spectral abscissa, formula (16) says that α^{h}(z_{0}; d) is the maximum of the real parts of the eigenvalues of the matrix

∑_{l=1}^{s} B_{kl}d_{l}  (18)

whereas the lower bound for α^{h}(z_{0}; d) given by the right hand side of inequality (8) in Theorem 1 is the average of these quantities. This behavior is repeated in the case of the spectral radius. If ρ(z_{0}) = 0, then ρ^{h}(z_{0}; d) is the spectral radius of the matrix (18) while the lower bound given by (11) is the modulus of the average of the eigenvalues of (18). Similarly, if ρ(z_{0}) ≠ 0, then ρ^{h}(z_{0}; d) is the maximum of the values

\frac{1}{ρ(z_{0})}Re \overline{λ}_{k}λ′_{kl}

while the lower bound in (14) is the average of these values (since N_{k} = 0). Apparently the difference between the actual value of the directional derivative (1) and the lower bounds given by Theorems 1 and 2 can be quite great. Nonetheless, these lower bounds indicate when these directional derivatives are infinite-valued and in the generic nonderogatory case they give precise values for the directional derivative.

In the general case, when the eigenvalues are derogatory but not semisimple, little precise information is known beyond the general lower bounds provided by Theorems 1 and 2. The semisimple case illustrated above indicates a possible upper bound.

4 The Proximal Normal Subdifferential

In this section, we use our knowledge of the directional derivatives α^{h}(z; d) and ρ^{h}(z; d) to obtain insight into the structure of the proximal normal subdifferential for the spectral radius and spectral abscissa. A vector v ∈ C^{s} is said to be a proximal normal subgradient for the function f: C^{s} ↦ R at z_{0} ∈ C^{s} if

lim inf_{z→z_{0}} \frac{f(z) − f(z_{0}) − ⟨v, z − z_{0}⟩}{||z − z_{0}||^{2}} > −∞,  (19)

where the inner product on C^{s} is given by

⟨y, w⟩ := Re \overline{y}^{T} w.

The collection of all proximal normal subgradients at z_{0} is called the proximal normal subdifferential of f at z_{0} and is denoted by ∂_{2}f(z_{0}). Our interest in understanding the proximal normal subdifferential for the functions α and ρ stems from the rich calculus that is available for this subdifferential and its limits. For more information about this subdifferential, we refer the reader to Mordukhovich [6] and Rockafellar [8].

Let z_{0} ∈ C^{s} and suppose that A(z_{0}) has the block diagonal decomposition described in Section 2. According to Theorem 1, the directional derivative α^{h}(z_{0}; d) is bounded below by the support function for the set

Φ(z_{0}) := \{ \frac{1}{n_{k}} [tr \overline{B}_{k1}, ⋯, tr \overline{B}_{ks}]^{T} : k ∈ A(z_{0}) \}
+ [\{ζ[tr \overline{N}_{k}\overline{B}_{k1}, ⋯, tr \overline{N}_{k}\overline{B}_{ks}]^{T} : k ∈ A(z_{0}), Re ζ ≥ 0 \} ∪
span\{[tr \overline{N}_{k}^{j−1}\overline{B}_{k1}, ⋯, tr \overline{N}_{k}^{j−1}\overline{B}_{ks}]^{T} : j = 3,…, n_{k}, k ∈ A(z_{0}) \}],

where the support functional for a set Ω ⊂ C^{s} is defined by the expression

σ_{Ω}(d) := sup_{y∈Ω}⟨y, d⟩.

Similarly, by Theorem 2, the directional derivative ρ^{h}(z_{0}; d) is bounded below by the support functional for the set

Ξ(z_{0}) := \{ \frac{e^{iθ}}{n} [tr \overline{B}_{11}, ⋯, tr \overline{B}_{1s}]^{T} : θ ∈ [0, 2π] \}
+ span\{[tr \overline{N}_{1}^{j−1}\overline{B}_{11}, ⋯, tr \overline{N}_{1}^{j−1}\overline{B}_{1s}]^{T} : j = 2,…, n\},

when ρ(z_{0}) = 0, and is bounded below by the support functional for the set

Ψ(z_{0}) := \{ \begin{matrix}\frac{e^{iθ}}{n_{k}ρ(z_{0})} [tr \overline{N}_{k}\overline{B}_{k1}, ⋯, tr \overline{N}_{k}\overline{B}_{ks}]^{T} \\ +\frac{λ_{k}}{n_{k}ρ(z_{0})}[tr \overline{B}_{k1}, ⋯, tr \overline{B}_{ks}]^{T} \end{matrix} | k ∈ R(z_{0}, d), θ ∈ [0, 2π] \}

+ [\{ζλ_{k}^{2}[tr \overline{N}_{k}\overline{B}_{k1}, ⋯, tr \overline{N}_{k}\overline{B}_{ks}] : k ∈ R(z_{0}), Re ζ ≥ 0 \} ∪
span\{[tr \overline{N}_{k}^{j−1}\overline{B}_{k1}, ⋯, tr \overline{N}_{k}^{j−1}\overline{B}_{ks}]^{T} : j = 3,…, n_{k}, k ∈ R(z_{0}) \}],

when ρ(z_{0}) ≠ 0. The vectors defining the sets Φ, Ξ, and Ψ are our prime candidates for proximal normal subgradients. The partial results that we have been able to obtain to date depend upon the resolvent theory for analytic operator valued mappings on C^{s} developed by Baumgärtel [2]. The key result that we require in this regard is [2, Theorem 2, page 374]. In order to understand this result, one must first understand the notion of a λ_{k}-group for λ_{k} ∈ Σ(z_{0}).

Given λ_{k} ∈ Σ(z_{0}) the λ_{k}-group is the set of all functions λ(z) ∈ Σ(z) such that λ(z) → λ_{k} as z → z_{0}. The λ_{k}-groups are well defined since the spectrum Σ(z) is a continuous multifunction. The projection onto the invariant subspace for the entire λ_{k}-group is called the group projection for λ_{k}. The following remarkable fact, established in [2, Theorem 2, page 374], states that each such group projection is locally analytic.

Theorem 4 Let z_{0} ∈ C^{s}. Then there is a neighborhood Ω of z_{0} in C^{s} such that for each λ_{k} ∈ Σ(z_{0}) the group projection Π_{k}(z) associated with λ_{k} is analytic on Ω. Moreover, for each λ_{k} ∈ Σ(z_{0}) there is a neighborhood G_{k} of λ_{k} in C such that

Spec(A(z)Π_{k}(z)) = Σ(z) ∩ G_{k}

for all z ∈ Ω and λ_{k} ∈ Σ(z_{0}) where Spec(A(z)Π_{k}(z)) denotes the spectrum of A(z)Π_{k}(z).

This result is the key to establishing the local factorization of the characteristic polynomial used in Section 2 of Part I of this study. In the current context, we simply observe that Theorem 4 implies the analyticity of the trace of each λ_{k}-group,

τ_{k}(z) := tr A(z)Π_{k}(z),  (20)

since this trace is simply minus the coefficient of the (λ − λ_{k})^{n_{k}−1} term in the characteristic polynomial for A(z)P_{k}(z). From Lemma 3 in Part I, we find that the gradient of the trace of each λ_{k}-group at z_{0} is given by

∇τ_{k}(z_{0}) = [tr B_{k1}, ⋯, tr B_{ks}]^{T} .  (21)

By combining this fact with the observation that the maximum of a finite set of real numbers always exceeds (or equals) their average, we are able to establish that certain members of the sets Φ(z_{0}), Ξ(z_{0}) (if ρ(z_{0}) = 0), and Ψ(z_{0}) (if ρ(z_{0}) ≠ 0) are proximal normal subgradients.

Theorem 5 Let z_{0} ∈ C^{s} and suppose that A(z_{0}) has the block diagonal decomposition described in Section 2. Then

\frac{1}{n_{k}} [tr \overline{B}_{k1}, ⋯, tr \overline{B}_{ks}]^{T} ∈ ∂_{2}α(z_{0}),  (22)

for every k ∈ A(z_{0}).

Proof Let k ∈ A(z_{0}). Since τ_{k}(z) is analytic near z_{0} and α(z) ≥ (1/n_{k})τ_{k}(z) for z near z_{0} and k ∈ A(z_{0}), we have that

α(z) − α(z_{0}) − \frac{1}{n_{k}} Re ∇τ_{k}(z_{0})^{T} (z − z_{0}) ≥ \frac{1}{n_{k}} Re [τ_{k}(z) − τ_{k}(z_{0}) − ∇τ_{k}(z_{0})^{T} (z − z_{0})]
= O(||z − z_{0}||^{2}).

Thus, by (21)

lim inf_{z→z_{0}} \frac{α(z) − α(z_{0}) − ⟨\frac{1}{n_{k}} [tr \overline{B}_{k1}, ⋯, tr \overline{B}_{ks}], z − z_{0}⟩}{||z − z_{0}||^{2}} > −∞.

Theorem 6 Let z_{0} ∈ C^{s} and suppose that A(z_{0}) has the block diagonal decomposition described in Section 2.

1. Suppose that ρ(z_{0}) = 0 so that Σ(z_{0}) reduces to the single eigenvalue λ_{1} = 0. Then

\frac{ηe^{iθ}}{n} [tr \overline{B}_{11}, ⋯, tr \overline{B}_{1s}]^{T} ∈ ∂_{2}ρ(z_{0}),  (23)

for every η ∈ [0, 1] and θ ∈ [0, 2π].

2. Suppose that ρ(z_{0}) ≠ 0. Then

\frac{λ_{k}}{n_{k}ρ(z_{0})}[tr \overline{B}_{k1}, ⋯, tr \overline{B}_{ks}]^{T} ∈ ∂_{2}ρ(z_{0}),  (24)

for each k ∈ R(z_{0}).

Proof (1) Let η ∈ [0, 1] and θ ∈ [0, 2π] be given. Since τ_{1}(z) is analytic near z_{0}, we have that

ρ(z) − ρ(z_{0}) − ⟨\frac{ηe^{iθ}}{n} [tr \overline{B}_{k1}, ⋯, tr \overline{B}_{ks}], z − z_{0}⟩
≥ \frac{1}{n}[|τ_{1}(z)| − |τ_{1}(z_{0}) + ∇τ_{1}(z_{0})^{T} (z − z_{0})|]
= O(||z − z_{0}||^{2}),

which establishes the result.

(2) Let k ∈ R(z_{0}). Since τ_{k}(z) is analytic near z_{0}, we have that

ρ(z) − ρ(z_{0}) ≥ \frac{1}{n_{k}} [|τ_{k}(z)| − |τ_{k}(z_{0})|]  (25)
= \frac{|τ_{k}(z)|^{2} − |τ_{k}(z_{0})|^{2}}{n_{k}[|τ_{k}(z)| + |τ_{k}(z_{0})|]}
= \frac{2Re (\overline{τ}_{k}(z_{0})(τ_{k}(z) − τ_{k}(z_{0})))+ |τ_{k}(z) − τ_{k}(z_{0})|^{2}}{n_{k}[|τ_{k}(z)| + |τ_{k}(z_{0})|]}
≥ \frac{2Re (\overline{τ}_{k}(z_{0})(τ_{k}(z) − τ_{k}(z_{0})))}{n_{k}[|τ_{k}(z)| + |τ_{k}(z_{0})|]}
= \frac{2Re (\overline{τ}_{k}(z_{0})(∇τ_{k}(z_{0})^{T} (z − z_{0}) + O(||z − z_{0}||^{2})))}{n_{k}[|τ_{k}(z)| + |τ_{k}(z_{0})|]}
= \frac{2Re \overline{τ}_{k}(z_{0})(∇τ_{k}(z_{0})^{T} (z − z_{0}))}{2n_{k} |τ_{k}(z_{0})|} + O(||z − z_{0}||^{2})  (26)
= \frac{Re \overline{λ}_{k}∇τ_{k}(z_{0})(z − z_{0})}{n_{k}ρ(z_{0})} + O(||z − z_{0}||^{2}),

where the inequality (25) follows from the inequality ρ(z) ≥ (1/n_{k}) |τ_{k}(z)| and the equation ρ(z_{0}) = (1/n_{k}) |τ_{k}(z_{0})|, and the equality (26) follows from the formula

\frac{1}{(a + b)} − \frac{1}{2b} = \frac{b − a}{2b(a + b)}

and the fact that [|τ_{k}(z_{0})| − |τ_{k}(z)|] = O(||z − z_{0}||). Therefore,

ρ(z) − ρ(z_{0}) − ⟨\frac{λ_{k}}{n_{k}ρ(z_{0})}[tr \overline{B}_{k1}, ⋯, tr \overline{B}_{ks}], z − z_{0}⟩
= ρ(z) − ρ(z_{0}) − \frac{1}{n_{k}ρ(z_{0})}Re (\overline{λ}_{k}(∇τ_{k}(z_{0})^{T} (z − z_{0})))
≥ O(||z − z_{0}||^{2})

Although the results stated in Theorems 5 and 6 are significant, they do not clarify the status of the remaining vectors in the sets Φ, Ξ and Ψ. We have yet to establish that these vectors are proximal normal subgradients. Indeed, we are uncertain whether or not this is the case. The difficulty stems from the fact that those vectors involving the matrix N_{k} arise from the bifurcation of the eigenvalues into Puiseux-Newton series of the form (3) where the power p satisfies (1/n) ≤ p < 1. Because of this, the individual behavior of these eigenvalues is not fully captured by the trace of their associated λ_{k}-group since these traces are analytic at z_{0}. However, it was the properties of these traces, especially their analyticity, that allowed us to establish the results in Theorems 5 and 6. Consequently, a different approach may be necessary in order to establish whether or not those vectors in the sets Φ, Ξ and Ψ involving the matrix N_{k} are proximal normal subgradients.

References

[1] V. I. Arnold, On matrices depending on parameters, Russian Math. Surveys 26:2(1971), 29-43.

[2] H. Baumgärtel, Analytic Perturbation Theory for Matrices and Operators, Birkhäuser Verlag, Boston (1985).

[3] J. V. Burke and M. L. Overton, On the subdifferentiability of functions of a matrix spectrum I: Mathematical foundations, this volume.

[4] J. V. Burke and M. L. Overton, Differential properties of eigenvalues, in preparation.

[5] T. Kato, Perturbation Theory for Linear Operators, Grundlehren der mathematischen Wissenschaften 132, Springer-Verlag, New York (1980).

[6] B.S. Mordukhovich, Approximation Methods in Optimization and Control Problems, Moscow, Nauka, Main Physical and Mathematical Editions (1988) (In Russian).

[7] M. L. Overton and R. S. Womersley, On minimizing the spectral radius of a nonsymmetric matrix function: Optimality conditions and duality theory, SIAM J. Matrix Anal. Appl., 9(1988), 473-498.

[8] R.T. Rockafellar, Extensions of Subgradient Calculus with Applications to Optimization, Nonlinear Analysis, Theory, Methods and Applications, vol. 9, no. 7, 1985, pp.665–698.