Safety Neighbourhoods for the Invariants of the Matrix Similarity^{∗}

Juan M. Gracia^{†}, Inmaculada de Hoyos^{‡}and Franscisco E. Velasco Departamento de Matemática Aplicada y EIO Facultad de Farmacia, Universidad del País Vasco Apartado 450 E-01080 Vitoria-Gasteiz, Spain

December 12, 1996 Revised May 21, 1997 Revised October 27, 1997

Abstract

We give safety neighbourhoods for the necessary conditions in the change of the Jordan canonical form of a matrix under small perturbations. We also obtain the minimum distance from an n×n complex matrix which has less than k nonconstant invariant factors (2 ≤ k ≤ n) to the set of matrices which have more or equal to k. When k = 2, we get in particular the distance from a nonderogatory matrix to the set of derogatory matrices.

Key Words: quantitative perturbation, Jordan form, invariant factors, singular values, nearest derogatory matrix.

AMS Classification: 15A18, 15A21, 15A60.

∗This work was supported by the Basque Country University under grant UPV 100.123-EA040/95.

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

1 Introduction

Let P be a property which may be satisfied, or not, by a matrix A. For example, “A is nonderogatory” , “A is stable”. Let us suppose that the set of the matrices X which have the property P is an open set of the space of all the matrices. In this case it makes sense to consider the problem of calculating the minimum distance from the matrix A to the set of matrices which do not satisfy P. In the case that it is not possible to obtain this minimum distance, we are interested in finding positive numbers ε(A) such that ∥X −A∥ < ε(A) implies that X has the property P (safety neighbourhoods).

If the set of the matrices which satisfy the property P is open and dense in the space of all the matrices, the property is said to be generic [19]. So, for example, the property “A is nonderogatory” is generic. Recall that a square matrix A is said to be stable if all its eigenvalues have negative real part. So this property is nongeneric.

Safety neigbourhoods or bounds for the case when P is “the matrix A has simple eigenvalues” were studied by Wilkinson [22, 23]. Some problems of calculating the minimum distance to the set of matrices which do not satisfy the property P, already studied, are the following:

(i) Let us consider the control linear system

x^{.}(t) = Ax(t) + Bu(t) ,

where A ∈ ℂ^{n×n} and B ∈ ℂ^{n×m}. There exists a z_{0} ∈ ℂ such that

rank(z_{0}[I_{n}, 0] − [A, B]) < n

if and only if the pair (A, B) is noncontrollable.

If the pair (A, B) is controllable, the minimum singular value of λ[I_{n}, 0]− [A, B], σ_{n}(λ[I_{n}, 0] − [A, B]), is greater than zero for all λ ∈ ℂ. In this case, Eising [6] proved that

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

In [21] Wicks and DeCarlo, 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.

(ii) If a matrix has one pure imaginary complex eigenvalue, it is unstable; moreover, when A ∈ ℂ^{n×n} is a stable matrix the minimum singular value of iωI_{n} − A , σ_{n}(iωI_{n} − A), is positive. In [20] Van Loan proved that

min_{A′∈ℂ^{n×n} ; unstable} ∥A′ − A∥ = min_{ω∈ℝ} σ_{n}(iωI_{n} − A) .

The solutions of (i) and (ii) are based on the theorem of singular value decomposition (SVD).

Other problems, analogous to these, can be found in the paper [9] of Higham and its references. In [16] Marques de Sá obtained a quantitative refinement of the inverse perturbation problem for the Kronecker canonical form of a complex matrix pencil.

In Section 3 we state a theorem on qualitative perturbation of the Jordan form of a square matrix due to Markus and Parilis [15] and den Boer and Thijsse [3]. This theorem gives two necessary conditions which must be satisfied by all the matrices that are sufficiently close to a given one. The first condition says that the eigenvalues of a square matrix depend continuously on this matrix, as it is known. The second one shows the inequalities between the sizes of the Jordan blocks of the matrix A for an eigenvalue α and the sum of the sizes of the Jordan blocks of the matrix A′, sufficiently close to A, for the eigenvalues μ_{i} of A′ that are close to α. The aim of this section is to find a quantitative version of this theorem; that is to say, to find a positive number such that if the distance from A′ to A is less than this number then the necessary conditions hold.

In Section 4 we obtain the minimum distance from an n × n complex matrix which has less than k nonconstant invariant factors (2 ≤ k ≤ n) to the set of matrices which have more or equal to k. When k = 2, we get in particular the distance from a nonderogatory matrix to the set of derogatory matrices.

Previously in Section 2 we give the notations and preliminaries necessary to achieve the considered objectives. In all the paper we will employ the matrix spectral norm (or operator norm): ∥A∥ = σ_{1}(A), where σ_{1}(A) is the greatest singular value of A.

2 Notations and Preliminaries

1) Partitions.

A partition is a finite or infinite sequence of nonnegative integers a = (a_{1}, a_{2}, …), ordered in nonincreasing order and such that there is only a finite number of them different from zero, a_{1} ≥ a_{2} ≥ … ≥ a_{l(a)} > 0 = a_{l(a)+1} = …. We call length of a, l(a), the number of terms of a different from zero. The conjugate partition \overline{a}, of a, is the partition whose ith component is

\overline{a}_{i} = Card\{j : a_{j} ≥ i\}, i = 1, 2, ….

If a and b are partitions and m := max{l(a), l(b)} we say that a is majorized by b and we denote it by a ≺ b if

∑_{i=1}^{k} a_{i} ≤ ∑_{i=1}^{k} b_{i} , k = 1, 2, …, m − 1,

and

∑_{i=1}^{m} a_{i} = ∑_{i=1}^{m} b_{i} ;

we say that a is weakly majorized by b and we denote it by a ≺≺ b if

∑_{i=1}^{k} a_{i} ≤ ∑_{i=1}^{k} b_{i} , k = 1, 2, ….

It is well known that

a ≺ b ⇔ \overline{b} ≺ \overline{a} .

The sum of a and b is denoted by a+b and is the partition whose ith component is a_{i} + b_{i}. The union of a and b is denoted by a ∪ b and is the partition obtained by reordering all the components of a and b in nonincreasing order. It is also known that

\overline{a ∪ b} = \overline{a} + \overline{b} .

2) Segre and Weyr characteristics.

Let A ∈ ℂ^{n×n} and let α be one of its eigenvalues. Let n_{α1} ≥ n_{α2} ≥ ⋯ ≥ n_{αν_{α}} > 0 be the sizes of the Jordan blocks associated with α in the Jordan form of A. We define the partition Segre(α, A) := (n_{α1}, n_{α2}, …, n_{αν_{α}}, 0, …); the conjugate partition of Segre(α, A) is called Weyr(α, A).

Let Weyr (α, A) = (m_{α1}, m_{α2}, …, m_{αk}, …). For each k = 1, 2, …, let P_{α,k}(A) be the kn × kn matrix

P_{α,k}(A) := [ \begin{matrix}αI − A & 0 & 0 & ⋯ & 0 & 0 \\ I & αI − A & 0 & ⋯ & 0 & 0 \\ 0 & I & αI − A & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & αI − A & 0 \\ 0 & 0 & 0 & ⋯ & I & αI − A \end{matrix} ] .

By means of block row and column elementary transformations it is easy to prove that

ν(P_{α,k}(A)) = ∑_{i=1}^{k} m_{αi} .  (1)

where ν denotes nullity.

Since A can be identified with the regular pencil λI − A, this result can also be deduced from the analogous ones which appear in [10, 18].

3) A fundamental algebraic result for the objective.

Let us suppose that we change α in the diagonal blocks of P_{α,k}(A) by different complex numbers: α_{1} in the k_{1} first blocks, α_{2} in the k_{2} following blocks, …, α_{q} in the k_{q} last blocks, with k_{1} + k_{2} + ⋯ + k_{q} = k

P_{α_{1},...,α_{q}}^{k_{1},...,k_{q}}(A) := [ \begin{matrix}P_{α_{1},k_{1}}(A) & 0 & ⋯ & 0 & 0 \\ Q_{k_{2},k_{1}}(I) & P_{α_{2},k_{2}}(A) & ⋯ & 0 & 0 \\ ⋮ & ⋮ & & ⋮ & ⋮ \\ 0 & 0 & ⋯ & Q_{k_{q},k_{q−1}}(I) & P_{α_{q},k_{q}}(A) \end{matrix} ]

where for j = 1, …, q − 1

Q_{k_{j+1},k_{j}}(I) := [ \begin{matrix}0 & ⋯ & 0 & I \\ 0 & ⋯ & 0 & 0 \\ ⋮ & & ⋮ & ⋮ \\ 0 & ⋯ & 0 & 0 \end{matrix} ] ∈ ℂ^{(k_{j+1}n)×(k_{j}n)} .

By means of elementary transformations it can be proved that

ν(P_{α_{1},···,α_{q}}^{k_{1},···,k_{q}}(A)) = ν(diag(P_{α_{1},k_{1}}(A), …, P_{α_{q},k_{q}}(A))) .  (2)

3 Safety Neighbourhood for the Perturbation of the Jordan Form

The following theorem on qualitative perturbation of the Jordan form of a square matrix is known [15, 3]. If r is a real positive number and α is a complex number, by B(α, r) we denote the open ball in ℂ of center α y radius r: {z ∈ ℂ :| z − α |< r}.

Theorem 3.1 . Let A ∈ ℂ^{n×n} and Λ(A) = {λ_{1}, …, λ_{u}} be the set of distinct eigenvalues of A. Let δ > 0 be a number such that B(λ_{i}, δ) ∩ B(λ_{j}, δ) = ø if i ≠ j, i, j ∈ {1, …, u}.

Then there exists a neighbourhood V of A in ℂ^{n×n} such that A′ ∈ V implies that

(i)

Λ(A′) ⊂ ⋃_{i=1}^{u} B(λ_{i}, δ) ;

(ii) for all α ∈ Λ(A) if μ_{1}, …, μ_{t} are the eigenvalues of A′ which are in B(α, δ), then

⋃_{i=1}^{t} Weyr(μ_{i}, A′) ≺ Weyr(α, A)

or equivalently

Segre(α, A) ≺ ∑_{i=1}^{t} Segre(μ_{i}, A′).

OBJECTIVE: We intend to find a quantitative version of this theorem in the following sense: We want to find explicitly a positive number ε(A, δ),which depends on A and δ, such that if

∥A′ − A∥ < ε(A, δ),

then the consequences (i) and (ii) of the theorem are true.

In order to be able to define a radius ε(A, δ) we have to choose a positive real number δ such that the open balls of center the eigenvalues of A and radius δ are pairwise disjoint. The greatest δ we can take is

δ := min_{{i,j∈\{1,...,u\} \atop i≠j}} \frac{1}{2} | λ_{i} − λ_{j} | .

Let us fix any number Δ > 0 and define

C_{n}(A, Δ) := c 2^{1−1/n}(∥A∥ + Δ)^{1−1/n} ,  (3)

where c := 16/(3\sqrt{3}) ≃ 3.08. Let α be an eigenvalue of A and for k = 1, 2, …, n, let

σ_{min}(P_{α,k}(A))

the minimum positive singular value of the matrix P_{α,k}(A).

We define

s(A, α) := min_{1≤k≤n} σ_{min}(P_{α,k}(A)) ,  (4)

if A is not a scalar matrix, and

s(A, α) := min_{2≤k≤n} σ_{min}(P_{α,k}(A)) ,  (5)

if A is a scalar matrix.

Finally, let us denote

δ_{1} := min \{\frac{s(A, α)}{2n}, δ\} .  (6)

Now we can state the following theorem.

Theorem 3.2 .With the previous notations let

ε(A, α, δ) := min \{Δ, \frac{s(A, α)}{2n}, (\frac{δ_{1}}{C_{n}(A, Δ)})^{n}\} .  (7)

Then if ∥A′ − A∥ < ε(A, α, δ):

(i)

Λ(A′) ⊂ ⋃_{i=1}^{u} B(λ_{i}, δ) ;  (8)

(ii) if μ_{1}, …, μ_{t} are the eigenvalues of A′ which are in B(α, δ) we have that

⋃_{i=1}^{t} Weyr(μ_{i}, A′) ≺≺ Weyr(α, A) .  (9)

Proof. Let A′ ∈ ℂ^{n×n} be such that ∥A′ − A∥ < ε(A, α, δ). By ([12]; see also [1] p. 9, p. 97 (20.8) and pp. 120 and 121) we have that

d(Eig A, Eig A′) ≤ c 2^{1−1/n}M^{1−1/n}∥A − A′∥^{1/n}  (10)

where: d(Eig A, Eig A′) is the optimal matching distance between the unordered n-tuples of the eigenvalues of A and A′ , respectively; and M := max(∥A∥, ∥A′∥). A proof of this inequality when c = 4 can be seen in ([2] p. 229, Theorem VIII.1.5).

Taking into account the inequality M < ∥A∥+Δ, (10) and (3) we obtain

d(Eig A, Eig A′) < C_{n}(A, Δ)∥A − A′∥^{1/n} .  (11)

From the definition in (7) we have that

∥A − A′∥^{1/n} < \frac{δ_{1}}{C_{n}(A, Δ)} ,

and therefore

d(Eig A, Eig A′) < δ_{1} .  (12)

From (6) we obtain

d(Eig A, Eig A′) < δ ,

and taking into account the definition of optimal matching distance ([1], p.9) we deduce the relation (8).

Now, let μ_{1}, …, μ_{t} be the eigenvalues of A′ which are in B(α, δ). Let us denote m′_{μ_{i}} = (m′_{μ_{i}1}, m′_{μ_{i}2}, …) = Weyr(μ_{i}, A′) and m_{α} = (m_{α1}, m_{α2}, …) = Weyr(α, A).

Let d := ⋃_{i=1}^{t} Weyr(μ_{i}, A′) = (d_{1}, d_{2}, …, d_{k}, …).

For each k ∈ {1, …, n}, d_{1}, d_{2}, …, d_{k} are the k greatest numbers in the union

⋃_{i=1}^{t} m′_{μ_{i}} ;

these k numbers come from some partitions m′_{μ_{i}}, let us say, from q partitions m′_{μ_{i}}: let us denote them by

m′_{μ_{i_{1}}}, …, m′_{μ_{iq}} .

Let us suppose that k_{1} of the numbers d_{1}, d_{2}, …, d_{k} are the k_{1} greatest terms of m′_{μ_{i_{1}}}, that k_{2} of the numbers d_{1}, d_{2}, …, d_{k} are the k_{2} greatest terms of m′_{μ_{i_{2}}}, …, and that k_{q} of the numbers d_{1}, d_{2}, …, d_{k} are the k_{q} greatest terms of m′_{μ_{iq}}. So,

k_{1} + k_{2} + ⋯ + k_{q} = k and

∑_{i=1}^{k} d_{i} = ∑_{j=1}^{k_{1}} m′_{μ_{i_{1}}j} + ∑_{j=1}^{k_{2}} m′_{μ_{i_{2}}j} + ⋯ + ∑_{j=1}^{k_{q}} m′_{μ_{iq} j} .  (13)

Taking into account the definitions of P_{α,k}(A) and P_{μ_{i_{1}},...,μ_{iq}}^{k_{1},...,k_{q}} (A′) it is easy to see that

∥P_{α,k}(A) − P_{μ_{i_{1}},...,μ_{iq}}^{k_{1},...,k_{q}} (A′)∥ ≤ ∑_{s=1}^{q}(| α − μ_{i_{s}} | +∥A − A′∥) .  (14)

Since (8) holds we can deduce that

| α − μ_{i_{s}} |≤ d(Eig A, Eig A′) .  (15)

Therefore, from (7),(12),(14) and (15) we obtain

∥P_{α,k}(A) − P_{μ_{i_{1}},...,μ_{iq}}^{k_{1},...,k_{q}} (A′)∥ < s(A, α) .

Then, given that the minimum positive singular value of a matrix B is equal to the distance from this matrix to the set of matrices with rank less than rank(B) ([8], p. 73, Theorem 2.5.2) and the definitions in (4) and (5), it follows that

ν(P_{μ_{i_{1}},...,μ_{iq}}^{k_{1},...,k_{q}} (A′)) ≤ ν(P_{α,k}(A)) .  (16)

Moreover, by (2),(16) is equivalent to

∑_{s=1}^{q} ν(P_{μ_{is},k_{s}}(A′)) ≤ ν(P_{α,k}(A)) .  (17)

By means of the equality in (1) we deduce from (17)

∑_{s=1}^{q} ∑_{j=1}^{k_{s}} m′_{μ_{is}j} ≤ ∑_{i=1}^{k} m_{αi} .  (18)

By (13), from (18) it follows that

∑_{i=1}^{k} d_{i} ≤ ∑_{i=1}^{k} m_{αi} .  (19)

Since inequality (19) holds for k = 1, 2, …, we conclude that the relation (9) is true, as we wanted to prove. □

The inequality (9) can be improved by reducing the neighbourhood of A:

Theorem 3.3 . With the previous notations let

ε(A, δ) := min_{α∈Λ(A)} ε(A, α, δ) .

Then if ∥A′ − A∥ < ε(A, δ):

Λ(A′) ⊂ ⋃_{i=1}^{u} B(λ_{i}, δ) ;  (20)

(ii) for all α ∈ Λ(A), if μ_{1}, …, μ_{t} are the eigenvalues of A′ which are in B(α, δ),we have that

⋃_{i=1}^{t} Weyr(μ_{i}, A′) ≺ Weyr(α, A) .  (21)

Another way to obtain a safety neighbourhood is the following one:

Let A, B, C be n × n, n × m and p × n complex matrices, respectively, and let Ω ⊂ ℂ be an open set for which Λ(A) ⊂ Ω. The structured stability radius of A (with respect to the set Ω and the matrices B and C) is defined by

r(A; B, C, Ω) := inf{∥D∥ : D ∈ ℂ^{m×p} , Λ(A + BDC) ∩ Ω^{c} ≠ ø} ,

where Ω^{c} denotes the complementary set of Ω.

The structured stability radius can be expressed in terms of the norm of a rational matrix function.

Theorem 3.4 . ([13] p. 449). Let

G(z) = C(zI − A)^{−1}B

be the p × m rational matrix function associated with the triple (A, B, C). Then

r(A; B, C, Ω) = (max_{z∈∂Ω} ∥G(z)∥)^{−1} ,

where ∂Ω denotes the boundary of the open set Ω and 0^{−1} := ∞.

Given that the positive singular values of the Moore-Penrose inverse M^{†} are the reciprocals of the positive singular values of the matrix M (Proposition 4, p. 435 of [14]), we deduce

r(A; B, C, Ω) = min_{z∈(∂Ω)^{∗}} σ_{min}(G(z)^{†})

where (∂Ω)^{∗} := {z ∈ ∂Ω : G(z) ≠ 0} and σ_{min}(G(z)^{†}) is the minimum positive singular value of G(z)^{†}.

In the particular case when B = C = I_{n} we obtain that

ρ := r(A; I_{n}, I_{n}, Ω) = min_{z∈∂Ω} σ_{n}(zI − A) ,

because for all z ∈ ∂Ω it holds that rank(zI − A) = n.

Let us now suppose that Λ(A) = {λ_{1}, …, λ_{u}} and let us define

δ := min_{{i,j∈\{1,...,u\} \atop i≠j}} \frac{1}{2} | λ_{i} − λ_{j} | .

and Ω := ⋃_{i=1}^{u} B(λ_{i}, δ).

Then we have that

ρ = min_{z∈∂Ω} σ_{n}(zI − A) = min_{1≤k≤u} min_{θ∈[0,2π]} σ_{n}((λ_{k} + δe^{iθ})I − A) .

Finally we conclude that if ∥A′ − A∥ < ρ then Λ(A′) ⊂ Ω. In this way the radius of a safety neighbourhood would be

ε′(A, δ) := min_{α∈Λ(A)} ε′(A, α, δ)

where by definition

ε′(A, α, δ) := min \{ρ, \frac{s(A, α)}{2n}, (\frac{s(A, α)/2n}{C_{n}(A, Δ)})^{n}\} .

Note. There is a bisection method of Byers [4] to find the distance from a matrix with all its eigenvalues in the unit circle to the set of matrices with some eigenvalue of absolute value equal to 1. This method can be adapted to find our minima for k = 1, …, u,

min_{θ∈[0,2π]} σ_{n}((λ_{k} + δe^{iθ})I − A).

4 Nearest Matrix with More Nonconstant Invariant Factors

By definition the invariant factors of an n-square complex matrix A are those of the polynomial matrix λI − A. A nonconstant invariant factor of A is an invariant factor of A that is a nonconstant polynomial. We will denote by i(A) the number of nonconstant invariant factors of A. It can be observed that i(A) is the greatest geometric multiplicity of the eigenvalues of A. Let k be an integer, 2 ≤ k ≤ n; we define

M_{k} := {A ∈ ℂ^{n×n} : i(A) < k}.

That is to say, M_{k} is the set of the matrices A with all its eigenvalues with geometric multiplicity < k. Thus, in particular, M_{2} is the set of the n × n nonderogatory matrices.

Since the geometric multiplicity of an eigenvalue λ of A is equal to the dimension of the kernel of the matrix λI − A, we deduce that

A ∈ M_{k} ⇔ for all λ ∈ Λ(A) rank (λI − A) > n − k .

Therefore, M_{k} is an open set. Moreover, taking into account that the matrices A ∈ ℂ^{n×n} with n different eigenvalues belong to M_{k} for any k ≥ 2 and they all form a dense set in ℂ^{n×n}, we conclude that M_{k} is a dense set. So that, the property which characterizes the elements of M_{k} is a generic property.

We want to calculate the distance from an element of M_{k} to the closed set complementary of M_{k}, that is to say, we want to obtain

min_{{A′∈ℂ^{n×n} \atop i(A′)≥k}} ∥A′ − A∥ .

This is a problem of constrained minimization for several variables. This problem can be transformed into one of global minimization for one variable by means of the following theorem. Before, let us denote by σ_{1}(M) ≥ σ_{2}(M) ≥ ⋯ ≥ σ_{p}(M) ≥ 0 the singular values of an m × n complex matrix M, where p := min{m, n}. Moreover, the matrix M^{∗} denotes the conjugate transpose of M.

Theorem 4.1 . Let k be an integer such that 2 ≤ k ≤ n. Let A ∈ ℂ^{n×n} be such that i(A) < k. Then

min_{{A′∈ℂ^{n×n} \atop i(A′)≥k}} ∥A′ − A∥ = min_{λ∈ℂ} σ_{n−(k−1)}(λI − A) .

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

A′ := A + 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 singular vectors which appear in a singular value decomposition of the matrix λ_{0}I − A. And λ_{0} is also an eigenvalue of A′ such that the geometric multiplicity of λ_{0} for A′ is equal to k.

Proof. Let λ ∈ ℂ and let us define

N_{k,λ} := {X ∈ ℂ^{n×n} : rank(λI − X) < n − k + 1} .

Then the complementary of M_{k} with respect to ℂ^{n×n} is:

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

Therefore, if we define

C := {∥A′ − A∥ : A′ ∈ M_{k}^{c}}

and

C_{λ} := {∥A′ − A∥ : A′ ∈ N_{k,λ}}

then

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

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

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

Moreover, for every λ ∈ ℂ

inf C_{λ} = min_{A′∈N_{k,λ}} ∥A′ − A∥,  (23)

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

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

σ_{n−k+1}(λI − A) = min_{{X∈ℂ^{n×n} \atop rank X<n−k+1}} ∥(λI − A) − X∥ .

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

Therefore

σ_{n−k+1}(λI − A) = min_{X′∈N_{k,λ}} ∥(λI − A) − (λI − X′)∥ = min_{X′∈N_{k,λ}} ∥X′ − A∥ ,

or equivalently

σ_{n−k+1}(λI − A) = min_{A′∈N_{k,λ}} ∥A′ − A∥ .  (24)

By (22), (23) and (24) we deduce

min_{A′∈M_{k}^{c}} ∥A′ − A∥ = inf_{λ∈ℂ} σ_{n−k+1}(λI − A) .  (25)

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

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

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

min_{A′∈M_{k}^{c}} ∥A′ − A∥ = min_{λ∈ℂ} σ_{n−k+1}(λI − A)

which is the equality we wanted to prove. Now, let us prove (26) by proving that σ_{n}(λI − A) → ∞ when | λ |→ ∞ :

Let A = (a_{ij}) ∈ ℂ^{n×n} and λ ∈ ℂ.

Let x ∈ ℂ^{n} be such that ∥x∥ = 1. Then, there exists an i ∈ {1, …, n} such that | x_{i} |≥ 1/n. In consequence,

∥(λI − A)x∥ ≥| − ∑_{{j=1 \atop j≠i}}^{n} a_{ij}x_{j} + (λ − a_{ii})x_{i} |≥| (λ − a_{ii})x_{i} | − | ∑_{{j=1 \atop j≠i}}^{n} a_{ij}x_{j} |

and thus,

∥(λI − A)x∥ ≥| (λ − a_{ii})x_{i} | − ∑_{{j=1 \atop j≠i}}^{n} | a_{ij} | | x_{j} |≥ \frac{1}{n} | λ − a_{ii} | − ∑_{{j=1 \atop j≠i}}^{n} | a_{ij} | .

Therefore, for all x such that ∥x∥ = 1

∥(λI − A)x∥ ≥ min_{i∈\{1,...,n\}} \{\frac{1}{n} | λ − a_{ii} | − ∑_{{j=1 \atop j≠i}}^{n} | a_{ij} |\} .

Since

σ_{n}(λI − A) = min_{∥x∥=1} ∥(λI − A)x∥

we deduce

σ_{n}(λI − A) ≥ min_{i∈\{1,...,n\}} \{\frac{1}{n} | λ − a_{ii} | − ∑_{{j=1 \atop j≠i}}^{n} | a_{ij} |\}

and the right term → ∞ as | λ |→ ∞ as we wanted to prove.

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 − A) is attained. By the singular value decomposition theorem there exist n × n unitary matrices U = [u_{1}, …, u_{n}] and V = [v_{1}, …, v_{n}] such that

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

Let us define

A′ := A + s_{n−(k−1)}u_{n−(k−1)}v_{n−(k−1)}^{∗} + … + s_{n}u_{n}v_{n}^{∗}  (27)

where

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

are the k last singular values and singular vectors which appear in the singular value decomposition of the matrix λ_{0}I − A.

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

f(λ_{0}) = σ_{n−k+1}(λ_{0}I − A) = s_{n−k+1} ,

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

Now then, from (27)

∥A′ − A∥ = ∥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′ − A∥ = ∥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′ − A∥ = ∥[ \begin{matrix}0 \\ & . & . & . \\ & & & & 0 \\ & & & & & s_{n−k+1} \\ & & & & & & . & . & . \\ & & & & & & & & & s_{n} \end{matrix} ]∥ = s_{n−k+1} ,

as we wanted to prove.

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

From (27) we have

U^{∗}(λ_{0}I −A′)V = U^{∗}(λ_{0}I −A)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 − A′)V = [ \begin{matrix}s_{1} \\ & . & . & . \\ & & & & s_{n−k} \\ & & & & & 0 \\ & & & & & & . & . & . \\ & & & & & & & & & 0 \end{matrix} ] .  (28)

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

rank (λ_{0}I − A′) = n − k .

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

As we have mentioned above, when k = 2 we have as a particular case that of the nonderogatory matrices.

Corollary 4.2 . Let A ∈ ℂ^{n×n} be a nonderogatory matrix. Then

min_{A′∈ℂ^{n×n} ; derogatory} ∥A′ − A∥ = min_{λ∈ℂ} σ_{n−1}(λI − A).

Moreover, if λ_{0} is a complex number where the minimum of σ_{n−1}(λI − A) is attained, then a matrix A′ which minimizes ∥A′ − A∥ where A′ is derogatory, is given by

A′ := A + s_{n−1}u_{n−1}v_{n−1}^{∗} + s_{n}u_{n}v_{n}^{∗} ,

where

s_{i}, u_{i}, v_{i}, i = n − 1, n ,

are the two last singular values and singular vectors of the matrix λ_{0}I − A. And λ_{0} is also an eigenvalue of A′ such that the geometric multiplicity of λ_{0} for A′ is equal to 2.

Remark 1. Let us show that in the case when k = n the Theorem 4.1 follows immediately:

On the one hand, the fact that i(A) < n is equivalent to rank (λI−A) > 0 for all λ ∈ Λ(A), that is to say, A is not a scalar matrix.

Therefore, i(A′) ≥ n means that A′ is a scalar matrix. As a consequence, we have that

min_{{A′∈ℂ^{n×n} \atop A′ scalar}} ∥A′ − A∥ = min_{α∈ℂ} ∥αI − A∥ .

On the other hand, if k = n, σ_{n−(k−1)}(λI −A) = σ_{1}(λI −A) = ∥λI −A∥ . Therefore,

min_{λ∈ℂ} σ_{n−(k−1)}(λI − A) = min_{λ∈ℂ} σ_{1}(λI − A) = min_{λ∈ℂ} ∥λI − A∥ .

Then, the equality is evidently true when k = n.

Finally we are going to see that it is possible to put ℝ instead of ℂ in Theorem 4.1, when k > n/2.

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

min_{{A′∈ℝ^{n×n} \atop i(A′)≥k}} ∥A′ − A∥ = min_{λ∈ℝ} σ_{n−k+1}(λI − A) .  (29)

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

A′ := A + 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 singular vectors which appear in the singular value decomposition of the matrix λ_{0}I − A. And λ_{0} is also an eigenvalue of A′ such that the geometric multiplicity of λ_{0} for A′ is equal to k. Here ^{T} denotes transpose.

Proof. Let λ ∈ ℝ and let us define

P_{k,λ} := {A′ ∈ ℝ^{n×n} : rank(λI − A′) ≤ n − k}

and

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

Let us prove that

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

If A′ ∈ P_{k,λ} for some λ ∈ ℝ then A′ ∈ P_{k} by the previous definitions. If A′ ∈ P_{k} there is a complex number λ_{0} such that the geometric mul-

tiplicity of λ_{0} for A′ is ≥ k. Let us suppose that λ_{0} ∈ ℂ \ ℝ. Then, the geometric multiplicity of the conjugate number, \overline{λ_{0}}, for A′ is ≥ k. But this is impossible because k > n/2 and 2k > n, and n is the size of the matrix A′. In consequence λ_{0} ∈ ℝ and A′ ∈ P_{k,λ_{0}}, as we wanted to prove.

Now we go on defining

C := {∥A′ − A∥ : A′ ∈ P_{k}}

and for each λ ∈ ℝ

C_{λ} := {∥A′ − A∥ : A′ ∈ P_{k,λ}} .

Then

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

and as we did in Theorem 4.1

min C = min( ⋃_{λ∈ℝ} C_{λ}) = min_{λ∈ℝ}(min C_{λ}) = min_{λ∈ℝ} σ_{n−k+1}(λI − A)

because ([8], p. 73, Theorem 2.5.2) holds for 𝕂 = ℝ. For this same reason, the second part of the theorem follows like in Theorem 4.1 .□

Remark 2. Let us show that if k ≤ n/2, Theorem 4.3 is false:

Let us consider the matrix

A = [ \begin{matrix}3 & 5 \\ −5 & 3 \\ & & 3.1 & 5.2 \\ & & −5.2 & 3.1 \\ & & & & 7 \end{matrix} ] ∈ ℝ^{5×5} .

One eigenvalue of A is λ_{0} = 3 + 5i and another is \overline{λ_{0}} = 3 − 5i, both with geometric multiplicity 1. In fact, i(A) = 1.

If we take

A′ = [ \begin{matrix}3 & 5 \\ −5 & 3 \\ & & 3 & 5 \\ & & −5 & 3 \\ & & & & 7 \end{matrix} ]

we have that i(A′) = 2 because the geometric multiplicities of 3 + 5i and of 3 − 5i for A′ are equal to 2, which is ≤ 5/2.

All the numerical computations, which follow, have been done with the MATLAB system.

The distance between the two matrices is

∥A′ − A∥ = ∥[ \begin{matrix}−0.1 & −0.2 \\ 0.2 & −0.1 \end{matrix} ]∥ ≃ 0.2236 ,

but, if we define f(λ) := σ_{4}(λI − A) and we calculate min_{λ∈ℝ} f(λ) with the MATLAB function FMIN we obtain that this minimum is approximatively equal to 5 and is attained for λ ≃ 3. Since 0.2236 < 5, we conclude that (29) does not hold in this case.

However, the minimum min_{λ∈ℂ} f(λ) is approximatively equal to 0.1118 and is attained for the approximate complex numbers 3.0504 ± 0.0998i. This minimum has been computed with the MATLAB functions FMINS and FMINU identifying ℂ with ℝ^{2}.

If A ∈ ℝ^{n×n}, then it is easy to check that for all λ ∈ ℂ, σ_{n−k+1}(λI −A) = σ_{n−k+1}(\overline{λ}I − A).

Now, we are going to expose two illustrative examples.

Example 1. Let us consider the matrix

A = [ \begin{matrix}1 & 2 & −3 & −4 & 5 \\ 6 & 7 & 8 & 9 & 10 \\ 9 & 8 & 7 & 6 & 5 \\ 4 & 3 & 2 & 1 & 0 \\ −7 & −4 & −9 & 0 & 0 \end{matrix} ] .

We have that Λ(A) = {8.0813±7.8375i, −0, 0813±1.3737i, 0}; thus i(A) = 1. Here n = 5.

Let k = 3, then

min_{λ∈ℂ} σ_{n−k+1}(λI − A) ≃ σ_{n−k+1}((1.2171 ± 2.9459i)I − A) ≃ 6.6288 ;

but

min_{λ∈ℝ} σ_{n−k+1}(λI − A) ≃ σ_{n−k+1}(0.0293I − A) ≃ 6.8940 .

Therefore, for k = 3

min_{λ∈ℝ} σ_{n−k+1}(λI − A) > min_{λ∈ℂ} σ_{n−k+1}(λI − A) .

However, for k = 2, 4 and 5 we think that

min_{λ∈ℝ} σ_{n−k+1}(λI − A) = min_{λ∈ℂ} σ_{n−k+1}(λI − A)

because we obtain that

min_{λ∈ℝ} σ_{4}(λI − A) ≃ σ_{4}(1.7706I − A) ≃ 2.7543 ≃ min_{λ∈ℂ} σ_{4}(λI − A) ;

min_{λ∈ℝ} σ_{2}(λI − A) ≃ σ_{2}(2.6093I − A) ≃ 8.4257 ≃ min_{λ∈ℂ} σ_{2}(λI − A) ;

and

min_{λ∈ℝ} σ_{1}(λI − A) ≃ σ_{1}(7.8881I − A) ≃ 23.6308 ≃ min_{λ∈ℂ} σ_{1}(λI − A) .

In this Example, Example 2 and Remark 3, the minima min_{λ∈ℝ} σ_{n−k+1}(λI− A) has been computed with the MATLAB function FMIN, minimizing for values of λ in the interval −∥A∥ ≤ λ ≤ ∥A∥. The minima when λ runs in ℂ has been computed with the MATLAB functions FMINS and FMINU identifying ℂ with ℝ^{2}.

Example 2. Let now

A = [ \begin{matrix}0 & 1 & 2 \\ 0 & 0 & 3 \\ 0 & 0 & 0 \end{matrix} ] .

The matrix A is nonderogatory; so i(A) = 1. Let X ∈ ℂ^{3×3} be a derogatory matrix; this is equivalent to I, X, X^{2} being linearly dependent. Stating this fact and by means of the DERIVE system we have seen that all the derogatory matrices sufficiently close to A have the following shape

X = [ \begin{matrix}a & b & c \\ \frac{f(ac+bf−ce)}{c^{2}} & e & f \\ \frac{(ac+bf−ce)(bf+c(g−e))}{c^{3}} & \frac{b(bf+c(g−e))}{c^{2}} & g \end{matrix} ]  (30)

with a, b, c, e, f, g ranging over ℂ, c ≠ 0.

Let

D_{1} := {X ∈ ℂ^{3×3} : X as in (30) with a, b, c, d, f, e, g ∈ ℂ and c ≠ 0},

D_{2} := {X ∈ ℝ^{3×3} : X as in (30) with a, b, c, d, f, e, g ∈ ℝ and c ≠ 0}.

Computing with the MATLAB software (functions FMINS and FMINU) the global minima

min_{X∈D_{1}} ∥A − X∥  (31)
min_{X∈D_{2}} ∥A − X∥  (32)

we have that both minima are approximatively equal to 0.6799. In the case (31) we minimize a real function of 12 real variables. In the case (32) we consider a real function of 6 real variables.

If k = 2, it also seems that

min_{λ∈ℝ} σ_{n−k+1}(λI − A) = min_{λ∈ℂ} σ_{n−k+1}(λI − A) ≃ 0.6799

and that the minimum value is attained for λ ≃ −0.4437.

Remark 3. Let k be an integer, 2 ≤ k ≤ n. Let A ∈ ℝ^{n×n} be such that i(A) < k. We have checked with a computer that in many cases the equality

min_{λ∈ℝ} σ_{n−k+1}(λI − A) = min_{λ∈ℂ} σ_{n−k+1}(λI − A)  (33)

seems to be true. But this is not always so, as it can be seen in the Remark 2 for the case k = 2 and in the Example 1 for k = 3.

It would be interesting to characterize the matrices A and the values k for which the equality (33) does not hold. This subject deserves to be investigated.

Remark 4. The MATLAB function FMIN uses the subroutine FMIN in [7, Chapter 8](See page 469 of [20]) . The MATLAB function FMINS uses the Simplex search algorithm of Nelder and Mead. The MATLAB function FMINU is referred as unsconstrained nonlinear optimization; its default algorithm is the BFGS quasi-Newton method using a mixed quadratic and cubic line search procedure. See [17].

Acknowledgements.

The authors thank Francisco Marcellán for having formulated the objective of Section 3 to them. They also thank the referee for the helpful comments and suggestions that have allowed to ameliorate this paper.

References

[1] R. Bhatia, Perturbation Bounds for Matrix Eigenvalues, Pitman Research Notes in Mathematics Series #162, Longman Scientific & Technical, Essex, 1987.

[2] R. Bhatia, Matrix Analysis, Springer, Berlin, 1997.

[3] H. den Boer and G. Ph. A. Thijsse, Semi-stability of sums of partial multiplicities under additive perturbation, Integral Equations and Operator Theory 3(1) (1980), 23–42.

[4] R. Byers, A bisection method for measuring the distance of a stable matrix to the unstable matrices, SIAM J. Sci. Stat. Comput. 9(5)(1988)875–881.

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

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

[7] G.E. Forsythe, M. Malcolm, C.B. Moler, Computer Methods for Mathematical Computations, Prentice-Hall, Englewood-Cliffs, New Jersey, 1977.

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

[9] N. J. Higham, Matrix nearness problems and applications, pp. 1-27 in Applications of Matrix Theory, Edited by M. J. C. Gover and S. Barnett, Clarendon Press, Oxford, 1989.

[10] N. Karcanias and G. Kalogeropoulos, On the Segré, Weyr characteristics of right (left) regular matrix pencils, Int. J. Control 44 (4) (1986), 991– 1015.

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

[12] G.M. Krause, Bounds for the variation of matrix eigenvalues and polynomial roots, Linear Algebra Appl. 208/209 (1994), 73–82.

[13] P. Lancaster and L. Rodman, Algebraic Riccati Equations, Clarendon Press, Oxford, 1995.

[14] P. Lancaster and M. Tismenetsky, The Theory of Matrices with Applications, Academic Press, New York, 1985.

[15] A. S. Markus, E. È. Parilis, The change of the Jordan structure of a matrix under small perturbations, Linear Algebra Appl. 54 (1983), 139– 152.

[16] E. Marques de Sá, The change of the Kronecker structure of a complex matrix pencil under small perturbations, Preprint (1990).

[17] Optimization Toolbox User’s Guide, 1994,1995, The MathWorks, Inc., Natick, Mass. 01760–1500.

[18] A. Pokrzywa, On perturbations and the equivalence orbit of a matrix pencil, Linear Algebra Appl. 82 (1986), 99–121.

[19] K. Tchon, On generic properties of linear systems: an overview, Kybernetika19, No. 6 (1983) 467–474.

[20] C. Van Loan, How near is a stable matrix to an unstable matrix ?, pp. 465–478 in Linear Algebra and its Role in Systems Theory, Edited by R. A. Brualdi, D. H. Carlson, B. N. Datta, C. R. Johnson and R. J. Plemmons, Contemporary Math., Vol. 47, A.M.S., Providence, 1985.

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

[22] J. H. Wilkinson, On neighbouring matrices with quadratic elementary divisors, Numer. Math 44 (1984), 1–21.

[23] J. H. Wilkinson, Sensitivity of eigenvalues, Utilitas Math. 25 (1984), 5–76.