Document [original]

μ-VALUES AND SPECTRAL VALUE SETS FOR LINEAR

PERTURBATION CLASSES DEFINED BY A SCALAR PRODUCT*

MICHAEL KAROW†

Abstract. We study the variation of the spectrum of matrices under perturbations which are self- or

skew-adjoint with respect to a scalar product. Computable formulas are given for the associated μ-values. The

results can be used to calculate spectral value sets for the perturbation classes under consideration. We discuss

the special case of complex Hamiltonian perturbations of a Hamiltonian matrix in detail.

Key words. linear systems, eigenvalues, perturbations, spectral value sets, μ-values

AMS subject classifications. 15A18, 15A57, 15A63, 93C05, 93C73

DOI. 10.1137/090774896

1. Introduction. μ-values are well established tools in stability analysis of uncer-

tain systems and in eigenvalue perturbation theory [5], [8], [10], [20], [25]. They can be

used to characterize several important quantities including stability radii and structured

eigenvalue condition numbers [11],[15]. The relationship of spectral value sets (also

known as structured pseudospectra) with μ-values will be shown below. There is a vast

literature on the problem of calculating μ-values with respect to various perturbation

classes [1], [2], [4], [6], [12], [14], [22], [23], [24]. In this paper we give computable formulas

for μif the underlying perturbation class is a set of self-adjoint or skew-adjoint matrices

with respect to a scalar product. The scalar product is assumed to be defined by a uni-

tary matrix; see section 4. It will be shown that in this case the associated μ-values can

be obtained by minimizing a univariate and unimodular function. The formulas pre-

sented in this paper have been applied in the software package Structured EigTool1

in order to compute structured pseudospectra with respect to skew-symmetric, Hermi-

tian, and Hamiltonian perturbations; see [13].

We use the following notation. The symbols Rand Crepresent the sets of real and

complex numbers, respectively. By Cn×mwe denote the set of nby mmatrices with

entries in C. Furthermore, Cn¼Cn×1is the set of column vectors of length n. The con-

jugate, the transpose, and the conjugate transpose of A∈Cn×mwill be written ¯

A,A⊤,

and A.IfAis square, then σðAÞand ρðAÞ¼C\σðAÞdenote its spectrum and its re-

solvent set. The identity matrix of size nwill be denoted by In. We drop the index nif

the size is clear from the context. The real and the imaginary part of z∈Care written as

ℜzand ℑz, respectively.

By a perturbation class Δwe mean a nonempty closed subset of Cl×qwhich is star

shaped with respect to 0∈Cl×q; i.e., if Δ∈Δ, then tΔ∈Δfor 0≤t≤1. We now give

the definition of μ-values.

DEFINITION 1.1. Let Δ⊆Cl×qbe a perturbation class, and let k·kbe a norm on Cl×q.

(i) The μ-value of M∈Cq×lwith respect to Δand k·kis

μΔðMÞ≔ðinffkΔk;Δ∈Δ;1∈σðΔMÞgÞ−1:ð1:1Þ

*Received by the editors October 26, 2009; accepted for publication (in revised form) by N. J. Higham May

25, 2011; published electronically September 6, 2011.

http://www.siam.org/journals/simax/32-3/77489.html

†Mathematics Institute, Berlin University of Technology, D-10623 Berlin, Germany, (karow@math.

TU-Berlin.de).

1Available from http://www.sam.math.ethz.ch/NLAgroup/software.html.

845

SIAM J. MATRIX ANAL.&APPL.

Vol. 32, No. 3, pp. 845–865

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

Thus, μΔðMÞis the inverse of the smallest norm of a Δ∈Δsuch that 1is an

eigenvalue of the matrix product ΔM. If there is no such Δ∈Δ,

then μΔðMÞ¼0.

(ii) If l¼q, then the μ-value of Mof second kind is defined as

μΔðMÞ≔inffkΔk;Δ∈Δ;detðM−ΔÞ¼0g:ð1:2Þ

Thus, ~

μΔðMÞis the structured distance of Mto the set of singular matrices.

We have ~

μΔðMÞ¼0iff Mis singular and ~

μΔðMÞ¼∞iff there is no Δ∈Δ

such that detðM−ΔÞ¼0.

It is easy to see that ~

μΔðMÞ¼μΔðM−1Þ−1if Mis nonsingular. Furthermore, if the

underlying norm is the spectral norm, then

μCl×qðMÞ¼σmaxðMÞfor all M∈Cl×q;

μCn×nðMÞ¼σminðMÞfor all M∈Cn×n;ð1:3Þ

where σmaxð·Þand σminð·Þdenote the maximum and the minimum singular value,

respectively.

We now briefly discuss the relationship of μ-values with the perturbation analysis of

eigenvalues. Consider matrix perturbations of the form

A⇝AΔ¼AþBΔC; Δ∈Δ;kΔk<δ;ð1:4Þ

where A∈Cn×n,B∈Cn×l,C∈Cq×nare fixed matrices. The set of all eigenvalues of all

matrices AΔgiven by (1.4) is called a spectral value set (stuctured pseudospectrum). It is

denoted by

σΔðA; B; C; δÞ≔[

Δ∈Δ;kΔk<δ

σðAþBΔCÞ

¼fs∈C;∃Δ∈Δ∶kΔk<δ;and detðsI −ðAþBΔCÞÞ ¼ 0g:ð1:5Þ

Let GðsÞ≔CðsI −AÞ−1B,s∈ρðAÞ, be the transfer function of the triple ðA; B; CÞ.

From the well known equivalence [7, Proposition 2.3]

s∈σðAþBΔCÞ⇔1∈σðΔGðsÞÞð1:6Þ

it follows that

μΔðGðsÞÞ ¼ ðinffkΔk;Δ∈Δ;s∈σðAþBΔCÞgÞ−1;s∈ρðAÞ:ð1:7Þ

This in turn yields

σΔðA; B; C; δÞ¼σðAÞ∪fs∈ρðAÞ;μΔðGðsÞÞ >δ−1g;δ>0:ð1:8Þ

For the cases B¼C¼Iand Δ⊆Cn×nwe simplify notation and denote the associated

spectral value sets by

σΔðA; δÞ≔σΔðA; I; I; δÞ¼ [

Δ∈Δ;kΔk<δ

σðAþΔÞ:ð1:9Þ

From the definition of ~

μit is immediate that, for A∈Cn×n,

846 MICHAEL KAROW

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

μΔðsI −AÞ¼inffkΔkjΔ∈Δ;s∈σðAþΔÞg;s∈C;ð1:10Þ

σΔðA; δÞ¼fs∈C;~

μΔðsI −AÞ<δg;δ>0:ð1:11Þ

The statements (1.8) and (1.11) yield that spectral value sets can be calculated by eval-

uating the functions s↦μΔðGðsÞÞ and s↦~

μΔðsI −AÞ, respectively.

The organization of this paper is as follows. In section 2 we provide useful charac-

terizations for μwith respect to Hermitian, complex symmetric, and complex skew-

symmetric perturbations. In particular we show that the μ-value and the ~

μ-value

for symmetric perturbations coincide with the μ-value and the ~

μ-value for unstructured

perturbations, i.e., with the maximum and the minimum singular value. Therefore, sym-

metric perturbations are not considered in the following sections. Section 3 contains the

main results of this paper. Here, we show how μ-values with respect to Hermitian and

skew-symmetric perturbations can be computed by maximizing or minimizing a certain

eigenvalue of a Hermitian pencil. The technical proofs of the main results are given in

section 6. In section 4 we treat μ-values for perturbation classes of self- and skew-adjoint

matrices with respect to a scalar product. Section 5 deals with a special case: μ-values

and spectral value sets for Hamiltonian perturbations of Hamiltonian matrices.

Throughout the rest of this paper the underlying norm k·kis the spectral norm.

2. Hermitian, symmetric, and skew-symmetric perturbations. In this sec-

tion we derive basic characterizations for μ-values with respect to the perturbation

classes

Δ∈fHermðnÞ;SymðnÞ;SkewðnÞg;

where

HermðnÞ≔fΔ∈Cn×n;Δ¼Δg;

SymðnÞ≔fΔ∈Cn×n;Δ⊤¼Δg;

SkewðnÞ≔fΔ∈Cn×n;Δ⊤¼−Δg:ð2:1Þ

THEOREM 2.1. Let M∈Cn×n. Then the following statements hold.

(a) If the Hermitian matrix Mh¼iðM−MÞis positive or negative definite,

then detðM−ΔÞ≠0and detðΔM−IÞ≠0for all Δ∈HermðnÞ. Hence,

μHermðMÞ¼∞and μHermðMÞ¼0.IfMhis not definite, then

μHermðMÞ¼maxfkMvk;v∈Cn;kvk¼1;v

Mhv¼0g;

μHermðMÞ¼minfkMvk;v∈Cn;kvk¼1;v

Mhv¼0g:ð2:2Þ

(b) Let Ms¼MþM⊤. Then, for n≥2,

μSkewðMÞ¼maxfkMvk;v∈Cn;kvk¼1;v

⊤Msv¼0g;

μSkewðMÞ¼minfkMvk;v∈Cn;kvk¼1;v

⊤Msv¼0g:ð2:3Þ

μSymðMÞ¼maxfkMvk;v∈Cn;kvk¼1g¼σmaxðMÞ;

μSymðMÞ¼minfkMvk;v∈Cn;kvk¼1g¼σminðMÞ;

μ-VALUES AND SPECTRAL VALUE SETS 847

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

where σmaxð·Þand σminð·Þdenote the maximum and the minimum singular

values.

Note that the μ-values for the symmetric case coincide with the μ-values for the

unstructured case Δ¼Cn×n(see relation (1.3)).

Proof. For Δ⊆Cn×nand x; y ∈Cnlet νΔðx; yÞ≔inffkΔk;Δ∈Δ;Δx¼yg:The

relation Δx¼yimplies kΔkkxk≥kyk. Thus, for all x≠0,

νΔðx; yÞ≥kyk∕kxk:ð2:4Þ

From the equivalences

1∈σðΔMÞ⇔ΔðMvÞ¼vfor some vwith kvk¼1;

detðM−ΔÞ¼0⇔Δv¼Mvfor some vwith kvk¼1;

1∈σðΔMÞ⇔ΔðMvÞ¼vfor some vwith kvk¼1;

detðM−ΔÞ¼0⇔Δv¼Mvfor some vwith kvk¼1;

it follows that

μΔðMÞ¼ðinffνΔðMv;vÞ;v∈Cn;kvk¼1gÞ−1;

μΔðMÞ¼inffνΔðv; MvÞ;v∈Cn;kvk¼1g:ð2:5Þ

Let Δ∈HermðnÞ. Then the relation Δx¼yimplies that ℑðxyÞ¼ℑðxΔxÞ¼0.

Suppose that ℑðxyÞ¼0and x≠0. Then by [18, Theorem A.2] there exists

Δ∈HermðnÞwith Δx¼yand kΔk¼kyk∕kxk. This combined with (2.4) yields that,

for any x; y ∈Cn,x≠0,

νHermðx; yÞ¼8

kyk∕kxkif x≠0 and ℑðxyÞ¼0;

0ifx¼y¼0;

∞otherwise.

ð2:6Þ

For any v∈Cn, we have that ℑðvðMvÞÞ ¼ ð1∕2iÞðvðMvÞ−ðMvÞvÞ¼

−ð1∕2ÞvMhv. Hence, (2.5) combined with (2.6) yields

μHermðMÞ¼supfkMvk;v∈Cn;kvk¼1;v

Mhv¼0g;

μHermðMÞ¼inffkMvk;v∈Cn;kvk¼1;v

Mhv¼0g:

Suppose that Mhis definite. Then vMhv≠0for all v≠0. Hence, μHermðMÞ¼0and

μHermðMÞ¼∞. Suppose Mhis not definite. Then the set of unit vectors vsatisfying

vMhv¼0is nonempty and closed. This concludes the proof of claim (a).

Let Δ∈SkewðnÞ. Then the relation Δx¼yimplies that x⊤y¼x⊤Δx¼0. Suppose

that x⊤y¼0and x≠0. Then by [18, Theorem A.2] there exists Δ∈SkewðnÞwith

Δx¼yand kΔk¼kyk∕kxk. This combined with (2.4) yields that, for any x; y ∈Cn,

x≠0,

νSkewðx; yÞ¼8

kyk∕kxkif x≠0andyTx¼0;

0ifx¼y¼0;

∞otherwise:

ð2:7Þ

848 MICHAEL KAROW

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

We have, for any v∈Cn, that ðMvÞ⊤v¼ð1∕2ÞððMvÞ⊤vþv⊤ðMvÞÞ ¼ ð1∕2Þv⊤Msv.

Furthermore, if n≥2, then by Lemma 6.2 there exists a unit vector vwith

v⊤Msv¼0. Hence, (2.7) combined with (2.5) yields claim (b).

If x≠0, then by [18, Theorem A.2] there exists Δ∈SymðnÞsuch that Δx¼yand

kΔk¼kyk∕kxk. Hence, we have

νSymðx; yÞ¼8

kyk∕kxkif x≠0;

0ifx¼y¼0;

∞otherwise:

ð2:8Þ

Now (2.5) yields claim (c). ▯

3. Computation of μfor the Hermitian and the skew-symmetric case.

Based on the identities (2.2) and (2.3) one can derive the following two theorems. They

provide computable formulas for the μ-values with respect to Hermitian and skew-

symmetric perturbations. In order not to disturb the flow of exposition, the proofs

are given in section 6.

THEOREM 3.1. Let M∈Cn×n,Mh¼iðM−MÞ, and

ϕðtÞ¼λmaxðMMþtMhÞ;

ϕðtÞ¼λminðMMþtMhÞ;t∈R;

where λmax and λmin denote the largest and the smallest eigenvalue, respectively. Then the

function ϕis convex and the function ~

ϕis concave. Suppose that Mhis not definite. Then

μHermðMÞ¼ðinft∈RϕðtÞÞ1∕2;~

μHermðMÞ¼ðsupt∈R~

ϕðtÞÞ1∕2:

Furthermore, the following statements hold.

(i) If Mhis indefinite, then the infimum is attained in the interval ½t1;t

2and the

supremum is attained in the interval ½−t2;−t1, where

t1¼σ2

maxðMÞ−σ2

minðMÞ

λminðMhÞ;t

2¼σ2

maxðMÞ−σ2

minðMÞ

λmaxðMhÞ:ð3:1Þ

(ii) Suppose Mhis positive (negative) semidefinite but not definite. Then the

functions ϕ∶R→Rand ~

ϕ∶R→Rare both increasing (both decreasing).

Moreover, we have

μHermðMÞ¼σmaxðMVÞ

¼(ðlimt→−∞ ϕðtÞÞ1∕2if Mhis positive semidefinite;

ðlimt→∞ϕðtÞÞ1∕2if Mhis negative semidefinite;

μHermðMÞ¼σminðMVÞ

¼(ðlimt→∞~

ϕðtÞÞ1∕2if Mhis positive semidefinite;

ðlimt→−∞ ~

ϕðtÞÞ1∕2if Mhis negative semidefinite;

where Vis any matrix whose columns form an orthonormal basis of ker Mh.

Remark 3.2. For any M∈Cn×nand any t∈R,

MMþtMh¼ðM−itIÞðM−itI Þ−t2I:

μ-VALUES AND SPECTRAL VALUE SETS 849

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

Hence, the objective functions in Theorem 3.1 can be written as

ϕðtÞ¼σ2

maxðM−itI Þ−t2;~

ϕðtÞ¼σ2

minðM−itIÞ−t2:

Let I⊆Rbe an interval. A function f∶I→Ris said to be unimodal2if each local

extremum of fattained in the interior of Iequals the global minimum of f. The global

minimum of a continuous unimodal function on a compact interval Ican reliably be

found by golden section search [21, section 2.1] or by any other locally minimizing

algorithm. The functions ϕand −~

ϕ, being convex, are unimodal. In [13] we proposed

a bisection method using the derivative of ϕto compute μHermðMÞ¼mint∈½t1;t2ϕðtÞin

the case that Mhis indefinite.

Next, we consider skew-symmetric perturbations.

THEOREM 3.3. Let M∈Cn×n,n≥2, and let Ms¼MþM⊤. For t∈½0;∞Þ, let

FðtÞ¼MMt

tMsMM∈Hermð2nÞ

and

ψðtÞ¼λ2ðFðtÞÞ;~

ψðtÞ¼λ2n−1ðFðtÞÞ;

where λ2and λ2n−1denote the second largest and the second smallest eigenvalue, respec-

tively. Then the functions ψð·Þand −~

ψð·Þare both unimodal on ½0;∞Þ, and

μSkewðMÞ¼ðinft∈½0;∞ÞψðtÞÞ1∕2;

μSkewðMÞ¼ðsupt∈½0;∞Þ~

ψðtÞÞ1∕2:

Furthermore, the following statements hold.

(i) If rankðMsÞ≥2, then both the infimum and the supremum are attained in the

interval ½0;t

1, where t1¼2σ2

maxðMÞ∕σ2ðMsÞand σ2ð·Þdenotes the second

largest singular value.

(ii) Suppose rankðMsÞ¼1. Then the function ψ∶½0;∞Þ→Ris decreasing, the

function ~

ψ∶½0;∞Þ→Ris increasing, and

μSkewðMÞ¼σmaxðMVÞ¼limt→∞ψðtÞ;

μSkewðMÞ¼σminðMVÞ¼limt→∞~

ψðtÞ;

where Vis any matrix whose columns form an orthonormal basis of ker Ms.

(iii) If Ms¼0, then the functions ψð·Þand ~

ψð·Þare both constant, and

μSkewðMÞ¼σmaxðMÞ¼ψð0Þ;

μSkewðMÞ¼σminðMÞ¼ ~

ψð0Þ:

Remark 3.4. The pencil FðtÞin Theorem 3.3 satisfies

FðtÞ¼MtI

tI ¯

MMtI

tI ¯

M−t2I:

2The definition of unimodality is not unique in the literature. By our definition strictly monotone functions

as well as constant functions are unimodal.

850 MICHAEL KAROW

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

Thus, the objective functions in Theorem 3.3 can be written as

ψðtÞ¼σ2

2MtI

tI ¯

M−t2;~

ψðtÞ¼σ2

2n−1MtI

tI ¯

M−t2;ð3:2Þ

where σ2and σ2n−1denote the second largest and the second smallest singular value,

respectively. For the computation of ψusing the representation (3.2), see [13]. ▯

Example 3.5. We compute μSkewðMÞand ~

μSkewðMÞfor M¼iI −A, where

A¼2

0100

−10 0 0

000

5:ð3:3Þ

In this case the pencil FðtÞsatisfies

FðtÞ¼MMt

tMsMM¼H−2itI

2itI ¯

H;H≔MM¼2

101 20i0

−20i101 0

001

For λ∈C\σðHÞ, we have λI−FðtÞ¼TGðλÞT, where

GðλÞ¼λI−H0

0ðλI−¯

HÞ−4t2ðλI−HÞ−1;T¼I0

2itðλI−HÞ−1I:

Thus, the characteristic polynomial of FðtÞis

detðλI−FðtÞÞ ¼ detðGðλÞÞ

¼detððλI−HÞðλI−¯

HÞ−4t2IÞ

¼ðλ2−2λþ1−4t2Þðλ2−202λþ9801 −4t2Þ2:

Hence, the six eigenvalues of FðtÞ(denoted by lkðtÞ)are

l1ðtÞ¼1þ2t;

l2ðtÞ¼1−2t;

l3ðtÞ¼l4ðtÞ¼101 þ2ﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ

100 þt2

l5ðtÞ¼l6ðtÞ¼101 −2ﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ

100 þt2

The eigenvalue curves lkð·Þare displayed in Figure 3.1. The second largest eigenvalue of

FðtÞis ψðtÞ¼λ2ðFðtÞÞ ¼ l3ðtÞ¼l4ðtÞ:The function ψðtÞattains its minimum at t¼0.

Thus, μSkewðMÞ¼ ﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ

ψð0Þ

p¼11. The second smallest eigenvalue of FðtÞis ~

ψðtÞ¼

λ5ðFðtÞÞ ¼ minfl1ðtÞ;l5ðtÞg:The function ~

ψðtÞattains its maximum at t¼24, where

the curves l1ð·Þand l5ð·Þmeet. Thus, ~

μSkewðMÞ¼ ﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ

ψð24Þ

q¼7. The skew-symmetric

spectral value sets

σSkewðA; δÞ¼ [

Δ∈Skewð3Þ;kΔk<δ

σðAþΔÞ¼fs∈C;~

μSkewðsI −AÞ<δg;δ∈f4;7;9g;

μ-VALUES AND SPECTRAL VALUE SETS 851

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

are depicted in the upper row of Figure 3.2. The lower row shows the unstructured spec-

tral value sets

σC3×3ðA; δÞ¼ [

Δ∈C3×3;kΔk<δ

σðAþΔÞ¼fs∈C;σminðsI −AÞ<δg;δ∈f4;7;9g:

The crosses mark the eigenvalues of A. Observe that the eigenvalue 0 is an isolated point

of σSkewðA; δÞ,δ¼4;7. This can be explained as follows. Let Dbe a disk about 0 that

does not contain an eigenvalue of Adifferent from 0. Let Δ∈Skewð3Þ.Ifδ>0is suffi-

ciently small and kΔk<δ, then by continuity only one eigenvalue of AþΔis contained

in D. This eigenvalue is 0 since AþΔis a skew-symmetric matrix of odd dimension.

FIG. 3.1. The eigenvalue curves lkð·Þ,ψð·Þ, and ~

ψð·Þfrom Example 3.5.

FIG. 3.2. The sets σSkewðA; δÞ(upper row) and σC3×3ðA; δÞ(lower row) for Adefined in (3.3).

852 MICHAEL KAROW

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

4. Self- and skew-adjoint matrices. We now treat μ-values with respect to lin-

ear subspaces which are induced by a scalar product on Cn. Specifically we show that

these μ-values are closely related to the μ-values with respect to Hermitian, symmetric,

and skew-symmetric perturbations. For nonsingular Π∈Cn×n, we consider the scalar

products

hx; yiΠ¼x⋆Πy; x; y ∈Cn;⋆∈f;⊤g:

Depending on whether ⋆¼⊤or ⋆¼the scalar product is a bilinear form or a sesqui-

linear form. We assume that Πsatisfies a symmetry relation of the form

Π⋆¼ϵ0Π;with ϵ0¼−1orϵ0¼1:ð4:1Þ

A matrix Δ∈Cn×nis said to be self-adjoint (skew-adjoint) with respect to the scalar

product h·;·iΠif

hΔx; yiΠ¼ϵhx; ΔyiΠfor all x; y ∈Cn

ð4:2Þ

and ϵ¼1(ϵ¼−1). It is easy to see that the relation (4.2) is equivalent to

ðΠΔÞ⋆¼ϵ0ϵΠΔ. We denote the sets of self- and skew-adjoint matrices by

structðΠ;⋆;ϵÞ≔fΔ∈Cn×n;ðΠΔÞ⋆¼ϵ0ϵΠΔg:

Thus,

Δ∈structðΠ;⋆;ϵÞ⇔8

ΠΔ ∈HermðnÞif ϵ0ϵ¼1;⋆¼;

ΠΔ ∈SymðnÞif ϵ0ϵ¼1;⋆¼⊤;

ΠΔ ∈SkewðnÞif ϵ0ϵ¼−1;⋆¼⊤;

iΠΔ ∈HermðnÞif ϵ0ϵ¼−1;⋆¼.

ð4:3Þ

In many applications Πis unitary. The most common examples are Π∈fdiagðIk;

−In−kÞ;En;Jng, where

Jn≔0In

−In0∈C2n×2n;E

n≔2

5∈Cn×n:ð4:4Þ

For unitary Πthe μ-values of the associated self- and skew-adjoint classes can be ex-

pressed in terms of the μ-values for HermðnÞ,SymðnÞ, and SkewðnÞ.

PROPOSITION 4.1. Suppose Π∈Cn×nis unitary and satisfies Π⋆¼ϵ0Πwith ϵ0¼−1

or ϵ0¼1. Let struct ¼structðΠ;⋆;ϵÞ. Then for any M∈Cn×n,

μstructðMÞ¼8

μHermðMΠÞif ϵ0ϵ¼1;⋆¼;

μSymðMΠÞif ϵ0ϵ¼1;⋆¼⊤;

μSkewðMΠÞif ϵ0ϵ¼−1;⋆¼⊤;

μHermðiMΠÞif ϵ0ϵ¼−1;⋆¼;

ð4:5Þ

and

μ-VALUES AND SPECTRAL VALUE SETS 853

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

μstructðMÞ¼8

μHermðΠMÞif ϵ0ϵ¼1;⋆¼;

μSymðΠMÞif ϵ0ϵ¼1;⋆¼⊤;

μSkewðΠMÞif ϵ0ϵ¼−1;⋆¼⊤;

μHermðiΠMÞif ϵ0ϵ¼−1;⋆¼.

ð4:6Þ

Proof. Since Πis unitary we have

μstructðMÞ¼ðinffkΔk;Δ∈struct;1∈σðΔMÞgÞ−1

¼ðinffkΠΔk;Δ∈struct;1∈σððΠΔÞðMΠÞÞgÞ−1;ð4:7Þ

μstructðMÞ¼inffkΔk;Δ∈struct;detðM−ΔÞ¼0g

¼inffkΠΔk;Δ∈struct;detðΠM−ΠΔÞ¼0g:ð4:8Þ

Thus, the first three identities in (4.5) and (4.6) are consequences of the first three equiv-

alences of (4.3). On replacing in (4.7) and (4.8) Πby iΠone obtains the fourth identity

in (4.5) and (4.6) from the fourth equivalence of (4.3). ▯

5. Application: Spectral value sets for Hamiltonian matrices. A matrix

which is skew-adjoint with respect to the sesquilinear form induced by Jnis called

Hamiltonian. Let HamðnÞ≔fΔ∈C2n×2n;ΔJn¼−JnΔgdenote the set of complex

Hamiltonian matrices. Each H∈HamðnÞhas block structure

H¼AC

B−Awith A∈Cn×nand B;C ∈HermðnÞ:

The spectral value sets of Hwith respect to Hamiltonian perturbations are by (1.11)

σHamðH;δÞ¼ [

Δ∈HamðnÞ;kΔk<δ

σðHþΔÞ¼fs∈C;fðsÞ<δg;δ>0;ð5:1Þ

where fðsÞ≔~

μHamðsI −HÞ,s∈C. Let ΦðsÞ≔JnðsI −HÞ¼h−BsIþA

−sI þAC

and ΦhðsÞ≔iðΦðsÞ−ΦðsÞÞ¼2iðℜsÞJn. Then by Corollary 4.1 and Theorem 2.1

fðsÞ¼ ~

μHermðΦðsÞÞ

¼minfkΦðsÞvk;v∈C2n;kvk¼1;v

ΦhðsÞv¼0g

¼σminðsI −HÞif s∈iR;

minfkðsI −HÞvk;v∈C2n;kvk¼1;v

Jnv¼0gotherwise:

ð5:2Þ

The latter equation holds since ΦðsÞ¼0iff s∈iR, and kΦðsÞvk¼kðsI −HÞvkfor all

v∈C2n. Since ~

μC2n×2nðsI −HÞ¼σminðsI −HÞ, (5.2) implies

σHamðHÞ∩ðiRÞ¼σC2n×2nðHÞ∩ðiRÞ:

Let s∈C\ðiRÞ. Then ΦhðsÞis indefinite since λmaxðΦhðsÞÞ ¼ −λminðΦhðsÞÞ ¼ 2jℜsj.

Thus, by Theorem 3.1

854 MICHAEL KAROW

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

fðsÞ¼maxt∈½−t0

2jℜsj;t0

2jℜsjλminðΦðsÞΦðsÞþtΦhðsÞÞ1

¼maxτ∈½−t0;t0λminððsI −HÞðsI −HÞþτiJnÞ1

2;ð5:3Þ

where t0¼σ2

maxðsI −HÞ−σ2

minðsI −HÞ. Formula (5.3) and the upper equation in (5.2)

have been used to compute the spectral value sets σHamðHγ;1Þin the upper row of

Figure 5.1. Here,

Hγ¼0−γ−1B

γB0;B¼diagð1;6;−6Þ;γ∈f1;1.3;5;6g:

The lower row in the figure shows the sets σC6×6ðHγ;1Þfor comparison. The crosses mark

the eigenvalues of Hγ. The pictures illustrate the fact that spectral value sets of

Hamiltonian matrices with respect to Hamiltonian perturbations are not necessarily

open. The proposition below states basic topological facts about these sets.

PROPOSITION 5.1. Let H∈HamðnÞand δ>0. Then

(a) σHamðH;δÞ∩ðiRÞis an open subset of iR.

(b) σHamðH;δÞ\ðiRÞis an open subset of C.

Let s0∈iRbe a purely imaginary eigenvalue of H, and let Edenote the associated

eigenspace.

of σHamðH;δÞ.

(d) Suppose that vJnv≠0for all v∈E\f0g. Then there exists a δ0>0and a disk

Dwith center s0such that σHamðH;δÞ∩D⊂iRfor all δ<δ0.

FIG. 5.1. The sets σHamðHγ;1Þ(upper row) and σC6×6ðHγ;1Þ(lower row).

μ-VALUES AND SPECTRAL VALUE SETS 855

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

Proof. For s∈C, let f1ðsÞ¼σminðsI −HÞand f2ðsÞ¼mins∈KkðsI −HÞvk, where

K¼fv∈C2n;kvk¼1;v

Jnv¼0g. Then f1and f2are continuous at all s∈C. (The

continuity of f2follows from the continuity of the map ðs; vÞ↦kðsI −HÞvkand the

compactness of K.) Furthermore, by (5.2)

σHamðH;δÞ∩ðiRÞ¼fs∈iR;f1ðsÞ<δg;

σHamðH;δÞ\ðiRÞ¼fs∈C\iR;f2ðsÞ<δg:ð5:4Þ

Hence, σHamðH;δÞ∩ðiRÞis an open subset of iRand σHamðH;δÞ\ðiRÞis an open subset

of C. Now let s0∈iRbe a purely imaginary eigenvalue of H. Then f1ðs0Þ¼0. Suppose

there exists an eigenvector v≠0with vJnv¼0. Then f2ðs0Þ¼0. From (5.4) it then

follows that s0is an interior point of σHamðH;δÞ. Assume there is no eigenvector such

that vJnv¼0. Then f2ðs0Þ>0. Let δ0¼f2ðs0Þ∕2. Then by continuity there is a disk

Dwith center s0such that f2ðsÞ≥δ0for s∈D. Thus, by (5.4)

ðσHamðH;δÞ\ðiRÞÞ ∩D¼∅for δ<δ0:▯

6. Proofs of Theorems 3.1 and 3.3. In what follows λmaxðHÞ¼λ1ðHÞ≥λ2ðHÞ≥

::: ≥λnðHÞ¼λminðHÞdenote the eigenvalues of H∈HermðnÞin decreasing order. The

corresponding eigenspaces are denoted by EkðHÞ,k¼1; :::;n. Recall that

λnþ1−kðHÞ¼−λkð−HÞð6:1Þ

and

λkðHÞþλminðGÞ≤λkðHþGÞ≤λkðHÞþλmaxðGÞð6:2Þ

for all H;G ∈HermðnÞ,k¼1; :::;n. The proofs of Theorem 3.1 and 3.3 use the same

technique as in [9], [17], [19], [22]. We need the following preliminary result on the ei-

genvalues and eigenvectors of a Hermitian pencil.

PROPOSITION 6.1. Let H0;H1∈HermðnÞand HðtÞ¼H0þtH1,t∈R, and

k∈f1; :::;ng.

(a) Suppose the function t↦λkðHðtÞÞ,t∈R, attains a local extremum at t0. Then

there exists a unit vector v∈EkðHðt0ÞÞ such that vH1v¼0. Suppose the ex-

tremum is a local minimum and we have k¼nor λkðHðt0ÞÞ >λkþ1ðHðt0ÞÞ.

Then vH1w¼0for all v; w ∈EkðHðt0ÞÞ.

(b) Suppose λkðH1Þ¼0and either k¼1or λk−1ðH1Þ>0. Then

limt→∞λkðHðtÞÞ ¼ λmaxðVH0VÞ;ð6:3Þ

where V∈Cn×pis a matrix whose columns form an orthonormal basis

of ker H1.

Proof. By [16, Thm. II.1.10 and subsec. II.4.5] there exist analytic functions

lj∶R→R,vj∶R→Rn,j¼1; :::;n, such that HðtÞvjðtÞ¼ljðtÞvjðtÞand

viðtÞvjðtÞ¼1ifi¼j;

0 otherwise

ð6:4Þ

for i; j ∈f1; :::;ngand t∈R. Hence, the vectors vjðtÞform an othonormal basis of

eigenvectors of HðtÞand the numbers ljðtÞare the corresponding eigenvalues not

necessarily ordered up to size. By differentiating the identity ljðtÞviðtÞvjðtÞ¼

viðtÞHðtÞvjðtÞ,t∈R, we obtain

856 MICHAEL KAROW

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

dt ðljðtÞviðtÞvjðtÞÞ ¼ d

dt ðviðtÞHðtÞvjðtÞÞ

¼viðtÞH 0ðtÞvjðtÞþv 0

iðtÞHðtÞvjðtÞþviðtÞHðtÞv 0

jðtÞ

¼viðtÞH1vjðtÞþljðtÞv 0

iðtÞvjðtÞþliðtÞviðtÞv 0

jðtÞ

¼viðtÞH1vjðtÞ

þljðtÞd

dt ðviðtÞvjðtÞÞ þ ðliðtÞ−ljðtÞÞviðtÞv 0

jðtÞ:

This combined with (6.4) yields the following facts.

Fact 1.Let i≠jand t∈R.IfliðtÞ¼ljðtÞ, then viðtÞH1vjðtÞ¼0:

Fact 2.The derivative of ljð·Þat t∈Rsatisfies l 0

jðtÞ¼vjðtÞH1vjðtÞ,j¼1; :::;n.

Let JkðtÞ¼fj;ljðtÞ¼λkðHðtÞÞg. Then the vectors vjðtÞ,j∈JkðtÞ, form an ortho-

normal basis of the eigenspace EkðHðtÞÞ. For any pair of indices i,j, the analytic func-

tions t↦liðtÞ,t↦ljðtÞ, are either identical or their graphs meet in a discrete set of

points. Thus, for any t0∈R, there are an ϵ>0and indices j1;j

2∈Jkðt0Þsuch that

λkðHðtÞÞ ¼ lj1ðtÞfor t∈½t0;t

0þϵ;

lj2ðtÞfor t∈½t0−ϵ;t

0:

ð6:5Þ

Hence, if the function t↦λkðHðtÞÞ attains a local minimum at t0, then l 0

j1ðt0Þ¼

vj1ðt0ÞH1vj1ðt0Þ≥0and l 0

j2ðt0Þ¼vj2ðt0ÞH1vj2ðt0Þ≤0. Clearly, if j1¼j2, then

vj1ðt0ÞH1vj1ðt0Þ¼0.Ifj1≠j2, then by continuity there exists a vector v∈EkðHðt0ÞÞ \

f0gof the form v¼cosðαÞvj1ðt0ÞþsinðαÞvj2ðt0Þ,α∈½0;π∕2, such that vH1v¼0.An

analogous argument holds if λkð·Þattains a local maximum. Thus, we have shown the

first statement of (a). To prove the second consider a t0∈Rsuch that λkðHðt0ÞÞ >

λkþ1ðHðt0ÞÞ. Then by continuity and the definition of Jkðt0Þthere exists an ϵ>0

such that

ljðtÞ>λkþ1ðHðtÞÞ for all j∈Jkðt0Þand all t∈½t0−ϵ;t

0þϵ:

Since each ljðtÞequals one of the eigenvalues of HðtÞit follows that

ljðtÞ≥λkðHðtÞÞ for all j∈Jkðt0Þand all t∈½t0−ϵ;t

0þϵ:ð6:6Þ

Note that the latter statement trivially holds for all t0∈Rif k¼n. Suppose now that λk

attains a local minimum at t0. Then (6.6) implies that the functions ljðtÞ,j∈Jkðt0Þ,

have a local minimum at t0, too. Thus, vjðt0ÞH1vjðt0Þ¼l 0

jðt0Þ¼0for all j∈Jkðt0Þ.

The latter combined with Fact 1 yields that viðt0ÞH1vjðt0Þ¼0for all i; j ∈Jkðt0Þ.

Hence, vH1w¼0for all v; w ∈EkðHðt0ÞÞ ¼ spanfvjðt0Þ;j∈Jkðt0Þg. This completes

the proof of (a).

In order to show (b) we consider the pencil ~

HðtÞ¼H1þtH0.Notethat

HðtÞ¼t~

Hð1∕tÞfor t≠0.Let~

vj∶R→Cn,~

lj∶R→Rbe analytic functions, such that

the vectors ~

vjðtÞform an orthonormal basis of eigenvectors of ~

HðtÞwith corresponding

eigenvalues ~

ljðtÞ.Letj1; :::;j

p∈f1; :::;ngdenote the indices jfor which ljð0Þ¼

λkð~

Hð0ÞÞ ¼ λkðH1Þ. Then the columns of the matrix V1≔½~

vj1ð0Þ; :::;~

vjpð0Þ form an

orthonormal basis of Ekð~

Hð0ÞÞ ¼ EkðH1Þ.Furthermore,byFacts1and2(appliedto

the pencil ~

HðtÞat t¼0) the matrix G1≔½~

vjαð0ÞH0~

vjβð0Þα;β¼1;:::;p ¼V

1H0V1is a

μ-VALUES AND SPECTRAL VALUE SETS 857

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

diagonal matrix whose diagonal elements are the derivatives ~

l 0

j1ð0Þ; :::; ~

l 0

jpð0Þ.LetV∈

Cn×pbe another matrix whose columns form an orthonormal basis of EkðH1Þ.ThenV¼

V1Ufor some unitary matrix U∈Cp×p. Hence, the matrix G≔VH0V¼UG1Uis

similar to G1. Thus, the derivatives ~

l 0

j1ð0Þ; :::; ~

l 0

jpð0Þare the eigenvalues of G.Assume

now w.l.o.g. that ~

lj1ðtÞ¼maxf~

ljαðtÞ;α¼1; :::;pgfor t∈½0;ϵand some ϵ>0.Then

l 0

j1ð0Þ¼maxfl 0

jαð0Þ;α¼1; :::;pg¼λmaxðG1Þ¼λmaxðGÞ:Assume further that k¼1

or λk−1ðH1Þ>λkðH1Þ.Then~

lj1ðtÞ¼λkð~

HðtÞÞ for t∈½0;ϵ. If additionally λkðH1Þ¼0,

then

λkð~

HðtÞÞ ¼ ~

lj1ðtÞ¼ ~

l 0

j1ð0ÞtþoðtÞ¼λmaxðGÞtþoðtÞ;limt→0þ

oðtÞ

t¼0:

It follows that

limt→∞λkðHðtÞÞ ¼ limt→∞tλk~

H1

t¼limt→∞tλmaxðGÞ1

tþo1

t¼λmaxðGÞ:

This concludes the proof of (b). ▯

Some of the assertions of Proposition 6.1 were shown in [9]. The complete proof was

given here for the convenience of the reader.

We are now in a position to prove Theorem 3.1. To this end we introduce the

notation

mhðH0;H1Þ≔supfvH0v;v∈Cn;v

H1v¼0;kvk¼1g;

mhðH0;H1Þ≔inffvH0v;v∈Cn;v

H1v¼0;kvk¼1g;

where H0;H1∈HermðnÞ. Then Theorem 2.1 states that

μHermðMÞ¼ðmhðMM;MhÞÞ1∕2;~

μHermðMÞ¼ð~

mhðMM;MhÞÞ1∕2

for any M∈Cn×nfor which the matrix Mh¼iðM−MÞis not definite. Thus,

Theorem 3.1 is obtained by substituting MMfor H0and Mhfor H1in the following

general result.

THEOREM 6.2. Let H0;H1∈HermðnÞ, and

ϕðtÞ¼λmaxðH0þtH1Þ;

ϕðtÞ¼λminðH0þtH1Þ;t∈R:

Then the function ϕis convex, the function ~

ϕis concave, and

mhðH0;H1Þ¼inf

t∈RϕðtÞ;

mhðH0;H1Þ¼sup

t∈R

ϕðtÞ:ð6:7Þ

Furthermore, the following statements hold.

(i) If H1is indefinite, then the infimum is attained in the interval ½t1;t

2and the

supremum is attained in the interval ½−t2;−t1, where

858 MICHAEL KAROW

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

t1¼λmaxðH0Þ−λminðH0Þ

λminðH1Þ;t

2¼λmaxðH0Þ−λminðH0Þ

λmaxðH1Þ:ð6:8Þ

(ii) Suppose H1is positive (negative) semidefinite but not definite. Then the func-

tions ϕð·Þand ~

ϕð·Þare both increasing (both decreasing). Moreover, we have

mhðH0;H1Þ¼λmaxðVH0VÞ

¼limt→−∞ ϕðtÞif H1is positive semidefinite;

limt→∞ϕðtÞif H1is negative semidefinite;

mhðH0;H1Þ¼λminðVH0VÞ

¼limt→∞~

ϕðtÞif H1is positive semidefinite;

limt→−∞ ~

ϕðtÞif H1is negative semidefinite;

where Vis any matrix whose columns form an orthonormal basis of ker H1.

(iii) Suppose H1is positive (negative) definite. Then the functions ϕð·Þand ~

ϕð·Þ

are both strictly increasing (both strictly decreasing). Moreover, we have

mhðH0;H1Þ¼−∞;

mhðH0;H1Þ¼∞:

Proof. It suffices to show the statements about ϕand mhðH0;H1Þ. The statements

about ~

ϕand ~

mhðH0;H1Þthen follow immediately using the facts that λminðHÞ¼

−λmaxð−HÞand ~

mhðH0;H1Þ¼−mhð−H0;−H1Þfor all H;H0;H1∈HermðnÞ.

The well-known convexity of the function H↦λmaxðHÞ;H ∈HermðnÞ[3,

Example 3.10] implies the convexity of ϕ. Furthermore, by (6.2) the following inequal-

ities hold:

λminðH0ÞþλmaxðtH1Þ≤ϕðtÞ≤λmaxðH0ÞþλmaxðtH1Þ;ð6:9Þ

ϕðtÞþλminðtH1Þ≤ϕðtþtÞ≤ϕðtÞþλmaxðtH1Þ;t;t

∈R:ð6:10Þ

Note that

λmaxðtH1Þ¼λmaxðH1Þtif t≥0;

λminðH1Þtif t≤0:

ð6:11Þ

The monotonicity statements about ϕin (ii) and (iii) follow from (6.10). Next we show

the identity (6.7). For any unit vector v∈Cnsatisfying vH1v¼0and any t∈Rwe

have by the Courant–Fischer theorem that vH0v¼vðH0þtH1Þv≤ϕðtÞ:This

implies

mhðH0;H1Þ≤inf

t∈RϕðtÞ:ð6:12Þ

In order to show the opposite inequality we now distinguish four cases.

Case 1.H1is indefinite and λminðH0Þ<λmaxðH0Þ.Lett1,t2be defined as in (6.8).

Then t1<0<t2, and (6.11) yields that ϕð0Þ¼λminðH0ÞþλmaxðtjH1Þ,j¼1,2.By

combining this with the left inequality in (6.9) we obtain ϕð0Þ≤ϕðtjÞ. Consequently,

the continuous function ϕð·Þattains a local minimum at some t0in the open interval

ðt1;t

2Þ. By claim (a) of Proposition 6.1 there exists a unit vector v0satisfying

μ-VALUES AND SPECTRAL VALUE SETS 859

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

ðH0þt0H1Þv0¼ϕðt0Þv0and v

0H1v0¼0, whence v

0H0v0¼ϕðt0Þ. Thus, inft∈RϕðtÞ≤

ϕðt0Þ≤mhðH0;H1Þ. Thus, equality holds in (6.12).

Case 2.H1is indefinite and λminðH0Þ¼λmaxðH0Þ. In this case H0is a scalar multiple

of the identity matrix: H0¼cI with c∈R. Hence, ϕðtÞ¼cþλmaxðtH1Þ, and (6.11)

yields inft∈RϕðtÞ¼ϕð0Þ¼c. On the other hand we have vH0v¼cfor all unit vectors

v. Moreover, since H1is indefinite there exists a unit vector vsatisfying vH1v¼0.

Thus, mhðH0;H1Þ¼c.

Case 3.H1is semidefinite but not definite. Then vH1v¼0implies v∈

ker H1≠f0g. Let Vbe a matrix whose columns form an orthonormal basis of

ker H1. Then

mhðH0;H1Þ¼maxfvH0v;v∈ker H1;kvk¼1g¼λmaxðVH0VÞ:

On the other hand claim (b) of Proposition 6.1 yields

λmaxðVH0VÞ¼limt→∞ϕðtÞif H1is negative semidefinite;

limt→−∞ ϕðtÞif H1is positive semidefinite:

It follows that inft∈RϕðtÞ≤λmaxðVH0VÞ¼mhðH0;H1Þ:The latter inequality is actu-

ally an equality because of (6.12).

Case 4.H1is definite. Then mhðH0;H1Þ¼−∞ by definition. Moreover, (6.9)

yields that

−∞ ¼limt→−∞ ϕðtÞif H1is positive definite;

limt→∞ϕðtÞif H1is negative definite:

Thus, (6.7) holds in this case. ▯

Next, we prove Theorem 3.3. For H∈HermðnÞ;S∈SymðnÞ, we define

mhsðH;SÞ≔supfvHv;v∈Cn;v

⊤Sv ¼0;kvk¼1g;

mhsðH;SÞ≔inffvHv;v∈Cn;v

⊤Sv ¼0;kvk¼1g:

Then Theorem 2.1 states that for any M∈Cn×n,n≥2,

μSkewðMÞ¼ðmhsðMM;MsÞÞ1∕2;

μSkewðMÞ¼ð~

mhsðMM;MsÞÞ1∕2;

where Ms¼MþM⊤. Thus, Theorem 3.3 is obtained by substituting MMfor Hand

Msfor Sin the result below.

THEOREM 6.3. H∈HermðnÞ,S∈SymðnÞ. For t∈R, let

FðtÞ¼Ht

tS ¯

H∈Hermð2nÞ

and

ψðtÞ¼λ2ðFðtÞÞ;~

ψðtÞ¼λ2n−1ðFðtÞÞ:

Then the functions ψð·Þand −~

ψð·Þare both unimodal on ½0;∞Þ, and

860 MICHAEL KAROW

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

mhsðH;SÞ¼ inf

t∈½0;∞ÞψðtÞ;

mhsðH;SÞ¼ sup

t∈½0;∞Þ

ψðtÞ:

Furthermore, the following statements hold.

(i) If rankðSÞ≥2, then both the infimum and the supremum are attained in the

interval ½0;t

1, where t1¼2kHk∕σ2ðSÞ.

(ii) Suppose rankðSÞ¼1. Then the function ψ∶½0;∞Þ→Ris decreasing, the

function ~

ψ∶½0;∞Þ→Ris increasing, and

mhsðH;SÞ¼limt→∞ψðtÞ¼λmaxðVHVÞ;

mhsðH;SÞ¼limt→∞~

ψðtÞ¼λminðVHVÞ;

where Vis any matrix whose columns form an orthonormal basis of ker S.

(iii) If S¼0, then the functions ψð·Þand ~

ψð·Þare both constant, and

mhsðH;SÞ¼λmaxðHÞ¼ψð0Þ;

mhsðH;SÞ¼λminðHÞ¼ ~

ψð0Þ:

It is enough to show the statements about mhsðH;SÞand ψ. The statements about

mhsðH;SÞand ~

ψthen follow immediately using the facts that ~

mhsðH;SÞ¼

−mhsð−H;−SÞand λ2n−1ðFÞ¼−λ2ð−FÞfor all H∈HermðnÞ,S∈SymðnÞ,F∈

Hermð2nÞ. We split the proof into several lemmas, which give some additional informa-

tion. First note that Fð−tÞ¼TFðtÞT−1, where T¼½

−I

I. Thus, ψðtÞ¼ψð−tÞfor

all t∈R.

LEMMA 6.1. ForanyH∈HermðnÞ;S∈SymðnÞ,wehavemhsðH;SÞ≤inft∈½0;∞ÞψðtÞ.

Proof. For a unit vector v∈Cn, let

Uv≔z1v

z2v;z1;z

2∈C:ð6:15Þ

Note that Uvis a 2-dimensional subspace of C2n, and

z1v

z2v

FðtÞz1v

z2v¼ðjz1j2þjz2j2ÞvHvþ2tℜðz1z2v⊤SvÞ;z

1;z

2∈C:ð6:16Þ

Suppose now that v⊤Sv ¼0. Then by the Courant–Fischer max-min-principle

and (6.16)

ψðtÞ¼λ2ðFðtÞÞ ≥min

x∈Uv;kxk¼1xFðtÞx¼vHv for all t∈R:

Hence, ψðtÞ≥mhsðH;SÞ.▯

Next, we consider the case that ψattains its minimum at 0. To this end we need the

lemma below, which has already been used in the proof of Theorem 2.1.

LEMMA 6.2. Let Vbe a subspace of Cnof dimension dim V≥2. Then to any

S∈SymðnÞthere is a nonzero v∈Vsatisfying v⊤Sv ¼0.

Proof. For z1;z

2∈C, let vz1;z2¼z1v1þz2v2, where v1;v

2∈Vare linearly indepen-

dent vectors. The function ðz1;z

2Þ↦v⊤

z1;z2Svz1;z2is a homogeneous quadratic polynomial

and has a zero ðz1;z

2Þ≠ð0;0Þ.▯

μ-VALUES AND SPECTRAL VALUE SETS 861

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

LEMMA 6.3. The following statements are equivalent.

(i) mhsðH;SÞ¼ψð0Þ¼λmaxðHÞ.

(ii) Either dim E1ðHÞ≥2,ordim E1ðHÞ¼1and v⊤Sv ¼0for v∈E1ðHÞ.

(iii) The function R∋t↦ψðtÞattains its minimum at t¼0.

Proof. Let v1; :::;v

dbe a basis of the eigenspace EkðHÞ. Then

E2k−1ðFð0ÞÞ ¼ E2kðFð0ÞÞ ¼ M

j¼1

Uvj;

where the subspaces Uvjare defined as in (6.15) and Ldenotes the direct sum. Hence,

the eigenspaces of Fð0Þhave even dimension, and λmaxðHÞ¼ψð0Þ.

ðiÞ⇔ðiiÞ. Let K¼fv∈Cn;kvk¼1;v

⊤Sv ¼0g. Then Kis compact and

mhsðH;SÞ¼maxv∈KvHv. Obviously, mhsðH;SÞ≤maxfvHv;v∈Cn;kvk¼1g¼

λmaxðHÞ. For any unit vector v, we have vHv ¼λmaxðHÞiff v∈E1. Thus, if

K∩E1ðHÞ¼∅, then vHv <λmaxðHÞfor all v∈K, whence mhsðH;SÞ<λmaxðHÞ.

On the other hand if K∩E1ðHÞ≠∅, then v⊤Sv ¼0and vHv ¼λmaxðHÞfor some unit

vector v, whence mhsðH;SÞ¼λmaxðHÞ. By Lemma 6.2 we have K∩E1ðHÞ≠∅ if

dim E1ðHÞ≥2. The implication ðiÞ⇒ðiiiÞfollows from Lemma 6.1. ðiiiÞ⇒ðiÞ. Since

ðiÞis satisfied if dim E1ðHÞ≥2, we may assume that dim E1ðHÞ¼1. Then E2ðFð0ÞÞ ¼

E1ðFð0ÞÞ ¼ Uvfor a unit vector v∈E1ðHÞ, and λ2ðFð0ÞÞ >λ3ðFð0ÞÞ. Hence, ðiiiÞand

claim (a) of Proposition 6.1 yield that x½0

0x¼0for all x∈E2ðFð0ÞÞ. In other words

we have for all z1;z

2∈C,

0¼z1v

z2v0¯

S0z1v

z2v¼2ℜðz1z2v⊤SvÞ:

This implies v⊤Sv ¼0. Thus, mhsðH;SÞ¼vHv ¼ψð0Þ.▯

LEMMA 6.4. Suppose the function R∋t↦ψðtÞattains a local extremum at t0≠0.

Then there is a unit vector v∈Cnsatisfying vHv ¼ψðt0Þand v⊤Sv ¼0.

Proof. If the assumption of the lemma holds, then by Proposition 6.1 there is a

nonzero v0∈C2nsuch that

Fðt0Þv0¼ψðt0Þv0;ð6:17Þ

v

00¯

S0v0¼0:ð6:18Þ

Let

H0≔H−ψðt0ÞI; v0¼x

y;x;y∈Cn:

Then (6.17) is equivalent to the equations

H0x¼−t0¯

Sy; H0y¼−t0Sx;ð6:19Þ

which imply

862 MICHAEL KAROW

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

xH0x¼−t0x⊤Sy ¼yH0y;

xH0y¼−t0x⊤Sx ¼−t0y⊤Sy:ð6:20Þ

Since t0≠0it follows that

x⊤Sy ∈R;ð6:21Þ

y⊤Sy ¼x⊤Sx:ð6:22Þ

Relation (6.18) states that 2ℜðx⊤SyÞ¼0. Thus, (6.21) yields

x⊤Sy ¼0:ð6:23Þ

Now let

β≔1ifxTSx ¼0;

ixTSx

jxTSxjotherwise:

Then we have

ðxβyÞ⊤SðxβyÞ¼xTSx þβ2y⊤Sy 2βx⊤Sy

¼x⊤Sx þβ2x⊤Sx

|ﬄﬄﬄﬄ{zﬄﬄﬄﬄ}

¼−xTSx

2βx⊤Sy

|ﬄﬄ{zﬄﬄ}

¼0

ðusing ð6.22Þand ð6.23ÞÞ

¼0;

and

ðxβyÞH0ðxβyÞ¼xH0xþjβj2yH0y2ℜðxH0yβÞ

¼−t0ðð1þjβj2Þx⊤Sy

|ﬄﬄ{zﬄﬄ}

¼0

2ℜðx⊤SxβÞ

|ﬄﬄﬄﬄﬄﬄﬄ{zﬄﬄﬄﬄﬄﬄﬄ}

¼0

ðusing ð6.20Þand ð6.23ÞÞ

¼0:

At least one of the vectors xβyis nonzero and can therefore be divided by its norm.

The resulting vector v∈Cnhas the required properties. ▯

COROLLARY 6.4. Suppose the function R∋t↦ψðtÞattains a local extremum at

t0>0. Then ψðt0Þ¼mhsðH;SÞ¼inft∈½0;∞ÞψðtÞ.

Proof. We have mhsðH;SÞ≤inft∈½0;∞ÞψðtÞ≤ψðt0Þ≤mhsðH;SÞ. The first of these

inequalities is Lemma 6.1. The third is a consequence of Lemma 6.4. ▯

Corollary 6.4 in particular states that the function ψð·Þis unimodal on ½0;∞Þ.

Now we treat the three cases rankðSÞ≥2,rankðSÞ¼1,andS¼0separately.

Case 1. rankðSÞ≥2. Let t1¼2kHk∕σ2ðSÞ. The eigenvalues of ½0

t¯

0¼

½0

tS

0are the singular values of Sand their negatives. In particular

λ20t¯

tS 0¼σ2ðtSÞ¼jtjσ2ðSÞ:

μ-VALUES AND SPECTRAL VALUE SETS 863

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

We conclude that

ψðtÞ¼λ2Ht

tS ¯

H≥λ20t¯

tS 0þλminH0

0¯

H≥jtjσ2ðSÞ−kHk:

Thus, if jtj>t

1, then ψðtÞ>kHk≥λmaxðHÞ¼ψð0Þ. Consequently, ψattains its mini-

mum at some t0∈Rwith jt0j≤t1. Since ψðtÞ¼ψð−tÞthere exists a minimizer t0≥0.

If t0¼0, then ψðt0Þ¼mhsðH;SÞ¼inft∈½0;∞ÞψðtÞby Lemma 6.3. If t0>0, then the lat-

ter chain of equalities holds by Corollary 6.4.

Case 2. rankðSÞ¼1. In this case Scan be written in the form S¼xx⊤for some

nonzero x∈Cn. Let Vbe a matrix whose columns form an orthonormal basis of

ker S¼fv∈Cn;x⊤v¼0g. Since v⊤Sv ¼ðx⊤vÞ2we have v⊤Sv ¼0ff v∈ker S¼

rangeðVÞ. This yields

mhsðH;SÞ¼maxfvHv;v∈rangeðVÞ;kvk¼1g¼λmaxðVHVÞ:ð6:24Þ

The columns of ½0

0form an orthonormal basis of kerð½0

0Þ. The nonzero eigenvalues

of ½0

0are jxj2. Thus, λ2ð½0

0Þ ¼ 0since we assume n≥2. Therefore, by claim (b) of

Proposition 6.1

limt→∞ψðtÞ¼λmax0V

V0H0

0¯

H0V

0¯

V¼λmaxðVHVÞ:ð6:25Þ

By combining (6.24), (6.25), and Lemma 6.1 we find that mhsðH;SÞ¼inft∈½0;∞ÞψðtÞ¼

limt→∞ψðtÞ¼λmaxðVHVÞ. It remains to show that ψis decreasing. However, this is

immediate from the inequality ψð0Þ≥mhsðH;SÞ¼limt→∞ψðtÞand Corollary 6.4.

Case 3. S¼0. In this case the function ψis constant and the identities mhsðH;SÞ¼

λmaxðHÞ¼ψð0Þ¼inft∈½0;∞ÞψðtÞare obvious.

This concludes the proofs of Theorems 6.3 and 3.3. ▯

Acknowledgment. The author thanks the referees and Daniel Kressner for

valuable comments on an earlier version of this paper.

REFERENCES

[1] G. J. BALAS,J.C.DOYLE,K.GLOVER,A.PACKARD,AND R. SMITH,μ-Analysis and Synthesis Toolbox.

User’s Guide, The MathWorks Inc., South Natick, MA, 1991.

[2] B. BERNHARDSSON,A.RANTZER,AND L. QIU,Real perturbation values and real quadratic forms in a complex

vector space, Linear Algebra Appl., 270 (1998), pp. 131–154.

[3] S. BOYD AND L. VANDENBERGHE,Convex Optimization, Cambridge University Press, Cambridge, UK,

2004.

[4] M. J. CHEN,K.N.FAN,AND C. N. NETT,Structured singular values with nondiagonal structures–Part I:

Characterizations, Part II: Computation, IEEE Trans. Automat. Control, 41 (1996), pp. 1507–1516.

[5] J. C. DOYLE,Analysis of feedback systems with structured uncertainties, IEE Proc., Part D, 129 (1982),

pp. 242–250.

[6] E. GALLESTEY,Computing spectral value sets using the subharmonicity of the norm of rational matrices,

BIT, 38 (1998), pp. 22–33.

[7] D. HINRICHSEN AND A. J. PRITCHARD,Real and complex stability radii: A survey, in Control of Uncertain

Systems, D. Hinrichsen and B. Mårtensson, eds., Birkhäuser, Basel, 1990, pp. 119–162.

[8] D. HINRICHSEN AND A. J. PRITCHARD,Mathematical Systems Theory I. Modelling, State Space Analysis,

Stability and Robustness, Springer-Verlag, Berlin, 2005.

864 MICHAEL KAROW

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

[9] T. HU AND L. QIU,On structured perturbation of Hermitian matrices, Linear Algebra Appl., 275–276

(1998), pp. 287–314.

[10] M. KAROW,Geometry of Spectral Value Sets, Ph.D. thesis, University of Bremen, Bremen, Germany,

2003.

[11] M. KAROW,Structured pseudospectra for small perturbations, SIAM J. Matrix Anal. Appl., to appear.

[12] M. KAROW,D.HINRICHSEN,AND A. J. PRITCHARD,Interconnected systems with uncertain couplings: explicit

formulae for μ-values, spectral value sets and stability radii, SIAM J. Control Optim., 45 (2006),

pp. 856–884.

[13] M. KAROW,E.KOKIOPOULOU,AND D. KRESSNER,On the computation of structured singular values and

pseudospectra, Systems Control Lett., 59 (2010), pp. 122–129.

[14] M. KAROW AND D. KRESSNER,On the structured distance to uncontrollability, Systems Control Lett., 58

(2009), pp. 128–132.

[15] M. KAROW,D.KRESSNER,AND F. TISSEUR,Structured eigenvalue condition numbers, SIAM J. Matrix Anal.

Appl., 28 (2006), pp. 1052–1068.

[16] T. KATO,Perturbation Theory for Linear Operators, 2nd ed., Springer, Berlin, Heidelberg, New York,

1976.

[17] R. A. LIPPERT,Fixing two eigenvalues by a minimal perturbation, Linear Algebra Appl., 406 (2005),

pp. 177–200.

[18] N. MACKEY,D.S.MACKEY,AND F. TISSEUR,Structured mapping problems for matrices associated

with scalar products part I: Lie and Jordan algebras, SIAM J. Matrix Anal. Appl., 29 (2008),

pp. 1389–1410.

[19] A. N. MALYSHEV,A formula for the 2-norm distance from a matrix to the set of matrices with multiple

eigenvalues, Numer. Math., 83 (1999), pp. 443–454.

[20] A. PACKARD AND J. C. DOYLE,The complex structured singular value, Automatica J. IFAC, 29 (1993),

pp. 71–109.

[21] E. POLAK,Computational Methods in Optimization: A Unified Approach, Academic Press, New York,

1971.

[22] L. QIU,B.BERNHARDSSON,A.RANTZER,E.J.DAVISON,P.M.YOUNG,AND J. C. DOYLE,A formula for

computation of the real stability radius, Automatica J. IFAC, 31 (1995), pp. 879–890.

[23] M. G. SAFONOV AND K.-H. M. FAN,Special issue: Multivariable stability margin, Int. J. Robust Nonlinear

Control, 7 (1997), pp. 97–226.

[24] L. N. TREFETHEN AND M. EMBREE,Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and

Operators, Princeton University Press, Princeton, NJ, 2005.

[25] K. ZHOU,J.C.DOYLE,AND K. GLOVER,Robust and Optimal Control, Prentice Hall, Upper Saddle River,

NJ, 1996.

μ-VALUES AND SPECTRAL VALUE SETS 865

Downloaded 12/14/17 to 130.149.176.172. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php