# On characteristic invariants of matrix pencils and linear relations

H. Gernandt Institut für Mathematik, Sekretariat MA 4–5, Technische
Universität Berlin, Straße des 17. Juni 136, D-10623 Berlin, Germany,
(gernandt@math.tu-berlin.de). F. Martínez Pería  Centro de Matemática de La
Plata – Facultad de Ciencias Exactas, Universidad Nacional de La Plata, C.C.
172, (1900) La Plata, and Instituto Argentino de Matemática “Alberto P.
Calderón” (CONICET), Saavedra 15 (1083) Buenos Aires, Argentina
(francisco@mate.unlp.edu.ar). F. Philipp Institute for Mathematics, Technische
Universität Ilmenau, Postfach 10 05 65, D-98684 Ilmenau, Germany
<EMAIL_ADDRESS>and carsten.trunk@tu-ilmenau.de). C. Trunk‡

###### Abstract

The relationship between linear relations and matrix pencils is investigated.
Given a linear relation, we introduce its Weyr characteristic. If the linear
relation is the range (or the kernel) representation of a given matrix pencil,
we show that there is a correspondence between this characteristic and the
Kronecker canonical form of the pencil. This relationship is exploited to
obtain estimations on the invariant characteristics of matrix pencils under
rank one perturbations.

##  1 Introduction

Canonical forms for square matrices like the Jordan normal form are a
fundamental tool in matrix analysis and uniquely describe the matrix up to
similarity transformations: Two matrices are similar if their Jordan normal
forms coincide. This is the case if and only if they share the same
eigenvalues and in these eigenvalues the Segre or the Weyr characteristic
coincide. These two characteristics count the Jordan chains at an eigenvalue
in two different ways.

The Weyr characteristic (for a given eigenvalue $\lambda$) is a finite, non-
increasing sequence $w$ of natural numbers, the first entry of $w$ corresponds
to the dimension of the kernel $N(A-\lambda)$ of $A-\lambda$, the second to
the dimension of the quotient space $N(A-\lambda)^{2}/N(A-\lambda)$, etc. The
Segre characteristic is the conjugate partition of the Weyr characteristic; it
counts the dimensions of the Jordan blocks corresponding to the eigenvalue
$\lambda$ or, what is the same, it counts the length of the corresponding
Jordan chains [30, 31, 34, 35].

Weyr and Segre characteristics exist also for matrix pencils. Recall that
matrix pencils allow a normal form: the Kronecker canonical form, see Appendix
A. Instead of one Segre characteristic as above, four different types of
indices appear: the finite and the infinite elementary divisors, the row
minimal indices and the column minimal indices. These indices measure the
sizes of the different blocks in the Kronecker canonical form. Moreover, two
matrix pencils are strictly equivalent if and only if all the four indices
coincide, see [22], or e.g. [12, 13]. Thus they can be considered as Segre-
type indices for matrix pencils. As in the case of matrices, where the Segre
and the Weyr characteristics are conjugate partitions, we define here the Weyr
characteristic of a matrix pencil as the conjugate partition of the four
Segre-type indices, see Section 4. We cite [17] and [26] where the terms Segre
and Weyr characteristics were used for (regular) matrix pencils.

Parallel to the Weyr characteristic of matrix pencils, we introduce the Weyr
characteristic of subspaces in the cartesian product
$\mathbb{C}^{m}\times\mathbb{C}^{m}$ in Section 3. These subspaces are usually
called linear relations in $\mathbb{C}^{m}$ [1, 16]. Different from the matrix
situation, it is well-known that linear relations contain not only Jordan
chains but also _chains at the eigenvalue $\infty$, singular chains,_ and
_multi-shifts_ , see [9, 10, 14, 32, 33]. A recent result states that every
linear relation in a finite dimensional space allows a direct sum
decomposition into four parts which are related to the above chains [10]. We
use this decomposition and define in Section 3 the Weyr characteristic of a
linear relation. As in the case of matrices and matrix pencils, it turns out
that the so defined Weyr characteristic is a set of invariants of a linear
relation in the following sense (cf. Section 5): Given two linear relations in
$\mathbb{C}^{m}$, their Weyr characteristics coincide if and only if the
linear relations are strictly equivalent. Concerning this notion, we refer to
Section 2.

The main goal of this paper is to reveal the connection between the Weyr
characteristic of matrix pencils and the Weyr characteristic of linear
relations. The connection is established by the kernel and range
representations of a matrix pencil, see also [14, 29]. In order to introduce
those representations, we consider a matrix pencil of the form

$sE-F,\quad\mbox{with}\quad E,F\in\mathbb{C}^{n\times m}$

If $E$ is non-singular, multiplication of the pencil from the left and the
right with the inverse of $E$ leads to the pencils

$sI-E^{-1}F\qquad\mbox{and}\qquad sI-FE^{-1},$

which shows that the spectrum of the original pencil coincides with those of
the matrices $E^{-1}F$ and $FE^{-1}$. However, in general the matrix $E$ is
singular. But its graph is a linear relation, and the inverse of a linear
relation always exists. Hence, we consider the linear relations

$E^{-1}F=\left\\{(x,y)\in\mathbb{C}^{m}\times\mathbb{C}^{m}:Fx=Ey\right\\}\quad\mbox{and}\quad
FE^{-1}=\left\\{(Ex,Fx):x\in\mathbb{C}^{m}\right\\},$

which were already studied in [7, 8]. We call $E^{-1}F$ the kernel and
$FE^{-1}$ the range representation (see also [14]) as we have

$E^{-1}F=N[F,-E]\qquad\mbox{ and }\qquad FE^{-1}=R\begin{bmatrix}E\\\
F\end{bmatrix}.$

It is natural to compare the Weyr characteristic of a matrix pencil and the
Weyr characteristic of the corresponding kernel and range representations. For
a given matrix pencil $sE-F$ with nontrivial row minimal indices and/or column
minimal indices a certain peculiarity happens: depending on the representation
(either $E^{-1}F$ or $FE^{-1}$) only the row minimal indices and/or column
minimal indices which are large enough are visible in the linear relation. We
provide two examples for this in Section 4. Nevertheless, we show how to
calculate the Weyr characteristic of the corresponding kernel and range
representations from the Kronecker canonical form of a given matrix pencil.

Also, considering the sizes of the matrices $E$ and $F$, it is possible to
recover the Weyr characteristic of the matrix pencil $sE-F$ from the Weyr
characteristic of its kernel or its range representation, see Sections 5 and
6. Hence, one can associate a linear object (the kernel or the range
representation) to a matrix pencil. This is extremely helpful, for instance,
in perturbation theory or stability, see e.g. [11, 23]. As a consequence, new
perturbation results for the Kronecker form of matrix pencils under rank one
perturbations can be derived from perturbation results for the Weyr
characteristic of linear relations given in [29]. These results can then be
used to describe the controllability indices of the associated descriptor
systems, see [15]. In Section 7 below we give an application to the rank one
perturbation theory for matrix pencils where both (kernel and range)
representations are used.

##  2 Linear relations in $\mathbb{C}^{m}$

Throughout this paper elements (pairs) from
$\mathbb{C}^{m}\times\mathbb{C}^{m}$ will be denoted by $(x,y)$, where
$x,y\in\mathbb{C}^{m}$. A linear relation in $\mathbb{C}^{m}$ is a linear
subspace of $\mathbb{C}^{m}\times\mathbb{C}^{m}$. A matrix
$A\in\mathbb{C}^{m\times m}$ can be identified with a linear relation in
$\mathbb{C}^{m}$ via its graph:

$\displaystyle\Gamma(A):=\left\\{(x,Ax):\ x\in\mathbb{C}^{m}\right\\}.$

For the basic notions and properties of linear relations we refer to [1, 20],
and for the more advanced notions see [9, 32, 33]. Here, we denote the domain
and the range of a linear relation $S$ in $X$ by ${\rm dom\,}S$ and $R(S)$,
respectively,

$\displaystyle{\rm dom\,}S$ $\displaystyle=\left\\{x\in\mathbb{C}^{m}\ :\
(x,y)\in S\ \text{for some $y\in\mathbb{C}^{m}$}\right\\}\quad\mbox{and}$
$\displaystyle R(S)$ $\displaystyle=\left\\{y\in\mathbb{C}^{m}\ :\ (x,y)\in S\
\text{for some $x\in\mathbb{C}^{m}$}\right\\}.$

Furthermore, $N(S)$ and $\operatorname{mul}(S)$ denote the kernel and the
multivalued part of $S$,

$\displaystyle N(S)=\left\\{x\in\mathbb{C}^{m}\;:\;(x,0)\in
S\right\\}\quad\mbox{and}\quad\operatorname{mul}(S)=\left\\{y\in\mathbb{C}^{m}\;:\;(0,y)\in
S\right\\}.$

Obviously, a linear relation $S$ is the graph of a matrix if and only if
$\operatorname{mul}(S)=\\{0\\}$.

Given a linear relation $S$ and $\lambda\in\mathbb{C}$, one defines $\lambda
S=\left\\{(x,\lambda y)\ :\ (x,y)\in S\right\\}$. For relations $S_{1}$ and
$S_{2}$ in $\mathbb{C}^{m}$ the operator-like sum $S_{1}+S_{2}$ is the
relation defined by

$\displaystyle S_{1}+S_{2}=\left\\{(x,y+z)\ :\ (x,y)\in S_{1},\ (x,z)\in
S_{2}\right\\}.$

If $S_{1}\cap S_{2}=\\{0\\}$ then the _direct sum_ is given by

$\displaystyle S_{1}\oplus S_{2}:=\\{(x_{1}+x_{2},y_{1}+y_{2})\ :\
(x_{i},y_{i})\in S_{i},\;i=1,2\\}.$

The product of the linear relations $S_{1}$ and $S_{2}$ in $\mathbb{C}^{m}$ is
the linear relation in $\mathbb{C}^{m}$ defined by

$S_{1}S_{2}=\left\\{(x,z)\ :\ (y,z)\in S_{1}\mbox{ and }(x,y)\in S_{2}\;\mbox{
for some }y\in\mathbb{C}^{m}\right\\}$

As for matrices, the sum and product of linear relations are associative
operations.

The inverse $S^{-1}$ of a linear relation $S$ in $\mathbb{C}^{m}$ always
exists, and it is the linear relation in $\mathbb{C}^{m}$ given by

$S^{-1}=\left\\{(y,x)\ :\ (x,y)\in S\right\\}.$

In the following, if $M$ is a matrix in $\mathbb{C}^{m\times m}$ and $S$ is a
linear relation in $\mathbb{C}^{m}$, we denote by
$\left[\begin{smallmatrix}M&0\\\ 0&M\end{smallmatrix}\right]\cdot S$ the
action of $M$ onto $S$:

$\displaystyle\begin{bmatrix}M&0\\\ 0&M\end{bmatrix}\cdot
S:=\\{(Mx,My)\in\mathbb{C}^{m}\times\mathbb{C}^{m}:(x,y)\in S\\}.$

Given two linear relations $S_{1}$ and $S_{2}$ in $\mathbb{C}^{m}$ we say that
they are _strictly equivalent_ if there exists an invertible matrix
$T\in\mathbb{C}^{m\times m}$ such that

$\displaystyle S_{2}=\begin{bmatrix}T&0\\\ 0&T\end{bmatrix}\cdot S_{1}.$ (1)

If one identifies the matrices $T$ and $T^{-1}$ with their graphs, (1) can be
written in the sense of linear relations in the following form

$\displaystyle S_{2}=TS_{1}T^{-1}.$

The notions of eigenvalue, root manifolds and point spectrum also apply to
linear relations. Given $\lambda\in\mathbb{C}$, $S-\lambda$ stands for the
linear relation $S-\lambda I$:

$\displaystyle S-\lambda=\left\\{(x,y-\lambda x)\ :\ (x,y)\in S\right\\}.$

Then, $\lambda\in\mathbb{C}$ is an _eigenvalue of $S$_ if
$N(S-\lambda)\neq\\{0\\}$. On the other hand, we say that $S$ has an
_eigenvalue at_ $\infty$ if $\operatorname{mul}(S)\neq\\{0\\}$. The point
spectrum of $S$ is the set $\sigma_{p}(S)$ consisting of the eigenvalues
$\lambda\in\mathbb{C}\cup\\{\infty\\}$ of $S$.

We denote $S^{0}:=I$, where $I$ denotes the identity relation (i.e. the graph
of the identity matrix in $\mathbb{C}^{m}$). For $k=1,2,\ldots$ the $k$-th
power of $S$ is defined recursively by

$S^{k}:=S\cdot S^{k-1}.$

Thus, we have $(x_{k},x_{0})\in S^{k}$ if and only if there exist
$x_{1},\ldots,x_{k-1}\in\mathbb{C}^{m}$ such that

$(x_{k},x_{k-1}),(x_{k-1},x_{k-2}),\ldots,(x_{1},x_{0})\in S.$ (2)

In what follows we show that any linear relation $S$ in a finite-dimensional
space admits a decomposition into four different parts. To do so, we have to
introduce some subspaces of $\mathbb{C}^{m}$ and subrelations of $S$. We start
with the following notions: A sequence of pairs in $S$ such as in (2) is
called a chain in $S$. The chain is called singular, if $x_{k}=x_{0}=0$. The
root manifolds $\mathcal{R}_{\lambda}(S)$ and $\mathcal{R}_{\infty}(S)$ are
given by

$\displaystyle\mathcal{R}_{\lambda}(S):=\bigcup_{k\in\mathbb{N}}N(S-\lambda)^{k}\quad\text{and}\quad\mathcal{R}_{\infty}(S):=\bigcup_{k\in\mathbb{N}}\operatorname{mul}S^{k},$

respectively. Note that $\mathcal{R}_{\lambda}(S)=\mathcal{R}_{0}(S-\lambda)$
and $\mathcal{R}_{\infty}(S)=\mathcal{R}_{\infty}(S-\lambda)$ for all
$\lambda\in\mathbb{C}$. If $\lambda\in\mathbb{C}$ and $x\in N(S-\lambda)^{l}$,
then there exist vectors $x_{1},\ldots,x_{l-1}\in\mathbb{C}^{m}$ with

$(x,x_{l-1}),(x_{l-1},x_{l-2}),\ldots,(x_{1},0)\in S-\lambda.$ (3)

A chain in $S-\lambda$ as in (3) is called a _Jordan chain of $S$ at
$\lambda$_. A chain of the form

$(0,x_{1}),(x_{1},x_{2}),\ldots,(x_{l-1},x_{l})\in S$

is called a _Jordan chain of $S$ at $\infty$_. Note that a singular chain is
always a Jordan chain at both zero and $\infty$. The notion of singular chains
will be used for a finer analysis of the root manifolds. For this, the
_singular chains subspace_ associated to $S$ is defined by

$\mathcal{R}_{\rm c}(S):=\mathcal{R}_{0}(S)\cap\mathcal{R}_{\infty}(S).$

The following lemma is from [9].

######  Lemma 2.1.

Let $S$ be a linear relation in a vector space $X$. Consider a singular chain
of the form

$(0,x_{s}),(x_{s},x_{s-1}),\dots,(x_{2},x_{1}),(x_{1},0)\in S.$

Then, for every $\lambda\in\mathbb{C}$, the vectors defined by

$z_{j}:=\sum_{i=1}^{j}\begin{pmatrix}s-i\\\
j-i\end{pmatrix}\lambda^{j-i}x_{i},\quad j=1,\ldots,s,$ (4)

satisfy

$(0,z_{s}),(z_{s},z_{s-1}),\ldots,(z_{2},z_{1}),(z_{1},0)\in S-\lambda.$

This implies that, for every $\lambda\in\mathbb{C}\cup\\{\infty\\}$,

$\mathcal{R}_{\rm c}(S)\subset\mathcal{R}_{\lambda}(S).$

Moreover, for $\lambda,\mu\in\mathbb{C}\cup\\{\infty\\}$ with
$\lambda\neq\mu$, in [9] it is shown that

$\mathcal{R}_{\rm c}(S)=\mathcal{R}_{\lambda}(S)\cap\mathcal{R}_{\mu}(S).$ (5)

Obviously, if $\mathcal{R}_{\rm c}(S)\neq\\{0\\}$ then
$\sigma_{p}(S)=\mathbb{C}\cup\\{\infty\\}$. Otherwise, if $\mathcal{R}_{\rm
c}(S)=\\{0\\}$, then the number of different eigenvalues in $\sigma_{p}(S)$ is
bounded by the space dimension $m$, cf. [32, Proposition 3.2 and Theorem 4.6].
Hence, it is natural to call an eigenvalue $\lambda\in\sigma_{p}(S)$
degenerate if $\mathcal{R}_{\lambda}(S)\subset\mathcal{R}_{\rm c}(S)$ and
proper otherwise. A linear relation $S$ is called _completely singular_ if
$S\subseteq\mathcal{R}_{c}(S)\times\mathcal{R}_{c}(S)$. If $S$ is not
completely singular,

$\displaystyle S_{\rm
sing}:=S\cap(\mathcal{R}_{c}(S)\times\mathcal{R}_{c}(S)),$

denotes the _completely singular part of $S$_.

Finally, there may exist a part of $S$ which has no Jordan chains at all, e.g.

$S:=\text{span}\\{(x_{1},x_{2}),(x_{2},x_{3}),\ldots,(x_{l-1},x_{l})\\},$

where $x_{1},\ldots,x_{l}$ are linear independent vectors in $\mathbb{C}^{m}$.
Then this linear relation has empty spectrum. A linear relation with empty
spectrum is called a _multi-shift_.

In the following we present a decomposition result for linear relations in
finite dimensional spaces, see [9]. To do so, we need the notion of a reducing
sum decomposition, cf. [10].

######  Definition 2.2.

Let $S$ be a linear relation in a vector space $X$. Assume that

$X=D_{1}\oplus D_{2}\oplus\cdots\oplus D_{n}$

and

$S=S_{1}\oplus S_{2}\oplus\cdots\oplus S_{n},$ (6)

where $S_{j}$ is a linear relation in $D_{j}$ for $j=1,\ldots,n$. Then the
decomposition (6) is called a _reducing sum decomposition of $S$ with respect
to $(D_{1},\ldots,D_{n})$_.

The following result is taken from [33, Lemma 8.1].

######  Lemma 2.3.

Let $S$ be a linear relation in $\mathbb{C}^{m}$ and assume that $S$ has a
reducing sum decomposition with respect to $(D_{1},\ldots,D_{n})$ as in
Definition 2.2. Let $k\in\mathbb{N}$, then

$S^{k}=S_{1}^{k}\oplus S_{2}^{k}\oplus\cdots\oplus S_{n}^{k},\quad$

is a reducing sum decomposition of $S^{k}$ with respect to
$(D_{1},\ldots,D_{n})$.

Let $S$ be a linear relation in $\mathbb{C}^{m}$ and assume that $S$ has a
reducing sum decomposition $S=S_{1}\oplus S_{2}$ with respect to
$\mathbb{C}^{m}=D_{1}\oplus D_{2}$. First of all, let us show that

$N(S)=N(S_{1})\oplus N(S_{2}).$ (7)

Obviously, $N(S_{1})+N(S_{2})\subset N(S)$. On the other hand, if $x\in
N(S_{1})\cap N(S_{2})$ then $(x,0)\in S_{1}$ and $(x,0)\in S_{2}$. As
$S=S_{1}\oplus S_{2}$ is a direct sum, $x=0$ follows and the sum of the
nullspaces is a direct sum.

Also, if $x\in N(S)$ then there exist $y_{1}\in D_{1}$ and $y_{2}\in D_{2}$
such that $(x,0)=(x_{1},y_{1})+(x_{2},y_{2})$ with $(x_{1},y_{1})\in S_{1}$
and $(x_{2},y_{2})\in S_{2}$. As $S_{1}\oplus S_{2}$ is a reduced sum
decomposition, $y_{1}=y_{2}=0$ and the proof is completed.

By Lemma 2.3 it is immediate that

$N(S^{k})=N(S_{1}^{k})\oplus
N(S_{2}^{k})\qquad\text{and}\qquad\mathcal{R}_{0}(S)=\mathcal{R}_{0}(S_{1})\oplus\mathcal{R}_{0}(S_{2}).$
(8)

Given $\lambda\in\mathbb{C}$, replacing the linear relations $S,S_{1}$, and
$S_{2}$ by $S-\lambda,S_{1}-\lambda$, and $S_{2}-\lambda$, respectively, we
conclude

$N((S-\lambda)^{k})=N((S_{1}-\lambda)^{k})\oplus N((S_{2}-\lambda)^{k})\mbox{
and
}\mathcal{R}_{\lambda}(S)=\mathcal{R}_{\lambda}(S_{1})\oplus\mathcal{R}_{\lambda}(S_{2}).$
(9)

Moreover, if $\mu\in\mathbb{C}$, $\mu\neq\lambda$, by (5) we have

$\displaystyle\mathcal{R}_{\rm c}(S)$
$\displaystyle=\mathcal{R}_{\lambda}(S)\cap\mathcal{R}_{\mu}(S)=\left(\mathcal{R}_{\lambda}(S_{1})\oplus\mathcal{R}_{\lambda}(S_{2})\right)\cap\left(\mathcal{R}_{\mu}(S_{1})\oplus\mathcal{R}_{\mu}(S_{2})\right)$
(10)
$\displaystyle=\left(\mathcal{R}_{\lambda}(S_{1})\cap\mathcal{R}_{\mu}(S_{1})\right)\oplus\left(\mathcal{R}_{\lambda}(S_{2})\cap\mathcal{R}_{\mu}(S_{2})\right)=\mathcal{R}_{\rm
c}(S_{1})\oplus\mathcal{R}_{\rm c}(S_{2}).$

In a similar way, replacing $S,S_{1}$, and $S_{2}$ by their inverses we obtain

$\operatorname{mul}(S^{k})=\operatorname{mul}(S_{1}^{k})\oplus\operatorname{mul}(S_{2}^{k}).$
(11)

Finally, notice that it is possible to show that

$R(S^{k})=R(S_{1}^{k})\oplus R(S_{2}^{k}).$ (12)

If $S$ has a reducing sum decomposition as in (6) then decompositions similar
to those presented in (7)-(12) follow by induction.

Given a proper eigenvalue $\lambda\in\mathbb{C}$ of $S$, consider the
subrelation

$S\cap\left(\mathcal{R}_{\lambda}(S)\times\mathcal{R}_{\lambda}(S)\right).$

Since $S_{\rm sing}$ is contained in it and
$\mathcal{R}_{c}(S)\subset\mathcal{R}_{\lambda}(S)$, it is possible to find a
subspace $D_{\lambda}$ such that $\mathcal{R}_{\lambda}(S)=\mathcal{R}_{\rm
c}(S)\oplus D_{\lambda}$ and a linear operator
$J_{\lambda}:D_{\lambda}\rightarrow D_{\lambda}$ with
$\sigma_{p}(J_{\lambda})=\\{\lambda\\}$ such that

$S\cap\left(\mathcal{R}_{\lambda}(S)\times\mathcal{R}_{\lambda}(S)\right)=S_{\rm
sing}\oplus J_{\lambda},$ (13)

is a reducing sum decomposition with respect to $(\mathcal{R}_{\rm
c}(S),D_{\lambda})$, see [10]. If $\infty$ is a proper eigenvalue of $S$ then
$J_{\infty}$ stands for a linear relation with
$\sigma_{p}(J_{\infty})=\\{\infty\\}$, which is the inverse (of the graph) of
a linear operator on a subspace $D_{\infty}$ such that
$\mathcal{R}_{\infty}(S)=\mathcal{R}_{\rm c}(S)\oplus D_{\infty}$ and

$S\cap\left(\mathcal{R}_{\infty}(S)\times\mathcal{R}_{\infty}(S)\right)=S_{\rm
sing}\oplus J_{\infty}$ (14)

is a reducing sum decomposition with respect to $(\mathcal{R}_{\rm
c}(S),D_{\infty})$.

######  Theorem 2.4.

Let $S$ be a linear relation in $\mathbb{C}^{m}$ with proper point spectrum
$\\{\lambda_{1},\ldots,\lambda_{l}\\}\subset\mathbb{C}\cup\\{\infty\\}$. Then,
there exist subspaces $D_{\lambda_{1}},\ldots,D_{\lambda_{l}},D_{M}$ such that
$\mathbb{C}^{m}=\mathcal{R}_{c}(S)\oplus D_{\lambda_{1}}\oplus\ldots\oplus
D_{\lambda_{l}}\oplus D_{M}$ and linear relations $S_{\rm
sing},J_{\lambda_{1}},\ldots,J_{\lambda_{l}},S_{M}$ as in (13) and (14) such
that

$S=S_{\rm sing}\oplus J_{\lambda_{1}}\oplus\cdots\oplus J_{\lambda_{l}}\oplus
S_{M}$ (15)

is a reduced sum decomposition of $S$ with respect to

$\left(\mathcal{R}_{c}(S),D_{\lambda_{1}},\ldots,D_{\lambda_{l}},D_{M}\right).$

The linear relation $S_{\rm sing}=S\cap\left(\mathcal{R}_{\rm
c}(S)\times\mathcal{R}_{\rm c}(S)\right)$ is completely singular and $S_{M}$
is a multishift. For $1\leq j\leq l$ the linear relation $J_{\lambda_{j}}$
satisfies $\sigma_{p}(J_{j})=\lambda_{j}$ and

$S\cap\left(\mathcal{R}_{\lambda_{j}}(S)\times\mathcal{R}_{\lambda_{j}}(S)\right)=S_{\rm
sing}\oplus J_{\lambda_{j}}$ (16)

is a reducing sum decomposition with respect to $(\mathcal{R}_{\rm
c}(S),D_{\lambda_{j}})$.

##  3 Weyr characteristic of a linear relation in $\mathbb{C}^{m}$

As it was mentioned in the introduction, the Weyr characteristic of a linear
operator $S$ acting on $\mathbb{C}^{m}$ is a complete set of invariants which
determines the Jordan normal form of $S$. The aim of this section is to
introduce a complete set of invariants for a linear relation and to show that
this is an analogue of the Weyr characteristic of a linear operator.

Let $S$ be a linear relation in $\mathbb{C}^{m}$ and assume that it is
decomposed as in (15). We introduce the Weyr characteristic for a linear
relation according to four different parts of it. We distinguish between (a)
the singular part of $S$, (b) each finite proper eigenvalue, and (c) the
possible proper eigenvalue $\infty$. The fourth kind corresponds to the part
of $S$ which has no eigenvalues.

######  Definition 3.1.

Given a linear relation $S$ in $\mathbb{C}^{m}$, let
$\lambda_{1},\ldots,\lambda_{l}$ be its different proper eigenvalues and
assume that (15) holds.

  1. 1.

The _Weyr characteristic corresponding to a proper eigenvalue_
$\lambda_{j}\in\mathbb{C}$ of $S$ is given by the sequence
$W(\lambda_{j}):=(W_{k}(\lambda_{j}))_{k\geq 1}$, where

$\displaystyle
W_{k}(\lambda_{j}):=\dim\frac{N((S-\lambda_{j})^{k})+\mathcal{R}_{\rm
c}(S)}{N((S-\lambda_{j})^{k-1})+\mathcal{R}_{\rm c}(S)}.$

  2. 2.

If $\infty$ is a proper eigenvalue of $S$ then the _Weyr characteristic
corresponding to_ $\infty$ is given by the sequence $A:=(A_{k})_{k\geq 1}$,
where

$\displaystyle A_{k}:=\dim\frac{\operatorname{mul}(S^{k})+\mathcal{R}_{\rm
c}(S)}{\operatorname{mul}(S^{k-1})+\mathcal{R}_{\rm c}(S)}.$

  3. 3.

If $S_{\rm sing}\neq\\{0\\}$ then the _Weyr characteristic corresponding to
the singular chains subspace_ is defined by the sequence $B:=(B_{k})_{k\geq
1}$, where

$\displaystyle B_{k}:=\dim\frac{N(S^{k})\cap\mathcal{R}_{\rm
c}(S)}{N(S^{k-1})\cap\mathcal{R}_{\rm c}(S)}.$

  4. 4.

If $S_{M}\neq\\{0\\}$ then the _Weyr characteristic corresponding to the
multi-shifts_ is given by the sequence $C:=(C_{k})_{k\geq 1}$, where

$\displaystyle C_{1}:=\dim\frac{R(S)+{\rm
dom\,}S}{R(S)+\mathcal{R}_{0}(S)}\quad\text{and}\quad
C_{k}:=\dim\frac{R(S^{k-1})+\mathcal{R}_{0}(S)}{R(S^{k})+\mathcal{R}_{0}(S)},\
k\geq 2.$

Each of the sequences $W(\lambda_{j})$, $A$, $B$, and $C$ is non-increasing
[10]. Since the underlying space is finite-dimensional each of the Weyr
characteristic sequences contains only a finite number of non-zero terms. In
what follows, we shall treat them as finite sequences and omit the zero
entries. Also, we collect the Weyr characteristics corresponding to the
different finite proper eigenvalues in a single sequence: if these are
$\lambda_{1},\ldots,\lambda_{l}$, we set

$W:=(W(\lambda_{1}),W(\lambda_{2}),\ldots,W(\lambda_{l})).$

######  Definition 3.2.

The collection of finite sequences

$\big{(}W,A,B,C\big{)}$ (17)

is called the _Weyr characteristic_ of the linear relation $S$. If it
necessary to refer to the underlying linear relation we also write
$\big{(}W(S),A(S),B(S),C(S)\big{)}$. Moreover, in the same manner, we write
then $W(S)=(W_{S}(\lambda_{1}),W_{S}(\lambda_{2}),\ldots,W_{S}(\lambda_{l}))$
and $W_{S}(\lambda_{j})=(W_{k}(S,\lambda_{j}))_{k\geq 1}$,
$A(S)=(A_{k}(S))_{k\geq 1}$, $B(S)=(B_{k}(S))_{k\geq 1}$, and
$C(S)=(C_{k}(S))_{k\geq 1}$.

Next, we explain the quantities measured by $W(\lambda_{j})$, $A$, $B$, and
$C$. Let us start with $B$. Since $S$ is a linear relation in a finite
dimensional space, there exists $k_{0}\in\mathbb{N}$ such that
$\mathcal{R}_{0}(S)=N(S^{k_{0}})$. If $[x]\neq 0$ belongs to
$\frac{N(S^{k_{0}})\cap\mathcal{R}_{\rm
c}(S)}{N(S^{k_{0}-1})\cap\mathcal{R}_{\rm c}(S)}$, then there exist
$y_{1},\ldots,y_{k_{0}-1}\in\mathbb{C}^{m}$ such that

$\displaystyle(x,y_{1}),(y_{1},y_{2}),\ldots,(y_{k_{0}-1},0)\in S.$

We have $x\in\mathcal{R}_{\rm c}(S)$ and the chain
$(x,y_{1}),(y_{1},y_{2}),\ldots,(y_{k_{0}-1},0)$ is a Jordan chain (at 0) of
length $k_{0}$. Moreover, the vectors $x,y_{1},\ldots,y_{k_{0}-1}$ are
linearly independent. Hence, $B_{k_{0}}$ is the number of linearly independent
Jordan chains (at 0) of length $k_{0}$ in $S$ that can be extended to a
singular chain. Following this reasoning, it is easy to see that for each $k$,
$1\leq k\leq k_{0}$, $B_{k}$ represents the number of linearly independent
Jordan chains (at 0) of length at least $k$ that can be extended to a singular
chain.

From the definition of $S_{\rm sing}$ we have that $(S^{-1})_{\rm
sing}=(S_{\rm sing})^{-1}$, which implies the following lemma.

######  Lemma 3.3.

Let $S$ be a linear relation in $\mathbb{C}^{m}$. Then, for each $k\geq 1$,

$B_{k}(S)=B_{k}(S^{-1}).$

To continue with the meaning of $W(\lambda_{j})$ for a complex eigenvalue
$\lambda_{j}$ of $S$ we show that, for each $k\in\mathbb{N}$, the sum
$W_{k}(\lambda_{j})+B_{k}$ equals the dimension of
$\frac{N((S-\lambda_{j})^{k})}{N((S-\lambda_{j})^{k-1})}$. Actually, this is
true not only for $\lambda_{j}$ but for any complex number $\lambda$.

######  Lemma 3.4.

Let $S$ be a linear relation in $\mathbb{C}^{m}$. For $k\geq 1$ and
$\lambda\in\mathbb{C}$,

$W_{k}(S,\lambda)+B_{k}(S)=\dim\frac{N((S-\lambda)^{k})}{N((S-\lambda)^{k-1})}.$

###### Proof.

First, assume that $x\in\mathbb{C}^{m}$ is such that $[x]\neq 0$ in
$\frac{N(S^{k})\cap\mathcal{R}_{\rm c}(S)}{N(S^{k-1})\cap\mathcal{R}_{\rm
c}(S)}$. Then there exist $x_{1},\ldots,x_{k-1}\in\mathbb{C}^{m}$ such that

$\displaystyle(x,x_{k-1}),(x_{k_{1}},x_{k-2}),\ldots,(x_{1},0)\in S.$

Also, since $x\in\mathcal{R}_{\rm c}(S)$, there exist $n\in\mathbb{N}$ and
$x_{k+1},\ldots,x_{k+n}\in\mathbb{C}^{m}$ such that

$\displaystyle(0,x_{k+n}),(x_{k+n},x_{k+n-1}),\ldots,(x_{k+1},x)\in S.$

Applying Lemma 2.1 to the chain $(0,x_{k+n})$, $(x_{k+n},x_{k+n-1})$, …,
$(x_{1},0)$ in $S$, we obtain a chain $(0,z_{k+n})$, $(z_{k+n},z_{k+n-1})$, …,
$(z_{1},0)$ in $S-\lambda$, where each $z_{j}$ is given by (4). In particular,
$z_{k}$ is a linear combination of $x$ and the vectors $x_{1},\ldots,x_{k-1}$.
Hence, $[z_{k}]\neq 0$ in $\frac{N((S-\lambda)^{k})\cap\mathcal{R}_{\rm
c}(S)}{N((S-\lambda)^{k-1})\cap\mathcal{R}_{\rm c}(S)}$.

A similar argument shows that if $[x^{1}],\ldots,[x^{l}]$ are linearly
independent in $\frac{N(S^{k})\cap\mathcal{R}_{\rm
c}(S)}{N(S^{k-1})\cap\mathcal{R}_{\rm c}(S)}$, then there exist linearly
independent classes $[z_{k}^{1}],\ldots,[z_{k}^{l}]$ in
$\frac{N((S-\lambda)^{k})\cap\mathcal{R}_{\rm
c}(S)}{N((S-\lambda)^{k-1})\cap\mathcal{R}_{\rm c}(S)}$. Thus, Lemma 2.1
implies that

$\dim\frac{N(S^{k})\cap\mathcal{R}_{\rm c}(S)}{N(S^{k-1})\cap\mathcal{R}_{\rm
c}(S)}=\dim\frac{N((S-\lambda)^{k})\cap\mathcal{R}_{\rm
c}(S)}{N((S-\lambda)^{k-1})\cap\mathcal{R}_{\rm c}(S)}.$

Therefore, the statement in the Lemma 3.4 is of the form

$\dim\frac{X+Z}{Y+Z}+\dim\frac{X\cap Z}{Y\cap Z}=\dim\frac{X}{Y},$ (18)

where $X:=N((S-\lambda)^{k})$, $Y:=N((S-\lambda)^{k-1})$, and
$Z:=\mathcal{R}_{\rm c}(S)$. But for arbitrary finite-dimensional subspaces
$X$, $Y$, $Z$ such that $Y\subseteq X$ it holds that

$\displaystyle\dim\frac{X+Z}{Y+Z}$ $\displaystyle=\dim(X+Z)-\dim(Y+Z)$
$\displaystyle=\dim X-\dim(X\cap Z)-\dim Y+\dim(Y\cap Z),$
$\displaystyle\dim\frac{X\cap Z}{Y\cap Z}$ $\displaystyle=\dim(X\cap
Z)-\dim(Y\cap Z),$

and summing up the above equations (18) follows.

As a consequence of Lemma 3.4, for each $k\geq 1$, $W_{k}(\lambda_{j})$
represents the number of linearly independent Jordan chains of $S$ at
$\lambda_{j}$ of length at least $k$ that cannot be extended into a singular
chain.

Since $\infty$ is an eigenvalue of $S$ if and only if $0$ is an eigenvalue of
the inverse relation $S^{-1}$, and $\operatorname{mul}(S)=N(S^{-1})$, the
above arguments also show that, for each $k\geq 1$, $A_{k}$ represents the
number of linearly independent Jordan chains of $S$ at $\infty$ of length at
least $k$ that cannot be extended into a singular chain. To make this precise,
we formulate another lemma.

######  Lemma 3.5.

Let $S$ be a linear relation in $\mathbb{C}^{m}$. Then, for each $k\geq 1$,

$A_{k}(S)+B_{k}(S)=\dim\frac{\operatorname{mul}(S^{k})}{\operatorname{mul}(S^{k-1})}.$

###### Proof.

This is an immediate consequence of Lemmas 3.3 and 3.4. Indeed, for every
$k\geq 1$, since $A_{k}(S)=W_{k}(S^{-1},0)$ and $B_{k}(S)=B_{k}(S^{-1})$ we
obtain that

$\displaystyle A_{k}(S)+B_{k}(S)$
$\displaystyle=W_{k}(S^{-1},0)+B_{k}(S^{-1})=\dim\frac{N((S^{-1})^{k})}{N((S^{-1})^{k-1})}$
$\displaystyle=\dim\frac{\operatorname{mul}(S^{k})}{\operatorname{mul}(S^{k-1})}.$

The meaning of $C$ is clearly explained in [10]. Given $k\geq 1$, $C_{k}$
stands for the number of linearly independent chains of the form

$(x_{1},x_{2}),(x_{2},x_{3}),\ldots,(x_{k},x_{k+1})$

that are contained in $S_{M}$ and are composed by linearly independent vectors
$x_{1},\ldots,x_{k+1}\in\mathbb{C}^{m}$. We say that such a chain is a _multi-
shift chain_ (_of length $k$_) in $S_{M}$. Therefore, $C_{k}$ represents the
number of linearly independent multi-shift chains of length $k$ in $S$ that
are not part of a Jordan chain of $S$ at $\lambda=0$.

The above considerations are made somehow more precise in Proposition 3.7
below. Before, we need to prove a somehow technical but very helpful lemma.
Given two multi-indices $a=(a_{1},\ldots,a_{k})\in\mathbb{N}^{k}$ and
$b=(b_{1},\ldots,b_{l})\in\mathbb{N}^{l}$ with $k\geq l$, we define $a+b$ as
the multi-index in $\mathbb{N}^{k}$ given by

$a+b:=(a_{1}+b_{1},\ldots,a_{l}+b_{l},b_{l+1},\ldots,b_{k}).$

Note that if $a$ and $b$ are non-increasing multi-indices, then so is $a+b$.

######  Lemma 3.6.

Let $S$ be a linear relation in $\mathbb{C}^{m}$ and assume that it has a
reduced sum decomposition $S=S_{1}\oplus S_{2}$ with respect to
$\mathbb{C}^{m}=D_{1}\oplus D_{2}$. Then,

$A(S)=A(S_{1})+A(S_{2}),\quad
B(S)=B(S_{1})+B(S_{2}),\quad\text{and\;\;}C(S)=C(S_{1})+C(S_{2}).$

If $\lambda$ is a proper eigenvalue of $S_{1}$ or $S_{2}$, we have

$W_{S}(\lambda)=W_{S_{1}}(\lambda)+W_{S_{2}}(\lambda).$ (19)

###### Proof.

Let $\lambda$ be a proper eigenvalue of $S_{1}$ or $S_{2}$. Then, using (9)
and (10) we obtain

$\displaystyle\frac{N((S-\lambda_{j})^{k})+\mathcal{R}_{\rm
c}(S)}{N((S-\lambda_{j})^{k-1})+\mathcal{R}_{\rm c}(S)}$
$\displaystyle=\frac{\left(N((S_{1}-\lambda_{j})^{k})+\mathcal{R}_{\rm
c}(S_{1})\right)\oplus\left(N((S_{2}-\lambda_{j})^{k})+\mathcal{R}_{\rm
c}(S_{2})\right)}{\left(N((S_{1}-\lambda_{j})^{k-1})+\mathcal{R}_{\rm
c}(S_{1})\right)\oplus\left(N((S_{2}-\lambda_{j})^{k-1})+\mathcal{R}_{\rm
c}(S_{2})\right)}$

which shows (19). The statement on $A(S)$ follows in the same way, using (9)
and (11). The same applies to $C(S)$, where one uses (12) and (8).

It remains to show the statement on $B(S)$. Using the same argument as above,
we have

$\displaystyle\dim\frac{N((S-\lambda)^{k})}{N((S-\lambda)^{k-1})}=\dim\frac{N((S_{1}-\lambda)^{k})}{N((S_{1}-\lambda)^{k-1})}+\dim\frac{N((S_{2}-\lambda)^{k})}{N((S_{2}-\lambda)^{k-1})}.$
(20)

Then, applying Lemma 3.4 repeatedly, together with (20), we have

$\displaystyle W_{k}(S,\lambda)+B_{k}(S)$
$\displaystyle=\dim\frac{N((S-\lambda)^{k})}{N((S-\lambda)^{k-1})}$
$\displaystyle=\left(W_{k}(S_{1},\lambda)+B_{k}(S_{1})\right)+\left(W_{k}(S_{2},\lambda)+B_{k}(S_{2})\right)$
$\displaystyle=W_{k}(S,\lambda)+B_{k}(S_{1})+B_{k}(S_{2}).$

Therefore, $B_{k}(S)=B_{k}(S_{1})+B_{k}(S_{2})$ for each $k\geq 1$.

######  Proposition 3.7.

Given a linear relation $S$ in $\mathbb{C}^{m}$ assume that the reduced sum
decomposition (15) holds. Then, the Weyr characteristic of $S$ satisfies:

$\displaystyle
W_{S}(\lambda_{j})=W_{J_{\lambda_{j}}}(\lambda_{j}),\qquad\text{for}\ 1\leq
j\leq l,$ $\displaystyle A(S)$ $\displaystyle=A(J_{\infty}),\quad
B(S)=B(S_{\rm sing}),\quad\text{and}\quad C(S)=C(S_{M}).$

###### Proof.

Fixed $1\leq i\leq l$, applying Lemma 3.6 to the reducing sum decomposition
(15) we get

$\displaystyle W_{S}(\lambda_{i})$ $\displaystyle=W_{S_{\rm
sing}}(\lambda_{i})+\sum_{j=1}^{l}W_{J_{\lambda_{j}}}(\lambda_{i})+W_{S_{M}}(\lambda_{i}),$

and similar descriptions hold for $A$, $B$ and $C$.

Note that $W_{S_{\rm sing}}(\lambda_{i})$ and $W_{S_{M}}(\lambda_{i})$ are
trivial sequences because $S_{\rm sing}\subset\mathcal{R}_{\rm
c}(S)\times\mathcal{R}_{\rm c}(S)$ and $\mathcal{R}_{\rm
c}(S_{M})=N((S_{M}-\lambda)^{k})=\\{0\\}$ for every $k\geq 1$ and every
$\lambda\in\mathbb{C}\cup\\{0\\}$, respectively. Therefore,
$W_{S}(\lambda_{i})=\sum_{j=1}^{l}W_{J_{\lambda_{j}}}(\lambda_{i})$. Moreover,
since $\sigma_{p}(J_{\lambda_{j}})=\\{\lambda_{j}\\}$ it follows that

$\displaystyle
W_{S}(\lambda_{i})=\sum_{j=1}^{l}W_{J_{\lambda_{j}}}(\lambda_{i})=W_{\lambda_{i}}(\lambda_{i}).$

Let us analyze the case of the sequence $A$. Once again, $A(S_{\rm sing})$ and
$A(S_{M})$ are trivial because $S_{\rm sing}\subset\mathcal{R}_{\rm
c}(S)\times\mathcal{R}_{\rm c}(S)$ and $\mathcal{R}_{\rm
c}(S_{M})=\operatorname{mul}(S_{M}^{k})=\\{0\\}$ for every $k\geq 0$,
respectively. Also, if $\lambda_{j}\in\mathbb{C}$ then $A(J_{\lambda_{j}})$ is
trivial because $\mathcal{R}_{\rm
c}(S_{J_{\lambda_{j}}})=\operatorname{mul}(J_{\lambda_{j}}^{k})=\\{0\\}$ for
every $k\geq 1$ and every $1\leq j\leq l$. Hence, $A(S)=A(J_{\infty})$.

According to (16), $\mathcal{R}_{\rm
c}(J_{\lambda_{j}})\subset\mathcal{R}_{\rm c}(S)\cap D_{\lambda_{j}}=\\{0\\}$
for every $1\leq j\leq l$. Then, $B(J_{\lambda_{j}})$ is trivial for every
$1\leq j\leq l$. Also, $B(S_{M})$ is trivial because $N(S_{M}^{k})=\\{0\\}$
for every $k\geq 1$. Thus, $B(S)=B(S_{\rm sing})$.

To complete the proof let us show that $C(S)=C(S_{M})$. We have that $C(S_{\rm
sing})$ is trivial because $R(S_{\rm sing}^{k})\subseteq\mathcal{R}_{\rm
c}(S_{\rm sing})\subseteq\mathcal{R}_{0}(S_{\rm sing})$ for every $k\geq 1$.

It remains to prove that $C(J_{\lambda_{j}})$ is trivial for each $j$, $1\leq
j\leq l$. Firstly, assume that $\lambda_{j}=0$ for some $j$. In this case,
$J_{0}$ is a nilpotent operator i.e. there exist $k_{0}\in\mathbb{N}$ such
that $J_{0}^{k_{0}}=0$. Then,
$\mathcal{R}_{0}(J_{0})=N(J_{0}^{k_{0}})=D_{0}={\rm dom\,}J_{0}$ and we have
that $R(J_{0}^{k})\subseteq D_{0}=\mathcal{R}_{0}(J_{0})$ for each $k\geq 1$,
so $C(J_{0})$ is trivial.

Secondly, assume that $\lambda_{j}=\infty$ for some $j$. Since $J_{\infty}$ is
the inverse of the graph of a linear operator $T_{0}$ defined on $D_{\infty}$,
it is immediate that ${\rm dom\,}J_{\infty}=R(T_{0})\subseteq D_{\infty}$,
$\mathcal{R}_{0}(J_{\infty})=\\{0\\}$ and $R(J_{\infty}^{k})={\rm
dom\,}(T_{0}^{k})=D_{\infty}$ for each $k\geq 1$. Hence, $C(J_{\infty})$ is
trivial. Finally, given $1\leq j\leq l$, assume that
$\lambda_{j}\in\mathbb{C}\setminus\\{0\\}$. Since
$0\notin\sigma_{p}(J_{\lambda_{j}})$ we have that $J_{\lambda_{j}}$ is
invertible. In particular, $\mathcal{R}_{0}(J_{\lambda_{j}})=\\{0\\}$ and
$R(J_{\lambda_{j}}^{k})=D_{\lambda_{j}}={\rm dom\,}J_{\lambda_{j}}$ for each
$k\geq 1$, which shows that $C(J_{\lambda_{j}})$ is the trivial sequence.
Therefore, $C(S)=C(S_{M})$.

We close this section with showing that the Weyr characteristic is invariant
under strict equivalence.

######  Lemma 3.8.

The Weyr characteristics of two strictly equivalent linear relations in
$\mathbb{C}^{m}$ coincide.

###### Proof.

Let $S$ and $\tilde{S}$ be two strictly equivalent linear relations in
$\mathbb{C}^{m}$. By definition, there is an invertible matrix $T$ such that
$(x,y)\in S$ if and only if $(Tx,Ty)\in\tilde{S}$. Therefore, for each
$k\in\mathbb{N}$ and any $\lambda\in\mathbb{C}$,

$\displaystyle\operatorname{mul}(\tilde{S}^{k})=T(\operatorname{mul}(S^{k})),\quad
N((\tilde{S}-\lambda)^{k})$
$\displaystyle=T(N((S-\lambda)^{k})),\quad\mathcal{R}_{\rm
c}(\tilde{S})=T(\mathcal{R}_{\rm c}(S)),$ $\displaystyle
R(\tilde{S}^{k})=T(R(S^{k})),\quad$
$\displaystyle\text{and}\quad\mathcal{R}_{r}(\tilde{S})=T(\mathcal{R}_{r}(S)).$

Hence,

$\displaystyle\frac{N(\tilde{S}-\lambda)^{k})+\mathcal{R}_{\rm
c}(\tilde{S})}{N((\tilde{S}-\lambda)^{k-1})+\mathcal{R}_{\rm
c}(\tilde{S})}=\frac{T\big{(}N((S-\lambda)^{k})+\mathcal{R}_{\rm
c}(S)\big{)}}{T\big{(}N((S-\lambda)^{k-1})+\mathcal{R}_{\rm c}(S)\big{)}}.$

The invertibility of $T$ thus implies that $W(S)=W(\tilde{S})$. The remaining
equalities $A(S)=A(\tilde{S})$, $B(S)=B(\tilde{S})$, and $C(S)=C(\tilde{S})$
are proved similarly.

##  4 Kernel and range representation for matrix pencils

Kronecker proved that any pair of matrices $E,F\in\mathbb{C}^{n\times m}$, or
what is the same any matrix pencil of the form $sE-F$, can be transformed into
a canonical form, cf. (21) below. Nowadays, this form is referred to as the
_Kronecker canonical form_ , see e.g. [12, 13, 22].

According to Kronecker [27], there exist invertible matrices
$U\in\mathbb{C}^{m\times m}$ and $V\in\mathbb{C}^{n\times n}$ such that
$V(sE-F)U$ has the following block quasi-diagonal form

$\displaystyle V(sE-F)U=\begin{bmatrix}sI_{n_{0}}-J_{0}&0&0&0\\\
0&sN_{\alpha}-I_{|\alpha|}&0&0\\\ 0&0&sK_{\beta}-L_{\beta}&0\\\
0&0&0&sK_{\gamma}^{\top}-L_{\gamma}^{\top}\end{bmatrix}$ (21)

where $J_{0}\in\mathbb{C}^{n_{0}\times n_{0}}$ is in Jordan normal form, and
it is unique up to a permutation of its Jordan blocks, and
$\alpha\in\mathbb{N}^{n_{\alpha}}$, $\beta\in\mathbb{N}^{n_{\beta}}$,
$\gamma\in\mathbb{N}^{n_{\gamma}}$ are multi-indices which are unique up to a
permutation of their entries and the absolute value of $\alpha$ is given by
$|\alpha|=\sum_{i=1}^{n_{\alpha}}\alpha_{i}$. For further details on the
remaining blocks appearing in (21) we refer to Appendix A, which is mainly
based on [22, Chapter XII].

For our purposes it is important to assume that the entries of the multi-
indices $\alpha$, $\beta$ and $\gamma$ as well as the sizes of the different
Jordan blocks in $J_{0}$ corresponding to a given eigenvalue $\lambda$ are
arranged in non-increasing order.

Recall that the Weyr characteristic of a matrix arises from its Segre
characteristic by computing the conjugate partition. Similar to the Segre
characteristic of the matrix $J_{0}$, also the multi-indices $\alpha,\beta$,
and $\gamma$ reflect the various block sizes in the Kronecker canonical form.
Hence, it is natural to define the Weyr characteristic of a matrix pencil by
conjugate partitions of the Kronecker invariants.

######  Definition 4.1.

Let $P(s)=sE-F$ be a matrix pencil with matrices $E$ and $F$ in
$\mathbb{C}^{n\times m}$. If $\lambda_{1},\ldots,\lambda_{l}$ are the
different eigenvalues of the matrix $J_{0}$ in (21), denote by
$w_{\lambda_{1}},\ldots,w_{\lambda_{l}}$ the corresponding Weyr
characteristics. Assuming that $\lambda_{1},\ldots,\lambda_{l}$ are given in a
certain order, we define the Weyr characteristic of $J_{0}$ by
$w=(w_{\lambda_{1}},\ldots,w_{\lambda_{l}})$. Also, consider the conjugate
partitions of the multi-indices $\alpha$, $\beta$, and $\gamma$ and denote
them by $a=(a_{1},\ldots,a_{n_{a}})$, $b=(b_{1},\ldots,b_{n_{b}})$, and
$c=(c_{1},\ldots,c_{n_{c}})$, respectively. Then, the collection of multi-
indices

$w(P):=(w,a,b,c)$ (22)

is called the _Weyr characteristic of the matrix pencil_ $P(s)=sE-F$.

As it was explained in the introduction, a given matrix pencil $P(s)=sE-F$
gives rise to two associated linear relations, namely

$\displaystyle E^{-1}F=N[F,-E]\qquad\text{and}\qquad
FE^{-1}=R\begin{bmatrix}E\\\ F\end{bmatrix},$

which are the kernel and the range representation of the pencil, respectively,
see [14]. Assuming that the Kronecker canonical form of $P(s)=sE-F$ is given
by (21), in [14, Example 4.4] the authors showed that the eigenvalues of
$P(s)$ are exactly the same as the proper eigenvalues of $FE^{-1}$. The same
correspondence holds for the kernel representation $E^{-1}F$. The proof is
omitted because it is similar to the arguments used for the range
representation.

######  Proposition 4.2.

Given $E,F\in\mathbb{C}^{n\times m}$, consider the pencil $P(s)=sE-F$. If
$\lambda\in\mathbb{C}\cup\\{\infty\\}$, the following conditions are
equivalent:

  * (a)

$\lambda$ is an eigenvalue of $P(s)$;

  * (b)

$\lambda$ is a proper eigenvalue of the linear relation $E^{-1}F$;

  * (c)

$\lambda$ is a proper eigenvalue of the linear relation $FE^{-1}$.

In Sections 5 and 6 below we describe the connection between the Weyr
characteristic of the matrix pencil and of its kernel and range
representation, respectively. It turns out that their Weyr characteristics
coincide in the first two entries in (17) and in (22), whereas there is a
certain shift in the last two entries. Before proving this in Sections 5 and
6, we present two simple examples.

######  Example 4.3.

Given $E=K_{(2,1,1)}=[1,0,0,0]$ and $F=L_{(2,1,1)}=[0,1,0,0]$ in
$\mathbb{C}^{1\times 4}$, consider the pencil

$\displaystyle P(s)=sE-F=[s,-1,0,0].$

It is given in Kronecker canonical form, and only the third block in the
Kronecker canonical form is present.

According to Definition 4.1, the only non-empty entry in the Weyr
characteristic of $P(s)$ is the entry $b=(b_{1},\ldots,b_{n_{b}})$, which in
this case is the conjugate of the multi-index $\beta=(2,1,1)$. Hence,

$b=(3,1).$ (23)

On the one hand, the kernel representation of the pencil $P(s)$ is

$E^{-1}F=\left\\{\big{(}(x_{1},x_{2},x_{3},x_{4}),(x_{2},y_{1},y_{2},y_{3})\big{)}:\
x_{1},x_{2},x_{3},x_{4},y_{1},y_{2},y_{3}\in\mathbb{C}\right\\},$

and also $(E^{-1}F)^{2}=\mathbb{C}^{4}\times\mathbb{C}^{4}$. This implies that
$\mathcal{R}_{c}(E^{-1}F)=\mathbb{C}^{4}$. Moreover, since $\dim N(E^{-1}F)=3$
and $\dim N(E^{-1}F)^{2}=4$, we obtain

$B(E^{-1}F)=(3,1),$

which coincides with (23).

On the other hand, the range representation of the matrix pencil $P(s)$ is

$FE^{-1}=R\begin{bmatrix}E\\\ F\end{bmatrix}=\mathbb{C}\times\mathbb{C}.$

Again, this implies that $\mathcal{R}_{c}(FE^{-1})=\mathbb{C}$ and, since
$\dim N(FE^{-1})=1$,

$B(FE^{-1})=(1).$ (24)

Comparing (23) and (24), we see that the range representation does not provide
the complete Weyr characteristic of $P(s)$. However $B(FE^{-1})$ is part of
the sequence $b$, it can be obtained by removing the first entry in $b$.

######  Example 4.4.

Given $E=K_{(2,1,1)}^{\top}=[1,0,0,0]^{\top}$ and
$F=L_{(2,1,1)}^{\top}=[0,1,0,0]^{\top}$ in $\mathbb{C}^{4\times 1}$, consider
the pencil

$\displaystyle Q(s)=sE-F=[s,-1,0,0]^{\top}.$

It is given in Kronecker canonical form and only the fourth block in the
Kronecker canonical form is present.

The only non-zero entry in the Weyr characteristic is the entry
$c=(c_{1},\ldots,c_{n_{c}})$, which is the conjugate of the multi-index
$\gamma=(2,1,1)$. Hence,

$c=(3,1).$

On the one hand, the kernel representation of the pencil $Q(s)$ is

$E^{-1}F=\\{0\\},$

which implies that $C(E^{-1}F)$ is trivial, and $c$ cannot be recovered from
$C(E^{-1}F)$. On the other hand, the range representation of $Q(s)$ is

$FE^{-1}=\left\\{\big{(}(x,0,0,0),(0,x,0,0)\big{)}:\ x\in\mathbb{C}\right\\},$

and $(FE^{-1})^{2}=\\{0\\}$. In this case, $C(FE^{-1})=(1)$, because
$\mathcal{R}_{\rm c}(FE^{-1})=\\{0\\}$, $\dim R(FE^{-1})=1$ and $\dim
R((FE^{-1})^{2})=0$. Hence, the range representation does not provide the
complete Weyr characteristic of $Q(s)$ but $C(FE^{-1})$ can be obtained from
$c$ by removing the first entry in it.

##  5 Weyr characteristics of a pencil and its kernel representation

In this section we present one of the main results of this paper. Theorem 5.1
and Proposition 5.2 below show that there is a correspondence between the Weyr
characteristic of a matrix pencil and that of its kernel representation.
Moreover, it is shown that strict equivalence of pencils and linear relations
is essentially the same as having the same Weyr characteristics.

######  Theorem 5.1.

Let $P(s)=sE-F$ be a matrix pencil with matrices $E$ and $F$ in
$\mathbb{C}^{n\times m}$ and Weyr characteristic $w(P)=(w,a,b,c)$. If
$(W,A,B,C)$ is the Weyr characteristic of the kernel representation $E^{-1}F$
then

$\displaystyle W=w,\quad A=a,\quad B=b.$

Moreover, if $c=(c_{1},\ldots,c_{n_{c}})$, then $C=(c_{3},\ldots,c_{n_{c}})$.

###### Proof.

Since $w(P)$ is invariant under strict equivalence, we assume that $P(s)=sE-F$
is in Kronecker canonical form, i.e. (21) holds with $U=I_{m}$ and $V=I_{n}$.
Then,

$\displaystyle E^{-1}F=S_{n_{0}}\oplus S_{\alpha}\oplus S_{\beta}\oplus
S_{\gamma},$ (25)

is a reducing sum decomposition in the sense of Definition 2.2, where
$S_{n_{0}}=N[J_{0},-I]$, $S_{\alpha}=N[I_{\alpha},-N_{\alpha}]$,
$S_{\beta}=N[L_{\beta},-K_{\beta}]$ and
$S_{\gamma}=N[L_{\gamma}^{\top},-K_{\gamma}^{\top}]$.

Moreover, $S_{n_{0}}$ admits a reducing sum decomposition where each
subrelation is determined by one and only one Jordan block of $J_{0}$.
Analogously, $S_{\alpha}$ admits a reducing sum decomposition where each
subrelation is given by one (and only one) of the blocks along the diagonal of
$N_{\alpha}$. Hence, according to Lemma 3.6, there is no restriction in
assuming that the matrix $J_{0}$ contains only a single Jordan block
$J_{n_{0}}(0)$ of size $n_{0}$ associated to the eigenvalue $\lambda=0$ and
that the multi-index $\alpha$ consists of one entry only. In this case, the
Segre characteristic of $sI-J_{0}$ is just the number $n_{0}$, whereas its
Weyr characteristic is the finite sequence
$(1,1,\ldots,1)\in\mathbb{N}^{n_{0}}$. Similarly, the Weyr characteristic of
$sN_{\alpha}-I_{\alpha}$ is $a=(1,1,\ldots,1)\in\mathbb{N}^{\alpha}$.

In general, the multi-indices $\beta$ and $\gamma$ are of the form

$\displaystyle\beta=(\beta_{1},\ldots,\beta_{l_{\beta}},1,\ldots,1),\quad\gamma=(\gamma_{1},\ldots,\gamma_{l_{\gamma}},1,\ldots,1),$

where $\beta_{1},\ldots,\beta_{l_{\beta}}$ and
$\gamma_{1},\ldots,\gamma_{l_{\gamma}}$ are integers larger than one and the
number of entries equal to one in $\beta$ and $\gamma$ are given by
$m_{\beta}$ and $m_{\gamma}$, respectively. As with the other relations in
(25), $S_{\beta}$ and $S_{\gamma}$ admit a reducing sum decomposition with
respect to the blocks corresponding to $\beta_{1},\ldots,\beta_{l_{\beta}-1}$,
$(\beta_{l_{\beta}}1,\ldots,1)$, $\gamma_{1},\ldots,\gamma_{l_{\gamma}-1}$ and
$(\gamma_{l_{\gamma}},1,\ldots,1)$, respectively. Hence, in view of Lemma 3.6,
there is no restriction in assuming that $\beta$ is either
$\beta=(\beta_{1})$, $\beta=(\beta_{1},1,\ldots,1)$ or $\beta=(1,\ldots,1)$
for some $m_{\beta}>1$. The same applies to $\gamma$. However, the computation
of the Weyr characteristic $(W,A,B,C)$ of $E^{-1}F$ depends on the form of
$\beta$ and $\gamma$. In the following we analyze five different cases.

_Case 1._ If $\beta=(\beta_{1},1,\ldots,1)\in\mathbb{N}^{m_{\beta}+1}$ for
$m_{\beta}\neq 0$, and
$\gamma=(\gamma_{1},1,\ldots,1)\in\mathbb{N}^{m_{\gamma}+1}$ for
$m_{\gamma}\neq 0$ then the Weyr characteristic of the pencil $P(s)=sE-F$ is

$\displaystyle\begin{array}[]{ll}w=(1,1,\ldots,1)\in\mathbb{N}^{n_{0}},&a=(1,1,\ldots,1)\in\mathbb{N}^{\alpha},\\\
b=(m_{\beta}+1,1,\ldots,1)\in\mathbb{N}^{\beta_{1}},&c=(m_{\gamma}+1,1,\ldots,1)\in\mathbb{N}^{\gamma_{1}}.\end{array}$
(28)

Now, let us compute the Weyr characteristic of the kernel representation
$S:=E^{-1}F$. To do so we calculate the powers of the four linear relations in
(25) separately (cf. Lemma 3.6). First, it is easy to see that $S_{n_{0}}$ is
the graph of $J_{n_{0}}(0)$, and consequently $S^{k}_{n_{0}}$ is the graph of
$J_{n_{0}}(0)^{k}$. Similarly, we have that

$S_{\alpha}=\\{(x,y)\in\mathbb{C}^{\alpha}\times\mathbb{C}^{\alpha}\,:\,x=N_{\alpha}y\\}=\\{(N_{\alpha}y,y)\,:\,y\in\mathbb{C}^{\alpha}\\},$

and it is easy to see that its $k$-th power is

$S_{\alpha}^{k}=\\{(N_{\alpha}^{k}\ y,y)\,:\,y\in\mathbb{C}^{\alpha}\\}.$ (29)

The third linear relation is of the form

$\displaystyle\begin{split}S_{\beta}&=\\{(x,y)\in\mathbb{C}^{\beta_{1}+m_{\beta}}\times\mathbb{C}^{\beta_{1}+m_{\beta}}\,:\,L_{\beta}x=K_{\beta}y\\}\\\
&=\left\\{\big{(}(x_{1},\ldots,x_{\beta_{1}+m_{\beta}}),(x_{2},\ldots,x_{\beta_{1}},y_{1},\ldots
y_{m_{\beta}+1})\big{)}\in\mathbb{C}^{\beta_{1}+m_{\beta}}\times\mathbb{C}^{\beta_{1}+m_{\beta}}\right\\}.\end{split}$

For $k<\beta_{1}$ the $k$-th power is of the form

$S_{\beta}^{k}=\left\\{\big{(}(x_{1},\ldots,x_{\beta_{1}+m_{\beta}})),(x_{k+1},\ldots,x_{\beta_{1}},y_{1},\ldots,y_{m_{\beta}+k})\big{)}\in\mathbb{C}^{\beta_{1}+m_{\beta}}\times\mathbb{C}^{\beta_{1}+m_{\beta}}\right\\},$

and for $k\geq\beta_{1}$ the first and the second components of the elements
in $S_{\beta}^{k}$ are completely unrelated to each other, that is,
$S_{\beta}^{k}=\mathbb{C}^{\beta_{1}+m_{\beta}}\times\mathbb{C}^{\beta_{1}+m_{\beta}}$.

The last linear relation is of the form

$\displaystyle\begin{split}S_{\gamma}=\\{(x,y)\in\mathbb{C}^{\gamma_{1}-1}\times\mathbb{C}^{\gamma_{1}-1}\,:\,L_{\gamma}^{\top}x=K_{\gamma}^{\top}y\\}.\end{split}$

On the one hand, if $\gamma_{1}=2$ then $S_{\gamma}=\\{(0,0)\\}$ and the same
holds for $S_{\gamma}^{k}$. On the other hand, if $\gamma_{1}>2$ we obtain

$\displaystyle\begin{split}S_{\gamma}=\left\\{\big{(}(x_{1},\ldots,x_{\gamma_{1}-2},0),(0,x_{1},\ldots,x_{\gamma_{1}-2})\big{)}\,:\,x_{1},\ldots,x_{\gamma_{1}-2}\in\mathbb{C}\right\\}.\end{split}$

For $k<\gamma_{1}-1$ the $k$-th power $S_{\gamma}^{k}$ is of the form

$\left\\{\big{(}(x_{1},\ldots,x_{\gamma_{1}-1-k},0,\ldots,0),(0,\ldots,0,x_{1},\ldots,x_{\gamma_{1}-1-k})\big{)}:x_{1},\ldots,x_{\gamma_{1}-1-k}\in\mathbb{C}\right\\},$

and for $k\geq\gamma_{1}-1$ we have that $S_{\gamma}^{k}=\\{(0,0)\\}.$

Taking into account the decomposition (25) and the above formulas for
$S_{n_{0}}^{k},S_{\alpha}^{k},S_{\beta}^{k}$, and $S_{\gamma}^{k}$, it is easy
to see that

$\displaystyle\begin{split}N(S^{k})=&\\{(x_{1},\ldots,x_{k},0,\ldots,0)\in\mathbb{C}^{n_{0}}\\}\oplus\\{0\\}^{\alpha}\\\\[4.30554pt]
&\oplus\\{(z_{1},\ldots,z_{k},0,\ldots,0,z_{\beta_{1}+1},\ldots,z_{\beta_{1}+m_{\beta}})\in\mathbb{C}^{\beta_{1}+m_{\beta}}\\}\oplus\\{0\\}^{\gamma_{1}-1}\end{split}$
(30)

and

$\operatorname{mul}(S^{k})=\\{0\\}^{n_{0}}\oplus
N(N_{\alpha}^{k})\oplus\\{(0,\ldots,0,y_{1},\ldots,y_{m_{\beta}+k})\in\mathbb{C}^{\beta_{1}+m_{\beta}}\\}\oplus\\{0\\}^{\gamma_{1}-1}.$
(31)

Hence,

$\displaystyle\begin{split}\mathcal{R}_{0}(S)=&\mathbb{C}^{n_{0}}\oplus\\{0\\}^{\alpha}\oplus\mathbb{C}^{\beta_{1}+m_{\beta}}\oplus\\{0\\}^{\gamma_{1}-1}\\\\[4.30554pt]
\mathcal{R}_{\infty}(S)=&\\{0\\}^{n_{0}}\oplus\mathbb{C}^{\alpha}\oplus\mathbb{C}^{\beta_{1}+m_{\beta}}\oplus\\{0\\}^{\gamma_{1}-1}.\end{split}$
(32)

By definition,
$\mathcal{R}_{c}(S)=\mathcal{R}_{0}(S)\cap\mathcal{R}_{\infty}(S)$ and we have

$\mathcal{R}_{c}(S)=\\{0\\}^{n_{0}}\oplus\\{0\\}^{\alpha}\oplus\mathbb{C}^{\beta_{1}+m_{\beta}}\oplus\\{0\\}^{\gamma_{1}-1}.$
(33)

Now, we use the (30), (31),(32), and (33) to compute the Weyr characteristics
of $S$ introduced in Definition 3.1. The Weyr characteristic corresponding to
the eigenvalue $\lambda=0$ has $n_{0}$ non zero entries. Given $1\leq k\leq
n_{0}$,

$\displaystyle
W_{k}(0)=\dim\frac{N(S^{k})+\mathcal{R}_{c}(S)}{N(S^{k-1})+\mathcal{R}_{c}(S)}=\dim\frac{\\{(x_{1},\ldots,x_{k},0,\ldots,0)\in\mathbb{C}^{n_{0}}\\}}{\\{(x_{1},\ldots,x_{k-1},0,\ldots,0)\in\mathbb{C}^{n_{0}}\\}}=1,$

and the finite sequence $W$ is of the form
$W=(1,\ldots,1)\in\mathbb{C}^{n_{0}}$, i.e. $W=w$. Analogously, the Weyr
characteristic corresponding to $\infty$ has $\alpha$ non zero entries which
are given by

$\displaystyle
A_{k}=\dim\frac{\operatorname{mul}(S^{k})+\mathcal{R}_{c}(S)}{\operatorname{mul}(S^{k-1})+\mathcal{R}_{c}(S)}=\dim\frac{N(N_{\alpha}^{k})}{N(N_{\alpha}^{k-1})}=1,\quad
1\leq k\leq\alpha.$

Hence, the finite sequence $A$ is of the form
$A=(1,\ldots,1)\in\mathbb{C}^{\alpha}$. Therefore, $A=a$.

The Weyr characteristic of the singular chains subspace is defined by

$\displaystyle\begin{split}B_{k}=&\dim\frac{N(S^{k})\cap\mathcal{R}_{c}(S)}{N(S^{k-1})\cap\mathcal{R}_{c}(S)}\\\\[4.30554pt]
=&\left\\{\begin{array}[]{ll}\dim\\{(z_{1},0,\ldots,0,z_{\beta_{1}+1},\ldots,z_{\beta_{1}+m_{\beta}})\in\mathbb{C}^{\beta_{1}+m_{\beta}}\\}=m_{\beta}+1,&\mbox{
if }k=1,\\\\[4.30554pt]
\dim\frac{\\{(z_{1},\ldots,z_{k},0,\ldots,0,z_{\beta_{1}+1},\ldots,z_{\beta_{1}+m_{\beta}})\in\mathbb{C}^{\beta_{1}+m_{\beta}}\\}}{\\{(z_{1},\ldots,z_{k-1},0,\ldots,0,z_{\beta_{1}+1},\ldots,z_{\beta_{1}+m_{\beta}})\in\mathbb{C}^{\beta_{1}+m_{\beta}}\\}}=1,&\mbox{
if }2\leq k\leq\beta_{1},\end{array}\right.\end{split}$

and the finite sequence $B$ coincides with $b$.

Finally, to compute $C$, note that (29) and (32) imply

$\displaystyle
R(S^{k})+\mathcal{R}_{0}(S)=\mathbb{C}^{n_{0}}\oplus\mathbb{C}^{\alpha}\oplus\mathbb{C}^{\beta_{1}+m_{\beta}}\oplus
R(S_{\gamma}^{k}).$

If $\gamma_{1}>2$ then,

$\displaystyle C_{1}=\dim\frac{R(S)+{\rm
dom\,}S}{R(S)+\mathcal{R}_{0}(S)}=\dim\frac{\mathbb{C}^{n_{0}}\oplus\mathbb{C}^{\alpha}\oplus\mathbb{C}^{\beta_{1}+m_{\beta}}\oplus\big{(}R(S_{\gamma})+{\rm
dom\,}(S_{\gamma})\big{)}}{\mathbb{C}^{n_{0}}\oplus\mathbb{C}^{\alpha}\oplus\mathbb{C}^{\beta_{1}+m_{\beta}}\oplus
R(S_{\gamma})}=1,$

and, for $2\leq k\leq\gamma_{1}-2$,

$\displaystyle
C_{k}=\dim\frac{R(S^{k})+\mathcal{R}_{0}(S)}{R(S^{k+1})+\mathcal{R}_{0}(S)}=\dim\frac{\\{(0,\ldots,0,x_{1},\ldots,x_{\gamma_{1}-1-k})\in\mathbb{C}^{\gamma_{1}-1}\\}}{\\{(0,\ldots,0,x_{1},\ldots,x_{\gamma_{1}-1-(k+1)})\in\mathbb{C}^{\gamma_{1}-1}\\}}=1.$

Therefore, the finite sequence $C$ is of the form
$C=(1,\ldots,1)\in\mathbb{N}^{\gamma_{1}-2}$. On the other hand, if
$\gamma_{1}\leq 2$ then $C$ is the trivial sequence.

_Case 2._ Assume that $\beta=(\beta_{1})$ with $\beta_{1}>1$ or
$\gamma=(\gamma_{1})$ with $\gamma_{1}>1$. This case can be solved exactly in
the same way as Case 1, the only difference is that in this case either
$m_{\beta}=0$ or $m_{\gamma}=0$.

_Case 3._ Assume that $\beta=(1,\ldots,1)\in\mathbb{N}^{m_{\beta}}$ for
$m_{\beta}\neq 0$ and that
$\gamma=(\gamma_{1},1,\ldots,1)\in\mathbb{N}^{m_{\gamma}+1}$ with
$\gamma_{1}>1$ and $m_{\gamma}\geq 0$. Also, assume that one (or both) of the
first two entries of the Kronecker canonical form in (21) is (are) present,
then the Kronecker canonical form of the pencil $sE-F$ has the form

$\displaystyle\begin{bmatrix}sI_{n_{0}}-J_{0}&0&0&0\\\
0&sN_{\alpha}-I_{\alpha}&0_{\alpha\times m_{\beta}}&0\\\
0&0&0&sK_{\gamma}^{\top}-L_{\gamma}^{\top}\end{bmatrix},$ (34)

where $0_{\alpha\times m_{\beta}}$ stands for the zero matrix with $\alpha$
rows and $m_{\beta}$ columns. On the contrary, if the first two entries of the
Kronecker canonical form in (21) are not present, then the Kronecker canonical
form of the pencil $sE-F$ has the form

$\displaystyle\begin{bmatrix}0_{|\gamma|\times
m_{\beta}}&sK_{\gamma}^{\top}-L_{\gamma}^{\top}\end{bmatrix}.$ (35)

In both cases $L_{\beta}$ and $K_{\beta}$ are zero matrices of appropriate
sizes and we have that
$S_{\beta}=\mathbb{C}^{m_{\beta}}\times\mathbb{C}^{m_{\beta}}$. Hence, the
reducing sum decomposition (25) reduces to $E^{-1}F=S_{n_{0}}\oplus
S_{\alpha}\oplus(\mathbb{C}^{m_{\beta}}\times\mathbb{C}^{m_{\beta}})\oplus
S_{\gamma}$, and we proceed as in Case 1 to show the statement.

_Case 4._ Assume that
$\beta=(\beta_{1},1,\ldots,1)\in\mathbb{N}^{m_{\beta}+1}$ with $\beta_{1}>1$
and $m_{\beta}\geq 0$ and $\gamma=(1,\ldots,1)\in\mathbb{N}^{m_{\gamma}}$ with
$m_{\gamma}\neq 0$. Then, the reducing sum decomposition (25) is of the form
$E^{-1}F=S_{n_{0}}\oplus S_{\alpha}\oplus S_{\beta}$, where

$\displaystyle S_{\beta}=N\left[\begin{bmatrix}L_{\beta_{1}}\\\
0_{m_{\gamma}\times|\beta_{1}|}\end{bmatrix},-\begin{bmatrix}K_{\beta_{1}}\\\
0_{m_{\gamma}\times|\beta_{1}|}\end{bmatrix}\right]=N\left[L_{\beta_{1}},-K_{\beta_{1}}\right],$

and the proof of the statement follows as in Case 1.

_Case 5._ Let $\beta=(1,\ldots,1)\in\mathbb{N}^{m_{\beta}}$ with
$m_{\beta}\geq 1$ and $\gamma=(1,\ldots,1)\in\mathbb{N}^{m_{\gamma}}$ with
$m_{\gamma}\geq 1$. If one (or both) of the first two entries of the KCF in
(21) is (are) present, then it is of the form

$\displaystyle\begin{bmatrix}sI_{n_{0}}-J_{0}&0&0\\\
0&sN_{\alpha}-I_{\alpha}&0\\\ 0&0&0_{m_{\gamma}\times
m_{\beta}}\end{bmatrix}.$

Then the reducing sum decomposition (25) is of the form
$E^{-1}F=S_{n_{0}}\oplus S_{\alpha}\oplus S_{\beta}$, where
$S_{\beta}=\mathbb{C}^{m_{\beta}}\times\mathbb{C}^{m_{\beta}}$ because
$L_{\beta}$ and $K_{\beta}$ are zero matrices of appropriate sizes. Finally,
if the first two entries are not present, the Kronecker canonical form equals
$0_{m_{\gamma}\times m_{\beta}}$ and the reduced sum decomposition is just
$E^{-1}F=S_{\beta}=\mathbb{C}^{m_{\beta}}\times\mathbb{C}^{m_{\beta}}$.
Therefore, in both cases $C_{k}=0$ for every $k\geq 1$,
$B_{1}=m_{\beta}=b_{1}$ and the equalities $W=w$ and $A=a$ follows as in Case
1.

Theorem 5.1 shows how the Weyr characteristic $(w,a,b,c)$ of a matrix pencil
determines the Weyr characteristic $(W,A,B,C)$ of its kernel representation.
As is shown, the multi-index $C$ differs from $c$ by two entries, $c_{1}$ and
$c_{2}$ vanish.

In order to reconstruct the Weyr characteristic of a matrix pencil from its
kernel representation, it is necessary to know not only the Weyr
characteristic of the linear relation but also the sizes of the matrices in
the kernel representation (these matrices are not uniquely given).

######  Proposition 5.2.

Let $S$ be a linear relation in $\mathbb{C}^{m}$ with Weyr characteristic
$(W,A,B,C)$. If there exist matrices $E,F\in\mathbb{C}^{n\times m}$ such that
the kernel representation $E^{-1}F$ of the matrix pencil $P(s)=sE-F$ coincides
with $S$, then the Weyr characteristic $(w,a,b,c)$ of the pencil $P(s)$ is
given by

$\displaystyle w=W,\quad a=A,\quad b=B,$

and, if $C=(C_{1},\ldots,C_{n_{C}})$ is the last multi-index in the Weyr
characteristic of the linear relation $S$ then

$c=(n-m+B_{1},m-|W|-|A|-|B|-|C|,C_{1},C_{2},C_{3},\ldots,C_{n_{C}}).$ (36)

###### Proof.

Assume that $S=E^{-1}F$ is the kernel representation of the matrix pencil
$P(s)$. Then, there exist invertible matrices $U\in\mathbb{C}^{n\times n}$ and
$V\in\mathbb{C}^{m\times m}$ such that $UP(s)V=sUEV-UFV$ is in Kronecker
canonical form. Note that $(x,y)\in(UEV)^{-1}(UFV)$ if and only if $(Vx,Vy)\in
E^{-1}F$. This implies that $(UEV)^{-1}(UFV)$ and $E^{-1}F$ are strictly
equivalent because

$\displaystyle(UEV)^{-1}(UFV)=\begin{bmatrix}V^{-1}&0\\\
0&V^{-1}\end{bmatrix}\cdot E^{-1}F.$

Hence, according to Lemma 3.8, they have the same Weyr characteristic.
Therefore, we can assume without loss of generality that $P(s)$ is already in
Kronecker canonical from.

Now, let $(w,a,b,c)$ be the Weyr characteristic of the pencil $P(s)$. It is
possible to express the numbers $m$ and $n$ of the matrix pencil $P(s)$ in
(21) in terms of the Weyr characteristic. In fact, $|w|$ and $|a|$ are the
number of rows (and columns) of $P(s)$ determined by the blocks associated to
the finite and the infinity eigenvalues, respectively. On the other hand,
$b_{1}$ and $c_{1}$ are the number of rectangular blocks corresponding to the
pencils $sK_{\beta}-L_{\beta}$ and $sK_{\gamma}^{\top}-L_{\gamma}^{\top}$,
respectively. In particular, the number of rows and columns of $P(s)$
determined by the pencil $sK_{\beta}-L_{\beta}$ are $|b|-b_{1}$ and $|b|$,
respectively. Analogously, the number of rows and columns of $P(s)$ determined
by the pencil $sK_{\gamma}^{\top}-L_{\gamma}^{\top}$ are $|c|$ and
$|c|-c_{1}$, respectively. Hence,

$n=|w|+|a|+(|b|-b_{1})+|c|\quad\text{and}\quad m=|w|+|a|+|b|+(|c|-c_{1}).$
(37)

By Theorem 5.1, we have that

$w=W,\quad a=A,\quad\text{and}\quad b=B.$

Also, we know the indices in $c$ with the exception of the first two:
$c_{k}=C_{k-2}$ if $k\geq 3$. Moreover, $c_{1}\geq c_{2}\geq c_{3}=C_{1}$ and

$\displaystyle|c|=|C|+c_{1}+c_{2}.$

Replacing the above formula in (37), we obtain

$\displaystyle n$ $\displaystyle=|W|+|A|+(|B|-B_{1})+|C|+c_{1}+c_{2},$
$\displaystyle m$ $\displaystyle=|W|+|A|+|B|+|C|+c_{2}.$

Thus,

$\displaystyle c_{2}$ $\displaystyle=m-|W|-|A|-|B|-|C|,\quad\text{and}$
$\displaystyle c_{1}$ $\displaystyle=n-|W|-|A|-(|B|-B_{1})-|C|-c_{2}$
$\displaystyle=n-|W|-|A|-(|B|-B_{1})-|C|-(m-|W|-|A|-|B|-|C|)$
$\displaystyle=n-m+B_{1}.$

######  Corollary 5.3.

Let $S$ be a linear relation in $\mathbb{C}^{m}$ and assume that its Weyr
characteristic is $(W,A,B,C)$. Then,

$\displaystyle n=2m-|W|-|A|-|B|-B_{1}-|C|,$

is the smallest possible number of rows for matrices
$E,F\in\mathbb{C}^{n\times m}$ such that the kernel representation $E^{-1}F$
of the matrix pencil $P(s)=sE-F$ coincides with $S$. In this case, the Weyr
characteristic $(w,a,b,c)$ of the pencil $P(s)$ is given by

$\displaystyle w=W,\quad a=A,\quad b=B,$

and, if $C=(C_{1},\ldots,C_{n_{c}})$ is the last multi-index in the Weyr
characteristic of the linear relation $S$, then

$\displaystyle
c=(m-|W|-|A|-|B|-|C|,m-|W|-|A|-|B|-|C|,C_{1},C_{2},C_{3},\ldots,C_{n_{C}}).$

###### Proof.

Assume that $E,F\in\mathbb{C}^{n\times m}$ are such that the kernel
representation $E^{-1}F$ of the matrix pencil $P(s)=sE-F$ coincides with $S$.
By Proposition 5.2, the Weyr characteristic $(w,a,b,c)$ of the pencil $P(s)$
is such that $w=W$, $a=A$, $b=B$, and $c$ is given by (36).

First of all, let us show that the proposed minimal number of rows is
positive. According to (37), $m=|W|+|A|+|B|+|C|+c_{2}$. Then,

$\displaystyle 2m-|W|-|A|-|B|-B_{1}-|C|$
$\displaystyle=m-B_{1}+(m-|W|-|A|-|B|-|C|)$ $\displaystyle=(m-B_{1})+c_{2}\geq
1.$

Also, according to (37) we have that $n=|w|+|a|+(|b|-b_{1})+|c|$. Then, in
order to minimize $n$ it is necessary to minimize $|c|$, and the minimum of
$|c|$ is attained only if $c_{1}=c_{2}=c_{3}$. Therefore, using the
expressions of $c_{1}$ and $c_{2}$ in (36) we get
$n-m+B_{1}=m-|W|-|A|-|B|-|C|$, i.e.

$\displaystyle n=2m-|W|-|A|-|B|-B_{1}-|C|.$

In the following we are going to prove the converse of Lemma 3.8, i.e. if two
linear relations $S_{1}$ and $S_{2}$ in $\mathbb{C}^{m}$ have the same Weyr
characteristic, then they are strictly equivalent, see Theorem 5.5 below.

######  Proposition 5.4.

Given $E_{1},E_{2},F_{1},F_{2}\in\mathbb{C}^{n\times m}$, consider the matrix
pencils $P_{1}(s)=sE_{1}-F_{1}$ and $P_{2}(s)=sE_{2}-F_{2}$. Let
$S_{1}=E_{1}^{-1}F_{1}$ and $S_{2}=E_{2}^{-1}F_{2}$ be their corresponding
kernel representations. If $P_{1}(s)$ is strictly equivalent to $P_{2}(s)$,
then $S_{1}$ is strictly equivalent to $S_{2}$. In this case, the Weyr
characteristics of $S_{1}$ and $S_{2}$ coincide.

###### Proof.

Assume that $P_{1}(s)$ is strictly equivalent to $P_{2}(s)$, i.e. there exist
invertible matrices $U\in\mathbb{C}^{n\times n}$ and $V\in\mathbb{C}^{m\times
m}$ such that

$\displaystyle E_{2}=UE_{1}V\quad\text{and}\quad F_{2}=UF_{1}V,$

(cf. Appendix A). Then, $S_{2}=E_{2}^{-1}F_{2}=(UE_{1}V)^{-1}(UF_{1}V)$, or
equivalently,

$\displaystyle S_{2}$ $\displaystyle=\left\\{(x,y):\ F_{1}Vx=E_{1}Vy\right\\}$
$\displaystyle=\begin{pmatrix}V^{-1}&0\\\
0&V^{-1}\end{pmatrix}\cdot\left\\{(Vx,Vy):\ F_{1}Vx=E_{1}Vy\right\\}$
$\displaystyle=\begin{pmatrix}T&0\\\ 0&T\end{pmatrix}\cdot S_{1},$

where $T:=V^{-1}$. Therefore, $S_{1}$ is strictly equivalent to $S_{2}$. The
last statement about the Weyr characteristics follows from Lemma 3.8.

######  Theorem 5.5.

Let $S_{1}$ and $S_{2}$ be linear relations in $\mathbb{C}^{m}$. Then their
Weyr characteristics coincide if and only if the linear relations $S_{1}$ and
$S_{2}$ are strictly equivalent.

###### Proof.

On the one hand, in Lemma 3.8 we showed that if $S_{1}$ and $S_{2}$ are
strictly equivalent then their Weyr characteristics coincide.

On the other hand, if $S_{1}$ and $S_{2}$ have the same Weyr characteristic
then, defining $n$ as the minimal value given in Corollary 5.3, there exist
matrices $E_{1},F_{1},E_{2},F_{2}\in\mathbb{C}^{n\times m}$ such that

$S_{1}=E_{1}^{-1}F_{1}\quad\text{and}\quad S_{2}=E_{2}^{-1}F_{2}.$

Moreover, the Weyr characteristics of the associated matrix pencils
$P_{1}(s)=sE_{1}-F_{1}$ and $P_{2}(s)=sE_{2}-F_{2}$ coincide. Therefore,
$P_{1}$ is strictly equivalent to $P_{2}$ and, by Proposition 5.4, the kernel
representations $S_{1}$ and $S_{2}$ are also strictly equivalent.

##  6 Weyr characteristics of a pencil and its range representation

Along this section we obtain results on the correspondence between the
Kronecker canonical form of a matrix pencil and the Weyr characteristic of its
range representation. They are similar to those presented in Section 5.

######  Theorem 6.1.

Let $P(s)=sE-F$ be a matrix pencil with matrices $E$ and $F$ in
$\mathbb{C}^{n\times m}$ and with Weyr characteristic $w(P)=(w,a,b,c)$. If
$(W,A,B,C)$ is the Weyr characteristic of the range representation $FE^{-1}$
then

$W=w,\quad A=a,$

and, if $b=(b_{1},\ldots,b_{n_{b}})$ and $c=(c_{1},\ldots,c_{n_{c}})$, then

$\displaystyle B=(b_{2},\ldots,b_{n_{b}})\quad\text{and}\quad
C=(c_{2},\ldots,c_{n_{c}}).$

The proof of Theorem 6.1 has the same structure as the proof of Theorem 5.1.
We concentrate our attention only on those calculations which are different.

###### Proof.

There is no restriction to assume that $P(s)=sE-F$ is in Kronecker canonical
form. As in the proof of Theorem 5.1, we assume that the matrix $J_{0}$ in
(21) contains only a single Jordan block $J_{n_{0}}(0)$ of size $n_{0}$
associated to the eigenvalue $\lambda=0$ and that the multi-index $\alpha$
consists of one entry only. Once again, there is no restriction in assuming
that $\beta$ is either $\beta=(\beta_{1})$, $\beta=(\beta_{1},1,\ldots,1)$ or
$\beta=(1,\ldots,1)$ for some $m_{\beta}>1$, and the same applies to $\gamma$.

The Kronecker canonical form induces a reducing sum decomposition of the range
representation $FE^{-1}$ as

$\displaystyle FE^{-1}=T_{n_{0}}\oplus T_{\alpha}\oplus T_{\beta}\oplus
T_{\gamma},$ (38)

where

$T_{n_{0}}:=R\begin{bmatrix}I\\\ J_{0}\end{bmatrix},\
T_{\alpha}:=R\begin{bmatrix}N_{\alpha}\\\ I_{\alpha}\end{bmatrix},\
T_{\beta}:=R\begin{bmatrix}K_{\beta}\\\ L_{\beta}\end{bmatrix},\mbox{ and
}T_{\gamma}:=R\begin{bmatrix}K_{\gamma}^{\top}\\\
L_{\gamma}^{\top}\end{bmatrix}.$

_Case 1._ If $\beta=(\beta_{1},1,\ldots,1)\in\mathbb{N}^{m_{\beta}+1}$ with
$\beta_{1}>1$ and $\gamma=(\gamma_{1},1,\ldots,1)\in\mathbb{N}^{m_{\gamma}+1}$
with $\gamma_{1}>1$ then the Weyr characteristic of the pencil $P(s)$ is given
again by (28).

As in the proof of Theorem 5.1, we calculate the powers of the four linear
relations in (38) separately (cf. Lemma 3.6). Obviously, $T_{n_{0}}$ is the
graph of $J_{0}$, and consequently $T^{k}_{n_{0}}$ is the graph of
$J_{0}^{k}$. Similarly,

$T_{\alpha}=\\{(N_{\alpha}y,y)\,:\,y\in\mathbb{C}^{\alpha}\\}\mbox{ and
}T_{\alpha}^{k}=\\{(N_{\alpha}^{k}y,y)\,:\,y\in\mathbb{C}^{\alpha}\\}.$ (39)

The third linear relation is of the form

$\displaystyle
T_{\beta}=\left\\{\big{(}(y_{1},x_{1},\ldots,x_{\beta_{1}-2}),(x_{1},\ldots,x_{\beta_{1}-2},z_{1})\big{)}:(x_{1},\ldots,x_{\beta_{1}-2})\in\mathbb{C}^{\beta_{1}-2},y_{1},z_{1}\in\mathbb{C}\right\\}.$

For $k\geq\beta_{1}-1$ we have that
$T_{\beta}^{k}=\mathbb{C}^{\beta_{1}-1}\times\mathbb{C}^{\beta_{1}-1}$, and
for $k<\beta_{1}-1$ the pairs in the $k$-th power $T_{\beta}^{k}$ are of the
form

$\big{(}(y_{1},\ldots,y_{k},x_{1},\ldots,x_{\beta_{1}-k-1}),(x_{1},\ldots,x_{\beta_{1}-k-1},z_{1},\ldots,z_{k})\big{)},$

where $x_{1},\ldots,x_{\beta_{1}-k-1},y_{1},\ldots
y_{k},z_{1},\ldots,z_{k}\in\mathbb{C}$.

The pairs in the last linear relation $T_{\gamma}$ are of the form

$\displaystyle\begin{split}\big{(}(x_{1},\ldots,x_{\gamma_{1}-1},0,\ldots,0),(0,x_{1},\ldots,x_{\gamma_{1}-1},0,\ldots,0)\big{)}\in\mathbb{C}^{\gamma_{1}+m_{\gamma}}\times\mathbb{C}^{\gamma_{1}+m_{\gamma}},\end{split}$

where $x_{1},\ldots,x_{\gamma_{1}-1}\in\mathbb{C}$. For $k\geq\gamma_{1}$ we
have that $T_{\gamma}^{k}=\\{(0,0)\\}$ and, for $k<\gamma_{1}$ the pairs in
the $k$-th power $T_{\gamma}^{k}$ are given by

$\big{(}(x_{1},\ldots,x_{\gamma_{1}-k},0,\ldots,0),(0,\ldots,0,x_{1},\ldots,x_{\gamma_{1}-k},0,\ldots,0)\big{)}\in\mathbb{C}^{\gamma_{1}+m_{\gamma}}\times\mathbb{C}^{\gamma_{1}+m_{\gamma}}.$

If $T:=FE^{-1}$ then the following descriptions hold:

$\displaystyle\begin{split}N(T^{k})=&\\{(x_{1},\ldots,x_{k},0,\ldots,0)\in\mathbb{C}^{n_{0}}\\}\oplus\\{0\\}^{\alpha}\\\\[4.30554pt]
&\oplus\\{(y_{1},\ldots,y_{k},0,\ldots,0)\in\mathbb{C}^{\beta_{1}-1}\\}\oplus\\{0\\}^{\gamma_{1}+m_{\gamma}}\end{split}$

and

$\operatorname{mul}(T^{k})=\\{0\\}^{n_{0}}\oplus
N(N_{\alpha}^{k})\oplus\\{(z_{1},\ldots,z_{k},0,\ldots,0)\in\mathbb{C}^{\beta_{1}-1}\\}\oplus\\{0\\}^{\gamma_{1}+m_{\gamma}}.$

Hence,

$\displaystyle\begin{split}\mathcal{R}_{0}(T)=&\mathbb{C}^{n_{0}}\oplus\\{0\\}^{\alpha}\oplus\mathbb{C}^{\beta_{1}-1}\oplus\\{0\\}^{\gamma_{1}+m_{\gamma}},\\\\[4.30554pt]
\mathcal{R}_{\infty}(T)=&\\{0\\}^{n_{0}}\oplus\mathbb{C}^{\alpha}\oplus\mathbb{C}^{\beta_{1}-1}\oplus\\{0\\}^{\gamma_{1}+m_{\gamma}},\\\\[4.30554pt]
\mathcal{R}_{c}(T)=&\\{0\\}^{n_{0}}\oplus\\{0\\}^{\alpha}\oplus\mathbb{C}^{\beta_{1}-1}\oplus\\{0\\}^{\gamma_{1}+m_{\gamma}}.\end{split}$
(40)

Therefore, the first two parts of the Weyr characteristics coincide,

$W=w\quad\text{and}\quad A=a.$

The entries of the Weyr characteristic of the singular chains subspace are

$\displaystyle
B_{k}=\dim\frac{N(T^{k})\cap\mathcal{R}_{c}(T)}{N(T^{k-1})\cap\mathcal{R}_{c}(T)}=\dim\frac{\\{(y_{1},\ldots,y_{k},0,\ldots,0)\in\mathbb{C}^{\beta_{1}-1}\\}}{\\{(y_{1},\ldots,y_{k-1},0,\ldots,0)\in\mathbb{C}^{\beta_{1}-1}\\}}=1,$

if $1\leq k\leq\beta_{1}-1$, and they are zero otherwise. So,
$B=(1,\ldots,1)\in\mathbb{N}^{\beta_{1}-1}$.

For the Weyr characteristic of multi-shifts, note that (39) and (40) imply

$\displaystyle
R(T^{k})+\mathcal{R}_{0}(T)=\mathbb{C}^{n_{0}}\oplus\mathbb{C}^{\alpha}\oplus\mathbb{C}^{\beta_{1}-1}\oplus
R(T_{\gamma}^{k}).$

Hence, the entries of $C$ are given by

$\displaystyle C_{1}$ $\displaystyle=\dim\frac{R(T)+{\rm
dom\,}T}{R(T)+\mathcal{R}_{0}(T)}=\dim\frac{\mathbb{C}^{n_{0}}\oplus\mathbb{C}^{\alpha}\oplus\mathbb{C}^{\beta_{1}-1}\oplus\big{(}R(T_{\gamma})+{\rm
dom\,}(T_{\gamma})\big{)}}{\mathbb{C}^{n_{0}}\oplus\mathbb{C}^{\alpha}\oplus\mathbb{C}^{\beta_{1}-1}\oplus
R(T_{\gamma})}=1,$ $\displaystyle C_{k}$
$\displaystyle=\dim\frac{R(T^{k})+\mathcal{R}_{0}(T)}{R(T^{k+1})+\mathcal{R}_{0}(T)}=\dim\frac{\\{(0,\ldots,0,x_{1},\ldots,x_{\gamma_{1}-k})\in\mathbb{C}^{\gamma_{1}+m_{\gamma}}\\}}{\\{(0,\ldots,0,x_{1},\ldots,x_{\gamma_{1}-k-1})\in\mathbb{C}^{\gamma_{1}+m_{\gamma}}\\}}=1,$

if $2\leq k\leq\gamma_{1}-1$, and they are zero otherwise. Thus,
$C=(1,\ldots,1)\in\mathbb{N}^{\gamma_{1}-1}$. Comparing the obtained
$(W,A,B,C)$ with (28) we complete the proof of this case.

_Case 2._ Assume that $\beta=(\beta_{1})$ with $\beta_{1}>1$ or
$\gamma=(\gamma_{1})$ with $\gamma_{1}>1$. As in the proof of Theorem 5.1,
this follows as in Case 1 with the condition $m_{\beta}=0$ or $m_{\gamma}=0$,
respectively.

_Case 3._ Assume that $\beta=(1,\ldots,1)\in\mathbb{N}^{m_{\beta}}$ for
$m_{\beta}>0$ and also that
$\gamma=(\gamma_{1},1,\ldots,1)\in\mathbb{N}^{m_{\gamma}+1}$ with
$\gamma_{1}>1$ and $m_{\gamma}\geq 0$. Then the Kronecker canonical form of
the pencil $sE-F$ has the form (34) or (35). In both cases (38) induces a
reducing sum decomposition with $T_{\beta}=\\{0\\}$. Hence, we can proceed as
in Case 1 to prove the statement.

_Case 4._ Assume that
$\beta=(\beta_{1},1,\ldots,1)\in\mathbb{N}^{m_{\beta}+1}$ with $\beta_{1}>0$
and $\gamma=(1,\ldots,1)\in\mathbb{N}^{m_{\gamma}}$ for some $m_{\gamma}>0$.
Then the Kronecker canonical form (21) of the pencil $sE-F$ is of the form
(44) and we obtain the following reducing sum decomposition

$\displaystyle FE^{-1}=R\begin{bmatrix}I\\\ J_{0}\end{bmatrix}\oplus
R\begin{bmatrix}N_{\alpha}\\\ I_{\alpha}\end{bmatrix}\oplus
R\begin{bmatrix}K_{\beta}\\\ 0_{m_{\gamma}\times|\beta|}\\\ L_{\beta}\\\
0_{m_{\gamma}\times|\beta|}\end{bmatrix},$

where $0_{m_{\gamma}\times|\beta|}$ stands for the zero matrix with
$m_{\gamma}$ rows and $|\beta|$ columns. Then the proof of this case is
similar to the proof of Case 1.

_Case 5._ Assume that $\beta=(1,\ldots,1)\in\mathbb{N}^{m_{\beta}}$ for
$m_{\beta}>0$ and $\gamma=(1,\ldots,1)\in\mathbb{N}^{m_{\gamma}}$ for
$m_{\gamma}>0$. Again, if one (or both) of the first two entries of the KCF in
(21) is (are) present, then it is of the form

$\displaystyle\begin{bmatrix}sI_{n_{0}}-J_{0}&0&0\\\
0&sN_{\alpha}-I_{\alpha}&0\\\ 0&0&0_{m_{\gamma}\times
m_{\beta}}\end{bmatrix}.$

Then the reducing sum decomposition (25) is of the form
$T=FE^{-1}=T_{n_{0}}\oplus T_{\alpha}\oplus T_{\gamma}$, where
$T_{\gamma}=\\{(0,0)\\}^{m_{\gamma}\times m_{\gamma}}$ because $L_{\gamma}$
and $K_{\gamma}$ are zero matrices of appropriate sizes. Since
$\mathcal{R}_{\rm c}(T)=\\{0\\}^{n_{0}+\alpha+m_{\gamma}}$, we have that
$B_{k}=0$ for every $k\geq 1$. Also, $\mathcal{R}_{0}(T)+R(T^{k})={\rm
dom\,}T+R(T)=\mathbb{C}^{n_{0}}\oplus\mathbb{C}^{\alpha}\oplus\\{0\\}^{m_{\gamma}}$
implies that $C_{k}=0$ for each $k\geq 1$.

Finally, if the two first entries are not present then the KCF equals
$0_{m_{\gamma}\times m_{\beta}}$ and the reduced sum decomposition is just
$FE^{-1}=T_{\gamma}=\\{(0,0)\\}^{m_{\gamma}\times m_{\gamma}}$. Once again, it
is easy to see that $B_{k}=C_{k}=0$ for every $k\geq 1$.

We end this section with versions of Proposition 5.2 and Corollary 5.3
corresponding to the range representation of a matrix pencil. The proofs are
omitted since they use similar arguments.

######  Proposition 6.2.

Let $S$ be a linear relation in $\mathbb{C}^{n}$ with Weyr characteristic
$(W,A,B,C)$. If there exist matrices $E,F\in\mathbb{C}^{n\times m}$ such that
the range representation $FE^{-1}$ of the matrix pencil $P(s)=sE-F$ coincides
with $S$, then the Weyr characteristic $(w,a,b,c)$ of the pencil $P(s)$ is
given by

$w=W,\quad a=A,$

and if $B=(B_{1},\ldots,B_{n_{B}})$ and $C=(C_{1},\ldots,C_{n_{C}})$, then

$\displaystyle b$
$\displaystyle=(n-|W|-|A|-(|B|-B_{1})-|C|,B_{1},\ldots,B_{n_{B}}),\quad\text{and}$
$\displaystyle c$
$\displaystyle=(m-|W|-|A|-|B|-(|C|-C_{1}),C_{1},\ldots,C_{n_{C}}).$

######  Corollary 6.3.

Let $S$ be a linear relation in $\mathbb{C}^{n}$ and assume that its Weyr
characteristic is $(W,A,B,C)$. Then

$\displaystyle n=|W|+|A|+|B|+|C|$

is the smallest possible number of rows for matrices
$E,F\in\mathbb{C}^{n\times m}$ such that the range representation $FE^{-1}$ of
the matrix pencil $P(s)=sE-F$ coincides with $S$. In this case, the Weyr
characteristic $(w,a,b,c)$ of the pencil $P(s)$ is given by

$\displaystyle w=W,\quad a=A,$

and if $B=(B_{1},\ldots,B_{n_{B}})$ and $C=(C_{1},\ldots,C_{n_{C}})$, then

$\displaystyle b$
$\displaystyle=(B_{1},B_{1},B_{2},\ldots,B_{n_{B}}),\quad\text{and}$
$\displaystyle c$
$\displaystyle=(m-|W|-|A|-|B|-(|C|-C_{1}),C_{1},C_{2},\ldots,C_{n_{C}}).$

##  7 Rank one perturbations of matrix pencils via linear relations

There is a lot of recent work on low-rank perturbations of matrix pencils, see
e.g. [6, 17, 18, 19] for generic perturbation results and [3, 4, 5, 21, 24]
for non-generic perturbation results. The above mentioned non-generic results
are mainly based on the use of invariant factors and the concept of
majorization of finite sequences.

Here we follow a different approach. Our goal is to obtain perturbation
results for matrix pencils via the Weyr characteristic of their kernel or
range representations. Due to the results developed in the Sections 5 and 6
these Weyr characteristics can be deduced from the Weyr characteristic of the
underlying, unperturbed pencil. Recent results for perturbations of linear
relations [29] describe the change of the Weyr characteristic under
perturbations, and, again due to Sections 5 and 6, allow to give bounds for
the change of the Weyr characteristic of the perturbed matrix pencil. The
choice whether to use kernel or range representation depends on the appearance
of the rank-one pencil.

Along this section we consider two matrix pencils,

$\displaystyle P(s):=sE-F\quad\text{and}\quad Q(s):=sG-H,$

where $E,F,G,H\in\mathbb{C}^{n\times m}$, and assume that they are a rank one
perturbation of each other, i.e.

$\displaystyle\operatorname{rank}(P-Q)=1.$

Every rank one pencil in $\mathbb{C}^{n\times m}$ can be written in one of the
following ways:

$\displaystyle(su-v)w^{*}$ or (41) $\displaystyle w(su^{*}-v^{*}),$ (42)

where $(u,v)\in\mathbb{C}^{m}\times\mathbb{C}^{m}$, $(u,v)\neq(0,0)$ and
$w\in\mathbb{C}^{n}$, $w\neq 0$, see [24].

The following definition, taken from [2], specifies the idea of a rank-one
perturbation for linear relations.

######  Definition 7.1.

Let $S$ and $T$ be linear relations in a vector space $X$. Then $S$ is called
a rank one perturbation of $T$ (and vice versa) if

$\max\left\\{\dim\frac{S}{S\cap T},\,\dim\frac{T}{S\cap T}\right\\}=1.$

Before returning to matrix pencils, we prove a simple result on rank one
perturbations of linear relations.

######  Lemma 7.2.

Let $S$ and $T$ be linear relations in an $m$-dimensional vector space $X$.
Then, the following conditions are equivalent:

  * (a)

$S$ is a rank one perturbation of $T$;

  * (b)

$S^{-1}$ is a rank one perturbation of $T^{-1}$;

  * (c)

$S^{\bot}$ is a rank one perturbation of $T^{\bot}$.

###### Proof.

In order to prove the equivalences, it suffices to show that

$\displaystyle\dim\left(\frac{S}{S\cap T}\right)$
$\displaystyle=\dim\left(\frac{S^{-1}}{S^{-1}\cap
T^{-1}}\right)=\dim\left(\frac{T^{\bot}}{S^{\bot}\cap T^{\bot}}\right).$

for two linear relations $S$ and $T$ in $X$. It is easy to see that $(S\cap\
T)^{-1}=S^{-1}\cap T^{-1}$ and also $\dim S^{-1}=\dim S$. Hence,

$\displaystyle\dim\left(\frac{S^{-1}}{S^{-1}\cap T^{-1}}\right)$
$\displaystyle=\dim S^{-1}-\dim\big{(}S^{-1}\cap T^{-1}\big{)}=\dim
S-\dim\big{(}(S\cap T)^{-1}\big{)}$ $\displaystyle=\dim S-\dim(S\cap
T)=\dim\left(\frac{S}{S\cap T}\right).$

Since $X$ is finite dimensional, we have that

$S^{\bot}\cap T^{\bot}=\left\\{(x_{1}+x_{2},y_{1}+y_{2})\,:\,(x_{1},y_{1})\in
S,(x_{2},y_{2})\in T\right\\}^{\bot},$

and $\dim S^{\bot}\cap T^{\bot}=2m-\dim S-\dim T+\dim S\cap T$. Hence,

$\displaystyle\dim\left(\frac{T^{\bot}}{S^{\bot}\cap T^{\bot}}\right)$
$\displaystyle=\dim T^{\bot}-\dim S^{\bot}\cap T^{\bot}$ $\displaystyle=\dim
T^{\bot}-(2m-\dim S-\dim T+\dim S\cap T)$ $\displaystyle=\dim S-\dim S\cap
T=\dim\left(\frac{S}{S\cap T}\right).$

In the following lemma we show that rank one perturbations of matrix pencils
can always be reformulated as rank one perturbations of their kernel or of
their range representation.

######  Lemma 7.3.

Let $P(s)=sE-F$ and $Q(s)=sG-H$ be matrix pencils in $\mathbb{C}^{n\times m}$.

  * (a)

If $(Q-P)(s)$ is a rank one matrix pencil as in (42), then

$FE^{-1}\quad\mbox{and}\quad HG^{-1},$

either coincide or they are rank one perturbations of each other.

  * (b)

If $(Q-P)(s)$ is a rank one matrix pencil as in (41), then

$E^{-1}F\quad\mbox{and}\quad G^{-1}H,$

either coincide or they are rank one perturbations of each other.

###### Proof.

We first prove item (a). If $(Q-P)(s)$ is a rank one matrix pencil as in (42),
then $G=E+uw^{*}$ and $H=F+vw^{*}$. Hence,

$\displaystyle HG^{-1}=R\begin{bmatrix}G\\\
H\end{bmatrix}=R\begin{bmatrix}E+uw^{*}\\\ F+vw^{*}\end{bmatrix},$

i.e. $(x,y)\in HG^{-1}$ if and only if there exists $z\in\mathbb{C}^{m}$ such
that $x=(E+uw^{*})z$ and $y=(F+vw^{*})z$.

If $w^{*}z=0$ then $(x,y)\in(HG^{-1})\cap(FE^{-1})$. Therefore,

$\displaystyle HG^{-1}=(HG^{-1})\cap(FE^{-1})+{\rm
span\,}\\{(u_{0},v_{0})\\},$

where $u_{0}=Ew+(w^{*}w)u$ and $v_{0}=Fw+(w^{*}w)v$. Thus, the range
representations are rank one perturbations of each other, cf. Definition 7.1.

Now, if $(Q-P)(s)$ is a rank one matrix pencil as in (41), then

$\displaystyle
G^{-1}H=\left(E+wu^{*}\right)^{-1}(F+wv^{*})=N[F+wv^{*},-E-wu^{*}].$

Thus, the orthogonal complements of $E^{-1}F$ and $G^{-1}H$ are of the form

$\displaystyle(E^{-1}F)^{\bot}=R\begin{bmatrix}F^{*}\\\
-E^{*}\end{bmatrix}\quad\text{and}\quad(G^{-1}H)^{\bot}=R\begin{bmatrix}F^{*}+vw^{*}\\\
-E^{*}-uw^{*}\end{bmatrix},$

respectively, i.e. they are the range representations of the pencils
$\widetilde{P}(s)=sE^{*}+F^{*}$ and
$\widetilde{Q}(s)=s(F^{*}+vw^{*})+(E^{*}+uw^{*})$, which differ in a rank one
perturbation of the form (42). Applying item (a), they either coincide or they
are rank one perturbations of each other. Finally, by Lemma 7.2 we have that
$E^{-1}F$ and $G^{-1}H$ are rank one perturbations of each other.

The following theorem is the main result of this section. It describes the
change of (a part of) the Weyr characteristic of matrix pencils under rank-one
perturbations. Very similar results have been previously obtained for regular
pencils in [24, Proposition 4.1], see also [18, 25]; for singular pencils such
a result was given in [29, Section 7] but only for perturbations of the form
(41).

######  Theorem 7.4.

Given $E,F\in\mathbb{C}^{n\times m}$, assume that $\lambda\in\mathbb{C}$ is an
eigenvalue of the matrix pencil $P(s)=sE-F$ and denote by
$w(\lambda)=(w_{k}(\lambda))$, $a=(a_{k})$ and $b=(b_{k})$ the finite
sequences corresponding to the Weyr characteristic $(w,a,b,c)$ of the pencil
$P$. Assume also that $Q(s)$ is another matrix pencil in $\mathbb{C}^{n\times
m}$ such that $\operatorname{rank}(P-Q)=1$. Denote by
$\widetilde{w}(\lambda)=(\widetilde{w}_{k}(\lambda))$,
$\widetilde{a}=(\widetilde{a}_{k})$ and $\widetilde{b}=(\widetilde{b}_{k})$
the corresponding parts of the Weyr characteristic
$(\widetilde{w},\widetilde{a},\widetilde{b},\widetilde{c})$ of the pencil $Q$.

  * (a)

If $(Q-P)(s)=w(su^{*}-v^{*})$ as in (41) then, for each $k\geq 1$,

$\displaystyle|(w_{k}(\lambda)+b_{k})-(\widetilde{w}_{k}(\lambda)+\widetilde{b}_{k})|\leq
k,$ $\displaystyle|(a_{k}+b_{k})-(\widetilde{a}_{k}+\widetilde{b}_{k})|\leq
k.$

  * (b)

If $(Q-P)(s)=(su-v)w^{*}$ as in (42) then, for each $k\geq 1$,

$\displaystyle|(w_{k}(\lambda)+b_{k+1})-(\widetilde{w}_{k}(\lambda)+\widetilde{b}_{k+1})|\leq
k,$
$\displaystyle|(a_{k}+b_{k+1})-(\widetilde{a}_{k}+\widetilde{b}_{k+1})|\leq
k.$

  * (c)

If $P$ and $Q$ are regular then, for each $k\geq 1$,
$b_{k}=\widetilde{b}_{k}=0$ and also

$\displaystyle|w_{k}(\lambda)-\widetilde{w}_{k}(\lambda)|\leq
1\quad\text{and}\quad|a_{k}-\widetilde{a}_{k}|\leq 1,$

independently of the form of the rank one pencil $Q-P$.

###### Proof.

First we prove (a). Assume that $S:=E^{-1}F$ and
$T:=\left(E+wu^{*}\right)^{-1}(F+wv^{*})$ are the kernel representations
corresponding to the unperturbed $P$ and the perturbed pencil $Q$,
respectively. Due to Lemma 7.3, they either coincide or they are rank one
perturbations of each other. On the one hand, [29, Theorem 4.5] and Lemma 3.4
imply that

$\left|\big{(}W_{k}(S,\lambda)+B_{k}(S)\big{)}-\big{(}W_{k}(T,\lambda)+B_{k}(T)\big{)}\right|\leq
k,$

for each $k\geq 1$. Now the first statement in item (a) follows from Theorem
5.1, because $W_{k}(S,\lambda)=w_{k}(\lambda)$,
$W_{k}(T,\lambda)=\widetilde{w}_{k}(\lambda)$, $B_{k}(S)=b_{k}$ and
$B_{k}(T)=\widetilde{b}_{k}$.

On the other hand, by Lemma 3.5,
$A_{k}(S)+B_{k}(S)=\dim\frac{\operatorname{mul}(S^{k})}{\operatorname{mul}(S^{k-1})}$
and
$A_{k}(T)+B_{k}(T)=\dim\frac{\operatorname{mul}(T^{k})}{\operatorname{mul}(T^{k-1})}$.
Note that $\operatorname{mul}(S^{k})=N((S^{-1})^{k})$ and
$\operatorname{mul}(T^{k})=N((T^{-1})^{k})$ for every $k\geq 1$. Also, by
Lemma 7.3, $S^{-1}$ and $T^{-1}$ are rank one perturbations of each other.
Then, [29, Theorem 4.5] implies that

$\left|\big{(}A_{k}(S)+B_{k}(S)\big{)}-\big{(}A_{k}(T)+B_{k}(T)\big{)}\right|\leq
k,$

for each $k\geq 1$ and the second statement in item (a) also follows from
Theorem 5.1.

Item (b) is proved in a similar way, where Theorem 6.1 is used instead of
Theorem 5.1. Assume that $S:=FE^{-1}$ and
$T:=(F+vw^{*})\left(E+uw^{*}\right)^{-1}$ are the range representations
corresponding to the unperturbed $P$ and the perturbed pencil $Q$,
respectively. In this case $S$ and $T$ are again rank one perturbations of
each other, see Lemma 7.3. Then, applying [29, Theorem 4.5] and Lemma 3.4 we
get

$\left|\big{(}W_{k}(S,\lambda)+B_{k}(S)\big{)}-\big{(}W_{k}(T,\lambda)+B_{k}(T)\big{)}\right|\leq
k,$

for each $k\geq 1$. By Theorem 6.1, we have that
$W_{k}(S,\lambda)=w_{k}(\lambda)$,
$W_{k}(T,\lambda)=\widetilde{w}_{k}(\lambda)$, $B_{k}(S)=b_{k+1}$ and
$B_{k}(T)=\widetilde{b}_{k+1}$, and the first inequality in (b) follows.

Analogously, we can use [29, Theorem 4.5] to show that

$\left|\big{(}A_{k}(S)+B_{k}(S)\big{)}-\big{(}A_{k}(T)+B_{k}(T)\big{)}\right|\leq
k,\quad k\geq 1,$

and the second inequality follows again from Theorem 6.1.

Finally, if $P(s)=sE-F$ and $Q(s)=sG-H$ are regular then
$\mathcal{R}_{c}(E^{-1}F)=\mathcal{R}_{c}(FE^{-1})=\mathcal{R}_{c}(G^{-1}H)=\mathcal{R}_{c}(HG^{-1})=\\{0\\}$
and therefore $B_{k}=\widetilde{B}_{k}=0$ for all $k\geq 1$. From [29,
Corollary 4.6] and Lemma 3.4 we have

$\displaystyle|W_{k}(\lambda)-\widetilde{W}_{k}(\lambda)|\leq
1\quad\text{and}\quad|A_{k}(\lambda)-\widetilde{A}_{k}(\lambda)|\leq 1.$

Thus, (c) follows after applying Theorem 5.1 if $Q-P$ is as in (41) and
Theorem 5.1 if $Q-P$ is as in (42), respectively.

##  Appendix A Invariant characteristics of matrix pencils

In the following, we recall some basic definitions and results for matrix
pencils and use the opportunity to fix some notation. Given a pair of matrices
$E,F\in\mathbb{C}^{n\times m}$, the matrix pencil

$P(s):=sE-F,\quad s\in\mathbb{C},$

is called _singular_ if one of the following conditions holds: $n\neq m$ or
$n=m$ and $\det(P(s))=0$ for all $s\in\mathbb{C}$. Otherwise the pencil is
called _regular_.

The _rank(or normal rank)_ of the pencil $P$ is the largest possible size of a
regular submatrix pencil of $P(s)$. We denote it by $\operatorname{rank}(P)$.

######  Definition A.1 ([36]).

A complex number $\lambda$ is a _finite eigenvalue_ of $P(s)=sE-F$, if the
rank of the matrix $P(\lambda)$ is less than $\operatorname{rank}(P)$. In
addition, $\infty$ is an eigenvalue of $P$ if zero is an eigenvalue of the
dual pencil $sF-E$.

Assume that $P_{1}$ and $P_{2}$ are two matrix pencils. They are called
strictly equivalent if there are invertible matrices $U\in\mathbb{C}^{n\times
n}$ and $V\in\mathbb{C}^{m\times m}$ such that $P_{2}(s)=UP_{1}(s)V$ for all
$s\in\mathbb{C}$.

Recall that every pencil $P(s)=sE-F$ is strictly equivalent to its Kronecker
canonical form, see e.g. [12, 13, 22]. To introduce this form the following
notation is used: for $k\in\mathbb{N}$ consider the square matrices

$\displaystyle N_{k}:=\left[\begin{array}[]{cccc}0&&&\\\ 1&0&&\\\
&\ddots&\ddots&\\\ &&1&0\end{array}\right]\in\mathbb{C}^{k\times k}.$

For a multi-index $\alpha=(\alpha_{1},\ldots,\alpha_{l})\in\mathbb{N}^{l}$
with absolute value $|\alpha|:=\sum_{i=1}^{l}\alpha_{i}$, define the block
diagonal matrix

$\displaystyle N_{\alpha}:={\rm
diag\,}(N_{\alpha_{1}},\ldots,N_{\alpha_{l}})\in\mathbb{C}^{|\alpha|\times|\alpha|}.$
(43)

On the other hand, for $k\in\mathbb{N}$, $k>1$, consider the rectangular
matrices

$\displaystyle K_{k}=\left[\begin{smallmatrix}&&&\\\ 1&0&&\\\
&\ddots&\ddots&&\\\ &&1&0\\\ \end{smallmatrix}\right],\
L_{k}=\left[\begin{smallmatrix}&&&\\\ 0&1&&\\\ &\ddots&\ddots&&\\\ &&0&1\\\
\end{smallmatrix}\right]\in\mathbb{C}^{(k-1)\times k}.$

For some multi-index
${\bf\alpha}=(\alpha_{1},\ldots,\alpha_{l})\in\mathbb{N}^{l}$ with
$\alpha_{j}>1$ for all $j=1,\ldots,l$, we define the block quasidiagonal
matrices

$\displaystyle K_{\alpha}:={\rm
diag\,}(K_{\alpha_{1}},\ldots,K_{\alpha_{l}}),\ L_{\alpha}:={\rm
diag\,}(L_{\alpha_{1}},\ldots,L_{\alpha_{l}})\in\mathbb{C}^{(|\alpha|-l)\times|\alpha|}.$

One extends the above notion to multi-indices
$\alpha=(\alpha_{1},\ldots,\alpha_{l})\in\mathbb{N}^{l}$ where some (but not
all) entries are equal to $1$ by adding a zero column at every position where
an entry in $\alpha$ is equal to one. As an example consider

$\displaystyle
K_{(2,1)}:=\begin{bmatrix}1&0&0\end{bmatrix}\quad\mbox{and}\quad
K_{(3,2,1,1)}:=\begin{bmatrix}1&0&0&0&0&0&0\\\ 0&1&0&0&0&0&0\\\
0&0&0&1&0&0&0\end{bmatrix}.$

The case that all entries in $\alpha$ are equal to one may also occur, for a
more detailed exposition of the corresponding definitions for $K_{\alpha}$ and
$L_{\alpha}$ see, e.g., [14]. In this case, if $sE_{0}-F_{0}$ with
$E_{0},F_{0}\in\mathbb{C}^{n_{0}\times n_{0}}$, and
$(1,\ldots,1)\in\mathbb{N}^{l}$ then the block diagonal pencil is defined as
follows

$\begin{bmatrix}sE_{0}-F_{0}&0\\\
0&sK_{(1,\ldots,1)}-L_{(1,\ldots,1)}\end{bmatrix}:=\begin{bmatrix}sE_{0}-A_{0},0_{n_{0}\times
l}\end{bmatrix}$

and, correspondingly,

$\begin{bmatrix}sE_{0}-F_{0}&0\\\
0&sK^{\top}_{(1,\ldots,1)}-L^{\top}_{(1,\ldots,1)}\end{bmatrix}:=\begin{bmatrix}sE_{0}-A_{0}\\\
0_{l\times n_{0}}\end{bmatrix}.$ (44)

According to Kronecker [27], for a matrix pencil $P(s)=sE-F$ there exist
invertible matrices $U\in\mathbb{C}^{m\times m}$ and $V\in\mathbb{C}^{n\times
n}$ such that $V(sE-F)U$ has a block quasi-diagonal form

$\displaystyle V(sE-F)U=\begin{bmatrix}sI_{n_{0}}-J_{0}&0&0&0\\\
0&sN_{\alpha}-I_{|\alpha|}&0&0\\\ 0&0&sK_{\beta}-L_{\beta}&0\\\
0&0&0&sK_{\gamma}^{\top}-L_{\gamma}^{\top}\end{bmatrix}$ (45)

for some $J_{0}\in\mathbb{C}^{n_{0}\times n_{0}}$ in Jordan normal form, which
is unique up to a permutation of its Jordan blocks, and multi-indices
$\alpha\in\mathbb{N}^{n_{\alpha}}$, $\beta\in\mathbb{N}^{n_{\beta}}$,
$\gamma\in\mathbb{N}^{n_{\gamma}}$ which are unique up to a permutation of
their entries, see [27] and also [22, Chapter XII] or [28]. For our purposes
it is important to sort the entries of the multi-indices and the Jordan blocks
in $J_{0}$ non-increasingly.

The entries in the Segre characteristic $s(J_{0};\lambda)$ of an eigenvalue
$\lambda$ of $J_{0}$ are called the _degrees of the finite elementary
divisors_ associated to the matrix pencil $P(s)=sE-F$, see e.g. [12, 22]. The
entries of the multi-index $\alpha$ are called the _degrees of the infinite
elementary divisors_. The _column minimal indices_ are defined by
$\varepsilon_{i}=\beta_{i}-1$ for $i=1,\ldots,n_{\beta}$, and
$\eta_{j}=\gamma_{j}-1$ ($j=1,\ldots,n_{\gamma}$) are called the _row minimal
indices_ , cf. [12, 22].

## References

  * [1] R. Arens, Operational calculus of linear relations, Pacific J. Math. 11 (1961), 9–23.
  * [2] T.Ya. Azizov, J. Behrndt, P. Jonas, and C. Trunk, Compact and finite rank perturbations of linear relations in Hilbert spaces, Integral Equations Operator Theory 63 (2009), 151–163.
  * [3] I. Baragaña, M. Dodig, A. Roca, and M. Stošić, Bounded rank perturbations of regular pencils over arbitrary fields, Linear Algebra Appl. 601 (2020), 180–188.
  * [4] I. Baragaña and A. Roca, _Weierstrass structure and eigenvalue placement of regular matrix pencils under low rank perturbations_ , SIAM J. Matrix Anal. Appl. 40 (2019), pp. 440–453.
  * [5] I. Baragaña and A. Roca, Rank-one perturbations of matrix pencils, Linear Algebra Appl. 606 (2020), 170–191.
  * [6] L. Batzke, Generic rank-one perturbations of structured regular matrix pencils, Linear Algebra Appl. 458 (2014), 638–670.
  * [7] P. Benner and R. Byers, Evaluating products of matrix pencils and collapsing matrix products, Numer. Linear Algebra Appl. 8 (2001), 357–380.
  * [8] P. Benner and R. Byers, An arithmetic for matrix pencils: theory and new algorithms, Numer. Math. 103 (2006), 539–573.
  * [9] T. Berger, H. de Snoo, C. Trunk, and H. Winkler, Linear relations and their singular chains, to appear in: Methods Funct. Anal. Topol.
  * [10] T. Berger, H. de Snoo, C. Trunk, and H. Winkler, On a Jordan-like decomposition for linear relations in finite dimensional spaces, submitted.
  * [11] T. Berger, H. Gernandt, C. Trunk, H. Winkler, and M. Wojtylak, The gap distance to the set of singular matrix pencils, Linear Algebra Appl. 564 (2019), 28–57.
  * [12] T. Berger and S. Trenn, The quasi-Kronecker form for matrix pencils, SIAM J. Matrix Anal. Appl. 33 (2012), 336–368.
  * [13] T. Berger and S. Trenn, Addition to “The quasi-Kronecker form for matrix pencils”, SIAM J. Matrix Anal. Appl. 34 (2013), 94–101.
  * [14] T. Berger, C. Trunk, and H. Winkler, Linear relations and the Kronecker canonical form, Linear Algebra Appl. 488 (2016), 13–44.
  * [15] Y. Chen and W. Respondek, Geometric Analysis of Differential-Algebraic Equations via Linear Control Theory, SIAM J. Control Optim. 59 (2021), 103–130.
  * [16] R. Cross, Multivalued Linear Operators, Monographs and Textbooks in Pure and Applied Mathematics 213, Marcel Dekker, Inc., New York, 1998.
  * [17] F. De Terán and F. Dopico, Low rank perturbation of Kronecker structures without full rank, SIAM J. Matrix Anal. Appl. 29 (2007), 496–529.
  * [18] F. De Terán, F. Dopico and J. Moro, Low rank perturbation of Weierstrass structure, SIAM J. Matrix Anal. Appl. 30 (2008), 538–547.
  * [19] F. De Terán and F. Dopico, Generic change of the partial multiplicities of regular matrix pencils under low-rank perturbations, SIAM J. Matrix Anal. Appl. 37 (2016), 823–835.
  * [20] A. Dijksma and H.S.V. de Snoo, Symmetric and selfadjoint relations in Krein spaces II. Ann. Acad. Sci. Fenn. Math. 12 (1987), 199–216.
  * [21] M. Dodig and M. Stošić, Rank One Perturbations of Matrix Pencils, SIAM J. Matrix Anal. Appl. 41, 1889-1911.
  * [22] F. Gantmacher, Theory of Matrices, Chelsea, New York, 1959.
  * [23] H. Gernandt, N. Moalla, F. Philipp, W. Selmi, C. Trunk, Invariance of the Essential Spectra of Operator Pencils. Operator Theory: Advances and Applications 278. Birkhäuser, Cham, 2020.
  * [24] H. Gernandt and C. Trunk, Eigenvalue placement for regular matrix pencils under rank one perturbations, SIAM J. Matrix Anal. Appl. 38 (2017), 134–154.
  * [25] H. Gernandt and C. Trunk, The spectrum and the Weyr characteristics of operator pencils and linear relations, Syphax Journal of Mathematics: Nonlinear Analysis, Operator and Systems 1 (2021), 73–89.
  * [26] N. Karcanis and G. Kalogeropoulos, On the Segré, Weyr characteristic of right (left) regular matrix pencils, Int. J. of Control 44.4 (1986), 991-1015.
  * [27] L. Kronecker, Algebraische Reduction der Schaaren bilinearer Formen, Sitzungsber. Akad. Berlin (1890), 1225–-1237.
  * [28] P. Kunkel and V. Mehrmann, Differential-Algebraic Equations. Analysis and Numerical Solution, EMS Publishing House, Zürich 2006.
  * [29] L. Leben, F. Martinez Peria, F. Philipp, C. Trunk and H. Winkler, Finite rank perturbations of linear relations and singular matrix pencils, Complex Anal. Oper. Theory 15 (2021) 37.
  * [30] R. Lippert and G. Strang, The Jordan forms of AB and BA, Electron. J. Linear Algebra 18 (2009), 281–288.
  * [31] C.C. MacDuffee, The Theory of Matrices, Springer, Berlin, 1933.
  * [32] A. Sandovici, H.S.V. de Snoo, and H. Winkler, The structure of linear relations in Euclidean spaces, Linear Algebra Appl. 397 (2005), 141–169.
  * [33] A. Sandovici, H.S.V. de Snoo, and H. Winkler Ascent, descent, nullity, defect, and related notions for linear relations in linear spaces, Linear Algebra Appl. 423 (2007), 456–497.
  * [34] H. Shapiro, Linear Algebra and Matrices. Topics for a Second Course, Providence, RI: American Mathematical Society (AMS), 2015.
  * [35] H. Shapiro, The Weyr Characteristic, American Mathematical Monthly 106 (1999), 919-929.
  * [36] J.G. Sun, Orthogonal projections and the perturbation of the eigenvalues of singular pencils, J. Comput. Math. 1 (1983), 63-–74.