Geometric multiplicity margin for a submatrix ^{∗}

José María González de Durana^{†} Juan-Miguel Gracia^{‡}

February 19, 2001

Abstract Let G be a square complex matrix with less than k nonconstant invariant factors. We find a complex matrix that gives an optimal approximation to G among all possible matrices that have more than or equal to k invariant factors, obtained by varying only the entries of a bottom right submatrix of G.

Key Words: invariant factors, derogatory eigenvalue, submatrix, singular values, structured pseudospectrum.

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

1 Introduction

Notations

In this paper we use the following notation. By ℂ we denote the field of complex numbers, and ℂ^{m×n} the set of m × n matrices with entries in ℂ. We always will use the spectral norm over ℂ^{p×q}:

∥M∥ = max_{\begin{matrix}x ∈ ℂ^{q×1} \\ ∥x∥_{2} = 1 \end{matrix}} ∥Mx∥_{2}, M ∈ ℂ^{p×q}

The singular values of a matrix M are denoted by σ_{1}(M) ≥ σ_{2}(M) ≥ ⋯ ≥ σ_{k}(M), where k = min(p, q). It is well known that ∥M∥ = σ_{1}(M). The Moore-Penrose inverse of M is denoted by M^{†} and M^{∗} denotes the conjugate transpose of M. And, when p = q, we denote by σ(M) the spectrum or set of distinct eigenvalues of M.

Let A ∈ ℂ^{n×n}; the geometric multiplicity of an eigenvalue λ_{0} of A is the number of Jordan blocks associated to λ_{0} into the Jordan canonical form of A; we denote this number by gm(λ_{0}, A). So gm(λ_{0}, A) is the maximum number of linearly independent eigenvectors of A associated to λ_{0}; this implies that

gm(λ_{0}, A) = dim Ker(λ_{0}I_{n} − A).

∗Supported by the Ministerio de Educación y Cultura (DGESIC), Proyecto PB97– 0599– CO3–01.

†Department of System Engineering and Automatics, The University of the Basque Country, EUITI, Nieves Cano,12 E-01006 Vitoria-Gasteiz, Spain. E-mail:jtpgogaj@vc.ehu.es

‡Department of Applied Mathematics and Statistics, The University of the Basque Country, Faculty of Pharmacy, P.O. Box 450, E-01080 Vitoria-Gasteiz, Spain.

E-mail: mepgrmej@vc.ehu.es

Let k, 2 ≤ k ≤ n, be an integer. A complex number λ_{0} is called a kderogatory eigenvalue of a matrix A ∈ ℂ^{n×n} if gm(λ_{0}, A) ≥ k. We will say that a matrix A ∈ ℂ^{n×n} is k-derogatory if A has a k-derogatory eigenvalue. We will denote by i(A) the number of nonconstant (or nontrivial) invariant factors of A. It can be observed that i(A) is the greatest geometric multiplicity of the eigenvalues of A.

We denote by ℳ_{k} ⊂ ℂ^{n×n} the set

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

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

A ∈ ℳ_{k} ⇔ for all λ ∈ Λ(A) rank(λI − A) > n − k,

the set ℳ_{k} is open. So, its complementary set ℳ_{k}^{c} is closed. Then, given a matrix D ∈ ℳ_{k}, if we consider a closed ball \overline{B}(D, ρ) ⊂ ℂ^{n×n}, with center at D and radius ρ, it makes sense to find the distance from D to the compact set ℳ_{k}^{c} ∩ \overline{B}(D, ρ) of k-derogatory matrices in the ball.

Antecedent of the problem

The problem of finding

min{∥Y − D∥ : Y ∈ ℳ_{k}^{c}}

was addressed in [7, Theorem 4.1]. There its authors calculated this minimum value and also the matrix where it is attained. They obtained the formula

min_{\begin{matrix}Y ∈ ℂ^{n×n} \\ i(Y) ≥ k \end{matrix}} ∥Y − D∥ = min_{λ∈ℂ} σ_{n−(k−1)}(λI_{n} − D)  (1.1)

for the minimum and they also proved that if λ_{0} ∈ ℂ is a point where the function λ ↦ σ_{n−(k−1)}(λI_{n} − D) attains its minimum value, then a matrix Y_{1} where the minimum of the left hand side of (1.1) is reached is given by

Y_{1} = D + s_{n−(k−1)}u_{n−(k−1)}v_{n−(k−1)}^{∗} + ⋯ + s_{n}u_{n}v_{n}^{∗}

where

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

are the k last singular values and singular vectors of the matrix λ_{0}I_{n} − D. Moreover λ_{0} is an eigenvalue of Y_{1} with geometric multiplicity equal to k.

Problem

The main result we obtain in this article (Theorem 4.1) generalizes this result to the case in which it is not allowed varying the whole matrix but only into a submatrix. Let G be an n × n complex matrix with less than k nonconstant invariant factors

G = (\begin{matrix}A & B \\ C & D \end{matrix}) ,

partitioned into four blocks A ∈ ℂ^{n_{1}×n_{1}}, B ∈ ℂ^{n_{1}×n_{2}}, C ∈ ℂ^{n_{2}×n_{1}}, D ∈ ℂ^{n_{2}×n_{2}}.

We are going to find the distance from D to the set of matrices Y ∈ ℂ^{n_{2}×n_{2}} such that the matrix

G_{Y} := (\begin{matrix}A & B \\ C & Y \end{matrix})

is k-derogatory (in case of this set is not empty):

min_{\begin{matrix}Y ∈ ℂ^{n_{2}×n_{2}} \\ G_{Y} ∈ ℳ_{k}^{c} \end{matrix}} ∥Y − D∥.  (1.2)

Also we are going to find a matrix Y_{1} ∈ ℂ^{n_{2}×n_{2}} where this constrained minimum is attained.

Submatrix that lowers the rank

In order to do that we will use some results from the papers [4],[13], [18] and the book [3] which point out what are the possible ranks of all the matrices in the form

\begin{matrix}n_{1} n_{2} \\ G_{X} := (\begin{matrix}A & B \\ C & X \end{matrix}) & \begin{matrix}m_{1} \\ m_{2} \end{matrix} , \end{matrix}

by varying X in ℂ^{m_{2}×n_{2}}, and what is the nearest matrix, of this form, to the previously fixed matrix

G = (\begin{matrix}A & B \\ C & D \end{matrix})

and such that rank G_{X} < rank G.

A summary of results from [13, Theorem 19, (8.1), (8.2) and (8.6)], [4, Theorem 3], [18, Theorem 2.1] and Theorem 6.3.7, page 102, of the book [3], which we need here, is the following theorem.

Theorem 1.1 With the previous notations, let

ρ := rank[A, B] + rank [\begin{matrix}A \\ C \end{matrix}] − rank A.

Then rank G_{X} must satisfy

ρ ≤ rank G_{X}

for all matrix X ∈ ℂ^{m_{2}×n_{2}}. Also it is true that there exists a matrix Z ∈ ℂ^{m_{2}×n_{2}} such that

rank G_{Z} = ρ.

Now let

M := (I − AA^{†})B, N := C(I − A^{†}A),

then, for all X ∈ ℂ^{m_{2}×n_{2}},

rank G_{X} = ρ + rank S(X),

where

S(X) := (I − NN^{†})(X − CA^{†}B)(I − M^{†}M).

If r is an integer which satisfy the inequalities

ρ ≤ r < rank G,

then a matrix X_{0} ∈ ℂ^{m_{2}×n_{2}} such that

∥X_{0} − D∥ = min{∥X − D∥ : rank G_{X} ≤ r}

is given by the formula

X_{0} := D − U diag(0, …, 0, σ_{p+1}(S(D)), σ_{p+2}(S(D)), …, σ_{l}(S(D))) V^{∗}, (1.3)

in which:

(i) p := r − ρ,

(ii) U ∈ ℂ^{m_{2}×m_{2}}, V ∈ ℂ^{n_{2}×n_{2}} are the unitary matrices which appear in the singular value decomposition of the matrix S(D):

U^{∗}S(D)V = diag(σ_{1}(S(D)), …, σ_{p}(S(D)), σ_{p+1}(S(D)), …, σ_{l}(S(D))) ∈ ℂ^{m_{2}×n_{2}},

(iii) l := min{m_{2}, n_{2}},

(iv) diag(σ_{1}(S(D)), …, σ_{p}(S(D)), σ_{p+1}(S(D)), …, σ_{l}(S(D))) is the m_{2} × n_{2} matrix Δ = (d_{ij}), not necessarily squared, such that

d_{ij} := \{ \begin{matrix}0 & if & i ≠ j, \\ σ_{i}(S(D)) & if & i = j, \end{matrix}

(v) diag(0, …, 0, σ_{p+1}(S(D)), σ_{p+2}(S(D)), …, σ_{l}(S(D))) is the matrix from (iv) with the change d_{ii} = 0 for i = 1, …, p.

From (1.3) it results obvious that

min{∥X − D∥ : X ∈ ℂ^{m_{2}×n_{2}}, rank G_{X} ≤ r} = σ_{p+1}(S(D)).

Organization

This paper is organized as follows: In Section 2 we address the question of existence of k-derogatory matrices in the shape ( \begin{matrix}A & B \\ C & Y \end{matrix}) with fixed A, B and C and variable Y; we will see that a such matrix exists always if the size of Y is greater than or equal to k. Section 3 is devoted to an important real function h_{k} defined on a plane domain constituted by ℝ^{2} minus some eigenvalues of A, if the size of D is greater than or equal to k; when this size is less than k, the definition set of the function h_{k} is a subset of the spectrum of A (so, it is finite). Section 4 deals with the conversion of the constrained minimization problem (1.2) in a problem of global minimization of the function h_{k} on its domain. Finally, in Section 5 we consider the related question of finding where are the k-derogatory eigenvalues of all matrices ( \begin{matrix}A & B \\ C & Y \end{matrix}) with Y adequately close to D; this is linked with the concept of pseudospectrum [16, 17].

2 Existence of k-derogatory matrices with constraints

In general, for a pair of matrices (A, B) ∈ ℂ^{n×n}×ℂ^{n×m} we call i[A, B] the number of nonconstant invariant factors of the polynomial matrix λ[I_{n}, 0] − [A, B]. If C ∈ ℂ^{m×n}, we denote by i [ \begin{matrix}A \\ C \end{matrix} ] the number of nonconstant invariant factors of the polynomial matrix λ [ \begin{matrix}I_{n} \\ 0 \end{matrix} ] − [ \begin{matrix}A \\ C \end{matrix} ] . Let ν ∈ \{1, …, n + m\}. A result from [15, Theorem 6, p. 6] says that there exists a matrix D ∈ ℂ^{m×m} such that

i (\begin{matrix}A & B \\ C & D \end{matrix}) ≤ ν

if and only if

max \{i[A, B], i [ \begin{matrix}A \\ C \end{matrix} ]\} ≤ ν.

Now we turn over our problem. So, let G be an n × n complex such that i(G) < k,

G = (\begin{matrix}A & B \\ C & D \end{matrix}) ,

partitioned into four blocks A ∈ ℂ^{n_{1}×n_{1}}, B ∈ ℂ^{n_{1}×n_{2}}, C ∈ ℂ^{n_{2}×n_{1}}, D ∈ ℂ^{n_{2}×n_{2}}. From aforementioned Silva’s result [15], we have that

max \{i[A, B], i [ \begin{matrix}A \\ C \end{matrix}]\} ≤ k − 1.

We are going to find the distance from D to the set of matrices Y ∈ ℂ^{n_{2}×n_{2}} such that the matrix

G_{Y} := (\begin{matrix}A & B \\ C & Y \end{matrix})

is k-derogatory, in case of this set is not empty.

General considerations

For each λ ∈ ℂ, let 𝒩_{k,λ} be the set of all matrices Y ∈ ℂ^{n_{2}×n_{2}} such that λ is an eigenvalue of G_{Y} with geometric multiplicity ≥ k; with symbols,

𝒩_{k,λ} := {Y ∈ ℂ^{n_{2}×n_{2}} : gm(λ, G_{Y}) ≥ k}.

As we will see later it can occur that for some λ ∈ ℂ the set 𝒩_{k,λ} be empty. Taking this into account we define the set

Ω_{k} := {λ ∈ ℂ : 𝒩_{k,λ} ≠ ∅}.  (2.1)

Or what is equivalent,

Ω_{k} := {λ ∈ ℂ : ∃Y ∈ ℂ^{n_{2}×n_{2}}, gm(λ, G_{Y}) ≥ k};

With words, Ω_{k} is the set of all k-derogatory eigenvalues of matrices in the shape ( \begin{matrix}A & B \\ C & Y \end{matrix}) where Y runs over ℂ^{n_{2}×n_{2}}. Calling

𝒩_{k} := {Y ∈ ℂ^{n_{2}×n_{2}} : i(G_{Y}) ≥ k},  (2.2)

we have

𝒩_{k} = ⋃_{λ∈Ω_{k}} 𝒩_{k,λ}.  (2.3)

So, Ω_{k} is empty if and only if 𝒩_{k} is empty. Note that

𝒩_{k} = {Y ∈ ℂ^{n_{2}×n_{2}} : G_{Y} ∈ ℳ_{k}^{c}}.

For every λ ∈ ℂ we define

ρ_{1}(λ) := rank[λI_{n_{1}} − A, −B] + rank [\begin{matrix}λI_{n_{1}} − A \\ −C \end{matrix}] − rank(λI_{n_{1}} − A); (2.4)
M(λ) := [I_{n_{1}} − (λI_{n_{1}} − A)(λI_{n_{1}} − A)^{†}]( − B);  (2.5)
N(λ) := ( − C)[I_{n_{1}} − (λI_{n_{1}} − A)^{†}(λI_{n_{1}} − A)].  (2.6)

Thus, the functions ρ_{1}, M and N depend only on λ ∈ ℂ. Moreover, for every λ ∈ ℂ and every Y ∈ ℂ^{n_{2}×n_{2}}, we define the matrix

\begin{matrix}S_{1}(λ, Y) := \\ (I_{n_{2}} − N(λ)N(λ)^{†}) · (λI_{n_{2}} − Y − C(λI_{n_{1}} − A)^{†}B) · (I_{n_{2}} − M(λ)^{†}M(λ)); \end{matrix}

(2.7)

by Theorem 1.1, it follows

rank(λI_{n} − G_{Y}) = rank ( \begin{matrix}λI_{n_{1}} − A & −B \\ −C & λI_{n_{2}} − Y \end{matrix} ) = ρ_{1}(λ) + rank S_{1}(λ, Y).

(2.8)

First of all, we deduce a lower bound of the function ρ_{1} due to the hypothesis i(G) < k.

Proposition 2.1 With the preceding notations, for all λ ∈ ℂ,

n_{1} − k + 1 ≤ ρ_{1}(λ).

Proof: By (2.8) we have

rank ( \begin{matrix}λI_{n_{1}} − A & −B \\ −C & λI_{n_{2}} − D \end{matrix} ) = ρ_{1}(λ) + rank S_{1}(λ, D).  (2.9)

As i(G) < k, for all λ ∈ ℂ,

n − k < rank ( \begin{matrix}λI_{n_{1}} − A & −B \\ −C & λI_{n_{2}} − D \end{matrix} ) = ρ_{1}(λ) + rank S_{1}(λ, D), (2.10)

So, by (2.9) and (2.10),

n_{1} + n_{2} − k < ρ_{1}(λ) + rank S_{1}(λ, D);

since rank S_{1}(λ, D) ≤ n_{2}, we have

n_{1} + n_{2} − k < ρ_{1}(λ) + n_{2}.

What implies n_{1} − k < ρ_{1}(λ) or, equivalently, n_{1} − k + 1 ≤ ρ_{1}(λ). □

Proposition 2.2

Ω_{k} = {λ ∈ ℂ : ρ_{1}(λ) ≤ n − k}.

Proof: If λ ∈ Ω_{k}, then there exists Y ∈ ℂ^{n_{2}×n_{2}} such that gm(λ, G_{Y}) ≥ k; what is equivalent to rank(λI_{n} − G_{Y}) ≤ n − k. Hence by (2.8),

ρ_{1}(λ) + rank S_{1}(λ, Y) ≤ n − k.

Therefore ρ_{1}(λ) ≤ n − k.

Conversely, if λ ∈ ℂ is such that ρ_{1}(λ) ≤ n − k, then taking

Y_{λ} := λI_{n_{2}} − C(λI_{n_{1}} − A)^{†}B,

it follows by (2.7) that S_{1}(λ, Y_{λ}) = 0. Thus,

rank(λI_{n_{2}} − G_{Y_{λ}}) = ρ_{1}(λ);

so,

rank(λI_{n_{2}} − G_{Y_{λ}}) ≤ n − k.

Consequently, 𝒩_{k,λ} ≠ ∅. Hence λ ∈ Ω_{k}. □

If k is greater than n_{2}, then the set Ω_{k} is “small” as we are going to see next.

Proposition 2.3 If n_{2} < k and λ ∉ Λ(A), then 𝒩_{k,λ} = ∅. Proof: Given that every eigenvalue of (A, B), resp. of (C, A), is an eigenvalue of A, from (2.4) for all λ ∉ Λ(A) we have ρ_{1}(λ) = n_{1}. And if there exists a matrix Y ∈ 𝒩_{k,λ} it follows from definition of 𝒩_{k,λ} and (2.8) that

ρ_{1}(λ) + rank S_{1}(λ, Y) ≤ n − k;

hence n_{1} ≤ n_{1} + n_{2} − k. What implies 0 ≤ n_{2} − k, which contradicts n_{2} − k < 0. □

Thus, from this proposition and the definition (2.1) of the set Ω_{k} we can derive the following result.

Proposition 2.4 If n_{2} < k, then

Ω_{k} ⊂ Λ(A).

So, when n_{2} < k, what eigenvalues of A belong to Ω_{k}? we will answer this question later on. Before, let us establish a sufficient condition to Ω_{k} be empty.

Proposition 2.5 Suppose that n_{2} < k and for all α ∈ Λ(A) we have

gm(α, A) < k − n_{2}.  (2.11)

Then

Ω_{k} = ∅.

Proof: If for all α ∈ Λ(A), gm(α, A) < k − n_{2}, then

rank(αI_{n_{1}} − A) > n_{1} − (k − n_{2}) = n_{1} + n_{2} − k = n − k;

therefore, ρ_{1}(α) > n − k. Hence, by Proposition 2.2 α ∉ Ω_{k} and, as Ω_{k} ⊂ Λ(A) from Proposition 2.4, we deduce

Ω_{k} = ∅.
□

Proposition 2.5 admits the next equivalent statements.

Proposition 2.6 Suppose that n_{2} < k and for all α ∈ Λ(A) we have

gm(α, A) < k − n_{2}.

Then, it does not exist any matrix Y ∈ ℂ^{n_{2}×n_{2}} such that

i (\begin{matrix}A & B \\ C & Y \end{matrix}) ≥ k;

i.e. the set 𝒩_{k} is empty.

Examples with n_{2} < k

We are going to consider two examples that show us the set Ω_{k} can be empty.

Example 2.1 Let

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

Here n_{2} = 2, n = 5. Let k := 4. Since i(G) = 1, we have i(G) < k; by the other hand, Λ(A) = {0, 1}. We see that gm(0, A) = 1, gm(1, A) = 1; so, 1 < 2 = 4 − 2 = k − n_{2}, but ρ_{1}(0) = 4 and ρ_{1}(1) = 4; hence

ρ_{1}(0) ≰ 1 = 5 − 4 = n − k so, Proposition 2.2 implies 0 ∉ Ω_{4}
ρ_{1}(1) ≰ 1 = 5 − 4 = n − k so, Proposition 2.2 implies 1 ∉ Ω_{4}

Hence, by Proposition 2.4,

Ω_{4} = ∅.

As k − n_{2} = 4 − 2 = 2, this result can also be deduced directly from Proposition 2.5 without need to compute ρ_{1}(0), ρ_{1}(1).

Notwithstanding it can occur that Ω_{k} = ∅ though for some α ∈ Λ(A) we have gm(α, A) ≥ k − n_{2}, as we can see in the next example.

Example 2.2 Let

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

Here we again take k := 4; given that i(G) = 2 it follows i(G) < k. Now Λ(A) = {0}, and

gm(0, A) = 2 ≮ 2 = k − n_{2};

but

ρ_{1}(0) = 3 ≰ 1 = 5 − 4 = n − k.

Thus, by Propositions 2.4 and 2.2, 0 ∉ Ω_{4}.

Therefore, condition (2.11) of Proposition 2.5 is sufficient for Ω_{k} = ∅, but it is not a necessary condition. However, the condition n_{2} < k is necessary for Ω_{k} = ∅, as we will see in Proposition 2.7.

Existence of k-derogatory matrices when n_{2} ≥ k

In the previous examples, n_{2} < k. Let us see that when n_{2} ≥ k, the situation changes. The following proposition give us a sufficient condition so that the set in (2.2) is not empty.

Proposition 2.7 Let n_{1}, n_{2} be positive integers, let A ∈ ℂ^{n_{1}×n_{1}}, B ∈ ℂ^{n_{1}×n_{2}}, C ∈ ℂ^{n_{2}×n_{1}} and let n := n_{1} + n_{2}. Let k, 2 ≤ k ≤ n, be an integer. If n_{2} ≥ k then there exist matrices Y ∈ ℂ^{n_{2}×n_{2}} such that the matrix

G_{Y} := (\begin{matrix}A & B \\ C & Y \end{matrix}) ∈ ℂ^{n×n}

is k-derogatory.

Proof: Let λ_{0} be a complex number which is not an eigenvalue of A. Let

Y_{0} := λ_{0}I_{n_{2}} − C(λ_{0}I_{n_{1}} − A)^{−1}B  (2.12)

By virtue of Theorem 1.1,

rank(λ_{0}I_{n} − G_{Y_{0}}) = rank ( \begin{matrix}λ_{0}I_{n_{1}} − A & −B \\ −C & λ_{0}I_{n_{2}} − Y_{0} \end{matrix} )

= rank[λ_{0}I_{n_{1}} − A, −B] + rank [\begin{matrix}λ_{0}I_{n_{1}} − A \\ −C \end{matrix}] − rank(λ_{0}I_{n_{1}} − A)
+ rank(λ_{0}I_{n_{2}} − Y_{0} − C(λ_{0}I_{n_{1}} − A)^{−1}B)
= n_{1} + n_{1} − n_{1} + rank(λ_{0}I_{n_{2}} − Y_{0} − C(λ_{0}I_{n_{1}} − A)^{−1}B)
= n_{1} + rank(λ_{0}I_{n_{2}} − λ_{0}I_{n_{2}} + C(λ_{0}I_{n_{1}} − A)^{−1}B − C(λ_{0}I_{n_{1}} − A)^{−1}B)
= n_{1}

As k ≤ n_{2}, we have n_{1} ≤ n_{1} + n_{2} − k = n − k. Therefore λ_{0} is a k-derogatory eigenvalue of G_{Y_{0}} and this matrix is k-derogatory. □

Remark 2.1 Note this proposition proves even more: For each λ ∈ ℂ ∖ σ(A) there exists a matrix Y_{λ} ∈ ℂ^{n_{2}×n_{2}} such that λ is a k-derogatory eigenvalue of G_{Y_{λ}}.

Existence of k-derogatory matrices when n_{2} < k

After Proposition 2.4 we write the following question: When n_{2} < k, what eigenvalues of A belong to Ω_{k}? An answer is λ_{0} ∈ Λ(A) belongs to Ω_{k} if and only if ρ_{1}(λ_{0}) ≤ n − k, as it can be seen from the final part of the proof of the next result (“if”) and Proposition 2.2 (“only if”).

Proposition 2.8 If n_{2} < k, then there exists a Y ∈ ℂ^{n_{2}×n_{2}} such that i(G_{Y}) ≥ k if and only if there exists a λ_{0} ∈ Λ(A) such that ρ_{1}(λ_{0}) ≤ n − k. Proof: If there exists a Y ∈ ℂ^{n_{2}×n_{2}} such that i(G_{Y}) ≥ k, then G_{Y} has a k-derogatory eigenvalue α; i.e. gm(α, G_{Y}) ≥ k. Hence

rank(αI_{n} − G_{Y}) ≤ n − k.  (2.13)

By (2.8)

rank(αI_{n} − G_{Y}) = ρ_{1}(α) + rank S_{1}(α, Y).  (2.14)

Therefore, α ∈ Λ(A); otherwise, given that 0 ≤ rank S_{1}(α, Y), from (2.13) and (2.14) we should have k ≤ n_{2}; what is absurd. Moreover, (2.13) and (2.14) imply ρ_{1}(α) ≤ n − k.

Conversely, if there exists a λ_{0} ∈ Λ(A) such that ρ_{1}(λ_{0}) ≤ n − k take

Y := λ_{0}I_{n_{2}} − C(λ_{0}I_{n_{1}} − A)^{†}B;

by (2.7), this implies S_{1}(λ_{0}, Y) = 0. Hence, by (2.8),

rank(λ_{0}I_{n} − G_{Y}) = ρ_{1}(λ_{0});

so, gm(λ_{0}, G_{Y}) ≥ k. □

Paraphrasing this statement in analogous terms to those of [15], we have:

Proposition 2.9 Let A ∈ ℂ^{n_{1}×n_{1}}, B ∈ ℂ^{n_{1}×n_{2}}, C ∈ ℂ^{n_{2}×n_{1}}. Let k be an integer, n_{2} < k ≤ n. Then there exists a Y ∈ ℂ^{n_{2}×n_{2}} such that

i (\begin{matrix}A & B \\ C & Y \end{matrix}) ≥ k

if and only if there exists a λ_{0} ∈ Λ(A) such that

rank[λ_{0}I_{n_{1}} − A, −B] + rank [\begin{matrix}λ_{0}I_{n_{1}} − A \\ −C \end{matrix}] − rank(λ_{0}I_{n_{1}} − A) ≤ n − k.

Remark 2.2 The reference to the Moore-Penrose inverse in this statement and many of the results of this paper referring to ranks can be weakened. According to Theorem 6.3.7, page 102, of the book [3] and Theorem 19 from [13], we can put A^{−} instead of A^{†}, where A^{−} is any (1)-inverse of the matrix A ∈ ℂ^{m×n}; that is to say, A^{−} is any solution of the equation

AXA = A.

Scalar matrices

Consider now the case k = n. Given the matrices A ∈ ℂ^{n_{1}×n_{1}}, B ∈ ℂ^{n_{1}×n_{2}}, C ∈ ℂ^{n_{2}×n_{1}}, D ∈ ℂ^{n_{2}×n_{2}} such that

i (\begin{matrix}A & B \\ C & D \end{matrix}) < n,

what conditions must satisfy A, B and C for there exists a matrix Y ∈ ℂ^{n_{2}×n_{2}} such that

i (\begin{matrix}A & B \\ C & Y \end{matrix}) ≥ n?

This question is equivalent to ask for conditions to

i (\begin{matrix}A & B \\ C & Y \end{matrix}) = n

or, what is the same, that the matrix ( \begin{matrix}A & B \\ C & Y \end{matrix}) se a scalar matrix. Recall that a scalar matrix is a matrix in the shape αI_{n} with an α ∈ ℂ. If there exists Y ∈ ℂ^{n_{2}×n_{2}} such that ( \begin{matrix}A & B \\ C & Y \end{matrix}) is a scalar matrix, then necessarily there is an α ∈ ℂ such that ( \begin{matrix}A & B \\ C & Y \end{matrix}) = αI_{n}; hence it follows

A = αI_{n_{1}}, B = 0
C = 0, Y = αI_{n_{2}}.

Therefore, for the existence of Y such that i ( \begin{matrix}A & B \\ C & Y \end{matrix}) ≥ n are necessary conditions that A, B and C be in the shape

A = αI_{n_{1}}, for some α ∈ ℂ,
B = 0,  (2.15)
C = 0.

Let see that these conditions (2.15) are also sufficient. In fact, under them there exists Y := αI_{n_{2}} such that

(\begin{matrix}αI_{n_{1}} & 0 \\ 0 & αI_{n_{2}} \end{matrix})

is a scalar matrix.

Reminding that

Ω_{k} = {λ ∈ ℂ : ρ_{1}(λ) ≤ n − k}

by Proposition 2.2, and assigning the value n to k, one has

Ω_{n} = {λ ∈ ℂ : ρ_{1}(λ) ≤ n − n};

so, λ ∈ Ω_{n} ⇔ ρ_{1}(λ) = 0. Now then, ρ_{1}(λ) = 0 is equivalent to

rank(λI_{n_{1}} − A) = 0, rank(−B) = 0, rank(−C) = 0;

and these conditions are equivalent to

A = λI_{n_{1}}, B = 0, C = 0.

Thus, the set Ω_{n} has only an element: the one λ ∈ ℂ such that A = λI_{n_{1}}. Therefore,

Ω_{n} = {α}.  (2.16)

3 The function of two real variables to be minimized

Let k be an integer, 2 ≤ k ≤ n. Let

G = (\begin{matrix}A & B \\ C & D \end{matrix}) ∈ ℂ^{(n_{1}+n_{2})×(n_{1}+n_{2})},

be an n × n, four block partitioned matrix such that i(G) < k. In order to use the Theorem 1.1, for each λ ∈ Ω_{k} we define

p_{k}(λ) := n − k − ρ_{1}(λ).  (3.1)

Proposition 3.1 For all λ ∈ Ω_{k}, 0 ≤ p_{k}(λ) ≤ n_{2} − 1.

Proof: From the definition of p_{k}(λ) and Proposition 2.2 for all λ ∈ Ω_{k} we have 0 ≤ p_{k}(λ). By Proposition 2.1,

p_{k}(λ) = n_{1} + n_{2} − k − ρ_{1}(λ) ≤ n_{1} + n_{2} − k − (n_{1} − k + 1)
= n_{1} + n_{2} − k − n_{1} + k − 1 = n_{2} − 1.
□

Let

\begin{aligned}h_{k} : & Ω_{k} & → & ℝ \\ & λ & ↦ & σ_{p_{k}(λ)+1}(S_{1}(λ, D)) \end{aligned}  (3.2)

be the function that associates to each complex number λ ∈ Ω_{k} the (p_{k}(λ) + 1)- th singular value of the n_{2} × n_{2} matrix S_{1}(λ, D). The definition of this matrix can be seen in (2.7) changing Y by D.

Let us assume now that n_{2} ≥ k, which is the most interesting case. Theorem 3.3 summarizes some properties of the function h_{k}. Before of giving its statement, we need some previous results.

Lemma 3.2 Let M_{1}, M_{2}, M_{3} be n × n complex matrices. Let k be an integer, 2 ≤ k ≤ n. Then the following inequalities concerning their singular values are true:

(i) σ_{n}(M_{1}) σ_{n−k+1}(M_{2}) σ_{n}(M_{3}) ≤ σ_{n−k+1}(M_{1}M_{2}M_{3}),

(ii) σ_{n−k+1}(M_{1}M_{2}M_{3}) ≤ ∥M_{1}∥ ∥M_{3}∥ σ_{n−k+1}(M_{2}).

Proof: The inequalities in each line follow from two applications of Theorem 1, p. 44, of [14]. □

Now let

F (λ) := λI_{n_{2}} − D − C(λI_{n_{1}} − A)^{−1}B;

here, λI_{n_{2}} − D is a polynomial matrix in the variable λ and C(λI_{n_{1}} − A)^{−1}B is a strictly proper rational matrix function because

lim_{|λ|→∞} C(λI_{n_{1}} − A)^{−1}B = 0.

Moreover, for each

λ ∈ ℂ ∖ (σ(A) ∪ σ ([\begin{matrix}A & B \\ C & D \end{matrix}])) ,

we have

n = rank ( \begin{matrix}λI_{n_{1}} − A & −B \\ −C & λI_{n_{2}} − D \end{matrix} ) =

rank(λI_{n_{1}} − A) + rank F (λ) = n_{1} + rank F (λ),

in virtue of formula (7), p. 46, of [12] on the Schur complement of λI_{n_{1}} − A in

( \begin{matrix}λI_{n_{1}} − A & −B \\ −C & λI_{n_{2}} − D \end{matrix} ) .

Hence,

rank F (λ) = n_{2}

and so det F (λ) ≢ 0. Therefore, we can consider the local Smith form of the rational matrix function F (λ) at λ_{0}, the complex number λ_{0} being an eigenvalue of A:

F (λ) = E_{1}(λ) diag[(λ − λ_{0})^{ν_{1}}, …, (λ − λ_{0})^{ν_{n_{2}}} ] E_{2}(λ),  (3.3)

where E_{1}(λ) and E_{2}(λ) are rational matrix functions that are defined and invertible at λ_{0}, and ν_{1}, …, ν_{n_{2}} are integers; these integers are uniquely determined by F (λ) and λ_{0} up to permutation and do not depend on the particular choice of the local Smith form (3.3); they are called the partial multiplicities of F (λ) at λ_{0}. See Section 7.2, p. 218–219, of [6].

In virtue of Theorem 1.13.2 (3), p. 25, of the book [10], the poles of F (λ) belong to Λ(A) even if the realization C(λI_{n_{1}} − A)^{−1}B is not minimal. But it may occur that some eigenvalues of A are not poles of F (λ).

Theorem 3.3 With the previous notations, let us assume n_{2} ≥ k. Let h_{k} : Ω_{k} → ℝ be the function we have defined in (3.2). Then

(i) the function h_{k} is continuous on Ω_{k} ∖ σ(A),

(ii) if λ_{0} ∈ σ(A) and the number of negative partial multiplicities of F (λ) at λ_{0} is greater than or equal to n_{2} − k + 1, then

lim_{λ→λ_{0}} h_{k}(λ) = ∞,

(iii) if λ_{0} ∈ σ(A) and the number of negative partial multiplicities of F (λ) at λ_{0} is less than n_{2} − k + 1, then there exists the limit

lim_{λ→λ_{0}} h_{k}(λ),

(iv)

lim_{|λ|→∞} h_{k}(λ) = ∞.

Proof:

(i) If λ ∈ Ω_{k} ∖ σ(A), then

(λI_{n_{1}} − A)^{†} = (λI_{n_{1}} − A)^{−1}

and therefore

M(λ) = 0, N(λ) = 0

and from (3.1) it follows

p_{k}(λ) = n_{1} + n_{2} − k − n_{1} = n_{2} − k;  (3.4)

so that

h_{k}(λ) = σ_{n_{2}−k+1}(λI_{n_{2}} − D − C(λI_{n_{1}} − A)^{−1}B).  (3.5)

By virtue of the continuity of the function

λ ↦ (λI_{n_{1}} − A)^{−1}

on ℂ∖σ(A) and because of being the singular values of a matrix continuous functions of it, it follows that the function

λ ↦ σ_{n_{2}−k+1}(λI_{n_{2}} − D − C(λI_{n_{1}} − A)^{−1}B)

is continuous at each point λ ∈ Ω_{k} ∖ σ(A).

(ii) Call Δ(λ) the diagonal matrix

diag[(λ − λ_{0})^{ν_{1}}, …, (λ − λ_{0})^{ν_{n_{2}}} ]

that appears in (3.3). Applying inequality (i) of Lemma 3.2 to product (3.3) we have

σ_{n_{2}}(E_{1}(λ)) σ_{n_{2}−k+1}(Δ(λ)) σ_{n_{2}}(E_{2}(λ)) ≤ σ_{n_{2}−k+1}(F (λ)).  (3.6)

It is easy to see that the singular values of Δ(λ) are

|λ − λ_{0}|^{ν_{1}} , …, |λ − λ_{0}|^{ν_{n_{2}}} ,

(not necessarily ordered from largest to smallest). By the hypothesis on the negative partial multiplicities of F (λ) at λ_{0}, we have that the (n_{2} −k +1)- th singular value of Δ(λ) (when ordered in nonincreasing order) is in the shape

\frac{1}{|λ − λ_{0}|^{p}} ,

with a positive integer p (the number p does not depend on λ!) for all λ sufficiently closed to λ_{0} and different from it. Hence,

lim_{λ→λ_{0}} σ_{n_{2}−k+1}(Δ(λ)) = lim_{λ→λ_{0}} \frac{1}{|λ − λ_{0}|^{p}} = ∞.  (3.7)

As E_{1}(λ_{0}) and E_{2}(λ_{0}) are invertible it follows

lim_{λ→λ_{0}} σ_{n_{2}}(E_{1}(λ)) = σ_{n_{2}}(E_{1}(λ_{0})) > 0,

lim_{λ→λ_{0}} σ_{n_{2}}(E_{2}(λ)) = σ_{n_{2}}(E_{2}(λ_{0})) > 0.

Therefore, by (3.7) we have

lim_{λ→λ_{0}} σ_{n_{2}}(E_{1}(λ)) σ_{n_{2}−k+1}(Δ(λ)) σ_{n_{2}}(E_{2}(λ)) = ∞;

from here and (3.6) it follows

lim_{λ→λ_{0}} σ_{n_{2}−k+1}(F (λ)) = ∞.

(iii) Let q be the number of negative partial multiplicities of F (λ) at λ_{0}. So, q < n_{2}−k+1. Permuting the elements of the diagonal of Δ(λ), if necessary, we can suppose that

ν_{1} < 0, …, ν_{q} < 0, ν_{q+1} ≥ 0, …, ν_{n_{2}} ≥ 0.

Then the singular values of Δ(λ) are

\frac{1}{|λ − λ_{0}|^{−ν_{1}}} , …, \frac{1}{|λ − λ_{0}|^{−ν_{q}}} , |λ − λ_{0}|^{ν_{q+1}} , …, |λ − λ_{0}|^{ν_{n_{2}}} .  (3.8)

In the case of λ is sufficiently close to λ_{0}, the numbers

\frac{1}{|λ − λ_{0}|^{−ν_{1}}} , …, \frac{1}{|λ − λ_{0}|^{−ν_{q}}} ,

are the q greatest numbers in the list (3.8); thus,

σ_{n_{2}−k+1}(Δ(λ)) = |λ − λ_{0}|^{ℓ}  (3.9)

with ℓ an integer ≥ 0 (the number ℓ does not depend on λ!).

Taking into account (3.3), (3.9) and inequality (ii) in Lemma 3.2,

σ_{n_{2}−k+1}(F (λ)) ≤ ∥E_{1}(λ)∥ ∥E_{2}(λ)∥ σ_{n_{2}−k+1}(Δ(λ))
= ∥E_{1}(λ)∥ ∥E_{2}(λ)∥ |λ − λ_{0}|^{ℓ}.  (3.10)

Given that E_{1}(λ_{0}) and E_{2}(λ_{0}) are invertible, ∥E_{1}(λ_{0})∥ > 0, ∥E_{2}(λ_{0})∥ > 0; then by (3.10) there exist a real number M > 0 and a deleted neighbourhood 𝒩 of λ_{0} such that for all λ ∈ 𝒩, we have

σ_{n_{2}−k+1}(F (λ)) ≤ M.

From this upper bound and due to the fact that σ_{n_{2}−k+1}(F (λ)) is an algebraic function, it follows that there exists the limit

lim_{λ→λ_{0}} σ_{n_{2}−k+1}(F (λ)).

(iv) For all λ ∈ ℂ ∖ σ(A), by [9, p.178, Theorem 3.3.16 (c)] we have

\begin{matrix}|σ_{n_{2}−k+1}(λI_{n_{2}} − D − C(λI_{n_{1}} − A)^{−1}B) − σ_{n_{2}−k+1}(λI_{n_{2}} − D)| \\ ≤ ∥ − C(λI_{n_{1}} − A)^{−1}B∥. \end{matrix}

(3.11)

As (λI_{n_{1}} − A)^{−1} is a matrix of strictly proper rational functions in λ, we have

∥ − C(λI_{n_{1}} − A)^{−1}B∥ → 0  (3.12)

when |λ| → ∞. Given that σ_{n_{2}−k+1}(λI_{n_{2}} − D) → ∞ when |λ| → ∞ [7, proof of Theorem 4.1], it follows from (3.11) and (3.12) that

lim_{|λ|→∞} σ_{n_{2}−k+1}(λI_{n_{2}} − D − C(λI_{n_{1}} − A)^{−1}B) = ∞.

□

Remark 3.1 From this theorem it follows that there exists the minimum

min_{λ∈Ω_{k}} h_{k}(λ).  (3.13)

If n_{2} < k, by Proposition 2.4 the set Ω_{k} is finite; from which the minimum (3.13) exists for whatever value of k.

In relation with point (iii) of the proof of Theorem 3.3, when λ_{0} is not a pole of F (λ), i.e. there is no negative partial multiplicity of λ_{0}, we can say more.

Theorem 3.4 With the preceding notations, if λ_{0} is not a pole of F (λ), then

lim_{λ→λ_{0}} σ_{n_{2}−k+1}(F (λ)) = σ_{n_{2}−k+1}(λ_{0}I_{n_{2}} − D − CS_{λ_{0}}B);

where

S_{λ_{0}} = ∑_{α∈Λ(A)∖\{λ_{0}\}} [\frac{P_{α}}{λ_{0} − α} + \frac{D_{α}}{(λ_{0} − α)^{2}} + ⋯ + \frac{D_{α}^{ν(α)−1}}{(λ_{0} − α)^{ν(α)}} ]

For each α ∈ Λ(A), the matrices P_{α}, D_{α} and the number ν(α) are the Riesz eigenprojection, the eigennilpotent and the index, belonging to the eigenvalue α, respectively. Proof: The Laurent expansion of the resolvent of A in a neighbourhood of λ_{0} is

(λI_{n_{1}} − A)^{−1} = \frac{P_{λ_{0}}}{λ − λ_{0}} + ∑_{j=2}^{ν(λ_{0})} \frac{D_{λ_{0}}^{j−1}}{(λ − λ_{0})^{j}} + ∑_{n=0}^{∞}(−1)^{n}S_{λ_{0}}^{n+1} · (λ − λ_{0})^{n}. (3.14)

where

P_{λ_{0}} := \frac{1}{2πi} ∮_{Γ}(λI_{n_{1}} − A)^{−1} dλ,

Γ being a suitable sufficiently small positively oriented circle centered at λ_{0}. The matrix P_{λ_{0}} is the Riesz projector or eigenprojection associated to λ_{0}. The matrix D_{λ_{0}} is the eigennilpotent matrix

D_{λ_{0}} := (A − λ_{0}I_{n_{1}})P_{λ_{0}},

associated to λ_{0}. See [1, p. 74, p.66–67 ][11, p. 41–42]. From (3.14), we deduce

F (λ) = λI_{n_{2}} − D − \frac{CP_{λ_{0}}B}{λ − λ_{0}} − ∑_{j=2}^{ν(λ_{0})} \frac{CD_{λ_{0}}^{j−1}B}{(λ − λ_{0})^{j}} − ∑_{n=0}^{∞}(−1)^{n}CS_{λ_{0}}^{n+1}B · (λ − λ_{0})^{n};

(3.15)

with

S_{λ_{0}} := \frac{1}{2πi} ∮_{Γ} \frac{1}{λ − λ_{0}} (λI_{n_{1}} − A)^{−1} dλ.

As λ_{0} is not a pole of F (λ), we have that all coefficients of negative powers of λ − λ_{0} in (3.15) are zero. So,

F (λ) = λI_{n_{2}} − D − ∑_{n=0}^{∞}(−1)^{n}CS_{λ_{0}}^{n+1}B · (λ − λ_{0})^{n};  (3.16)

from it follows

lim_{λ→λ_{0}} σ_{n_{2}−k+1}(F (λ)) = σ_{n_{2}−k+1}(λ_{0}I_{n_{2}} − D − CS_{λ_{0}}B).

From [12, p. 315] (where it puts Z_{k0} instead of P_{λ_{0}}), we have

P_{λ_{0}} = φ_{λ_{0}}(A) with φ_{λ_{0}}(λ) := \frac{∏_{j=1}^{s−1}(λ − λ_{j})}{∏_{j=1}^{s−1}(λ_{0} − λ_{j})},

with

{λ_{1}, …, λ_{s−1}} := Λ(A) ∖ {λ_{0}}.

The formula

S_{λ_{0}} = ∑_{α∈Λ(A)∖\{λ_{0}\}} [\frac{P_{α}}{λ_{0} − α} + \frac{D_{α}}{(λ_{0} − α)^{2}} + ⋯ + \frac{D_{α}^{ν(α)−1}}{(λ_{0} − α)^{ν(α)}} ]

for S_{λ_{0}} it can be seen in [11, p. 42, (5.32)] (Kato defined the resolvent of A as (A − λI_{n_{1}})^{−1}; hence the minus sign which appears in its formula (5.32)).

□

Remark 3.2 The index, ν(α), of each eigenvalue α of A satisfies that

D_{α} ≠ 0, …, D_{α}^{ν(α)−1} ≠ 0 and D_{α}^{ν(α)} = 0.

4 Optimal submatrix that increases the geometric multiplicity

Let n_{1}, n_{2} be positive integers and n := n_{1} + n_{2}. Let k be an integer, 2 ≤ k ≤ n. Let A ∈ ℂ^{n_{1}×n_{1}}, B ∈ ℂ^{n_{1}×n_{2}}, C ∈ ℂ^{n_{2}×n_{1}} and D ∈ ℂ^{n_{2}×n_{2}} be matrices such that i(G) < k, where

G := (\begin{matrix}A & B \\ C & D \end{matrix}) .

For each Y ∈ ℂ^{n_{2}×n_{2}} let G_{Y} := ( \begin{matrix}A & B \\ C & Y \end{matrix}). In this section we give a solution to the problem of finding the minimum of the set

{∥Y − D∥ : Y ∈ ℂ^{n_{2}×n_{2}}, i(G_{Y}) ≥ k}  (4.1)

by means of the following theorem.

Theorem 4.1 Using the preceding notation, let A ∈ ℂ^{n_{1}×n_{1}}, B ∈ ℂ^{n_{1}×n_{2}}, C ∈ ℂ^{n_{2}×n_{1}}, D ∈ ℂ^{n_{2}×n_{2}} be matrices such that the n × n matrix

G := (\begin{matrix}A & B \\ C & D \end{matrix})

satisfies i(G) < k. Then

min_{\begin{matrix}Y ∈ ℂ^{n_{2}×n_{2}} \\ i(G_{Y} ) ≥ k \end{matrix}} ∥Y − D∥ = min_{λ∈Ω_{k}} h_{k}(λ).  (4.2)

Moreover, if λ_{0} is a complex number where the function h_{k} : Ω_{k} → ℝ attains its minimum value, then a matrix Y_{1} which minimizes the left-hand side of (4.2) is given by

Y_{1} := D + U diag(0, …, 0, τ_{p_{k}(λ_{0})+1}, …, τ_{n_{2}})V^{∗},  (4.3)

where U, V ∈ ℂ^{n_{2}×n_{2}} are the unitary matrices which appear into the singular value decomposition of the matrix S_{1}(λ_{0}, D):

U^{∗}S_{1}(λ_{0}, D)V = diag (τ_{1}, …, τ_{p_{k}(λ_{0})}, τ_{p_{k}(λ_{0})+1}, …, τ_{n_{2}}).  (4.4)

And λ_{0} is also a k-derogatory eigenvalue of the matrix G_{Y_{1}}; in fact, its geometric multiplicity is equal to k.

Proof: Recall that we denoted by 𝒩_{k} the set of matrices Y ∈ ℂ^{n_{2}×n_{2}} such that the matrix G_{Y} is k-derogatory.

Let us call

C := {∥Y − D∥ : Y ∈ 𝒩_{k}}

and

C_{λ} := {∥Y − D∥ : Y ∈ 𝒩_{k,λ}}

for each λ ∈ Ω_{k}. Then, by (2.3)

C = ⋃_{λ∈Ω_{k}} C_{λ}.

Because 0 is a lower bound of C and of C_{λ} for each λ ∈ Ω_{k}, by [5, Proposition 2.3.6] we have

inf C = inf( ⋃_{λ∈Ω_{k}} C_{λ}) = inf_{λ∈Ω_{k}} (inf C_{λ}) .  (4.5)

Moreover, for all λ ∈ Ω_{k}

inf C_{λ} = min_{Y ∈𝒩_{k,λ}} ∥Y − D∥,  (4.6)

since 𝒩_{k,λ} is a closed set (due to the lower semicontinuity of the function X ↦ rank(X)) .

On the other hand, by Theorem 1.1, for each λ in Ω_{k},

\begin{matrix}σ_{p_{k}(λ)+1}(S_{1}(λ, D)) = \\ min_{\begin{matrix}X ∈ ℂ^{n_{2}×n_{2}} \\ rank ( \begin{matrix}λI_{n_{1}} − A & −B \\ −C & X \end{matrix} ) ≤ n − k \end{matrix}} ∥( \begin{matrix}λI_{n_{1}} − A & −B \\ −C & λI_{n_{2}} − D \end{matrix} ) − ( \begin{matrix}λI_{n_{1}} − A & −B \\ −C & X \end{matrix} )∥; \end{matrix}

(4.7)

if X ∈ ℂ^{n_{2}×n_{2}} is any matrix such that

rank ( \begin{matrix}λI_{n_{1}} − A & −B \\ −C & X \end{matrix} ) ≤ n − k

and we define X′ := λI_{n_{2}} − X, then X′ ∈ 𝒩_{k,λ}; conversely, if X′ ∈ 𝒩_{k,λ} and X := λI_{n_{2}} − X′, then

rank ( \begin{matrix}λI_{n_{1}} − A & −B \\ −C & X \end{matrix} ) ≤ n − k.

Consequently, for each λ ∈ Ω_{k}, by virtue of (4.7),

σ_{p_{k}(λ)+1}(S_{1}(λ, D)) = min_{X′∈𝒩_{k,λ}} ∥( \begin{matrix}λI_{n_{1}} − A & −B \\ −C & λI_{n_{2}} − D \end{matrix} ) − ( \begin{matrix}λI_{n_{1}} − A & −B \\ −C & λI_{n_{2}} − X′ \end{matrix} )∥

= min_{X′∈𝒩_{k,λ}} ∥( \begin{matrix}0 & 0 \\ 0 & (λI_{n_{2}} − D) − (λI_{n_{2}} − X′) \end{matrix} )∥

= min_{X′∈𝒩_{k,λ}} ∥X′ − D∥ .  (4.8)

From (4.5), (4.6) and (4.8) we deduce

min_{Y ∈𝒩_{k}} ∥Y − D∥ = inf_{λ∈Ω_{k}} σ_{p_{k}(λ)+1}(S_{1}(λ, D))
= inf_{λ∈Ω_{k}} h_{k}(λ) = min_{λ∈Ω_{k}} h_{k}(λ).

Now let λ_{0} ∈ Ω_{k} be such that

h_{k}(λ_{0}) = min_{λ∈Ω_{k}} h_{k}(λ).  (4.9)

Let τ_{1}, …, τ_{n_{2}} be the singular values of S_{1}(λ_{0}, D) in nonincreasing order. By the singular value decomposition theorem, there exist unitary matrices U, V ∈ ℂ^{n_{2}×n_{2}} such that

U^{∗}S_{1}(λ_{0}, D)V = diag(τ_{1}, …, τ_{p_{k}(λ_{0})}, τ_{p_{k}(λ_{0})+1}, …, τ_{n_{2}}).

By definition of h_{k}, see (3.2), we have

h_{k}(λ_{0}) = σ_{p_{k}(λ_{0})+1}(S_{1}(λ_{0}, D)) = τ_{p_{k}(λ_{0})+1}.  (4.10)

Next we define

Y_{1} := D + U diag(0, …, 0, τ_{p_{k}(λ_{0})+1}, …, τ_{n_{2}})V^{∗}.  (4.11)

As the spectral norm is unitarily invariant it follows that

∥Y_{1} − D∥ = ∥ diag(0, …, 0, τ_{p_{k}(λ_{0})+1}, …, τ_{n_{2}})∥ = τ_{p_{k}(λ_{0})+1}.  (4.12)

Still it remains to prove that Y_{1} ∈ 𝒩_{k}. In fact, we are going to prove that Y_{1} ∈ 𝒩_{k,λ_{0}}. Indeed, calling Δ_{0} := diag(0, …, 0, τ_{p_{k}(λ_{0})+1}, …, τ_{n_{2}}),

rank ( \begin{matrix}λ_{0}I_{n_{1}} − A & −B \\ −C & λ_{0}I_{n_{2}} − Y_{1} \end{matrix} )

= rank ( \begin{matrix}λ_{0}I_{n_{1}} − A & −B \\ −C & λ_{0}I_{n_{2}} − D − UΔ_{0}V^{∗} \end{matrix} ) = n − k,

because, by (1.3), subtracting UΔ_{0}V^{∗} to the matrix λ_{0}I_{n_{2}} − D we attain to lower the rank of the matrix

( \begin{matrix}λ_{0}I_{n_{1}} − A & −B \\ −C & λ_{0}I_{n_{2}} − D \end{matrix} )

to the value

rank ( \begin{matrix}λ_{0}I_{n_{1}} − A & −B \\ −C & λ_{0}I_{n_{2}} − D − UΔ_{0}V^{∗} \end{matrix} ) = n − k.

□

Remark 4.1 From (4.2) of Theorem 4.1 we deduce that the nonnegative integer ℓ that appears in (3.9) must be equal to 0: If ℓ > 0, upper bound (3.10) should imply that

lim_{λ→λ_{0}} σ_{n_{2}−k+1}(F (λ)) = 0;

hence

inf_{λ∈Ω_{k}} h_{k}(λ) = 0,

and, by (4.2),

inf ; \begin{matrix}Y ∈ ℂ^{n_{2}×n_{2}} \\ i(G_{Y}) ≥ k \end{matrix} ∥Y − D∥ = 0;

but this contradicts that the set ℳ_{k} is open.

Theorem 4.1 can be proved with inf instead of min.

Scalar matrices. Case k = n

Following the exposed material in the subsection “Scalar matrices” at the end of Section 2, let

(\begin{matrix}αI_{n_{1}} & 0 \\ 0 & D \end{matrix})

be an n × n matrix with α ∈ ℂ, D ∈ ℂ^{n_{2}×n_{2}}, n = n_{1} + n_{2}, and i ( \begin{matrix}αI_{n_{1}} & 0 \\ 0 & D \end{matrix} ) < n.

Consider the problem of finding the nearest matrix Y ∈ ℂ^{n_{2}×n_{2}} to D so that i ( \begin{matrix}αI_{n_{1}} & 0 \\ 0 & Y \end{matrix} ) ≥ n; or what is the same, with ( \begin{matrix}αI_{n_{1}} & 0 \\ 0 & Y \end{matrix} ) a scalar matrix. Now we are going to see that the conclusions (4.2) and (4.3) of Theorem 4.1 follows straightforwardly in this case. Taking into account (2.16) the domain of the function h_{n} is Ω_{n} = {α}. Furthermore ρ_{1}(α) = 0 and, accordingly, p_{n}(α) = 0; hence

h_{n}(α) = σ_{1}(αI_{n_{2}} − D) = ∥αI_{n_{2}} − D∥.

and

min_{λ∈Ω_{n}} h_{n}(λ) = h_{n}(α) = ∥αI_{n_{2}} − D∥.  (4.13)

On the other hand,

min Y ∈ ℂ^{n_{2}×n_{2}} G_{Y} scalar matrix ∥Y − D∥ = ∥αI_{n_{2}} − D∥,  (4.14)

because the set

{Y ∈ ℂ^{n_{2}×n_{2}} | G_{Y} is a scalar matrix}

only has an element: αI_{n_{2}}. Therefore, from (4.13) and (4.14) the assertion (4.2) is evident in this case. Besides, by (4.3) and (4.4), as S_{1}(α, D) := αI_{n_{2}} − D, let U, V ∈ ℂ^{n_{2}×n_{2}} be the unitary matrices that appear in the singular value decomposition of αI_{n_{2}} − D:

U^{∗}(αI_{n_{2}} − D)V = diag(τ_{1}, …, τ_{n_{2}}) with τ_{1} > 0.

Take

Y_{1} := D + U diag(τ_{1}, …, τ_{n_{2}})V^{∗} = D + αI_{n_{2}} − D = αI_{n_{2}};

which confirms the aforementioned exposed.

5 k-Derogatory pseudospectrum

Let M ∈ ℂ^{n×n}; we will denote by S_{k}(M) the set of k-derogatory eigenvalues of M. So, S_{1}(M) = Λ(M), the spectrum of M. Let G ∈ ℂ^{n×n} be the partitioned matrix

G = ( \begin{matrix}A & B \\ C & D \end{matrix} ) ,

with A ∈ ℂ^{n_{1}×n_{1}}, B ∈ ℂ^{n_{1}×n_{2}}, C ∈ ℂ^{n_{2}×n_{1}}, D ∈ ℂ^{n_{2}×n_{2}}, and i(G) < k. Where are the k-derogatory eigenvalues of all matrices

G_{Y} := ( \begin{matrix}A & B \\ C & Y \end{matrix} )

such that Y ∈ ℂ^{n_{2}×n_{2}}, is sufficiently close to D? This question is closely related with the problem treated in Section 4. We would like to find out the geometric description of the set in the complex plane formed by the k-derogatory eigenvalues of all the matrices G_{Y} whose distance from G is less than or equal to a prefixed ε > 0. If ε is less than

min_{λ∈Ω_{k}} h_{k}(λ),

then there is no k-derogatory eigenvalue of the matrices G_{Y} where ∥Y −D∥ ≤ ε, because, by (4.2), all these matrices satisfy i(G_{Y}) < k. So, a necessary condition for the set

⋃_{∥Y −D∥≤ε} S_{k}(G_{Y}) (k-derogatory pseudospectrum of G of radius ε)

be nonempty is that

ε ≥ min_{λ∈Ω_{k}} h_{k}(λ).

It is natural that the k-derogatory pseudospectrum of G of radius ε is equal to the set enclosed by the ε–level curve of the function f(x, y) := h_{k}(x + yi). This fact is consequence of the following theorem.

Theorem 5.1 With the preceding notations, let ε > 0 be a real number. Then

⋃_{{Y ∈ℂ^{n_{2}×n_{2}} \atop ∥Y −D∥≤ε}} S_{k}(G_{Y}) = \{z ∈ Ω_{k} : h_{k}(z) ≤ ε\}.  (5.1)

Proof: Recall that

Ω_{k} = {λ ∈ ℂ : ρ_{1}(λ) ≤ n − k} = {λ ∈ ℂ : 𝒩_{k,λ} ≠ ∅}.

Let z ∈ Ω_{k} be such that h_{k}(z) ≤ ε; then

σ_{p_{k}(z)+1}(S_{1}(z, D)) ≤ ε.  (5.2)

But

σ_{p_{k}(z)+1}(S_{1}(z, D)) =

min_{\begin{matrix}X ∈ ℂ^{n_{2}×n_{2}} \\ rank ( \begin{matrix}zI_{n_{1}} − A & −B \\ −C & X \end{matrix} ) ≤ n − k \end{matrix}} ∥( \begin{matrix}zI_{n_{1}} − A & −B \\ −C & zI_{n_{2}} − D \end{matrix} ) − ( \begin{matrix}zI_{n_{1}} − A & −B \\ −C & X \end{matrix} )∥;

= min_{X′∈𝒩_{k,z}} ∥X′ − D∥ = ∥X′_{0} − D∥,

with X′_{0} ∈ 𝒩_{k,z} (what implies z is a k-derogatory eigenvalue of G_{X′_{0}}). Furthermore, from (5.2) we have ∥X′_{0} − D∥ ≤ ε. Hence

{z ∈ Ω_{k} : h_{k}(z) ≤ ε} ⊂ ⋃_{∥Y −D∥≤ε} S_{k}(G_{Y}).

Reciprocally, if z ∈ S_{k}(G_{X′_{0}}) for some X′_{0} ∈ ℂ^{n_{2}×n_{2}} such that ∥X′_{0} −D∥ ≤ ε, it follows that X′_{0} ∈ 𝒩_{k,z}; this implies 𝒩_{k,z} ≠ ∅, so z ∈ Ω_{k}. Besides,

∥X′_{0} − D∥ = ∥( \begin{matrix}0 & 0 \\ 0 & (zI_{n_{2}} − D) − (zI_{n_{2}} − X′_{0}) \end{matrix} )∥ =

∥( \begin{matrix}zI_{n_{1}} − A & −B \\ −C & zI_{n_{2}} − D \end{matrix} ) − ( \begin{matrix}zI_{n_{1}} − A & −B \\ −C & zI_{n_{2}} − X′_{0} \end{matrix} )∥ ≥

σ_{p_{k}(z)+1}(S_{1}(z, D)) = h_{k}(z);

therefore it implies ε ≥ h_{k}(z). Hence

⋃_{∥Y −D∥≤ε} S_{k}(G_{Y}) = {z ∈ Ω_{k} : h_{k}(z) ≤ ε}.

□

Structured pseudospectrum

Let G ∈ ℂ^{n×n} be the partitioned matrix

G = ( \begin{matrix}A & B \\ C & D \end{matrix} ) ,

with A ∈ ℂ^{n_{1}×n_{1}}, B ∈ ℂ^{n_{1}×n_{2}}, C ∈ ℂ^{n_{2}×n_{1}} and D ∈ ℂ^{n_{2}×n_{2}}. Here G is any matrix, and it is not necessary that i(G) < k.

Where are the eigenvalues of all matrices

G_{Y} := ( \begin{matrix}A & B \\ C & Y \end{matrix} )

such that Y ∈ ℂ^{n_{2}×n_{2}} is sufficiently close to D? This question is closely related with the problem treated in the first part of this Section 5. We would like to find out the geometric description of the set in the complex plane formed by the eigenvalues of all the matrices G_{Y} whose distance from G is less than or equal to a prefixed ε > 0. The same question, if it is permitted to perturb in all entries of the matrix G, has been studied in [16], [17], with the name of pseudospectrum of the matrix G of radius ε > 0:

⋃_{{G′∈ℂ^{n×n} \atop ∥G′−G∥≤ε}} σ(G′).

It was proved that

⋃_{{G′∈ℂ^{n×n} \atop ∥G′−G∥≤ε}} σ(G′) = \{z ∈ ℂ : σ_{n}(zI_{n} − G) ≤ ε\},

where σ_{n}(zI_{n} − G) is the minimum singular value of the matrix zI_{n} − G. For every λ ∈ ℂ , define

N_{1,λ} := \{Y ∈ ℂ^{n_{2}×n_{2}} : λ is an eigenvalue of ( \begin{matrix}A & B \\ C & Y \end{matrix} )\} .

and let Ω_{1} be the set {λ ∈ ℂ : N_{1,λ} ≠ ∅}. Given the matrices A, B and C, can it happen that for some λ ∈ ℂ the set N_{1,λ} be empty? The answer is affirmative as we can see that for all y ∈ ℂ

det ( \begin{matrix}λ − 1 & −2 \\ −3 & λ − y \end{matrix} ) = (λ − 1)(λ − y) − 6;

So if λ = 1, there is no y such that 1 be an eigenvalue of

( \begin{matrix}1 & 2 \\ 3 & y \end{matrix} ) .

In fact, in this example Ω_{1} = ℂ ∖ {1}. Calling for any λ ∈ Ω_{1}, ρ_{1}(λ) as in (2.4) and S_{1}(λ, D) as in (2.7), it is simple to see that Ω_{1} = {λ ∈ ℂ : ρ_{1}(λ) ≤ n−1}. We have always ℂ ∖ σ(A) ⊂ Ω_{1}, because for all λ ∈ ℂ ∖ σ(A) it follows ρ_{1}(λ) = n_{1} and n_{1} ≤ n − 1.

Now we define the set Ω^{(1)} := {λ ∈ ℂ : n_{1} ≤ ρ_{1}(λ) ≤ n − 1}. Obviously Ω^{(1)} ⊂ Ω_{1}, but the content can be strict. For example, given the matrix

G = (\begin{matrix}A & B \\ C & D \end{matrix}) = ( \begin{matrix}3 & 1 & −2 & 0 & 0 \\ 0 & 4 & 2 & 0 & 0 \\ 0 & 0 & 5 & 0 & 0 \\ 0 & 0 & 0 & 6 & −4 \\ 0 & 0 & 0 & 0 & 3 \end{matrix} ) ,

we have that 3 ∈ Ω_{1}, because 3 is an eigenvalue of ( \begin{matrix}A & B \\ C & D \end{matrix}); but ρ_{1}(3) = 2 ≱ 3, so 3 ∉ Ω^{(1)}.

For all λ ∈ Ω^{(1)}, we define p_{1}(λ) := n − 1 − ρ_{1}(λ) and the function

h_{1} : Ω^{(1)} → ℝ

by h_{1}(λ) := σ_{p_{1}(λ)+1}(S_{1}(λ, D)). It is easy to see that this has meaning given that for all λ ∈ Ω^{(1)}, 0 ≤ p_{1}(λ) ≤ n_{2} − 1. Moreover, λ ∈ σ(G) ∩ Ω^{(1)} if and only if h_{1}(λ) = 0. By an analogous way of the proof of Theorem 5.1 we can prove the following result.

Theorem 5.2 Let G ∈ ℂ^{n×n} be the partitioned matrix

G = ( \begin{matrix}A & B \\ C & D \end{matrix} ) ,

with A ∈ ℂ^{n_{1}×n_{1}}, B ∈ ℂ^{n_{1}×n_{2}}, C ∈ ℂ^{n_{2}×n_{1}} and D ∈ ℂ^{n_{2}×n_{2}}. And let ε > 0 be a real number. Then

⋃_{{Y ∈ℂ^{n_{2}×n_{2}} \atop ∥Y −D∥≤ε}} σ(G_{Y}) = \{z ∈ Ω^{(1)} : h_{1}(z) ≤ ε\} ∪ σ(G).

There is an alternative characterization of the restricted pseudospectrum of G of radius ε > 0

⋃_{{Y ∈ℂ^{n_{2}×n_{2}} \atop ∥Y −D∥≤ε}} σ(G_{Y}),

as

⋃_{{Y ∈ℂ^{n_{2}×n_{2}} \atop ∥Y −D∥≤ε}} σ(G_{Y}) = \{z ∈ ℂ ∖ σ(G) : σ_{n_{2}}(R(z)) ≤ ε\} ∪ σ(G),

where

R(z) := [(0, I_{n_{2}}) (zI_{n} − G)^{−1} ( \begin{matrix}0 \\ I_{n_{2}} \end{matrix} )]^{†}

is the Moore-Penrose inverse of a transfer matrix. See [8, Proposition 2.3, p. 128].

Conclusions

In [18] it was reformulated a result of [4] that gives in a precise manner how to find the nearest matrix ( \begin{matrix}A & B \\ C & Y \end{matrix}) that lowers the rank of the matrix ( \begin{matrix}A & B \\ C & D \end{matrix}), by means of ordinary singular values of a matrix related with A, B, C and D through the Moore-Penrose inverse. Given that many important features of the Jordan canonical form of a matrix (in particular, the geometric multiplicity of its eigenvalues) can be formulated in terms of ranks of certain matrices, we have been able to obtain a solution to related nearness matrix problems from this theorem.

We have obtained the nearest matrix ( \begin{matrix}A & B \\ C & Y \end{matrix}), i ( \begin{matrix}A & B \\ C & Y \end{matrix}) ≥ k, to the matrix ( \begin{matrix}A & B \\ C & D \end{matrix}) such that i ( \begin{matrix}A & B \\ C & D \end{matrix}) < k, if we perturb only in D. Also, we have established the relation of this last problem with the question of where are the k-derogatory eigenvalues of matrices ( \begin{matrix}A & B \\ C & Y \end{matrix}) with Y adequately close to D.

References

[1] H. Baumgärtel: Analytic Perturbation Theory for Matrices and Operators. Birkhäuser, 1985. 17

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

[3] S.L. Campbell, C.D. Meyer: Generalized Inverses of Linear Transformations. Pitman, London, 1979. 3, 10

[4] J.W. Demmel: The smallest perturbation of a submatrix which lowers the rank and constrained total least squares problems. SIAM J. Numer. Anal. 24,(1) (1987) 199–206. 3, 24

[5] J. Dieudonné: Fondements de l’Analyse Moderne. Gauthier-Villars, Paris, 1966. 18

[6] I. Gohberg, P. Lancaster, L. Rodman: Invariant Subspaces of Matrices with Applications. Wiley, 1986. 13

[7] J.M. Gracia, I. de Hoyos, F.E. Velasco: Safety neighbourhoods for the invariants of the matrix similarity. Linear Multilinear Algebra 46, (1999) 25–49. 2, 16

[8] D. Hinrichsen, B. Kelb: Spectral value sets: a graphical tool for robustness analysis. Systems and Control Letters 21, (1993) 127–136. 24

[9] R. A. Horn, C. R. Johnson: Topics in Matrix Analysis. Cambridge University Press, 1991. 15

[10] V. Ionescu, C. Oară, M. Weiss: Generalized Riccati Theory and Robust Control. A Popov Function Approach. Wiley, 1999. 13

[11] T. Kato: A Short Introduction to Perturbation Theory for Linear Operators. Springer, 1982. 17

[12] P. Lancaster, M. Tismenetsky: The Theory of Matrices with Applications. Academic Press, 1985. 13, 17

[13] G. Marsaglia and G. P. H. Styan: Equalities and inequalities for ranks of matrices. Linear Multilinear Algebra 2, (1974) 269–292. 3, 10 [14] J. F. Queiró and E. Marques de Sá: Singular values and invariant factors of

matrix sums and products. Linear Algebra Appl. 225, (1995) 43–56. 12

[15] F. C. Silva: On the number of invariant factors of partially prescribed matrices and control theory. Linear Algebra Appl. 311, (2000) 1–12. 5, 10

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

[17] L.N. Trefethen: Pseudospectra of linear operators. SIAM Rev. 39, (3) (1997) 383–406. 4, 23

[18] M. Wei: Perturbation theory for the Eckart-Young-Mirsky theorem and the constrained total least squares problem. Linear Algebra Appl. 280, (1998) 267–287. 3, 24