Nearest pair with more nonconstant invariant factors. Pseudospectrum^{∗}

Juan-Miguel Gracia^{†}and Inmaculada de Hoyos^{‡} Departamento de Matemática Aplicada y Estadística e I.O.

Universidad del País Vasco, Facultad de Farmacia Apartado 450 E-01080 Vitoria-Gasteiz, Spain

March 17, 1999

Abstract

Let (A, B) ∈ ℂ^{n×n} × ℂ^{n×m}. Suppose that the number of nonconstant (i.e. ≠ 1) invariant factors of the polynomial matrix

λ[I_{n}, 0] − [A, B]

is less than k. For all complex number λ denote by

σ_{n−(k−1)}(λ[I_{n}, 0] − [A, B])

the greatest (n−(k−1))th singular value of the matrix λ[I_{n}, 0]−[A, B].

The minimum absolute value of the real function of complex variable

λ ↦ σ_{n−(k−1)}(λ[I_{n}, 0] − [A, B])

∗Partially supported by the DGICYT (MEC), Projects PB94–1365–CO3–01 and PB97– 0599–CO3–01 and developed during the stay of the first author at the Centro Internacional de Matemática (Coimbra, Portugal) in June 1998, which was supported by the Foundation Calouste Gulbenkian.

†mepgrmej@vc.ehu.es ‡mepdeizi@vc.ehu.es

gives the distance from (A, B) to the set of pairs with more or equal number of nonconstant invariant factors. When k = 1, this specializes in the formula of Eising for the distance from a controllable pair (A, B) to the nearest uncontrollable pair.

The complex numbers λ lying in the sublevel set {λ ∈ ℂ | σ_{n}(λ[I_{n}, 0]− [A, B]) ≤ ε} of the function

λ ↦ σ_{n}(λ[I_{n}, 0] − [A, B]),

are the uncontrollable modes of all the pairs that are within an ε tolerance of (A, B).

All the results of this paper are an immediate consequence of the Singular Value Decomposition of a matrix and of the interpretation of the singular values as the distances to the nearest matrices of lower ranks.

Key Words: invariant factors, nearest, singular values, controllable, observable, geometric multiplicity.

AMS Subject Classification: 15A18, 93B10, 93B35.

1 Introduction

Let (A, B) ∈ L_{nm} where L_{nm} := ℂ^{n×n} × ℂ^{n×m}. This pair of matrices is associated with the control linear system ẋ = Ax + Bu. We call invariant factors of the pair (A, B) the invariant factors of the polynomial matrix λ[I_{n}, 0] − [A, B] = [λI_{n} − A, −B]. It is well known that a pair (A, B) is controllable if and only if its invariant factors are 1, …, 1. Let us denote by i(A, B) the number of nonconstant invariant factors of (A, B). So, the pair (A, B) is controllable if and only if i(A, B) = 0.

We use here the spectral norm of matrices ∥ · ∥. For every matrix M ∈ ℂ^{m×n} we will denote by σ_{1}(M), …, σ_{q}(M) its singular values placed in nonincreasing order σ_{1}(M) ≥ … ≥ σ_{q}(M), where q = min{m, n}.

As it is known the set of controllable pairs is open and dense in L_{nm}. In 1984 Eising [3] proved that the distance from a controllable pair (A, B) ∈ L_{nm} to the set of uncontrollable pairs satisfies the equality:

min_{(A′,B′)∈Lnm uncontrollable} ∥[A′, B′] − [A, B]∥ = min_{λ∈ℂ} σ_{n}(λ[I_{n}, 0] − [A, B]) .

In 1991 Wicks and DeCarlo [12], proved that if the complex number λ_{0} minimizes σ_{n}(λ[I_{n}, 0] − [A, B]), then λ_{0} is an eigenvalue of an uncontrollable pair whose distance from [A, B] is the minimum on the left hand side of the above formula.

In [7] we considered the problem of finding the distance from a square complex matrix A that has less than k nonconstant (≠ 1) invariant factors to the set of matrices A′ that have more than or equal to k nonconstant invariant factors. When k = 2 , we obtained in particular the distance from a nonderogatory matrix to the set of derogatory matrices.

Trefethen [10, 11] and Godunov [5] exposed the concept of pseudospectrum or spectral portrait of a square matrix A: Where are the eigenvalues of all matrices A′ close to A? Here we generalize this to the case of pairs (A, B) ∈ ℂ^{n×n} × ℂ^{n×m} or pairs (C, A) ∈ ℂ^{p×n} × ℂ^{n×n}. We also answer the question: Where are the eigenvalues of geometric multiplicity ≥ k, k a positive integer, of all matrices A′ close to A?

The paper is organized as follows. In Section 2, given a pair (A, B) ∈ ℂ^{n×n} × ℂ^{n×m} with less than k nonconstant (≠ 1) invariant factors, a nearest pair with more than or equal to k nonconstant invariant factors is obtained; the same problem for pairs (C, A) ∈ ℂ^{p×n} × ℂ^{n×n} is solved. In Section 3 the real case of these problems when k > n/2 is considered; when k ≤ n/2 a counterexample is presented and a conjecture is formulated in order that the given answer in case k > n/2 remains true. Finally, in Section 4 the pseudospectrum of eigenvalues of geometric multiplicity greater than or equal to k of pairs (A, B) (or (C, A)), and of square matrices A, of radius ε ≥ 0 is analyzed in the light of the results of Section 2.

2 Nearest pair with more nonconstant invariant factors

A complex number α is an eigenvalue or an input decoupling zero (or an uncontrollable mode) of a pair (A, B) ∈ L_{nm} if rank (α[I_{n}, 0] − [A, B]) < n. So, α is an eigenvalue of (A, B) if and only if σ_{n}(α[I_{n}, 0]−[A, B]) = 0. Let us denote by σ(A, B) the spectrum or set of eigenvalues of (A, B). The geometric multiplicity of an eigenvalue α of the pair (A, B), denoted by gm (α, (A, B)), is the number of elementary divisors of the form (λ − α)^{ℓ} of the polynomial matrix λ[I_{n}, 0] − [A, B]. It can be easily proved that gm (α, (A, B)) = n − rank (α[I_{n}, 0] − [A, B]). For every complex number z we can define

gm (z, (A, B)) := n − rank (z[I_{n}, 0] − [A, B]);

so, z is an eigenvalue of (A, B) if and only if gm (z, (A, B)) ≥ 1. Let k be an integer, 1 ≤ k ≤ n, and let M_{k} be the set of matrix pairs (A, B) ∈ L_{nm} such that i(A, B) < k. This is equivalent to saying that M_{k} is the set of pairs (A, B) that have all its eigenvalues with geometric multiplicity < k. Thus, (A, B) ∈ M_{k} if and only if for all α ∈ σ(A, B) we have rank (α[I_{n}, 0] − [A, B]) > n − k. As the eigenvalues of a pair (A, B) depend continuously on (A, B), we deduce that the set M_{k} is open in L_{nm}; it is also dense in L_{nm} because it contains the controllable pairs. In consequence the set of pairs (A, B) such that i(A, B) ≥ k is closed. We want to obtain the distance from a pair (A, B) such that i(A, B) < k to the complementary set of M_{k}; that is to say, we want to obtain

min_{{(A′,B′)∈Lnm \atop i(A′,B′)≥k}} ∥[A′, B′] − [A, B]∥.

An answer to this question is given in the following theorem.

Theorem 2.1 Let k be an integer such that 1 ≤ k ≤ n. Let (A, B) ∈ L_{nm} be such that i(A, B) < k. Then

min_{{(A′,B′)∈Lnm \atop i(A′,B′)≥k}} ∥[A′, B′] − [A, B]∥ = min_{λ∈ℂ} σ_{n−(k−1)}(λ[I_{n}, 0] − [A, B]) .

Moreover, if λ_{0} is a complex number where the minimum of σ_{n−(k−1)}(λ[I_{n}, 0]− [A, B]) is attained, then a pair (A′, B′) which minimizes ∥[A′, B′] − [A, B]∥ where (A′, B′) has k or more nonconstant invariant factors, is given by

[A′, B′] := [A, B] + s_{n−(k−1)}u_{n−(k−1)}v_{n−(k−1)}^{∗} + ⋯ + s_{n−1}u_{n−1}v_{n−1}^{∗} + s_{n}u_{n}v_{n}^{∗},

where

s_{i}, u_{i}, v_{i} i = n − (k − 1), …, n − 1, n,

are the k last singular values and left singular vectors, and the (n − (k − 1))th, …,(n−1)th, nth right singular vectors that appear in a singular value decomposition of the matrix λ_{0}[I_{n}, 0] − [A, B]. And λ_{0} is also an eigenvalue of (A′, B′) of geometric multiplicity equal to k.

Proof. This proof is analogous to that of [7, Theorem 4.1].

Let λ ∈ ℂ and let us define

N_{k,λ} := {(X, Y) ∈ L_{nm} : rank(λ[I_{n}, 0] − [X, Y]) < n − k + 1} .

Then the complementary of M_{k} with respect to L_{nm} is:

M_{k}^{c} = ⋃_{λ∈ℂ}N_{k,λ} .

Therefore, if we define

C := {∥[A′, B′] − [A, B]∥ : (A′, B′) ∈ M_{k}^{c}}

and

C_{λ} := {∥[A′, B′] − [A, B]∥ : (A′, B′) ∈ N_{k,λ}}

then

C = ⋃_{λ∈ℂ}C_{λ} .

Since 0 is a lower bound of C and of C_{λ} for every λ ∈ ℂ, by [2, statement (2.3.6)] we have that

inf C = inf(⋃_{λ∈ℂ}C_{λ}) = inf_{λ∈ℂ}(inf C_{λ}) .  (1)

Moreover, for every λ ∈ ℂ

inf C_{λ} = min_{(A′,B′)∈N_{k,λ}} ∥[A′, B′] − [A, B]∥,  (2)

because N_{k,λ} is a closed set.

By [6, Theorem 2.5.2, p.73] , for every λ ∈ ℂ it holds

σ_{n−k+1}(λ[I_{n}, 0] − [A, B]) = min_{{(X,Y )∈Lnm \atop rank [X,Y ]<n−k+1}} ∥(λ[I_{n}, 0] − [A, B]) − [X, Y]∥ .

If [X, Y] is an n×(n+m) complex matrix such that rank [X, Y] < n−k+1, let us define [X′, Y′] := λ[I_{n}, 0] − [X, Y], that is to say, [X, Y] = λ[I_{n}, 0] − [X′, Y′] and, since rank (λ[I_{n}, 0] − [X′, Y′]) < n − k + 1, it follows that (X′, Y′) ∈ N_{k,λ} and conversely, if (X′, Y′) ∈ N_{k,λ} and [X, Y] := λ[I_{n}, 0] − [X′, Y′], then rank [X, Y] < n − k + 1.

Therefore

σ_{n−k+1}(λ[I_{n}, 0] − [A, B]) = min_{(X′,Y′)∈N_{k,λ}} ∥(λ[I_{n}, 0] − [A, B]) − (λ[I_{n}, 0] − [X′, Y′])∥
= min_{(X′,Y′)∈N_{k,λ}} ∥[X′, Y′] − [A, B]∥ ,

or equivalently

σ_{n−k+1}(λ[I_{n}, 0] − [A, B]) = min_{(A′,B′)∈N_{k,λ}} ∥[A′, B′] − [A, B]∥ .  (3)

By (1), (2) and (3) we deduce

min_{(A′,B′)∈M_{k}^{c}} ∥[A′, B′] − [A, B]∥ = inf_{λ∈ℂ}σ_{n−k+1}(λ[I_{n}, 0] − [A, B]) .  (4)

Let us define the function f(λ) := σ_{n−k+1}(λ[I_{n}, 0] − [A, B]) from ℂ to ℝ. It is well known (see [9, p. 143] and [8, Theorem 3.3.16, p. 178] ) that this is a continuous function. Then if we prove

lim_{|λ|→∞} f(λ) = ∞  (5)

we conclude that we can put min in place of inf in (4), that is to say, we obtain

min_{(A′,B′)∈M_{k}^{c}} ∥[A′, B′] − [A, B]∥ = min_{λ∈ℂ}σ_{n−k+1}(λ[I_{n}, 0] − [A, B])

which is the equality we wanted to prove. Now, let us prove (5) by proving that σ_{n}(λ[I_{n}, 0] − [A, B]) → ∞ when | λ |→ ∞ :

In our paper [7] we have proved that σ_{n}(λI − A) → ∞ when | λ |→ ∞. And by the interlacing inequalities for singular values of a matrix and a submatrix [8, Corollary 3.1.3, p. 149] we have that

σ_{n}(λ[I_{n}, 0] − [A, B]) ≥ σ_{n}(λI − A)

Therefore we obtain σ_{n}(λ[I_{n}, 0] − [A, B]) → ∞ when | λ |→ ∞.

In order to prove the second part of the theorem, let us consider λ_{0} a complex number where the minimum of σ_{n−(k−1)}(λ[I_{n}, 0]−[A, B]) is attained. By the singular value decomposition theorem there exist unitary matrices U = [u_{1}, …, u_{n}] ∈ ℂ^{n×n} and V = [v_{1}, …, v_{n+m}] ∈ ℂ^{(n+m)×(n+m)} such that

U^{∗}(λ_{0}[I_{n}, 0] − [A, B])V = [diag(s_{1}, …, s_{n−k}, s_{n−k+1}, …, s_{n}), 0] .

Let us define

[A′, B′] := [A, B] + s_{n−(k−1)}u_{n−(k−1)}v_{n−(k−1)}^{∗} + … + s_{n}u_{n}v_{n}^{∗}  (6)

where

s_{i}, u_{i}, v_{i}, i = n − (k − 1), …, n ,

are the k last singular values and left singular vectors, and the (n−(k−1))th, …,nth right singular vectors which appear in the singular value decomposition of the matrix λ_{0}[I_{n}, 0] − [A, B].

Since f(λ) := σ_{n−k+1}(λ[I_{n}, 0] − [A, B]) and min_{λ∈ℂ} f(λ) = f(λ_{0}) we deduce that

f(λ_{0}) = σ_{n−k+1}(λ_{0}[I_{n}, 0] − [A, B]) = s_{n−k+1} ,

so that we have to prove that ∥[A′, B′] − [A, B]∥ = s_{n−k+1}.

Now then, from (6)

∥[A′, B′] − [A, B]∥ = ∥s_{n−k+1}u_{n−k+1}v_{n−k+1}^{∗} + … + s_{n}u_{n}v_{n}^{∗}∥ .

Since the spectral norm is unitarily invariant we have

∥[A′, B′] − [A, B]∥ = ∥U^{∗}(s_{n−k+1}u_{n−k+1}v_{n−k+1}^{∗} + … + s_{n}u_{n}v_{n}^{∗})V ∥,

and an easy computation gives

∥[A′, B′]−[A, B]∥ = ∥[ \begin{matrix}0 & & & & & & & & & & 0 & ⋯ & 0 \\ & . & . & . \\ & & & & 0 \\ & & & & & s_{n−k+1} \\ & & & & & & . & . & . \\ & & & & & & & & & s_{n} & 0 & ⋯ & 0 \end{matrix} ]∥ = s_{n−k+1} ,

as we wanted to prove.

Finally we want to show that λ_{0} is an eigenvalue of (A′, B′) such that the geometric multiplicity of λ_{0} for (A′, B′) is equal to k:

From (6) we have

U^{∗}(λ_{0}[I_{n}, 0] − [A′, B′])V =

U^{∗}(λ_{0}[I_{n}, 0] − [A, B])V − s_{n−k+1}U^{∗}u_{n−k+1}v_{n−k+1}^{∗}V − ⋯ − s_{n}U^{∗}u_{n}v_{n}^{∗}V

and an easy computation yields

U^{∗}(λ_{0}[I_{n}, 0] − [A′, B′])V = [ \begin{matrix}s_{1} & & & & & & & & & & 0 & ⋯ & 0 \\ & . & . & . \\ & & & & s_{n−k} \\ & & & & & 0 \\ & & & & & & . & . & . \\ & & & & & & & & & 0 & 0 & ⋯ & 0 \end{matrix} ] . (7)

Since (A, B) ∈ M_{k} we have that for all λ ∈ ℂ rank (λ[I_{n}, 0] − [A, B]) > n − k. Thus, in particular rank (λ_{0}[I_{n}, 0] − [A, B]) ≥ n − k + 1 and s_{n−k+1} = σ_{n−k+1}(λ_{0}[I_{n}, 0] − [A, B]) > 0. Therefore s_{n−k} > 0 and by (7)

rank (λ_{0}[I_{n}, 0] − [A′, B′]) = n − k .

In consequence, λ_{0} ∈ σ(A′, B′) and the geometric multiplicity of λ_{0} for (A′, B′) is equal to k, as we wanted to prove.

□

Particular Cases:

1.- Case k = 1. In this case i(A, B) < 1, what is equivalent to i(A, B) = 0: (A, B) is a controllable pair. The first formula in Theorem 2.1 is the Eising’s formula for the distance from a controllable pair to the nearest uncontrollable pair.

2.- Case k = n. Now we have i(A, B) < n, and the first formula in Theorem 2.1 is:

min_{{(A′,B′)∈Lnm \atop i(A′,B′)≥n}} ∥[A′, B′] − [A, B]∥ = min_{λ∈ℂ} σ_{1}(λ[I_{n}, 0] − [A, B]) .

But i(A′, B′) ≥ n is equivalent to i(A′, B′) = n; so the invariant factors of (A′, B′) are

f_{1}(λ) | f_{2}(λ) | ⋯ | f_{n}(λ),

where the degree of f_{1}(λ), is equal to 1. Thus there exists an α ∈ ℂ such that f_{1}(λ) = λ − α. Therefore, f_{i}(λ) = λ − α for every i = 1, 2, …, n. Passing from (A′, B′) to its Brunovsky canonical form we see that (A′, B′) = (αI_{n}, 0). Thus,

min_{{(A′,B′)∈Lnm \atop i(A′,B′)≥n}} ∥[A′, B′] − [A, B]∥ = min_{α∈ℂ} ∥[αI_{n}, 0] − [A, B]∥

= min_{α∈ℂ} σ_{1}(α[I_{n}, 0] − [A, B]);

therefore the formula is obvious in this case.

These results are also true for pairs (C, A) ∈ L_{pn}, where L_{pn} := ℂ^{p×n} × ℂ^{n×n}. Let us write them briefly. These pairs of matrices are associated with the linear systems

\{ \begin{matrix}ẋ = Ax \\ y = Cx \end{matrix}

A complex number α is an eigenvalue or an output decoupling zero of a pair (C, A) ∈ L_{pn} if

rank (α (\begin{matrix}I_{n} \\ 0 \end{matrix}) − (\begin{matrix}A \\ C \end{matrix})) < n.

So, α is an eigenvalue of (C, A) if and only if

σ_{n} (α (\begin{matrix}I_{n} \\ 0 \end{matrix}) − (\begin{matrix}A \\ C \end{matrix})) = 0.

Let us denote by σ(C, A) the spectrum or set of eigenvalues of (C, A). The geometric multiplicity of an eigenvalue α of the pair (C, A), denoted by gm (α, (C, A)), is the number of elementary divisors of the form (λ − α)^{ℓ}

of the polynomial matrix λ (\begin{matrix}I_{n} \\ 0 \end{matrix}) − (\begin{matrix}A \\ C \end{matrix}). It can be easily proved that

gm (α, (C, A)) = n − rank (λ (\begin{matrix}I_{n} \\ 0 \end{matrix}) − (\begin{matrix}A \\ C \end{matrix})) .

We call invariant factors of the pair (C, A) the invariant factors of the polynomial matrix

λ (\begin{matrix}I_{n} \\ 0 \end{matrix}) − (\begin{matrix}A \\ C \end{matrix}) .

It is well known that a pair (C, A) is observable if and only if its invariant factors are 1, …, 1. Let us denote by i (C, A) the number of nonconstant invariant factors of (C, A). So, the pair (C, A) is observable if and only if i (C, A) = 0.

Theorem 2.2 Let k be an integer such that 1 ≤ k ≤ n. Let (C, A) ∈ L_{pn} be such that i(C, A) < k. Then

min_{{(C′,A′)∈Lpn \atop i(C′,A′)≥k}} ∥ (\begin{matrix}A′ \\ C′ \end{matrix}) − (\begin{matrix}A \\ C \end{matrix}) ∥ = min_{λ∈ℂ} σ_{n−(k−1)} (λ (\begin{matrix}I_{n} \\ 0 \end{matrix}) − (\begin{matrix}A \\ C \end{matrix})) .

Moreover, if λ_{0} is a complex number where the minimum of

σ_{n−(k−1)} (λ (\begin{matrix}I_{n} \\ 0 \end{matrix}) − (\begin{matrix}A \\ C \end{matrix}))

is attained, then a pair (C′, A′) which minimizes ∥ (\begin{matrix}A′ \\ C′ \end{matrix}) − (\begin{matrix}A \\ C \end{matrix}) ∥ where

(C′, A′) has k or more nonconstant invariant factors, is given by

(\begin{matrix}A′ \\ C′ \end{matrix}) := (\begin{matrix}A \\ C \end{matrix}) + s_{n−(k−1)}u_{n−(k−1)}v_{n−(k−1)}^{∗} + ⋯ + s_{n−1}u_{n−1}v_{n−1}^{∗} + s_{n}u_{n}v_{n}^{∗},

where

s_{i}, v_{i}, u_{i} i = n − (k − 1), …, n − 1, n,

are the k last singular values and right singular vectors, and the (n − (k − 1))th, …,(n − 1)th, nth left singular vectors that appear in a singular value decomposition of the matrix

λ_{0} (\begin{matrix}I_{n} \\ 0 \end{matrix}) − (\begin{matrix}A \\ C \end{matrix}) .

And λ_{0} is also an eigenvalue of (C′, A′) of geometric multiplicity equal to k.

When k = 1 this theorem gives the Eising’s formula for the distance from an observable pair to the nearest unobservable pair.

3 Real pairs

If we put everywhere ℝ instead of ℂ we can see that the following theorem is true when k > n/2:

Theorem 3.1 Let k be an integer such that k > n/2. Let (A, B) ∈ ℝ^{n×n} × ℝ^{n×m} such that i(A, B) < k. Then

min_{{(A′,B′)∈ℝ^{n×n}×ℝ^{n×m} \atop i(A′,B′)≥k}} ∥[A′, B′] − [A, B]∥ = min_{λ∈ℝ} σ_{n−(k−1)}(λ[I_{n}, 0] − [A, B]) .

Moreover, if λ_{0} is a real number where the minimum of σ_{n−(k−1)}(λ[I_{n}, 0] − [A, B]) over the real numbers is attained, then a real matrix pair (A′, B′) which minimizes ∥[A′, B′]−[A, B]∥ where (A′, B′) has k or more nonconstant invariant factors, is given by

[A′, B′] := [A, B] + s_{n−(k−1)}u_{n−(k−1)}v_{n−(k−1)}^{T} + ⋯ + s_{n−1}u_{n−1}v_{n−1}^{T} + s_{n}u_{n}v_{n}^{T} ,

where

s_{i}, u_{i}, v_{i} i = n − (k − 1), …, n − 1, n,

are the k last singular values and left singular vectors, and the (n − (k − 1))th, …,(n−1)th, nth right singular vectors that appear in a singular value decomposition of the matrix λ_{0}[I_{n}, 0] − [A, B]. And λ_{0} is also an eigenvalue of (A′, B′) of geometric multiplicity equal to k. Here ^{T} denotes transpose.

Proof. This proof is analogous to that of [7, Theorem 4.3].

Let λ ∈ ℝ and let us define

P_{k,λ} := {(A′, B′) ∈ ℝ^{n×n} × ℝ^{n×m} : rank(λ[I_{n}, 0] − [A′, B′]) ≤ n − k}

and

P_{k} := {(A′, B′) ∈ ℝ^{n×n} × ℝ^{n×m} : i(A′, B′) ≥ k} .

Let us prove that

P_{k} = ⋃_{λ∈ℝ}P_{k,λ} :

If (A′, B′) ∈ P_{k,λ} for some λ ∈ ℝ then (A′, B′) ∈ P_{k} by the previous definitions.

If (A′, B′) ∈ P_{k} there is a complex number λ_{0} such that the geometric multiplicity of λ_{0} for (A′, B′) is ≥ k. Let us suppose that λ_{0} ∈ ℂ\ℝ. Then, the geometric multiplicity of the conjugate number, \overline{λ_{0}}, for (A′, B′) is ≥ k. But this is impossible because k > n/2 and 2k > n, and n × (n + m) is the size of the matrix [A′, B′]. In consequence λ_{0} ∈ ℝ and (A′, B′) ∈ P_{k,λ_{0}}, as we wanted to prove.

Now we go on defining

C := {∥[A′, B′] − [A, B]∥ : (A′, B′) ∈ P_{k}}

and for each λ ∈ ℝ

C_{λ} := {∥[A′, B′] − [A, B]∥ : (A′, B′) ∈ P_{k,λ}} .

Then

C = ⋃_{λ∈ℝ}C_{λ}

and as we did in Theorem 2.1

min C = min(⋃_{λ∈ℝ}C_{λ}) = min_{λ∈ℝ}(min C_{λ}) = min_{λ∈ℝ}σ_{n−k+1}(λ[I_{n}, 0] − [A, B])

because [6, Theorem 2.5.2, p. 73] holds for 𝕂 = ℝ. For this same reason, the second part of the theorem follows like in Theorem 2.1.

□

A theorem, similar to Theorem 3.1, is true for real pairs (C, A).

The Theorem 3.1 is not true in general when k ≤ n/2. In particular, it is false for k = 1: Let (A, B) ∈ ℝ^{n×n} × ℝ^{n×m} a controllable pair, then

min_{(A′,B′)∈ℝ^{n×n}×ℝ^{n×m} uncontrollable} ∥[A′, B′] − [A, B]∥ = min_{λ∈ℝ} σ_{n}(λ[I_{n}, 0] − [A, B]) .

This formula is asserted by Boley and Lu without a proof in a paper of 1986 [1, Theorem 3, pag. 250]. But in general it is false, as it can be seen by means of the following counterexample: Let

A := ( \begin{matrix}0 & 2 \\ −2 & 0 \end{matrix} ) , B := ( \begin{matrix}1 \\ 0 \end{matrix} ) .

Then rank [B, AB] = rank ( \begin{matrix}1 & 0 \\ 0 & −2 \end{matrix} ) = 2. So, (A, B) is a controllable pair.

Take A′ := A and B′ := ( \begin{matrix}0 \\ 0 \end{matrix} ); then (A′, B′) is uncontrollable and

∥[A′, B′] − [A, B]∥ = ∥ ( \begin{matrix}0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix} ) ∥ = 1.

But

λ[I_{2}, 0] − [A, B] = [λI_{2} − A, −B] = ( \begin{matrix}λ & −2 & −1 \\ 2 & λ & 0 \end{matrix} );

what implies that

[λI_{2} − A, −B][λI_{2} − A, −B]^{T} = ( \begin{matrix}λ^{2} + 5 & 0 \\ 0 & λ^{2} + 4 \end{matrix} ) .

So, σ_{1}(λ[I_{2}, 0]−[A, B]) = \sqrt{λ^{2} + 5} and σ_{2}(λ[I_{2}, 0]−[A, B]) = \sqrt{λ^{2} + 4}. Therefore,

min_{λ∈ℝ} σ_{2}(λ[I_{2}, 0] − [A, B]) = min_{λ∈ℝ} \sqrt{λ^{2} + 4} = 2.

So, the above-mentioned equality is false.

This example also seems to contradict the second formula of (2.13) in [4], where — unless a possible erratum— it is asserted that

μ_{ℝ,1}(A, B) = min_{λ∈ℝ} σ_{min}(A − λI, B),

μ_{ℝ,1}(A, B) being the Frobenius norm of a minimal real rank-one perturbation (δA, δB) such that the real pair (A + δA, B + δB) is uncontrollable.

Perhaps, what Boley and Lu meant by the formula in their paper was the following theorem.

Theorem 3.2 Let (A, B) ∈ ℝ^{n×n} × ℝ^{n×m} be a controllable pair, then

min_{(A′,B′)∈ℝ^{n×n}×ℝ^{n×m} uncontrollable σ(A′,B′)∩ℝ≠∅} ∥[A′, B′] − [A, B]∥ = min_{λ∈ℝ} σ_{n}(λ[I_{n}, 0] − [A, B]) .

Proof. The proof is analogous to that of Theorem 2.1.

Let us define

P := {(A′, B′) ∈ ℝ^{n×n}×ℝ^{n×m} : (A′, B′) is uncontrollable and σ(A′, B′)∩ℝ ≠ ∅}.

Let λ ∈ ℝ and

P_{λ} := {(A′, B′) ∈ ℝ^{n×n} × ℝ^{n×m} : rank(λ[I_{n}, 0] − [A′, B′]) < n}.

Then

P = ⋃_{λ∈ℝ}P_{λ}

Therefore, if we define

C := {∥[A′, B′] − [A, B]∥ : (A′, B′) ∈ P}

and

C_{λ} := {∥[A′, B′] − [A, B]∥ : (A′, B′) ∈ P_{λ}}

then

C = ⋃_{λ∈ℝ}C_{λ} .

Following like in the proof of Theorem 2.1 we have that

min C = min(⋃_{λ∈ℝ}C_{λ})

= min_{λ∈ℝ}(min C_{λ}) = min_{λ∈ℝ}(σ_{n}(λ[I_{n}, 0] − [A, B])).

□

Remark. When k ≤ n/2 the first equality in Theorem 3.1 is true if

min_{λ∈ℝ} σ_{n−(k−1)}(λ[I_{n}, 0] − [A, B]) = min_{λ∈ℂ} σ_{n−(k−1)}(λ[I_{n}, 0] − [A, B]).

Because if λ_{0} ∈ ℝ is a point where the absolute minimum of the function, defined in ℝ,

λ ↦ σ_{n−(k−1)}(λ[I_{n}, 0] − [A, B])

is attained, then λ_{0} is a point where the absolute minimum of the function, defined in ℂ,

λ ↦ σ_{n−(k−1)}(λ[I_{n}, 0] − [A, B])

is also attained.

Thus the matrix λ_{0}[I_{n}, 0] − [A, B] is real. Therefore, by the second part of Theorem 2.1 the matrix [A′, B′] where the minimum

min_{{(A′,B′)∈ℂ^{n×n}×ℂ^{n×m} \atop i(A′,B′)≥k}} ∥[A′, B′] − [A, B]∥

is attained, is also real. In consequence,

min_{{(A′,B′)∈ℂ^{n×n}×ℂ^{n×m} \atop i(A′,B′)≥k}} ∥[A′, B′] − [A, B]∥ = min_{{(A′,B′)∈ℝ^{n×n}×ℝ^{n×m} \atop i(A′,B′)≥k}} ∥[A′, B′] − [A, B]∥.

Hence by the first equality in Theorem 2.1 we obtain the first equality in Theorem 3.1.

□

This is the case of the following example:

Let A := ( \begin{matrix}0 & 0 \\ 2 & 0 \end{matrix} ) and B := ( \begin{matrix}1 \\ 0 \end{matrix} ). The pair (A, B) is controllable.

The absolute minimum of the function

λ ↦ σ_{2}(λ[I_{2}, 0] − [A, B])

when λ ∈ ℝ is attained at the points λ = \frac{\sqrt{7}}{4} and λ = −\frac{\sqrt{7}}{4} and its value is \frac{\sqrt{15}}{4} ≈ 0.9682; and when λ runs over ℂ the absolute minimum is attained at every point of the circle | λ |= \frac{\sqrt{7}}{4}, and there is a relative maximum at λ = 0.

Notwithstanding, a possible sufficient condition is the following one: In the case of k ≤ n/2 we guess that the first equality in Theorem 3.1 is

valid when the function, defined on ℝ,

x ↦ σ_{n−(k−1)}(x[I_{n}, 0] − [A, B])

attains its absolute minimum in a single point x_{0} and the function, defined on ℝ^{2},

(x, y) ↦ σ_{n−(k−1)}((x + yi)[I_{n}, 0] − [A, B])

is convex in a neighbourhood of the point (x_{0}, 0). For this it is sufficient that the Hessian matrix of the function at this point is nonnegative definite —when the (n − (k − 1))th singular value of x_{0}[I_{n}, 0] − [A, B] is simple.

4 Pseudospectrum

Where are the eigenvalues of all pairs (A′, B′) that are sufficiently close to a pair (A, B)? More in general, where are the eigenvalues of geometric multiplicity greater than or equal to k of all pairs (A′, B′) sufficiently close to a pair (A, B)? This question contains the first one in the case k = 1.

The answer is given in the next theorem. Let (A′, B′) ∈ L_{nm} and k be an integer, 1 ≤ k ≤ n. We denote S_{k}(A′, B′) := {λ ∈ σ(A′, B′) | gm (λ, (A′, B′)) ≥ k}.

Theorem 4.1 Let (A, B) ∈ L_{nm} and k be an integer, 1 ≤ k ≤ n. For every real number ε ≥ 0, we have

\{λ ∈ ℂ | σ_{n−(k−1)}(λ[I_{n}, 0] − [A, B]) ≤ ε\} = ⋃_{{(A′,B′)∈Lnm \atop ∥[A′,B′]−[A,B]∥≤ε}} S_{k}(A′, B′).

Proof. If ε = 0 the theorem is obvious. So, we suppose that ε > 0. Let z ∈ ℂ such that σ_{n−(k−1)}(z[I_{n}, 0] − [A, B]) ≤ ε. Then there exists a matrix [F, G] ∈ ℂ^{n×(n+m)} with rank [F, G] < n − k + 1 such that

∥(z[I_{n}, 0] − [A, B]) − [F, G]∥ = min_{rank [F′,G′]<n−k+1} ∥(z[I_{n}, 0] − [A, B]) − [F′, G′]∥

= σ_{n−k+1}(z[I_{n}, 0] − [A, B]).

Let [A′, B′] := z[I_{n}, 0] − [F, G]. Then

rank (z[I_{n}, 0] − [A′, B′]) = rank [F, G] < n − k + 1;

so, k ≤ n − rank (z[I_{n}, 0] − [A′, B′]) and, therefore, z ∈ σ(A′, B′) and gm (z, (A′, B′)) ≥ k. Hence, z ∈ S_{k}(A′, B′).

Moreover,

∥[A′, B′] − [A, B]∥ = ∥z[I_{n}, 0] − [F, G] − [A, B]∥

= σ_{n−k+1}(z[I_{n}, 0] − [A, B]).

What implies

z ∈ ⋃_{∥[A′,B′]−[A,B]∥≤ε} S_{k}(A′, B′).

Reciprocally, if z ∈ S_{k}(A′, B′) for a pair (A′, B′) such that ∥[A′, B′] − [A, B]∥ ≤ ε, it follows that z ∈ σ(A′, B′) and gm (z, (A′, B′)) ≥ k; this implies that rank (z[I_{n}, 0] − [A′, B′]) < n − k + 1. Thus,

ε ≥ ∥[A′, B′] − [A, B]∥ = ∥z[I_{n}, 0] − [A, B] − (z[I_{n}, 0] − [A′, B′])∥ ≥

σ_{n−k+1}(z[I_{n}, 0] − [A, B]);

hence,

σ_{n−k+1}(z[I_{n}, 0] − [A, B]) ≤ ε.

In consequence,

⋃_{{(A′,B′)∈Lnm \atop ∥[A′,B′]−[A,B]∥≤ε}} S_{k}(A′, B′) ⊂ \{z ∈ ℂ : σ_{n−k+1}(z[I_{n}, 0] − [A, B]) ≤ ε\}.

□

If i(A, B) < k and ε is less than the absolute minimum of the function

λ ↦ σ_{n−(k−1)}(λ[I_{n}, 0] − [A, B]),

from Theorem 2.1 it is clear that the left and right hand sides of the formula in the last theorem are the empty set.

Corollary 4.2 Let (A, B) ∈ L_{nm}. For every real number ε ≥ 0, we have

\{λ ∈ ℂ | σ_{n}(λ[I_{n}, 0] − [A, B]) ≤ ε\} = ⋃_{{(A′,B′)∈Lnm \atop ∥[A′,B′]−[A,B]∥≤ε}} σ(A′, B′).

By analogy with the square matrix case, we will call pseudospectrum of (A, B) of radius ε the set {λ ∈ ℂ | σ_{n}(λ[I_{n}, 0] − [A, B]) ≤ ε}. It is a sublevel set of the function

λ ↦ σ_{n}(λ[I_{n}, 0] − [A, B]).

When (A, B) has eigenvalues, let us say λ_{1}, …, λ_{d}, then for small values of ε the pseudospectrum consists of the union of small regions around the points λ_{1}, …, λ_{d}. As ε increases these regions are more and more large until two of them coalesce for the first time. Finally all regions join in a unique large region. The knowledge of these regions has great importance in practice; for example to assess if a system ẋ = Ax + Bu is stabilizable when (A, B) is known within an ε tolerance.

In the case that (A, B) is controllable, it does not have eigenvalues and when ε is less than the absolute minimum of the function

λ ↦ σ_{n}(λ[I_{n}, 0] − [A, B]),

the pseudospectrum is empty; but this minimum value is equal to the distance from (A, B) to the nearest uncontrollable pair, so, if ∥[A′, B′] − [A, B]∥ ≤ ε then the pair (A′, B′) is also controllable and the union

⋃_{{(A′,B′)∈Lnm \atop ∥[A′,B′]−[A,B]∥≤ε}} σ(A′, B′)

is empty as well.

Analogously for a pair (C, A) ∈ L_{pn}, where L_{pn} := ℂ^{p×n} × ℂ^{n×n}, we have the following results.

Theorem 4.3 Let (C, A) ∈ L_{pn} and k be an integer, 1 ≤ k ≤ n. For every nonnegative real number ε, we have

\{λ ∈ ℂ | σ_{n−(k−1)} (λ (\begin{matrix}I_{n} \\ 0 \end{matrix}) − (\begin{matrix}A \\ C \end{matrix})) ≤ ε\} = ⋃_{{(C′,A′)∈Lpn \atop ∥(\begin{matrix}A′ \\ C′ \end{matrix})−(\begin{matrix}A \\ C \end{matrix})∥≤ε}} S_{k}(C′, A′),

where S_{k}(C′, A′) is the set of eigenvalues of the pair (C′, A′) ∈ L_{pn} that have geometric multiplicity greater than or equal to k.

Corollary 4.4 Let (C, A) ∈ L_{pn}. For every real number ε ≥ 0, we have

\{λ ∈ ℂ | σ_{n} (λ (\begin{matrix}I_{n} \\ 0 \end{matrix}) − (\begin{matrix}A \\ C \end{matrix})) ≤ ε\} = ⋃_{{(C′,A′)∈Lpn \atop ∥(\begin{matrix}A′ \\ C′ \end{matrix})−(\begin{matrix}A \\ C \end{matrix})∥≤ε}} σ(C′, A′),

where σ(C′, A′) is the set of eigenvalues of the pair (C′, A′) ∈ L_{pn}.

The knowledge of the sublevel region

\{λ ∈ ℂ | σ_{n} (λ (\begin{matrix}I_{n} \\ 0 \end{matrix}) − (\begin{matrix}A \\ C \end{matrix})) ≤ ε\} ,

is also important to assess if a system

\{ \begin{matrix}ẋ = Ax \\ y = Cx \end{matrix}

is detectable when (C, A) is known within an ε tolerance.

In the case that (C, A) is observable, it does not have eigenvalues, and when ε is less than the absolute minimum of the function

λ ↦ σ_{n} (λ (\begin{matrix}I_{n} \\ 0 \end{matrix}) − (\begin{matrix}A \\ C \end{matrix})) ,

the pseudospectrum of (C, A) of radius ε is empty; but this minimum value is equal to the distance from (C, A) to the nearest unobservable pair, so, if

∥ (\begin{matrix}A′ \\ C′ \end{matrix}) − (\begin{matrix}A \\ C \end{matrix}) ∥ ≤ ε

then the pair (C′, A′) is also observable and the union

⋃_{{(C′,A′)∈Lpn \atop ∥(\begin{matrix}A′ \\ C′ \end{matrix})−(\begin{matrix}A \\ C \end{matrix})∥≤ε}} σ(C′, A′)

is empty as well.

A theorem similar to Theorem 4.1 can be proved for square matrices:

Theorem 4.5 Let A ∈ ℂ^{n×n} and k an integer, 1 ≤ k ≤ n. For every real number ε ≥ 0, we have

\{λ ∈ ℂ | σ_{n−(k−1)}(λI_{n} − A) ≤ ε\} = ⋃_{{A′∈ℂ^{n×n} \atop ∥A′−A∥≤ε}} S_{k}(A′),

where S_{k}(A′) denotes the set of eigenvalues of geometric multiplicity ≥ k of A′.

For k = 1 this theorem produces the known result about the pseudospectra or spectral portraits of a square matrix [10] , [5] .

References

[1] D.L. Boley and W-S. Lu: Measuring how far a controllable system is from an uncontrollable one, IEEE Trans. Automat. Control, AC–31, No. 3 (1986) 249–251.

[2] J. Dieudonné: Foundations of Modern Analysis, Academic Press, New York, 1960.

[3] R. Eising: Between controllable and uncontrollable, Systems and Control Letters 4 (1984) 263–264.

[4] P. Gahinet and A.J. Laub: Algebraic Riccati equations and the distance to the nearest uncontrollable pair, SIAM J. Control Optim., 30, No. 4 (1992) 765–786.

[5] S.K. Godunov: Spectral portraits of matrices and criteria of spectrum dichotomy, in J. Herzberger and L. Atanassova, eds., Computer arithmetic and enclosure methods, North- Holland and IMACS, October 1992.

[6] G.H. Golub and C.F. Van Loan: Matrix Computations, Second Edition, The Johns Hopkins University Press, Baltimore, 1989.

[7] J.M. Gracia, I. de Hoyos and F.E. Velasco: Safety neighbourhoods for the invariants of the matrix similarity, Preprint 1996, to appear in Linear Multilinear Algebra.

[8] R. Horn and C. Johnson: Topics in Matrix Analysis, Cambridge University Press, New York, 1991.

[9] T. Kato: A Short Introduction to Perturbation Theory for Linear Operators, Springer-Verlag, New York, 1982.

[10] L.N. Trefethen: Pseudospectra of matrices, in Numerical Analysis 1991, D.F. Griffiths and G.A. Watson, eds., Longman Scientific and Technical, Harlow, UK, 1992, pp. 234– 266.

[11] L.N. Trefethen: Pseudospectra of Linear Operators, SIAM Rev.,39, No. 3 (1997) 383–406.

[12] M. Wicks and R.A. DeCarlo: Computing the distance to an uncontrollable system, IEEE Trans. Automat. Control 36 (1) (1991) 39–49.