# Eigenstructure perturbations for a class of Hamiltonian matrices and
solutions of related Riccati inequalities

Volker Mehrmann 111Institut für Mathematik, MA 4-5, TU Berlin, Str. des 17.
Juni 136, D-10623 Berlin, FRG<EMAIL_ADDRESS> Hongguo Xu 222
Department of Mathematics, University of Kansas, Lawrence, KS 44045, USA.
<EMAIL_ADDRESS>
###### Abstract

The characterization of the solution set for a class of algebraic Riccati
inequalities is studied. This class arises in the passivity analysis of linear
time invariant control systems. Eigenvalue perturbation theory for the
Hamiltonian matrix associated with the Riccati inequality is used to analyze
the extremal points of the solution set.

Keywords Kalman-Yacubovich-Popop-inequality, Riccati equation, Riccati
inequality, Hamiltonian matrix, Lagrangian invariant subspace, eigenvalue
perturbations.

AMS subject classification. 65F15, 65H10, 93D15

##  1 Introduction

We study the solution set of a class of algebraic Riccati inequalities (ARI)

$F^{H}X+XF+XGX+K\leq 0,$ (1)

as well as the related algebraic Riccati equations (ARE) of the form

$F^{H}X+XF+XGX+K=0.$ (2)

We consider the special class of problems with $0\leq
G=G^{H}\in\mathbb{C}^{n\times n}$, $0\leq K=K^{H}\in\mathbb{C}^{n\times n}$,
and $F\in\mathbb{C}^{n\times n}$, where $\mathbb{C}^{n\times m}$ denotes the
set of complex $n\times m$ matrices and $G>0$ ($G\geq 0$) denotes that $G$ is
positive definite (semidefinite).

The main goal of this paper is to characterize the set of positive definite
solutions of (1) and (2) and we do this by studying the perturbation theory
for the eigenstructure of the associated _Hamiltonian matrix_

$H=\left[\begin{array}[]{cc}F&G\\\ -K&-F^{H}\end{array}\right],$ (3)

formed from the coefficients, which satisfies $(JH)^{H}=JH$ for
$J=\left[\begin{array}[]{cc}0&I\\\ -I&0\end{array}\right].$

Our study of the solvability of (1) and (2) is motivated by the passivity
analysis of linear time-invariant systems

$\begin{array}[]{c}\dot{x}\ =\ A\,x+B\,u,\\\\[2.84526pt] y\ =\
C\,x+D\,u,\end{array}$ (4)

with $A\in\mathbb{C}^{n\times n}$, $B\in\mathbb{C}^{n\times m}$,
$C\in\mathbb{C}^{m\times n}$, and $D\in\mathbb{C}^{m\times m}$.

A system of the form (4) is called _(impedance) passive_ if there exists a
continuously differentiable _storage function_
${\mathcal{H}}:\mathbb{C}^{n}\rightarrow[0,\infty)$ such that the _dissipation
inequality_

${\mathcal{H}}(x(t_{1}))-{\mathcal{H}}(x(t_{0}))\leq\int_{t_{0}}^{t_{1}}y(t)^{T}u(t)\
dt,$ (5)

holds for all admissible inputs $u$.

For system of the form (4) that are _minimal_ , i.e. both _controllable_ and
_observable_ , the classical theorem of [21] characterizes passivity.

###### Theorem 1

Assume that the system (4) is minimal. The matrix inequality

$\left[\begin{array}[]{cr}A^{T}X+XA&XB-C^{H}\\\\[5.69054pt]
B^{H}X-C&-(D+D^{H})\end{array}\right]\leq 0$ (6)

has a solution $X=X^{H}>0$ if and only if (4) is a _passive_ system. In this
case ${\mathcal{H}}(x)=\frac{1}{2}x^{T}Xx$ defines a storage function for (4)
associated with the supply rate $y^{T}u$, satisfying (5).

Furthermore, for passive systems there exist maximum and minimum Hermitian
solutions to (6) satisfying $0<X_{-}\leq X_{+}$ such that for all Hermitian
solutions $X$ to (6), $X_{-}\leq X\leq X_{+}$.

If the matrix $D+D^{H}$ in (6) is positive definite, then (using Schur
complements) $X$ is a positive definite solution of (6) if and only if it is a
positive definite solution of (1) with

$F:=A-B(D+D^{H})^{-1}C^{H},\ G:=B(D+D^{H})^{-1}B^{H},\
K:=C^{H}(D+D^{H})^{-1}C.$ (7)

The same argument applies to the equality case (2).

The solvability of (1) is well understood, see e.g. [5], and the same holds
for (2), see e.g. [10]. However, in most cases the study is motivated from
linear quadratic optimal control theory [13], where the quadratic term has a
negative sign, while here we study the case where the sign is positive.

A second motivation arises from energy based modeling of passive systems via
_port-Hamiltonian (pH)_ systems. See [15] for a detailed survey on pH systems
covering also the case of descriptor systems.

A linear time invariant _port-Hamiltonian (pH) system_ has the form

$\begin{array}[]{rcl}\dot{x}&=&(J-R)Qx+(\hat{B}-\hat{P})u,\\\
y&=&(\hat{B}+\hat{P})^{H}Qx+Du,\end{array}$ (8)

with $Q=Q^{H}>0$, $J=-J^{H}$, $0\leq
W^{H}=W:=\left[\begin{array}[]{lc}R&\hat{P}\\\
\hat{P}^{H}&S\end{array}\right]$, with $S=\frac{1}{2}(D+D^{H})$.

It is well-known, see e.g. [2], that if $X=X^{H}>0$ is a solution of (2) then
multiplication of (4) from the left by $X^{\frac{1}{2}}$ and a change of
variable $\xi=X^{\frac{1}{2}}x$ leads to the pH formulation

$\displaystyle\dot{\xi}$ $\displaystyle=$ $\displaystyle
X^{\frac{1}{2}}AX^{-\frac{1}{2}}\xi+X^{\frac{1}{2}}Bu=(J-R)\xi+(\hat{B}-\hat{P})u,$
(9) $\displaystyle y$ $\displaystyle=$ $\displaystyle
CX^{-\frac{1}{2}}\xi+Du=(\hat{B}+\hat{P})^{H}\xi+(S+N)u,$

with
$J=\frac{1}{2}(X^{\frac{1}{2}}AX^{-\frac{1}{2}}-X^{-\frac{1}{2}}A^{H}X^{\frac{1}{2}})$,
$R=\frac{1}{2}(X^{\frac{1}{2}}AX^{-\frac{1}{2}}+X^{-\frac{1}{2}}A^{H}X^{\frac{1}{2}})$,
$\hat{B}=\frac{1}{2}(X^{-\frac{1}{2}}B+X^{-\frac{1}{2}}C^{H})$,
$\hat{P}=\frac{1}{2}(-X^{-\frac{1}{2}}B+X^{-\frac{1}{2}}C^{H})$,
$S=\frac{1}{2}(D+D^{H})$, $N=\frac{1}{2}(D-D^{H})$, and $Q=I$.

In this way any positive definite solution $X$ of (2) leads to a pH
representation of the system. This immediately raises the question which
solution of (2) leads to a robust or even optimally robust representation (9).
This has been the topic of several recent papers, see [1, 8, 14]. To answer
this question, it is essential to characterize the set of positive definite
solutions of (6) and thus this question as well motivates our work.

A classical approach to solve (2) is to compute $n$-dimensional _Lagrangian
invariant subspaces_ of the Hamiltonian matrix (3), i.e. subspaces satisfying

$\left[\begin{array}[]{cc}F&G\\\
-K&-F^{H}\end{array}\right]\left[\begin{array}[]{c}W_{1}\\\
W_{2}\end{array}\right]=\left[\begin{array}[]{c}W_{1}\\\
W_{2}\end{array}\right]T,$ (10)

where $T\in\mathbb{C}^{n\times n}$ and $W_{1}^{H}W_{2}=W_{2}^{H}W_{1}$.

If $W_{1}$ is invertible then $X=W_{2}W_{1}^{-1}$ is a Hermitian solution of
(2) and the different solutions can be characterized by the choice of the
Lagrangian invariant subspace which depends on the selection of the spectrum
of $T$, see [7] for a complete characterization of the set of Lagrangian
subspaces of $H$. This solution set is particularly complicated if the matrix
$H$ has purely imaginary eigenvalues, because in this case the approach to
solve (2) via the numerical calculation of the Lagrangian invariant subspaces
as in (10) may not be feasible. It may happen that either Lagrangian invariant
subspaces do not exist or the matrix $W_{1}$ is not invertible, see [7, 10,
13] for a detailed analysis under controllability, observability,
stabilizability, and detectability conditions. An approach that can deal with
possible limiting situations where eigenvalues of (3) are on the imaginary is
the use of Newton’s method, see [4, 9].

In this paper we study the Riccati equations (2) and inequalities (1) arising
in the passivity analysis, where both $G$ and $K$ are positive semidefinite.
We derive the perturbation theory for the invariant subspaces in (10), and
extend in particular the perturbation theory of [16].

The paper is organized as follows. In Section 2 we recall and extend some
known results on the positive definiteness of solutions of the ARE (2) and the
notation.

Section 3 then studies the behavior of the eigenvalues of the Hamiltonian
matrix that is obtained when the ARE is perturbed by a positive semidefinite
constant term.

##  2 Classical solution theory

In this section we present the notation and recall some well-known results on
the solvability of (1) and (2).

A pair of matrices $A\in\mathbb{C}^{n\times n}$, $B\in\mathbb{C}^{n\times m}$
is called _controllable_ if $\mathop{\rm
rank}\nolimits\left[\begin{array}[]{cc}sI-A&B\end{array}\right]=n$ for all
$s\in\mathbb{C}$, and a pair of matrices $A\in\mathbb{C}^{n\times n}$,
$C\in\mathbb{C}^{p\times n}$ is called _observable_ if $\mathop{\rm
rank}\nolimits\left[\begin{array}[]{c}sI-A\\\ C\end{array}\right]=n$ for all
$s\in\mathbb{C}$. For our analysis it will be very important to identify
controllable as well observable subspaces, because the solution of (1) and (2)
will turn out only to be nonsingular and therefore positive definite in these
subspaces.

These subspaces can be obtained via a Kalman decomposition under unitary
transformations. The following result is well-known [18], but we present a
proof in our notation because it will be useful for our analysis.

###### Proposition 1

For matrices $F,G,K$ as in (7) there exists a unitary matrix $U$ such that

$\displaystyle U^{H}FU$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cc|c}\widetilde{F}_{11}&0&\widetilde{F}_{13}\\\
\widetilde{F}_{21}&\widetilde{F}_{22}&\widetilde{F}_{23}\\\ \hline\cr
0&0&\widetilde{F}_{33}\end{array}\right]=:\left[\begin{array}[]{cc}F_{11}&F_{12}\\\
0&F_{22}\end{array}\right]$ $\displaystyle U^{H}GU$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cc|c}\widetilde{G}_{11}&\widetilde{G}_{21}^{H}&0\\\
\widetilde{G}_{21}&\widetilde{G}_{22}&0\\\ \hline\cr
0&0&0\end{array}\right]=:\left[\begin{array}[]{cc}G_{11}&0\\\
0&0\end{array}\right]$ $\displaystyle U^{H}KU$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cc|c}\widetilde{K}_{11}&0&\widetilde{K}_{31}^{H}\\\
0&0&0\\\
\hline\cr\widetilde{K}_{31}&0&\widetilde{K}_{33}\end{array}\right]=:\left[\begin{array}[]{cc}K_{11}&K_{21}^{H}\\\
K_{21}&K_{22}\end{array}\right],$

where $(F_{11},G_{11})$ and $(\widetilde{F}_{11},\widetilde{G}_{11})$ are
controllable, and $(\widetilde{F}_{11},\widetilde{K}_{11})$ is observable.

Proof. The proof that $(F_{11},G_{11})$ is controllable and
$(\widetilde{F}_{11},\widetilde{K}_{11})$ is observable follows from the
computation of the staircase form of
$\left[\begin{array}[]{cc}F&G\end{array}\right]$ and
$\left[\begin{array}[]{cc}F_{11}^{H}&K_{11}\end{array}\right]$, see [18].

Since $G\geq 0$, so is $G_{11}$, which implies that
$(\widetilde{F}_{11},\widetilde{G}_{11})$ is controllable. To see this,
suppose that $(\widetilde{F}_{11},\widetilde{G}_{11})$ is not controllable.
Then there exists a nonzero vector $x$ and a scalar $\lambda$ such that
$x^{H}(\lambda I-\widetilde{F}_{11})=0$ and $x^{H}\widetilde{G}_{11}=0$. Then
$x^{H}\widetilde{G}_{12}=0$ as well. If this was not the case, then for
$y=\widetilde{G}_{12}^{H}x$, we have

$\left[\begin{array}[]{cc}x&0\\\
0&y^{H}\end{array}\right]G_{11}\left[\begin{array}[]{cc}x&0\\\
0&y\end{array}\right]=\left[\begin{array}[]{cc}0&|\\!|y|\\!|_{2}^{2}\\\
|\\!|y|\\!|_{2}^{2}&y^{H}\widetilde{G}_{22}y\end{array}\right],$

which is indefinite, contradicting the positive semi-definiteness of $G_{11}$.
Thus

$\left[\begin{array}[]{c}x\\\
0\end{array}\right]^{H}\left[\begin{array}[]{cc}\lambda
I-F_{11}&G_{11}\end{array}\right]=0,$

which contradicts the controllability of $(F_{11},G_{11})$.

###  2.1 Solvability of algebraic Riccati equations

In order to characterize the existence of positive definite (positive
semidefinite) solutions of (1) and (2), we have to identify what happens in
the uncontrollable and unobservable subspaces.

To study this, let $U$ be the unitary matrix in Proposition 1 and let
$U^{H}XU=\left[\begin{array}[]{cc}X_{11}&X_{21}^{H}\\\
X_{21}&X_{22}\end{array}\right]$. Multiplying both (1) and (2) from the left
by $U^{H}$ and from the right by $U$, the Riccati operator on the left sides
takes the form $\left[\begin{array}[]{cc}\Phi_{11}&\Phi_{21}^{H}\\\
\Phi_{21}&\Phi_{22}\end{array}\right]$, with

$\displaystyle\Phi_{11}$ $\displaystyle=$ $\displaystyle
F_{11}^{H}X_{11}+X_{11}F_{11}+X_{11}G_{11}X_{11}+K_{11},$
$\displaystyle\Phi_{21}$ $\displaystyle=$ $\displaystyle
X_{21}(F_{11}+G_{11}X_{11})+F_{22}^{H}X_{21}+F_{12}^{H}X_{11}+K_{21},$
$\displaystyle\Phi_{22}$ $\displaystyle=$ $\displaystyle
F_{22}^{H}X_{22}+X_{22}F_{22}+F_{12}^{H}X_{21}^{H}+X_{21}F_{12}+X_{21}G_{11}X_{21}^{H}+K_{22}.$

For (1), respectively (2), to have a positive definite solution $X$ it is
necessary that $\Phi_{11}\leq 0$, respectively, $\Phi_{11}=0$ has a positive
definite solution $X_{11}$, respectively. The latter is equivalent to the
condition that $\Psi\leq 0$, respectively $\Psi=0$, has a positive definite
solution $Y$, where $\Psi$ is the _dual Riccati operator_ defined by

$\Psi=F_{11}Y+YF_{11}^{H}+YK_{11}Y+G_{11}.$

Using the block structures of $F_{11},K_{11},G_{11}$ given in Proposition 1,
and partitioning $Y=\left[\begin{array}[]{cc}Y_{11}&Y_{21}^{H}\\\
Y_{21}&Y_{22}\end{array}\right]$, one has

$\Psi=\left[\begin{array}[]{cc}\Psi_{11}&\Psi_{21}^{H}\\\
\Psi_{21}&\Psi_{22}\end{array}\right],$

where

$\Psi_{11}=\widetilde{F}_{11}Y_{11}+Y_{11}\widetilde{F}_{11}^{H}+Y_{11}\widetilde{K}_{11}Y_{11}+\widetilde{G}_{11}.$

Its dual operator is

$\widetilde{\Phi}_{11}=\widetilde{F}_{11}^{H}\widetilde{X}_{11}+\widetilde{X}_{11}\widetilde{F}_{11}+\widetilde{X}_{11}\widetilde{G}_{11}\widetilde{X}_{11}+\widetilde{K}_{11}.$

As shown in [3], a necessary condition for (1), respectively (2), to have a
positive definite solution is that $\widetilde{\Phi}_{11}\leq 0$ or
$\widetilde{\Phi}_{11}=0$ has a positive definite solution. Recall that
$(\widetilde{F}_{11},\widetilde{G}_{11})$ is controllable and
$(\widetilde{F}_{11},\widetilde{K}_{11})$ is observable. In the following we
therefore mainly consider the matrix triples $(F,G,K)$ where these properties
hold.

The ARE (2) is associated with the Hamiltonian matrix (3). Now suppose that
the columns of $W=\left[\begin{array}[]{c}W_{1}\\\
W_{2}\end{array}\right]\in\mathbb{C}^{2n\times n}$ are orthonormal and span a
_Lagrangian invariant subspace_ , i.e.

$HW=WT_{11},\quad W^{H}W=I,\quad W^{H}JW=0$ (14)

for some matrix $T_{11}\in\mathbb{C}^{n\times n}$. Then

$Q=\left[\begin{array}[]{cc}W_{1}&-W_{2}\\\ W_{2}&W_{1}\end{array}\right]$

is unitary and symplectic, i.e., $Q^{H}Q=I$ and $Q^{H}JQ=J$, and

$Q^{H}HQ=\left[\begin{array}[]{cc}T_{11}&T_{12}\\\
0&-T_{11}^{H}\end{array}\right]$ (15)

is a Hamiltonian Schur form of $H$. Note that if $H$ is real then $Q$ can be
chosen to be real orthogonal so that $H$ has a real Hamiltonian Schur form,
see [12].

######  Lemma 2 ([3, 10])

Suppose that the Hamiltonian matrix (3) has a Lagrangian invariant subspace,
i.e., there exist square matrices $W_{1}$, $W_{2}$, $T$ such that (14) holds.

If the pair $(F,G)$ is controllable then $W_{1}$ is invertible, and if $(F,K)$
is observable then $W_{2}$ is invertible.

We have the following characterization when all solutions of (2) are positive
definite, see [20]. For completeness, we present a proof in our notation.

###### Lemma 3

All solutions of the ARE (2) are positive definite if and only if the pair
$(F,G)$ is controllable, the pair $(F,K)$ is observable, and $F$ is
asymptotically stable, i.e., every eigenvalue of $F$ has a negative real part.

Proof. Lemma 2 shows the controllability of $(F,G)$ and the observability of
$(F,K)$ ensures the existence of invertible solutions and the asymptotic
stability of $F$ guarantees the positive definiteness of the solutions. For
necessity, without loss of generality we set

$F=\left[\begin{array}[]{cc}F_{11}&0\\\ F_{21}&F_{22}\end{array}\right],\quad
G=\left[\begin{array}[]{cc}G_{11}&G_{21}^{H}\\\
G_{21}&G_{22}\end{array}\right],\quad K=\left[\begin{array}[]{cc}K_{11}&0\\\
0&0\end{array}\right],$

where $(F_{11},K_{11})$ is observable. If
$X=\left[\begin{array}[]{cc}X_{11}&X_{21}^{H}\\\
X_{21}&X_{22}\end{array}\right]$ is a positive definite solution, then
$X_{22}$ is positive definite as well. With

$Y=\left[\begin{array}[]{cc}I&-X_{21}^{H}X_{22}^{-1}\\\ 0&I\end{array}\right]$

we then have

$\widetilde{F}=Y^{-H}FY^{H}=:\left[\begin{array}[]{cc}F_{11}&0\\\
\widetilde{F}_{21}&F_{22}\end{array}\right],\quad\widetilde{G}=Y^{-H}GY^{-1}=:\left[\begin{array}[]{cc}G_{11}&\widetilde{G}_{21}^{H}\\\
\widetilde{G}_{21}&\widetilde{G}_{22}\end{array}\right]$

and

$\widetilde{X}=YXY^{H}=\left[\begin{array}[]{cc}\widetilde{X}_{11}&0\\\
0&X_{22}\end{array}\right],\quad\widetilde{K}=YKY^{H}=K.$

Since
$\widetilde{F}^{H}\widetilde{X}+\widetilde{X}\widetilde{F}+\widetilde{X}\widetilde{G}\widetilde{X}+\widetilde{K}=0$,
by comparing the blocks we have

$F_{11}^{H}\widetilde{X}_{11}+\widetilde{X}_{11}F_{11}+\widetilde{X}_{11}G_{11}\widetilde{X}_{11}+K_{11}=0$

and

$(\widetilde{F}_{21}^{H}+\widetilde{X}_{11}\widetilde{G}_{21}^{H})X_{22}=0,\quad
F_{22}^{H}X_{22}+X_{22}F_{22}+X_{22}\widetilde{G}_{22}X_{22}=0.$

Using $\widetilde{X}_{11}$, we are able to construct
$\widehat{X}=\left[\begin{array}[]{cc}\widetilde{X}_{11}&0\\\
0&0\end{array}\right]$ that solves (2) as well. However, $\widehat{X}$ is
singular and hence $(F,K)$ must be observable.

The matrix $X$ is a Hermitian positive definite solution of (2) if and only if
$Y=X^{-1}$ is a Hermitian positive definite solution of $FY+YF^{H}+YKY+G=0$.
We therefore conclude that $(F,G)$ must be controllable.

Finally, suppose that $\lambda$ is an eigenvalue of $F$ and $x$ is a
corresponding right eigenvector. Let $X$ be a positive definite solution of
(2). Then, since

$x^{H}(F^{H}X+XF+XGX+K)x=0,$

we have that

$(\lambda+\bar{\lambda})x^{H}Xx+x^{H}(XKX+K)x=0.$

Since $(F,K)$ is observable, we have that $Kx\neq 0$, and thus

$(\lambda+\bar{\lambda})x^{H}Xx=-x^{H}(XGX+K)x\leq-x^{H}Kx<0,$

which shows that $\lambda$ has a negative real part.

The following result is well-known.

######  Lemma 4 ([5, 10])

Suppose that $(F,G)$ is controllable and that $(F,K)$ is observable. Then (2)
is has a positive definite solution if and only if (1) has a positive definite
solution.

In this subsection we have summarized some preliminary results about the
existence of positive definite solutions of (2) and (1). In the next
subsection we discuss the construction of such solutions for (2) when $(F,G)$
is not controllable or $(F,K)$ is not observable.

###  2.2 Positive definite solutions of the ARE (2).

In this subsection we discuss the solution of the ARE (2) with $F$
asymptotically stable and $G=G^{H}\geq 0,K=K^{H}\geq 0$. We assume that the
system has been transformed similarly as in Proposition 1 just with the roles
of $G$ and $K$ exchanged, i.e.

$\displaystyle F$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cc|c}\widetilde{F}_{11}&\widetilde{F}_{12}&0\\\
0&\widetilde{F}_{22}&0\\\
\hline\cr\widetilde{F}_{21}&\widetilde{F}_{32}&\widetilde{F}_{33}\end{array}\right]=:\left[\begin{array}[]{cc}F_{11}&0\\\
F_{21}&F_{22}\end{array}\right]$ (21) $\displaystyle G$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cc|c}\widetilde{G}_{11}&0&\widetilde{G}_{31}^{H}\\\
0&0&0\\\
\hline\cr\widetilde{G}_{31}&0&\widetilde{G}_{33}\end{array}\right]=:\left[\begin{array}[]{cc}G_{11}&G_{21}^{H}\\\
G_{21}&G_{22}\end{array}\right],$ (27) $\displaystyle K$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cc|c}\widetilde{K}_{11}&\widetilde{K}_{21}^{H}&0\\\
\widetilde{K}_{21}&\widetilde{K}_{22}&0\\\ \hline\cr
0&0&0\end{array}\right]=:\left[\begin{array}[]{cc}K_{11}&0\\\
0&0\end{array}\right],$ (33)

where $(F_{11},K_{11})$ and $(\widetilde{F}_{11},\widetilde{K}_{11})$ are
observable, and $(\widetilde{F}_{11},\widetilde{G}_{11})$ is controllable.

Suppose that the ARE

$\widetilde{F}_{11}^{H}\widetilde{X}_{11}+\widetilde{X}_{11}\widetilde{F}_{11}+\widetilde{X}_{11}\widetilde{G}_{11}\widetilde{X}_{11}+\widetilde{K}_{11}=0$
(34)

has a solution $\widetilde{X}_{11}=\widetilde{X}_{11}^{H}$. Since
$(\widetilde{F}_{11},\widetilde{G}_{11})$ is controllable,
$(\widetilde{F}_{11},\widetilde{K}_{11})$ is observable and
$\widetilde{F}_{11}$ is asymptotically stable by Lemma 2, $\widetilde{X}_{11}$
is positive definite. Now we consider the Sylvester equation

$(\widetilde{F}_{11}+\widetilde{G}_{11}\widetilde{X}_{11})^{H}\widetilde{X}_{21}^{H}+\widetilde{X}_{21}^{H}\widetilde{F}_{22}+\widetilde{X}_{11}\widetilde{F}_{12}+\widetilde{K}_{21}^{H}=0.$

If $-(\widetilde{F}_{11}+\widetilde{G}_{11}\widetilde{X}_{11})^{H}$ and
$\widetilde{F}_{22}$ do not have common eigenvalues, then the Sylvester
equation has a unique solution $\widetilde{X}_{21}^{H}$. If
$-(\widetilde{F}_{11}+\widetilde{G}_{11}\widetilde{X}_{11})^{H}$ and
$\widetilde{F}_{22}$ share some common eigenvalues and the Sylvester equation
is consistent, then we may choose a solution $\widetilde{X}_{21}^{H}$ (from
infinitely many solutions). If it is not consistent, we need to choose a
$\widetilde{X}_{11}$ such that
$-(\widetilde{F}_{11}+\widetilde{G}_{11}\widetilde{X}_{11})^{H}$ and
$\widetilde{F}_{22}$ do not have the same eigenvalues. Note that
$\widetilde{F}_{22}$ is asymptotically stable and the eigenvalues of the
Hamiltonian matrix
$\left[\begin{array}[]{cc}\widetilde{F}_{11}&\widetilde{G}_{11}\\\
-\widetilde{K}_{11}&-\widetilde{F}_{11}^{H}\end{array}\right]$ corresponding
to (34) are those of $\widetilde{F}_{11}+\widetilde{G}_{11}\widetilde{X}_{11}$
and $-(\widetilde{F}_{11}+\widetilde{G}_{11}\widetilde{X}_{11})^{H}$. So it is
always possible to choose a solution $\widetilde{X}_{11}$ such that the common
eigenvalues (with negative real parts) are contained in
$\widetilde{F}_{11}+\widetilde{G}_{11}\widetilde{X}_{11}$, see [7]. With such
an $\widetilde{X}_{11}$ the Sylvester equation has a unique solution
$\widetilde{X}_{12}^{H}.$

Once we have determined $\widetilde{X}_{11}$ and $\widetilde{X}_{21}^{H}$,
since $\widetilde{F}_{22}$ is asymptotically stable, the Lyapunov equation

$\widetilde{F}_{22}^{H}\widetilde{X}_{22}+\widetilde{X}_{22}\widetilde{F}_{22}+\widetilde{F}_{12}^{H}\widetilde{X}_{21}^{H}+\widetilde{X}_{21}\widetilde{F}_{12}+\widetilde{X}_{21}\widetilde{G}_{11}\widetilde{X}_{21}^{H}+\widetilde{K}_{22}=0$

has a unique solution $\widetilde{X}_{22}$. Then the matrix
$X_{11}=\left[\begin{array}[]{cc}\widetilde{X}_{11}&\widetilde{X}_{21}^{H}\\\
\widetilde{X}_{21}&\widetilde{X}_{22}\end{array}\right]$ solves the ARE

$F_{11}^{H}X_{11}+X_{11}F_{11}+X_{11}G_{11}X_{11}+K_{11}=0.$ (35)

Since $(F_{11},K_{11})$ is observable, similar to the proof of Lemma 3 we can
show that $X_{11}>0$. Obviously, $\left[\begin{array}[]{cc}X_{11}&0\\\
0&0\end{array}\right]$ is a positive semidefinite solution of (2) with $F,G,K$
given in (27). The ARE (2) may or may not have positive definite solutions.
Suppose it has one. Then we express it as

$X=\left[\begin{array}[]{cc}I&Z\\\
0&I\end{array}\right]\left[\begin{array}[]{cc}X_{11}&0\\\
0&X_{22}\end{array}\right]\left[\begin{array}[]{cc}I&0\\\
Z^{H}&I\end{array}\right],\qquad X_{11}>0,\quad X_{22}>0.$ (36)

By premultiplying $\left[\begin{array}[]{cc}I&Z\\\ 0&I\end{array}\right]$ and
postmultiplying $\left[\begin{array}[]{cc}I&0\\\ Z^{H}&I\end{array}\right]$ to
(2), one has the ARE

$\displaystyle\left[\begin{array}[]{cc}F_{11}&0\\\
\widehat{F}_{21}&F_{22}\end{array}\right]^{H}\left[\begin{array}[]{cc}X_{11}&0\\\
0&X_{22}\end{array}\right]+\left[\begin{array}[]{cc}X_{11}&0\\\
0&X_{22}\end{array}\right]\left[\begin{array}[]{cc}F_{11}&0\\\
\widehat{F}_{21}&F_{22}\end{array}\right]$
$\displaystyle+\left[\begin{array}[]{cc}X_{11}&0\\\
0&X_{22}\end{array}\right]\left(\left[\begin{array}[]{cc}I&0\\\
Z^{H}&I\end{array}\right]G\left[\begin{array}[]{cc}I&Z\\\
0&I\end{array}\right]\right)\left[\begin{array}[]{cc}X_{11}&0\\\
0&X_{22}\end{array}\right]+\left[\begin{array}[]{cc}K_{11}&0\\\
0&0\end{array}\right]=0,$

where $\widehat{F}_{21}=F_{21}+Z^{H}F_{11}-F_{22}Z^{H}.$ From the $(1,1)$
block, $X_{11}$ has to be a positive definite solution of (35), which always
exists. From the $(1,2)$ block, one has

$(\widehat{F}_{21}^{H}+X_{11}(G_{11}Z+G_{21})^{H})X_{22}=0.$

Because $X_{22}>0$, it becomes the Sylvester equation

$(F_{11}+G_{11}X_{11})^{H}Z-ZF_{22}^{H}+F_{21}^{H}+X_{11}G_{21}^{H}=0.$ (39)

From the $(2,2)$ block, $X_{22}$ solves the ARE

$F_{22}^{H}X_{22}+X_{22}F_{22}+X_{22}(G_{22}+Z^{H}G_{21}^{H}+G_{21}Z+Z^{H}G_{11}Z)X_{22}=0.$
(40)

Since

$F_{11}+G_{11}X_{11}=\left[\begin{array}[]{cc}\widetilde{F}_{11}+\widetilde{G}_{11}\widetilde{X}_{11}&\widetilde{F}_{12}+\widetilde{G}_{11}\widetilde{X}_{21}^{H}\\\
0&\widetilde{F}_{22}\end{array}\right],$

when $F_{11}+G_{11}X_{11}$ and $F_{22}$ do not share the same eigenvalues, the
Sylvester equation (39) has a unique solution $Z$. Otherwise, if the Sylvester
equation is consistent, we may choose one solution $Z$. If it is not
consistent, then we have two cases. If $\widetilde{F}_{22}$ and $F_{22}$ do
not have common eigenvalues, as discussed before we may choose another
solution $X_{11}$ ($\widetilde{X}_{11}$) such that $F_{11}+G_{11}X_{11}$ and
$F_{22}$ have no common eigenvalues and then (39) has a unique solution $Z$.
If $\widetilde{F}_{22}$ and $F_{22}$ have the same eigenvalues, (39) has no
solution and then the ARE (2) has no solution as well.

When both $X_{11}$ and $Z$ exist, then the ARE (40) has an invertible solution
$X_{22}$ if and only if $X_{22}^{-1}$ solves

$F_{22}Y_{22}+Y_{22}F_{22}^{H}+\left[\begin{array}[]{c}Z\\\
I\end{array}\right]^{H}G\left[\begin{array}[]{c}Z\\\ I\end{array}\right]=0.$

Such a solution exists if and only if
$\left(F_{22},\left[\begin{array}[]{c}Z\\\
I\end{array}\right]^{H}G\left[\begin{array}[]{c}Z\\\
I\end{array}\right]\right)$ is controllable and in this case $X_{22}>0$. When
we have determined all $X_{11}$, $Z$, and $X_{22}$, then $X$ given in (36)
solves (2) with $(F,G,K)$ transformed as in (27). Reversing the transformation
to the form (27) then gives a solution to the original ARE (2).

Note under the same assumptions that $F$ is asymptotically stable and (34) has
a positive definite solution, (1) always has a positive definite solution, see
[3]. This shows the difference between (2) and (1) when $(F,G)$ is not
controllable or $(F,K)$ is not observable.

In the next subsection we study the extreme solutions of (2) and (1).

###  2.3 Extreme solutions

In this subsection we discuss the extreme solutions of (2) and (1), i.e. the
solutions when we are on the boundary of set of positive definite solutions of
(1).

If $X=X^{H}$ solves (2), then

$H\left[\begin{array}[]{cc}I&0\\\
X&I\end{array}\right]=\left[\begin{array}[]{cc}I&0\\\
X&I\end{array}\right]\left[\begin{array}[]{cc}F+GX&G\\\
0&-(F+GX)^{H}\end{array}\right],$ (41)

where $H$ is defined in (3). So the columns of $\left[\begin{array}[]{c}I\\\
X\end{array}\right]$ form a Lagrangian invariant subspace of $H$ corresponding
to the eigenvalues of $F+GX$ or equivalently, $H$ has a Hamiltonian Schur form
(15). However, once $H$ has a Hamiltonian Schur form, then it may have many.
The whole classification of the Hamiltonian Schur form and therefore the
solutions of (2) were presented under some further assumptions in [19] and the
complete picture is given in [7].

The existence of a Hamiltonian Schur form (15) implies that the algebraic
multiplicity of each purely imaginary eigenvalue (including zero) of $H$ must
be even and the eigenvalues that are not purely imaginary are symmetrically
placed with respect to the imaginary axis. Recall the following results from
[19] summarized in one lemma.

###### Lemma 5

Consider a triple of matrices $(F,G,K)$ with $G=G^{H}\geq 0$ and $K=K^{H}\geq
0$.

  1. a.

Suppose that $X_{-}$ is a solution of (2) such that $F+GX_{-}$ is
asymptotically stable and suppose that $X$ is another solution of (2). Then
$X_{-}\leq X$. Also, $X_{-}$ is a monotonically non-decreasing function when
increasing $K$ in the Loewner ordering.

  2. b.

Suppose that $X_{+}$ is a solution of (2) such that $-(F+GX_{+})$ is
asymptotically stable and suppose that $X$ is another solution of (2). Then
$X_{+}\geq X$. Also, $X_{+}$ is monotonically non-increasing when increasing
$K$ in the Loewner ordering.

  3. c.

Suppose that (2) has two extreme solutions $X_{-}$ and $X_{+}$ with both
$F+GX_{-}$ and $-(F+GX_{+})$ asymptotically stable. Then any solution $X$ of
(2) satisfies $X_{-}\leq X\leq X_{+}$.

  4. d.

Suppose that $(F,G)$ is controllable, $(F,K)$ is observable, and (2) has a
solution. Then (2) has two extreme solutions $X_{-}$ and $X_{+}$ with all the
eigenvalues of $F+GX_{-}$ and $-(F+GX_{+})$ in the closed left half complex
plane. Furthermore any solution $X$ of (1) satisfies $X_{-}\leq X\leq X_{+}$.

Let us discuss the case d. in Lemma 5. If $X$ solves (1), then there exists
$\Delta_{K}=\Delta_{K}^{H}\geq 0$ such that

$F^{H}X+XF+XGX+K+\Delta_{K}=0.$ (42)

Because $(F,G)$ is controllable and $(F,K+\Delta_{K})$ is still observable,
the ARE (42) has two extremal solutions bounding $X$. By Lemma 5 these
extremal solutions are also bounded by $X_{-}$ and $X_{+}$, the extreme
solutions of (2). Thus $X$ is bounded by $X_{-}$ and $X_{+}$ as well.

Consider now a perturbation matrix

$\Delta=\left[\begin{array}[]{cc}\Delta_{G}&\Delta_{F}\\\
\Delta_{F}^{H}&\Delta_{K}\end{array}\right]\geq 0$

and suppose that the ARE

$(F+\Delta_{F})^{H}X+X(F+\Delta_{F})+X(G+\Delta_{G})X+(K+\Delta_{K})=0$ (43)

has a solution $X$. Then

$F^{H}X+XF+XGX+K=-\Delta_{F}^{H}X-X\Delta_{F}-X\Delta_{G}X-\Delta_{K}=-\left[\begin{array}[]{c}X\\\
I\end{array}\right]^{H}\Delta\left[\begin{array}[]{c}X\\\
I\end{array}\right]\leq 0,$

which implies that $X$ is a solution of (1). On the other hand, if $X$ solves
(1), then there exists $\Delta_{K}\geq 0$ such that

$F^{H}X+XF+XGX+K=-\Delta_{K}=-\left[\begin{array}[]{c}X\\\
I\end{array}\right]^{H}\left[\begin{array}[]{cc}0&0\\\
0&\Delta_{K}\end{array}\right]\left[\begin{array}[]{c}X\\\
I\end{array}\right].$ (44)

Thus we immediately have the following result.

###### Lemma 6

The ARI (1) has a solution $X$ if and only if $X$ solves (43) for some
$\Delta\geq 0$.

In this section we have reviewed classical results on the existence of
positive (semi)-definite solutions to (2) and (1). In order to proceed with
the characterization of the solution sets we study the eigenvalue perturbation
theory for the Hamiltonian matrix (3).

##  3 Eigenvalue perturbation theory for Hamiltonian matrices

In this section we discuss how the perturbation of the coefficients of the ARI
(1) in (43) affects the eigenvalues and invariant subspaces of the Hamiltonian
matrix (3). We assume that $(F,G)$ is controllable. Suppose that (2) has a
solution $X$, or equivalently that (41) holds. Then there exists an invertible
matrix $M$ such that

$M^{-1}(F+GX)M=\mathop{\rm diag}\nolimits(T_{1},T_{2}),$

where $T_{1}$ and $T_{2}$ contain the eigenvalues with nonzero real parts and
zero real parts, respectively. If we partition $M^{-1}GM^{-H}=[G_{ij}]$
conformably, then

$\left[\begin{array}[]{cc}M^{-1}&0\\\
0&M^{H}\end{array}\right]\left[\begin{array}[]{cc}F+GX&G\\\
0&-(F+GX)^{H}\end{array}\right]\left[\begin{array}[]{cc}M&0\\\
0&M^{-H}\end{array}\right]=\left[\begin{array}[]{cc|cc}T_{1}&0&G_{11}&G_{21}^{H}\\\
0&T_{2}&G_{21}&G_{22}\\\ \hline\cr 0&0&-T_{1}^{H}&0\\\
0&0&0&-T_{2}^{H}\end{array}\right].$

Let $Z_{12}$ be the unique solution of the Sylvester equation

$T_{1}Z_{12}+Z_{12}T_{2}^{H}+G_{21}^{H}=0,$

and define the symplectic matrix

$Z=\left[\begin{array}[]{cc|cc}I&0&0&Z_{12}\\\ 0&I&Z_{12}^{H}&0\\\ \hline\cr
0&0&I&0\\\ 0&0&0&I\end{array}\right].$

Then for $S=\left[\begin{array}[]{cc}M&0\\\ 0&M^{-H}\end{array}\right]Z$, one
has

$S^{-1}\left[\begin{array}[]{cc}F+GX&G\\\
0&-(F+GX)^{H}\end{array}\right]S=\left[\begin{array}[]{cc|cc}T_{1}&0&G_{11}&0\\\
0&T_{2}&0&G_{22}\\\ \hline\cr 0&0&-T_{1}^{H}&0\\\
0&0&0&-T_{2}^{H}\end{array}\right].$ (45)

In this way, we have decoupled the part that contains all the purely imaginary
eigenvalues, which is the block upper triangular Hamiltonian matrix
$\left[\begin{array}[]{cc}T_{2}&G_{22}\\\ 0&-T_{2}^{H}\end{array}\right]$.
Since $G\geq 0$, one also has $G_{22}\geq 0$.

Since $(F,G)$ is controllable, $(T_{2},G_{22})$ is controllable as well. To
see this, suppose that ${\imath}\gamma$ (${\imath}=\sqrt{-1}$) is an
eigenvalue of $T_{2}$ and $x$ is a corresponding left eigenvector such that
$x^{H}\left[\begin{array}[]{cc}T_{2}-{\imath}\gamma
I&G_{22}\end{array}\right]=0$. Then it follows that $G_{12}x=0$. If this were
not the case, then there exists a vector $x_{1}\neq 0$ such that
$x_{1}^{H}G_{21}^{H}x\neq 0$ (say, $x_{1}=G_{21}^{H}x$). Then

$\left[\begin{array}[]{cc}x_{1}&0\\\
0&x\end{array}\right]^{H}G\left[\begin{array}[]{cc}x_{1}&0\\\
0&x\end{array}\right]=\left[\begin{array}[]{cc}x_{1}^{H}G_{11}x_{1}&x_{1}^{H}G_{21}^{H}x\\\
x^{H}G_{21}x_{1}&0\end{array}\right]$

is indefinite, contradicting that $G\geq 0$. We then have

$\displaystyle\left[\begin{array}[]{c}0\\\
x\end{array}\right]^{H}M^{-1}\left[\begin{array}[]{cc}F+GX-{\imath}\gamma
I&G\end{array}\right]\left[\begin{array}[]{cc}M&0\\\
0&M^{-H}\end{array}\right]$ $\displaystyle\qquad=\left[\begin{array}[]{c}0\\\
x\end{array}\right]^{H}\left[\begin{array}[]{cc|cc}T_{1}-{\imath}\gamma
I&0&G_{11}&G_{21}^{H}\\\ 0&T_{2}-{\imath}\gamma
I&G_{21}&G_{22}\end{array}\right]=0,$

which shows that $(F+GX,G)$ is not controllable. But this contradicts the
controllability of $(F,G)$ due to the relation

$\left[\begin{array}[]{cc}F-\alpha
I&G\end{array}\right]\left[\begin{array}[]{cc}I&0\\\
X&I\end{array}\right]=\left[\begin{array}[]{cc}F+GX-\alpha
I&G\end{array}\right]$

for all $\alpha\in\mathbb{C}$. In the same way we can show that
$(T_{1},G_{11})$ is controllable. By Theorem 4.2 in [7], the controllability
of $(T_{2},G_{22})$ implies that the only Lagrangian invariant subspace of the
matrix $\left[\begin{array}[]{cc}T_{2}&G_{22}\\\
0&-T_{2}^{H}\end{array}\right]$ is $\mathop{\rm
range}\nolimits\left[\begin{array}[]{c}I\\\ 0\end{array}\right]$ and there
exists a block upper triangular symplectic matrix

$\widetilde{Z}=\left[\begin{array}[]{cc}\widetilde{Z}_{11}&\widetilde{Z}_{12}\\\
0&\widetilde{Z}_{11}^{-H}\end{array}\right]$

such that

$\widetilde{Z}^{-1}\left[\begin{array}[]{cc}T_{2}&G_{22}\\\
0&-T_{2}^{H}\end{array}\right]\widetilde{Z}=\left[\begin{array}[]{cc}\widetilde{T}&\widetilde{G}\\\
0&\widetilde{T}^{H}\end{array}\right],$

where

$\widetilde{T}=\mathop{\rm
diag}\nolimits(N_{1}({\imath}\gamma_{1}),\ldots,N_{r}({\imath}\gamma_{r})),\quad\widetilde{G}=\mathop{\rm
diag}\nolimits(\widetilde{G}_{1},\ldots,\widetilde{G}_{r}),$ (48)

and $N_{j}({\imath}\gamma_{j})$ is a Jordan block associated with a purely
imaginary eigenvalue ${\imath}\gamma_{j}$ of size $k_{j}\times k_{j}$,
$\widetilde{G}_{j}=e_{k_{j}}e_{k_{j}}^{H}$, for $j=1,\ldots,r$. Here
$e_{k_{j}}$ is the $k_{j}$th column of the identity matrix. This also shows
that $\left[\begin{array}[]{cc}T_{2}&G_{22}\\\ 0&-T_{2}^{H}\end{array}\right]$
has eigenvalues ${\imath}\gamma_{1},\ldots,{\imath}\gamma_{r}$ (not
necessarily distinct) with ${\imath}\gamma_{i}$ having a Jordan block of size
$2k_{j}\times 2k_{j}$.

Using (45), any Lagrangian invariant subspace of $H$ can be expressed as the
span of the matrix

$\left[\begin{array}[]{cc}I&0\\\
X&I\end{array}\right]\left[\begin{array}[]{cc}M&0\\\
0&M^{-H}\end{array}\right]\left[\begin{array}[]{cc|cc}I&0&0&Z_{12}\\\
0&I&Z_{12}^{H}&0\\\ \hline\cr 0&0&I&0\\\
0&0&0&I\end{array}\right]\left[\begin{array}[]{cc}U_{11}&0\\\ 0&I\\\ \hline\cr
U_{21}&0\\\ 0&0\end{array}\right],$

where $\left[\begin{array}[]{cc}U_{11}\\\ U_{21}\end{array}\right]$ spans a
Lagrangian invariant subspace of $\left[\begin{array}[]{cc}T_{1}&G_{11}\\\
0&-T_{1}^{H}\end{array}\right].$ The corresponding solution of the ARE (2) is

$X+M^{-H}\left[\begin{array}[]{cc}U_{21}U_{11}^{-1}&0\\\
0&0\end{array}\right]M^{-1}.$

In particular, if $X=X_{-}$ is the solution such that $F+GX_{-}$ has all its
eigenvalues in the closed left half plane, then $U_{21}U_{11}^{-1}\geq 0$.
Similarly if $X=X_{+}$ is a solution such that all eigenvalues of $F+GX_{+}$
are in the closed right half plane then $U_{21}U_{11}^{-1}\leq 0$. This
characterization is similar to the one in [19].

Another immediate consequence is that when the block $T_{1}$ is void, i.e. the
Hamiltonian matrix has only purely imaginary eigenvalues then the ARE (2) has
a unique solution and $X_{-}=X_{+}$, i.e. from a perturbation point of view,
when the eigenvalues are converging to the imaginary axis then all solutions
of (2) converge to $X_{-}$.

###  3.1 General perturbations

In this subsection we study perturbations to the Hamiltonian matrix that are
associated with the perturbation (43). For this we consider a Hamiltonian
matrix that is already in the block upper triangular form

$H_{0}=\left[\begin{array}[]{cc}F&G\\\ 0&-F^{H}\end{array}\right],$ (49)

where $G=G^{H}\geq 0$ and $(F,G)$ is controllable. Let
$\Delta=\Delta^{H}=\left[\begin{array}[]{cc}\Delta_{11}&\Delta_{21}^{H}\\\
\Delta_{21}&\Delta_{22}\end{array}\right]\geq 0$ and we consider the perturbed
matrix $H_{0}+J\Delta$.

Suppose that $(F,\Delta_{11})$ is not observable. Using a simultaneous
congruence transformation with a unitary matrix, $F$ and $\Delta_{11}$ can be
transformed to the form

$\left[\begin{array}[]{cc}F_{11}&F_{12}\\\
0&F_{22}\end{array}\right],\qquad\left[\begin{array}[]{cc}0&0\\\
0&\widetilde{\Delta}_{22}\end{array}\right],$ (50)

where $(F_{22},\widetilde{\Delta}_{22})$ is observable. Without loss of
generality we may assume that both matrices are already in the given block
form. Partition

$G=\left[\begin{array}[]{cc}G_{11}&G_{21}^{H}\\\
G_{21}&G_{22}\end{array}\right]$ (51)

accordingly and repartition

$\Delta=\left[\begin{array}[]{cc|cc}0&0&0&0\\\
0&\widetilde{\Delta}_{22}&\widetilde{\Delta}_{32}^{H}&\widetilde{\Delta}_{42}^{H}\\\
\hline\cr
0&\widetilde{\Delta}_{32}&\widetilde{\Delta}_{33}&\widetilde{\Delta}_{43}^{H}\\\
0&\widetilde{\Delta}_{42}&\widetilde{\Delta}_{43}&\widetilde{\Delta}_{44}\end{array}\right]$
(52)

conformably. The zero blocks in $\Delta$ are a result of the block form of
$\Delta_{11}$ and the fact that $\Delta\geq 0$. Note the zero block structure
also shows that $(F+\Delta_{21},\Delta_{11})$ is not observable. Then

$H_{0}+J\Delta=\left[\begin{array}[]{cc|cc}F_{11}&F_{12}+\widetilde{\Delta}_{32}&G_{11}+\widetilde{\Delta}_{33}&(G_{21}+\widetilde{\Delta}_{43})^{H}\\\
0&F_{22}+\widetilde{\Delta}_{42}&G_{21}+\widetilde{\Delta}_{43}&G_{22}+\widetilde{\Delta}_{44}\\\
\hline\cr 0&0&-F_{11}^{H}&0\\\
0&-\widetilde{\Delta}_{22}&-(F_{12}+\widetilde{\Delta}_{32})^{H}&-(F_{22}+\widetilde{\Delta}_{42})^{H}\end{array}\right]$

Clearly, the eigenvalues of $F_{11}$ and $-F_{11}^{H}$ are not affected by the
perturbation matrix $\Delta$, the affected eigenvalues are those of the
submatrix

$\left[\begin{array}[]{cc}F_{22}+\widetilde{\Delta}_{42}&G_{22}+\widetilde{\Delta}_{44}\\\
-\widetilde{\Delta}_{22}&-(F_{22}+\widetilde{\Delta}_{42})^{H}\end{array}\right]=\left[\begin{array}[]{cc}F_{22}&G_{22}\\\
0&-F_{22}^{H}\end{array}\right]+J\left[\begin{array}[]{cc}\widetilde{\Delta}_{22}&\widetilde{\Delta}_{42}^{H}\\\
\widetilde{\Delta}_{42}&\widetilde{\Delta}_{44}\end{array}\right].$

Note that since
$\left[\begin{array}[]{cc}\widetilde{\Delta}_{22}&\widetilde{\Delta}_{24}\\\
\widetilde{\Delta}_{24}^{H}&\widetilde{\Delta}_{44}\end{array}\right]$ is a
submatrix of $\Delta$, it is positive semidefinite.

Based on the previous analysis, we have the following observations.

  1. a.

For the perturbation analysis we may assume that $(F,\Delta_{11})$ is
observable, since otherwise we may work on a reduced size problem.

  2. b.

We are able to construct $\Delta$ to perturb some eigenvalues of $H_{0}$ while
keeping the remaining eigenvalues unchanged.

In order to simplify the perturbation theory we consider

$H(t)=H_{0}+tJ\Delta,\qquad t\geq 0,$ (53)

We assume that $(F,\Delta_{11})$ is observable and that $(F,G)$ is
controllable.

Without loss of generality we assume that

$F=\left[\begin{array}[]{cc}F_{11}&0\\\ 0&F_{22}\end{array}\right],\qquad
G=\left[\begin{array}[]{cc}G_{11}&0\\\ 0&G_{22}\end{array}\right],$ (54)

and that
$(\Lambda(F_{11})\cup\Lambda(-F_{11}^{H}))\cap(\Lambda(F_{22})\cup\Lambda(-F_{22}^{H}))=\emptyset$,
where $\Lambda(F)$ denotes the spectrum of the matrix $F$. Partition

$\Delta=\left[\begin{array}[]{cc|cc}\Delta_{11}&\Delta_{21}^{H}&\Delta_{31}^{H}&\Delta_{41}^{H}\\\
\Delta_{21}&\Delta_{22}&\Delta_{32}^{H}&\Delta_{42}^{H}\\\
\hline\cr\Delta_{31}&\Delta_{32}&\Delta_{33}&\Delta_{43}^{H}\\\
\Delta_{41}&\Delta_{42}&\Delta_{43}&\Delta_{44}\end{array}\right]$ (55)

conformably.

We now show that the controllability of $(F,G)$ implies the controllability of
$(F_{11},G_{11})$ and $(F_{22},G_{22})$, and the observability of
$\left(F,\left[\begin{array}[]{cc}\Delta_{11}&\Delta_{21}^{H}\\\
\Delta_{21}&\Delta_{22}\end{array}\right]\right)$ implies the observability of
$(F_{11},\Delta_{11})$ and $(F_{22},\Delta_{22})$.

The controllability of $(F_{11},G_{11})$ and $(F_{22},G_{22})$ is obvious. For
the observability statement, suppose that $(F_{11},\Delta_{11})$ is not
observable. Then there is an eigenvector $x\neq 0$ of $F_{11}$ such that
$F_{11}x=\lambda x$ and $\Delta_{11}x=0$. Due to the positive semidefiniteness
of $\Delta$, one also has $\Delta_{21}x=0$. Then

$F\left[\begin{array}[]{c}x\\\
0\end{array}\right]=\lambda\left[\begin{array}[]{c}x\\\
0\end{array}\right],\quad\left[\begin{array}[]{cc}\Delta_{11}&\Delta_{21}^{H}\\\
\Delta_{21}&\Delta_{22}\end{array}\right]\left[\begin{array}[]{c}x\\\
0\end{array}\right]=0,$

which is a contradiction. The observability of $(F_{22},\Delta_{22})$ follows
in the same way.

In the following with $t\in[0,\infty)$, we construct a _homotopy_

$H(t)=\left[\begin{array}[]{cc|cc}F_{11}+t\Delta_{31}&t\Delta_{32}&G_{11}+t\Delta_{33}&t\Delta_{43}^{H}\\\
t\Delta_{41}&F_{22}+t\Delta_{42}&t\Delta_{43}&G_{22}+t\Delta_{44}\\\
\hline\cr-t\Delta_{11}&-t\Delta_{21}^{H}&-(F_{11}+t\Delta_{31})^{H}&-t\Delta_{41}^{H}\\\
-t\Delta_{21}&-t\Delta_{22}&-t\Delta_{32}^{H}&-(F_{22}+t\Delta_{42})^{H}\end{array}\right].$

Let $P$ be a permutation matrix that interchanges the middle two block columns
when it is postmultiplied to a matrix of the block form as $H(t)$. Then

$\widetilde{J}=P^{H}JP=\left[\begin{array}[]{cc}J_{1}&0\\\
0&J_{2}\end{array}\right],$

where $J_{1}$ and $J_{2}$ are version of $J$ of smaller size, and

$\displaystyle\widetilde{H}(t)$ $\displaystyle:=$ $\displaystyle
P^{H}H(t)P=\left[\begin{array}[]{cc|cc}F_{11}+t\Delta_{31}&G_{11}+t\Delta_{33}&t\Delta_{32}&t\Delta_{43}^{H}\\\
-t\Delta_{11}&-(F_{11}+t\Delta_{31})^{H}&-t\Delta_{21}^{H}&-t\Delta_{41}^{H}\\\
\hline\cr t\Delta_{41}&t\Delta_{43}&F_{22}+t\Delta_{42}&G_{22}+t\Delta_{44}\\\
-t\Delta_{21}&-t\Delta_{32}^{H}&-t\Delta_{22}&-(F_{22}+t\Delta_{42})^{H}\end{array}\right]$
$\displaystyle=:$
$\displaystyle\left[\begin{array}[]{c|c}H_{1}(t)&tJ_{1}L^{H}J_{2}\\\ \hline\cr
tL&H_{2}(t)\end{array}\right].$

Note that both $H_{1}(t)$ and $H_{2}(t)$ are Hamiltonian matrices.

Consider the quadratic matrix equation

$H_{2}(t)Y(t)-Y(t)H_{1}(t)-tY(t)J_{1}L^{H}J_{2}Y(t)+tL=0.$

Since $\lambda(H_{1}(0))\cap\lambda(H_{2}(0))=\emptyset$, it follows that when
$t$ is sufficiently small then this equation has a unique solution $Y(t)$ with
$|\\!|Y(t)|\\!|=\mathcal{O}(t)$. Furthermore, the matrices

$I-J_{1}Y^{H}(t)J_{2}Y(t),\quad I-Y(t)J_{1}Y^{H}(t)J_{2}$

are skew-Hamiltonian, and have the form $I+\mathcal{O}(t^{2})$.

Using the structured Jordan canonical form, both skew-Hamiltonian matrices
have a principal skew-Hamiltonian square root
$S_{1}(t),S_{2}(t)=I+\mathcal{O}(t^{2})$, see [6], satisfying

$S_{1}^{2}(t)=J_{1}^{H}S_{1}^{H}(t)J_{1}S_{1}(t)=I-J_{1}Y^{H}(t)J_{2}Y(t),\quad
S_{2}^{2}(t)=J_{2}^{H}S_{2}^{H}(t)J_{2}S_{2}(t)=I-Y(t)J_{1}Y^{H}(t)J_{2}.$

Defining

$S(t)=\left[\begin{array}[]{cc}I&J_{1}Y^{H}(t)J_{2}\\\
Y(t)&I\end{array}\right]\left[\begin{array}[]{cc}S_{1}^{-1}(t)&0\\\
0&S_{2}^{-1}(t)\end{array}\right],$

one has

$S^{-1}(t)=\left[\begin{array}[]{cc}S_{1}^{-1}(t)&0\\\
0&S_{2}^{-1}(t)\end{array}\right]\left[\begin{array}[]{cc}I&-J_{1}Y^{H}(t)J_{2}\\\
-Y(t)&I\end{array}\right],\quad S^{H}(t)\widetilde{J}S(t)=\widetilde{J},$

so that $P^{H}S(t)P$ is symplectic.

Using $S(t)$ and the fact that $H_{1}(t)$ and $H_{2}(t)$ are Hamiltonian, we
can eliminate the blocks $tL$ and $tJ_{1}L^{H}J_{2}$ in $\widetilde{H}(t)$ via

$\displaystyle S^{-1}(t)\widetilde{H}(t)S(t)$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cc}S_{1}(t)(H_{1}(t)+tJ_{1}L^{H}J_{2}Y(t))S_{1}^{-1}(t)&0\\\
0&S_{2}^{-1}(t)(H_{2}(t)-tY(t)J_{1}L^{H}J_{2})S_{2}(t)\end{array}\right]$
$\displaystyle=$
$\displaystyle\left[\begin{array}[]{cc}\widetilde{H}_{1}(t)&0\\\
0&\widetilde{H}_{2}(t)\end{array}\right],$

and by construction, both $\widetilde{H}_{1}(t)$ and $\widetilde{H}_{2}(t)$
are still Hamiltonian. Because $S^{H}(t)\widetilde{J}S(t)=\widetilde{J}$, we
also have

$S^{-1}(t)\widetilde{H}(t)S(t)=\widetilde{J}^{H}S^{H}(t)\widetilde{J}\widetilde{H}(t)S(t),$

from which we get

$\displaystyle\widetilde{H}_{1}(t)$ $\displaystyle=$ $\displaystyle
J_{1}^{H}S_{1}^{-H}(t)\left[\begin{array}[]{c}I\\\
Y(t)\end{array}\right]^{H}\widetilde{J}\widetilde{H}(t)\left[\begin{array}[]{c}I\\\
Y(t)\end{array}\right]S_{1}^{-1}(t)$ $\displaystyle=$ $\displaystyle
J_{1}^{H}S_{1}^{-H}(t)(J_{1}H_{1}(t)-tL^{H}J_{2}Y(t)-tY^{H}(t)J_{2}^{H}L+Y^{H}(t)J_{2}H_{2}(t)Y(t))S_{1}^{-1}(t),$
$\displaystyle\widetilde{H}_{2}(t)$ $\displaystyle=$ $\displaystyle
J_{2}^{H}S_{2}^{-H}(t)\left[\begin{array}[]{c}J_{1}Y^{H}(t)J_{2}\\\
I\end{array}\right]^{H}\widetilde{J}H(t)\left[\begin{array}[]{c}J_{1}Y^{H}(t)J_{2}\\\
I\end{array}\right]S_{2}^{-1}(t)$ $\displaystyle=$ $\displaystyle
J_{2}S_{2}^{-H}(t)J_{2}^{H}[H_{2}(t)J_{2}+tY(t)J_{1}L^{H}+tLJ_{1}^{H}Y^{H}(t)+Y(t)H_{1}(t)J_{1}Y^{H}(t)]J_{2}S_{2}^{-1}(t).$

The Hamiltonian structure of $\widetilde{H}_{1}(t)$, $\widetilde{H}_{2}(t)$ is
obvious.

In this subsection we have reformulated the Hamiltonian matrix that is
obtained after perturbing the Riccati inequality (1). In the next subection we
use this reformulation to study the perturbation theory for the eigenvalues.

###  3.2 Perturbations of a purely imaginary eigenvalue

In this subsection we begin our analysis of the perturbation of the
eigenvalues of $H_{0}+J\Delta$ with $H_{0}$ as in (49) in the transformed
version (3.1). We first consider the case where $F_{11}$ as in (54) has a
single purely imaginary eigenvalue that is different from the eigenvalues of
$F_{22}$. We consider how the eigenvalues of $F_{11}$ and $-F_{11}^{H}$ are
perturbed in $H(t)$ as in (53) with $\Delta=\Delta^{H}\geq 0$ given in (55).
Again, we assume that $(F_{11},G_{11})$ is controllable and
$(F_{11},\Delta_{11})$ is observable.

Following the analysis in the last subsection, the perturbed eigenvalues are
those of $\widetilde{H}_{1}(t)$ in (3.1). Suppose that the single purely
imaginary eigenvalue of $F_{11}$ (as well as
$H_{1}(0)=\left[\begin{array}[]{cc}F_{11}&G_{11}\\\
0&-F_{11}^{H}\end{array}\right]$) is ${\imath}\alpha$. Then
$H_{1}(0)-{\imath}\alpha I$ is still Hamiltonian but with single eigenvalue
$0$. Because of this, we may assume that zero is the only eigenvalue of
$F_{11}$, i.e., $F_{11}$ is nilpotent.

As shown in [12], the matrix
$H_{1}(0)=\left[\begin{array}[]{cc}F_{11}&G_{11}\\\
0&-F_{11}^{H}\end{array}\right]$ can be transformed to a Hamiltonian Jordan
form with a symplectic similarity transformation using a block upper
triangular matrix. Applying the transformation to $H_{0}+tJ\Delta$ on
appropriate block rows and columns, the matrix $\Delta$ changes, but a close
inspection shows that the controllability and observability properties remain.
So as in (48), without loss of generality, we may assume that

$F_{11}=\mathop{\rm
diag}\nolimits(\widehat{N}_{1},\ldots,\widehat{N}_{k}),\quad
G_{11}=\mathop{\rm diag}\nolimits(G_{1},\ldots,G_{k}),$

where, for $j=1,2,\ldots,k$,

$\widehat{N}_{j}=\left[\begin{array}[]{cccc}0&I_{s_{j}}&&\\\
&\ddots&\ddots&\\\ &&\ddots&I_{s_{j}}\\\ &&&0\end{array}\right]_{j\times
j},\quad G_{k}=\left[\begin{array}[]{cccc}0&\ldots&0&0\\\ \vdots&\ddots&0&0\\\
0&\ldots&0&0\\\ 0&\ldots&0&I_{s_{j}}\end{array}\right].$

This implies that $F_{11}$ has $s_{j}$ Jordan blocks of order $j$ and
$H_{1}(0)$ has $s_{j}$ Jordan blocks of order $2j$, for $j=1,\ldots,k$. Also,
the block forms show that $(F_{11},G_{11})$ is controllable. Note that
$\widehat{N}_{1}$ is a zero matrix of order $s_{1}$. If $s_{j}=0$ or
$\widehat{N}_{j}$ is void for some $j\in\\{1,\ldots,k\\}$, then $F_{11}$ does
not have Jordan blocks of such an order. Let $P_{0}$ be a block permutation
matrix such that

$P_{0}^{H}H_{1}(0)P_{0}=\mathop{\rm
diag}\nolimits\left(\left[\begin{array}[]{cc}\widehat{N}_{1}&G_{1}\\\
0&-\widehat{N}_{1}^{H}\end{array}\right],\left[\begin{array}[]{cc}\widehat{N}_{2}&G_{2}\\\
0&-\widehat{N}_{2}^{H}\end{array}\right],\ldots,\left[\begin{array}[]{cc}\widehat{N}_{k}&G_{k}\\\
0&-\widehat{N}_{k}^{H}\end{array}\right]\right).$

With

$\Sigma_{j}=\left[\begin{array}[]{ccccc}0&0&\ldots&0&(-1)^{j-1}I_{s_{j}}\\\
0&0&\ldots&(-1)^{j-2}I_{s_{j}}&0\\\ \vdots&\vdots&\mbox{
\begin{picture}(8.0,7.0)\put(-4.0,1.0){.}\put(0.0,4.0){.}
\put(4.0,7.0){.}\end{picture}}&\vdots&\vdots\\\ 0&-I_{s_{j}}&\ldots&0&0\\\
I_{s_{j}}&0&\ldots&0&0\end{array}\right],\quad j=1,2,\ldots,k,$

and

$P=P_{0}\mathop{\rm
diag}\nolimits\left(\left[\begin{array}[]{cc}I_{s_{1}}&0\\\
0&\Sigma_{1}\end{array}\right],\left[\begin{array}[]{cc}I_{2s_{2}}&0\\\
0&\Sigma_{2}\end{array}\right],\ldots,\left[\begin{array}[]{cc}I_{ks_{k}}&0\\\
0&\Sigma_{k}\end{array}\right]\right),$

one has

$P^{H}H_{1}(0)P=\mathop{\rm diag}\nolimits(N_{1},N_{2},\ldots,N_{k}),$

where

$N_{j}=\left[\begin{array}[]{cccc}0&I_{s_{j}}&&\\\ &\ddots&\ddots&\\\
&&\ddots&I_{s_{j}}\\\ &&&0\end{array}\right]_{2j\times 2j},\quad
j=1,\ldots,k.$

With this $P$ one has $P^{H}J_{1}P=\mathop{\rm
diag}\nolimits\left(\widehat{\Sigma}_{1},\widehat{\Sigma}_{2},\ldots,\widehat{\Sigma}_{k}\right)$,
where

$\widehat{\Sigma}_{j}=\left[\begin{array}[]{cccccc}0&\ldots&0&0&\ldots&(-1)^{j-1}I_{s_{j}}\\\
\vdots&\vdots&\vdots&\vdots&\mbox{
\begin{picture}(8.0,7.0)\put(-4.0,1.0){.}\put(0.0,4.0){.}
\put(4.0,7.0){.}\end{picture}}&\vdots\\\ 0&\ldots&0&I_{s_{j}}&\ldots&0\\\
0&\ldots&-I_{s_{j}}&0&\ldots&0\\\ \vdots&\mbox{
\begin{picture}(8.0,7.0)\put(-4.0,1.0){.}\put(0.0,4.0){.}
\put(4.0,7.0){.}\end{picture}}&\vdots&\vdots&\vdots&\vdots\\\
(-1)^{j}I_{s_{j}}&\vdots&0&0&\ldots&0\end{array}\right]=(-1)^{j}\left[\begin{array}[]{cccc}0&0&\ldots&(-1)^{2j-1}I_{s_{j}}\\\
\vdots&\vdots&\mbox{ \begin{picture}(8.0,7.0)\put(-4.0,1.0){.}\put(0.0,4.0){.}
\put(4.0,7.0){.}\end{picture}}&\vdots\\\ 0&-I_{s_{j}}&\ldots&0\\\
I_{s_{j}}&0&\ldots&0\end{array}\right],$

for $j=1,\ldots,k$. Recalling that

$H_{1}(t)=H_{1}(0)+t\left[\begin{array}[]{cc}\Delta_{31}&\Delta_{33}\\\
-\Delta_{11}&-\Delta_{31}^{H}\end{array}\right],$

we partition

$\displaystyle\Delta_{11}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cccc}\Delta^{(11)}_{11}&(\Delta^{(11)}_{21})^{H}&\ldots&(\Delta^{(11)}_{k1})^{H}\\\
\Delta_{21}^{(11)}&\Delta^{(11)}_{22}&\ldots&(\Delta^{(11)}_{k2})^{H}\\\
\vdots&\vdots&\ddots&\vdots\\\
\Delta^{(11)}_{k1}&\Delta^{(11)}_{k2}&\ldots&\Delta^{(11)}_{kk}\end{array}\right],\quad,\quad\Delta_{31}=\left[\begin{array}[]{cccc}\Delta_{(11)}^{(31)}&\Delta^{(31)}_{12}&\ldots&\Delta^{(31)}_{1k}\\\
\Delta_{21}^{(31)}&\Delta^{(31)}_{22}&\ldots&\Delta^{(31)}_{2k}\\\
\vdots&\vdots&\ddots&\vdots\\\
\Delta^{(31)}_{k1}&\Delta^{(31)}_{k2}&\ldots&\Delta^{(31)}_{kk}\end{array}\right],$
$\displaystyle\Delta_{33}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cccc}\Delta^{(33)}_{11}&(\Delta^{(33)}_{21})^{H}&\ldots&(\Delta^{(33)}_{k1})^{H}\\\
\Delta_{21}^{(33)}&\Delta^{(33)}_{22}&\ldots&(\Delta^{(33)}_{k2})^{H}\\\
\vdots&\vdots&\ddots&\vdots\\\
\Delta^{(33)}_{k1}&\Delta^{(33)}_{k2}&\ldots&\Delta^{(33)}_{kk}\end{array}\right]$

conformably with the block form of $F_{11}$. Then

$P^{H}H_{1}(t)P=P^{H}H_{1}(0)P+tP^{H}\left[\begin{array}[]{cc}\Delta_{31}&\Delta_{33}\\\
-\Delta_{11}&-\Delta_{31}^{H}\end{array}\right]P=P^{H}H_{1}(0)P+t\widetilde{\Delta},$

where

$\widetilde{\Delta}=\left[\begin{array}[]{cc|cc|c|cc}\Delta^{(31)}_{11}&\Delta^{(33)}_{11}\Sigma_{1}&\Delta^{(31)}_{12}&(\Delta^{(33)}_{21})^{H}\Sigma_{2}&\ldots&\Delta^{(31)}_{1k}&(\Delta^{(33)}_{k1})^{H}\Sigma_{k}\\\
-\Sigma_{1}^{H}\Delta_{11}^{(11)}&-\Sigma_{1}^{H}(\Delta_{11}^{(31)})^{H}\Sigma_{1}&-\Sigma_{1}^{H}(\Delta_{21}^{(11)})^{H}&-\Sigma_{1}^{H}(\Delta_{21}^{(31)})^{H}\Sigma_{2}&\ldots&-\Sigma_{1}^{H}(\Delta_{k1}^{(11)})^{H}&-\Sigma_{1}^{H}(\Delta_{k1}^{(31)})^{H}\Sigma_{k}\\\
\hline\cr\Delta^{(31)}_{21}&\Delta^{(33)}_{21}\Sigma_{1}&\Delta^{(31)}_{22}&\Delta^{(33)}_{22}\Sigma_{2}&\ldots&\Delta^{(31)}_{2k}&(\Delta^{(33)}_{k2})^{H}\Sigma_{k}\\\
-\Sigma_{2}^{H}\Delta_{21}^{(11)}&-\Sigma_{2}^{H}(\Delta_{12}^{(31)})^{H}\Sigma_{1}&-\Sigma_{2}^{H}\Delta_{22}^{(11)}&-\Sigma_{2}^{H}(\Delta_{22}^{(31)})^{H}\Sigma_{2}&\ldots&-\Sigma_{2}^{H}(\Delta_{k2}^{(11)})^{H}&-\Sigma_{2}^{H}(\Delta_{k2}^{(31)})^{H}\Sigma_{k}\\\
\hline\cr\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
\hline\cr\Delta^{(31)}_{k1}&\Delta^{(33)}_{k1}\Sigma_{1}&\Delta^{(31)}_{k2}&\Delta^{(33)}_{k2}\Sigma_{2}&\ldots&\Delta^{(31)}_{kk}&\Delta^{(33)}_{kk}\Sigma_{k}\\\
-\Sigma_{k}^{H}\Delta_{k1}^{(11)}&-\Sigma_{k}^{H}(\Delta_{1k}^{(31)})^{H}\Sigma_{1}&-\Sigma_{k}^{H}\Delta_{k2}^{(11)}&-\Sigma_{k}^{H}(\Delta_{2k}^{(31)})^{H}\Sigma_{2}&\ldots&-\Sigma_{k}^{H}\Delta_{kk}^{(11)}&-\Sigma_{k}^{H}(\Delta_{kk}^{(31)})^{H}\Sigma_{k}\end{array}\right].$

Partition further

$\Delta_{ij}^{(11)}=\left[\begin{array}[]{cccc}\widehat{\Delta}_{11}^{(ij)}&\widehat{\Delta}_{12}^{(ij)}&\ldots&\widehat{\Delta}_{1j}^{(ij)}\\\
\widehat{\Delta}_{21}^{(ij)}&\widehat{\Delta}_{22}^{(ij)}&\ldots&\widehat{\Delta}_{2j}^{(ij)}\\\
\vdots&\vdots&\ddots&\vdots\\\
\widehat{\Delta}_{i1}^{(ij)}&\widehat{\Delta}_{i2}^{(ij)}&\ldots&\widehat{\Delta}_{ij}^{(ij)}\end{array}\right],\quad
i,j=1,\ldots,k$

and note that $\widehat{\Delta}_{11}^{(11)}=\Delta_{11}^{(11)}$. Recall also
that $\Delta_{11}$ is Hermitian and thus
$\widehat{\Delta}_{ji}^{(\ell\ell)}=(\widehat{\Delta}_{ij}^{(\ell\ell)})^{H}$
for $i,j=1,\ldots,\ell$ and $\ell=1,\ldots,k$.

From the observability of $(F_{11},\Delta_{11})$ it follows that

$\Pi:=\left[\begin{array}[]{cccc}\widehat{\Delta}_{11}^{(11)}&(\widehat{\Delta}_{11}^{(21)})^{H}&\ldots&(\widehat{\Delta}_{11}^{(k1)})^{H}\\\
\widehat{\Delta}_{11}^{(21)}&\widehat{\Delta}_{11}^{(22)}&\ldots&(\widehat{\Delta}_{11}^{(k2)})^{H}\\\
\vdots&\vdots&\ddots&\vdots\\\
\widehat{\Delta}_{11}^{(k1)}&\widehat{\Delta}_{11}^{(k2)}&\ldots&\widehat{\Delta}_{11}^{(kk)}\end{array}\right]>0.$

The submatrix of $\widetilde{\Delta}$ corresponding to the zero block rows and
columns of $P^{H}H_{1}(0)P$ is given by

$W=\left[\begin{array}[]{cccc}-\widehat{\Delta}_{11}^{(11)}&-(\widehat{\Delta}_{11}^{(21)})^{H}&\ldots&-(\widehat{\Delta}_{11}^{(k1)})^{H}\\\
\widehat{\Delta}_{11}^{(21)}&\widehat{\Delta}_{11}^{(22)}&\ldots&(\widehat{\Delta}_{11}^{(k2)})^{H}\\\
\vdots&\vdots&\ddots&\vdots\\\
(-1)^{k}\widehat{\Delta}_{11}^{(k1)}&(-1)^{k}\widehat{\Delta}_{11}^{(k2)}&\ldots&(-1)^{k}\widehat{\Delta}_{11}^{(kk)}\end{array}\right]=\mathop{\rm
diag}\nolimits(-I_{s_{1}},I_{s_{2}},\ldots,(-1)^{k}I_{s_{k}})\Pi.$

Define the principal block submatrices

$\Pi_{j}=\left[\begin{array}[]{cccc}\widehat{\Delta}_{11}^{(jj)}&(\widehat{\Delta}_{11}^{(j,j+1)})^{H}&\ldots&(\widehat{\Delta}_{11}^{(jk)})^{H}\\\
\widehat{\Delta}_{11}^{(j+1,j)}&\widehat{\Delta}_{11}^{(j+1,j+2)}&\ldots&(\widehat{\Delta}_{11}^{(k,j+1)})^{H}\\\
\vdots&\vdots&\ddots&\vdots\\\
\widehat{\Delta}_{11}^{(kj)}&\widehat{\Delta}_{11}^{(k,j+1)}&\ldots&\widehat{\Delta}_{11}^{(kk)}\end{array}\right],$

and

$\displaystyle W_{j}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cccc}(-1)^{j}\widehat{\Delta}_{11}^{(jj)}&(-1)^{j}(\widehat{\Delta}_{11}^{(j+1,j)})^{H}&\ldots&(-1)^{j}(\widehat{\Delta}_{11}^{(kj)})^{H}\\\
(-1)^{j+1}\widehat{\Delta}_{11}^{(j+1,j)}&(-1)^{j+1}\widehat{\Delta}_{11}^{(j+1,j+1)}&\ldots&(-1)^{j+1}(\widehat{\Delta}_{11}^{(k,j+1)})^{H}\\\
\vdots&\vdots&\ddots&\vdots\\\
(-1)^{k}\widehat{\Delta}_{11}^{(kj)}&(-1)^{k}\widehat{\Delta}_{11}^{(k,j+1)}&\ldots&(-1)^{k}\widehat{\Delta}_{11}^{(kk)}\end{array}\right]$
$\displaystyle=$
$\displaystyle\left[\begin{array}[]{c|ccc}(-1)^{j}\widehat{\Delta}_{11}^{(jj)}&(-1)^{j}(\widehat{\Delta}_{11}^{(j+1,j)})^{H}&\ldots&(-1)^{j}(\widehat{\Delta}_{11}^{(kj)})^{H}\\\
\hline\cr(-1)^{j+1}\widehat{\Delta}_{11}^{(j+1,j)}&&&\\\ \vdots&&W_{j+1}&\\\
(-1)^{k}\widehat{\Delta}_{11}^{(kj)}&&&\end{array}\right]$ $\displaystyle=$
$\displaystyle\mathop{\rm
diag}\nolimits((-1)^{j}I_{s_{j}},\ldots,(-1)^{k}I_{s_{k}})\Pi_{j},$

for $j=1,\ldots,k$ with $\Pi_{1}=\Pi$, $W_{1}=W$, and
$\Pi_{k}=\widehat{\Delta}_{11}^{(kk)}$,
$W_{k}=(-1)^{k}\widehat{\Delta}_{11}^{(kk)}$. Then define the Schur
complements $\mathcal{S}_{k}=W_{k}=(-1)^{k}\widehat{\Delta}_{11}^{(k,k)}$,

$\displaystyle\mathcal{S}_{j}$ $\displaystyle=$
$\displaystyle(-1)^{j}\left(\widehat{\Delta}_{11}^{(jj)}-\left[\begin{array}[]{c}\widehat{\Delta}_{11}^{(j+1,j)}\\\
\vdots\\\
\widehat{\Delta}_{11}^{(kj)}\end{array}\right]^{H}W_{j+1}^{-1}\left[\begin{array}[]{c}(-1)^{j+1}\widehat{\Delta}_{11}^{(j+1,j)}\\\
\vdots\\\ (-1)^{k}\widehat{\Delta}_{11}^{(kj)}\end{array}\right]\right)$
$\displaystyle=$
$\displaystyle(-1)^{j}\left(\widehat{\Delta}_{11}^{(jj)}-\left[\begin{array}[]{c}\widehat{\Delta}_{11}^{(j+1,j)}\\\
\vdots\\\
\widehat{\Delta}_{11}^{(kj)}\end{array}\right]^{H}\Pi_{j+1}^{-1}\left[\begin{array}[]{c}(\widehat{\Delta}_{11}^{(j+1,j)}\\\
\vdots\\\ \widehat{\Delta}_{11}^{(kj)}\end{array}\right]\right),\quad
j=1,\ldots,k-1.$

Note that $(-1)^{j}\mathcal{S}_{j}>0$ for all $j=1,\ldots,k$. Then, from the
perturbation results in [11, 17, 22], for a fixed $\rho\in\\{1,\ldots,k\\}$,
if
$(-1)^{\rho}\gamma_{1}^{(\rho)},\ldots,(-1)^{\rho}\gamma_{s_{\rho}}^{(\rho)}$
are the $s_{\rho}$ eigenvalues of $\mathcal{S}_{\rho}$ (with
$\gamma_{i}^{(\rho)}>0$ for $i=1,\ldots,s_{\rho}$), then for $t$ sufficiently
small, $P^{H}H_{1}(t)P$ as well as $H_{1}(t)$ has $2\rho s_{\rho}$ eigenvalues

$\lambda^{(\rho)}_{ij}(t)=(t\gamma_{i}^{(\rho)})^{\frac{1}{2\rho}}\mu^{(\rho)}_{j}+\mathcal{O}(t^{\frac{1}{\rho}}),\quad
i=1,\ldots,s_{\rho},\quad j=1,\ldots,2\rho,$ (76)

where $\mu^{(\rho)}_{1},\ldots,\mu^{(\rho)}_{2\rho}$ are the $2\rho$ roots of
$\mu^{2\rho}=(-1)^{\rho}$, i.e.,

$\mu_{j}^{(\rho)}=\left\\{\begin{array}[]{ll}e^{\frac{(2j-1)\pi\imath}{2\rho}}&\rho\mbox{
is odd}\\\ e^{\frac{(j-1)\pi\imath}{\rho}}&\rho\mbox{ is
even}\end{array}\right.\qquad j=1,\ldots,2\rho.$

Note that for different values of $\rho$, the corresponding eigenvalue sets
are well separated due to the different fractional orders when $t$ is
sufficiently small. For a fixed $\rho$, since $\mathcal{S}_{\rho}$ is
Hermitian, all the eigenvalues of $\mathcal{S}_{\rho}$ are semisimple. Then
all the eigenvalues of $\lambda^{(\rho)}$ are semisimple as well, see [22].

The set $\\{\mu^{(\rho)}_{j}\\}_{j=1}^{2\rho}$ contains exactly two purely
imaginary numbers, namely $\pm\imath$ for $j=(\rho+1)/2,(3\rho+1)/2$ when
$\rho$ is odd and $j=\rho/2+1,3\rho/2+1$ when $\rho$ is even. Let us denote
the corresponding eigenvalues of $H_{1}(t)$ by

$\lambda^{(\rho)}_{i,\pm}(t)=\pm\imath(t\gamma_{i}^{(\rho)})^{\frac{1}{2\rho}}+\mathcal{O}(t^{\frac{1}{\rho}}),\quad
i=1,\ldots,s_{\rho}.$

Consider the eigenvalues $\lambda^{(\rho)}_{i,+}(t)$, $i=1,\ldots,s_{\rho}$.
Let

$\mathop{\rm
diag}\nolimits(\lambda^{(\rho)}_{1,+}(0),\ldots,\lambda^{(\rho)}_{s_{\rho},+}(0))=\imath\Omega_{\rho,+},\qquad\Omega_{\rho,+}=\mathop{\rm
diag}\nolimits((t\gamma_{1}^{(\rho)})^{\frac{1}{2\rho}},\ldots,(t\gamma_{s_{\rho}}^{(\rho)})^{\frac{1}{2\rho}})>0.$

Following [22] and recalling that the order of all Jordan blocks of $H_{1}(0)$
is even, there exists a full column rank matrix
$V(t)=\left[\begin{array}[]{c}V_{1}(t)\\\ \vdots\\\ V_{\rho}(t)\\\ \vdots\\\
V_{k}(t)\end{array}\right]$ such that

$P^{H}H_{1}(t)PV(t)=V(t)(\imath\Omega_{\rho,+}(t)),\quad\mbox{or}\quad
H_{1}(t)PV(t)=PV(t)(\imath\Omega_{\rho,+}(t)),$

where $\Omega_{\rho,+}(t)=\Omega_{\rho,+}+\mathcal{O}(t^{\frac{1}{\rho}})$ and

$\displaystyle V_{i}(t)$ $\displaystyle=$
$\displaystyle\mathcal{O}\left(\left[\begin{array}[]{c}t^{1-\frac{2i}{2\rho}}\\\
t^{1-\frac{2i-1}{2\rho}}\\\ \vdots\\\
t^{1-\frac{1}{2\rho}}\end{array}\right]\right),\quad i=1,\dots,\rho-1;$
$\displaystyle V_{\rho}(t)$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{c}Q\\\ \imath Q\Omega_{\rho,+}\\\
\vdots\\\
\imath^{2\rho-1}Q\Omega_{\rho,+}^{2\rho-1}\end{array}\right]+\mathcal{O}\left(\left[\begin{array}[]{c}t^{\frac{1}{2\rho}}\\\
t^{\frac{2}{2\rho}}\\\ \vdots\\\ t\end{array}\right]\right),$ $\displaystyle
V_{i}(t)$ $\displaystyle=$
$\displaystyle\mathcal{O}\left(\left[\begin{array}[]{c}t^{0}\\\
t^{\frac{1}{2\rho}}\\\ \vdots\\\ t^{1-\frac{1}{2\rho}}\\\ t\\\ \vdots\\\
t\end{array}\right]\right),\quad i=\rho+1,\ldots,k,$

where $Q$ is a unitary matrix such that
$\mathcal{S}_{\rho}Q=(-1)^{\rho}Q\mathop{\rm
diag}\nolimits(\gamma_{1}^{(\rho)},\ldots,\gamma_{s_{\rho}}^{(\rho)})$, and
the notation $\mathcal{O}(t^{\frac{j}{2\rho}})$ represents the fractional
order (in $t$) of a block in the matrix.

Then

$(PV(t))^{H}J_{1}(PV(t))=\sum_{i=1}^{k}V_{i}(t)^{H}\widehat{\Sigma}_{i}V_{i}(t),$

and one can easily check that
$V_{i}(t)^{H}\widehat{\Sigma}_{i}V_{i}(t)=\mathcal{O}(t),\quad
i=1,\ldots,\rho-1,\rho+1,\ldots,k,$ and
$V_{\rho}(t)^{H}\widehat{\Sigma}_{\rho}V_{\rho}(t)=2\rho\imath\Omega_{\rho,+}^{2\rho-1}+\mathcal{O}(t).$
Note that $\Omega_{\rho,+}^{2\rho-1}=\mathcal{O}(t^{\frac{2\rho-1}{2\rho}})$.
Hence,

$(PV(t))^{H}J_{1}(PV(t))=2\rho\imath\Omega_{\rho,+}^{2\rho-1}+\mathcal{O}(t).$

Then for sufficiently small $t>0$, by symmetry it follows that

$\imath(PV(t))^{H}J_{1}(PV(t))=-2\rho\Omega_{\rho,+}^{2\rho-1}+\mathcal{O}(t)<0.$

Suppose that one of the eigenvalues
$\lambda_{1,+}^{(\rho)}(t),\ldots,\lambda_{s_{\rho},+}^{(\rho)}(t)$ is not
purely imaginary, say $\lambda(t)$, with a corresponding right eigenvector
$x(t)$, i.e., $H_{1}(t)x(t)=\lambda(t)x(t)$. By the symmetry of the spectrum
we have that $-\bar{\lambda}(t)$ is also an eigenvalue of $H_{1}(t)$ and,
moreover, $x(t)^{H}J_{1}x(t)=0$. Apparently, if $\lambda(t)$ is a multiple
eigenvalue, due to the fractional order and eigenvalue distribution (76) they
must be all in the set $\\{\lambda_{j,+}^{(\rho)}(t)\\}_{j=1}^{s_{\rho}}$.
This implies that $x(t)=PV(t)y(t)$ for some $y(t)\neq 0$. Then
$x(t)^{H}J_{1}x(t)=0$ implies that

$y(t)^{H}(PV(t))^{T}J_{1}(PV(t))y(t)=0,$

contradicting the negative definiteness of ${\imath}(PV(t))^{T}J_{1}(P(V(t))$.

We conclude that all
$\lambda_{1,+}^{(\rho)}(t),\ldots,\lambda_{s_{\rho},+}^{(\rho)}(t)$ must be
purely imaginary and the structure inertia index of $H_{1}(t)$ corresponding
to each of them is $-1$, see e.g., [7, 16]. In the same way, one can show that
all $\lambda_{1,-}^{(\rho)}(t),\ldots,\lambda_{s_{\rho},-}^{(\rho)}(t)$ are
also purely imaginary and the structure inertia index of $H_{1}(t)$
corresponding to each of them is $+1$. It is easily verified that
$\widetilde{H}_{1}(t)=H_{1}(t)+\mathcal{O}(t^{2})$. Following [22] and using
the Hamiltonian structure of $\widetilde{H}_{1}(t)$ for each $\rho$,
$\widetilde{H}_{1}(t)$ still has $2\rho$ purely imaginary eigenvalues

$\widetilde{\lambda}_{i,\pm}(t)\pm\imath(t\gamma_{i}^{(\rho)})^{\frac{1}{2\rho}}+\mathcal{O}(t^{\frac{1}{\rho}}),\quad
i=1,\ldots,s_{\rho},$

and their structure inertia indices are exactly the same as those of
$\lambda_{i,\pm}(t)$, $i=1,\ldots,s_{\rho}$.

Note that when $t$ is sufficiently small, then both $H_{1}(t)$ and
$\widetilde{H}_{1}(t)$ have exactly $\sum_{\rho=1}^{k}2s_{\rho}$ purely
imaginary eigenvalues, half of which with positive imaginary parts and half
with negative imaginary parts. As a consequence, $\widetilde{H}_{1}(t)$ does
not have a Lagrangian invariant subspace when $t$ is sufficiently small but
positive, but then also $H(t)$ does not have a Lagrangian invariant subspace
neither.

###  3.3 Perturbation theory for pre-existing purely imaginary eigenvalues

Suppose that a general Hamiltonian matrix $H$ has a semisimple purely
imaginary eigenvalue $i\alpha$ with algebraic multiplicity $r$. Let $V$ be a
full column rank matrix such that

$HV={\imath}\alpha V,\quad W:=\imath V^{H}JV<0.$

The inequality indicates that the structure inertia indices corresponding to
${\imath}\alpha$ are all $-1$, see, [7, 12].

Let $\Delta\geq 0$ and consider the perturbed Hamiltonian matrix
$H(t)=H+tJ\Delta$. Following Theorem 3.2 in [16], for sufficiently small $t$,
$H(t)$ has $r$ semisimple purely imaginary eigenvalues as

$\lambda_{j}(t)=\imath(\alpha+\delta_{j}t)+\mathcal{O}(t^{2}),\qquad
j=1,\ldots,r,$ (80)

where $\delta_{1},\ldots,\delta_{r}$ are the eigenvalues of the pencil
$\lambda W+V^{H}\Delta V$. Since $W<0$ and $V^{H}\Delta V\geq 0$, all
$\delta_{1},\ldots,\delta_{r}\geq 0$. If $\Delta\neq 0$, at least the
imaginary part of some of $\lambda_{1}(t),\ldots,\lambda_{r}(t)$ is
increasing. Based on the first order perturbation theory, there is a matrix
$V(t)=V+\mathcal{O}(t)$ such that

$H(t)V(t)=V(t)\mathop{\rm
diag}\nolimits(\lambda_{1}(t),\ldots,\lambda_{r}(t)),$ (81)

and

$W(t):=\imath V(t)^{H}JV(t)=\imath V^{H}JV+\mathcal{O}(t)<0.$

Similarly, when $W>0$ for some full rank matrix $V$ as above, $H(t)$ has $r$
eigenvalues as those in (80) but $\delta_{1},\ldots,\delta_{r}\leq 0$. Also in
this case there is a matrix $V(t)=V+\mathcal{O}(t)$ satisfying (81), but the
corresponding $W(t)>0$.

Combining these observations with the results in the previous subsection, we
have the global picture. Suppose that $H_{0}$ already has purely imaginary
eigenvalues. Consider a small perturbation $J\Delta$ with
$\Delta=\left[\begin{array}[]{cc}\Delta_{11}&\Delta_{21}^{H}\\\
\Delta_{21}&\Delta_{22}\end{array}\right]\geq 0$. If $Fx={\imath}\alpha x$ and
$\Delta_{11}x\neq 0$ at least for some purely imaginary eigenvalue
${\imath}\alpha$ of $F$, then $H_{0}+J\Delta$ still will have purely imaginary
eigenvalues that are semisimple. The eigenvalues with the maximum imaginary
parts must have structure inertia indices $-1$ and those with the minimum
imaginary parts must have structure inertia indices $1$. If we keep adding
perturbations $J\Delta$ with $\Delta\geq 0$, this will keep purely imaginary
eigenvalues on the imaginary axis. Those with negative structure inertia
indices will be nondecreasing and those with positive structure inertia
indices will be nonincreasing. Some purely imaginary eigenvalues with opposite
structure inertia indices may collide and leave the imaginary axis by adding
$J\Delta$ with $\Delta>0$ ([16]). However, based on the properties shown
above, the extreme purely imaginary eigenvalues never have such a chance and
will stay on the imaginary axis and keep the structure inertia indices.

In summary, once $H_{0}$ has purely imaginary eigenvalues, then
$H_{0}+J\Delta$ will not have a Lagrangian invariant subspace for any
$\Delta\geq 0$, unless the purely imaginary eigenvalues ${\imath}\alpha$ of
$F$ are _non-detectable_ in $(F,\Delta_{11})$, i.e. $\mathop{\rm
rank}\nolimits[{\imath}\alpha I-F,\Delta_{11}]<n$.

###  3.4 Perturbation of eigenvalues that are not purely imaginary

In this subsection, we will show that by adding a matrix $J\Delta$, with a
nonzero perturbation
$\Delta=\left[\begin{array}[]{cc}\Delta_{11}&\Delta_{21}^{H}\\\
\Delta_{21}&\Delta_{22}\end{array}\right]\geq 0$, to $H_{0}$ as in (49),
$H(t)=H_{0}+tJ\Delta$ will eventually have purely imaginary eigenvalues
(including maybe the eigenvalue zero) when $t>0$ is sufficiently large. We
assume that $F$ does not have purely imaginary eigenvalues. Therefore $F$ is
invertible. Let $U$ be unitary such that

$U^{H}\Delta_{11}U=\left[\begin{array}[]{cc}0&0\\\
0&\widetilde{\Delta}_{22}\end{array}\right],\quad\widetilde{\Delta}_{22}>0.$

Since $\Delta_{11}$ is positive semidefinite, we have
$\Delta_{21}U=\left[\begin{array}[]{cc}0&\widetilde{\Delta}_{2}\end{array}\right]$.
Partitioning accordingly
$FU=\left[\begin{array}[]{cc}\widetilde{F}_{1}&\widetilde{F}_{2}\end{array}\right]$,
then since $F$ is invertible, $\widetilde{F}_{1}$ has full column rank. Let
$V$ be unitary such that

$V^{H}\widetilde{F}_{1}=\left[\begin{array}[]{c}\widetilde{F}_{11}\\\
0\end{array}\right]$

with $\widetilde{F}_{11}$ invertible and set

$V^{H}\widetilde{F}_{2}=\left[\begin{array}[]{c}\widetilde{F}_{12}\\\
\widetilde{F}_{22}\end{array}\right],\quad
V^{H}\widetilde{\Delta}_{2}=\left[\begin{array}[]{c}\widetilde{\Delta}_{32}\\\
\widetilde{\Delta}_{42}\end{array}\right],\quad
V^{H}GV=\left[\begin{array}[]{cc}\widetilde{G}_{11}&\widetilde{G}_{21}^{H}\\\
\widetilde{G}_{21}&\widetilde{G}_{22}\end{array}\right],\quad
V^{H}\Delta_{22}V=\left[\begin{array}[]{cc}\widetilde{\Delta}_{33}&\widetilde{\Delta}_{43}^{H}\\\
\widetilde{\Delta}_{43}&\widetilde{\Delta}_{44}\end{array}\right].$

Then

$\left[\begin{array}[]{cc}U&0\\\
0&V\end{array}\right]^{H}J^{H}H(t)\left[\begin{array}[]{cc}U&0\\\
0&V\end{array}\right]=\left[\begin{array}[]{cccc}0&0&\widetilde{F}_{11}^{H}&0\\\
0&t\widetilde{\Delta}_{22}&(\widetilde{F}_{12}+t\widetilde{\Delta}_{32})^{H}&(\widetilde{F}_{22}+t\widetilde{\Delta}_{42})^{H}\\\
\widetilde{F}_{11}&\widetilde{F}_{12}+t\widetilde{\Delta}_{32}&\widetilde{G}_{11}+t\widetilde{\Delta}_{33}&(\widetilde{G}_{21}+t\widetilde{\Delta}_{43})^{H}\\\
0&\widetilde{F}_{22}+t\widetilde{\Delta}_{42}&\widetilde{G}_{21}+t\widetilde{\Delta}_{43}&\widetilde{G}_{22}+t\widetilde{\Delta}_{44}\end{array}\right].$

Using $\widetilde{F}_{11}^{H}$ and $\widetilde{F}_{11}$ as pivots to eliminate
the blocks in positions $(2,3),(4,3)$ and $(3,2),(3,4)$, respectively, it
follows that $J^{H}H(t)$ is congruent to

$\left[\begin{array}[]{cccc}0&0&\widetilde{F}_{11}^{H}&0\\\
0&t\widetilde{\Delta}_{22}&0&(\widetilde{F}_{22}+t\widetilde{\Delta}_{42})^{H}\\\
\widetilde{F}_{11}&0&\widetilde{G}_{11}+t\widetilde{\Delta}_{33}&0\\\
0&\widetilde{F}_{22}+t\widetilde{\Delta}_{42}&0&\widetilde{G}_{22}+t\widetilde{\Delta}_{44}\end{array}\right],$

and furthermore also to $\mathop{\rm diag}\nolimits(M_{1},M_{2})$, where

$M_{1}=\left[\begin{array}[]{cc}0&\widetilde{F}_{11}^{H}\\\
\widetilde{F}_{11}&\widetilde{G}_{11}+t\widetilde{\Delta}_{33}\end{array}\right],\quad
M_{2}=\left[\begin{array}[]{cc}t\widetilde{\Delta}_{22}&(\widetilde{F}_{22}+t\widetilde{\Delta}_{42})^{H}\\\
\widetilde{F}_{22}+t\widetilde{\Delta}_{42}&\widetilde{G}_{22}+t\widetilde{\Delta}_{44}\end{array}\right].$

Since $\widetilde{F}_{11}$ is invertible, $M_{1}$ is invertible and has the
same number of positive and negative inertia indices. For $t>0$, $M_{2}$ is
congruent to $\mathop{\rm
diag}\nolimits(t\widetilde{\Delta}_{22},\widehat{M})$ with

$\displaystyle\widehat{M}$ $\displaystyle=$
$\displaystyle\widetilde{G}_{22}+t\widetilde{\Delta}_{44}-t^{-1}(\widetilde{F}_{22}+t\widetilde{\Delta}_{42})\widetilde{\Delta}_{22}^{-1}(\widetilde{F}_{22}+t\widetilde{\Delta}_{42})^{H}$
$\displaystyle=$
$\displaystyle\widetilde{G}_{22}-t^{-1}\widetilde{F}_{22}\widetilde{\Delta}_{22}^{-1}\widetilde{F}_{22}^{H}+t(\widetilde{\Delta}_{44}-\widetilde{\Delta}_{42}\widetilde{\Delta}_{22}^{-1}\widetilde{\Delta}_{42}^{H})-\widetilde{F}_{22}\widetilde{\Delta}_{22}^{-1}\widetilde{\Delta}_{42}^{H}-\widetilde{\Delta}_{42}\widetilde{\Delta}_{22}^{-1}\widetilde{F}_{22}^{H}.$

We may choose $\Delta$ such that
$\widetilde{\Delta}_{44}-\widetilde{\Delta}_{42}\widetilde{\Delta}_{22}^{-1}\widetilde{\Delta}_{42}^{H}>0$.
Then when $t$ is sufficiently large we have $\widehat{M}>0$ and $M_{2}>0$ as
well. When this happens, then the positive and negative inertia indices of
$J^{H}H(t)$ cannot be equal. This indicates that $H(t)$ has purely imaginary
eigenvalues, since otherwise $J^{H}H(t)$ must have $n$ positive and $n$
negative inertia indices. This shows that there is always $\Delta\geq 0$ so
that $H(t)$ has purely imaginary eigenvalues for some $t>0$.

The analysis shows that we are always able to choose $\Delta_{1}\geq 0$ to
move some of the eigenvalues of $H_{0}$ to the imaginary axis, then freeze
these eigenvalues and move other eigenvalues to the imaginary axis with
another $\Delta_{2}\geq 0$, and continue this perturbation process until all
eigenvalues of $H_{0}+J\Delta$ are on the imaginary axis and the Lagrangian
invariant subspace is unique. If $H_{0}$ is the Hamiltonian matrix $H$ of (3),
using the relation (41), then under the assumption that $(F,G)$ is
controllable and $(F,K)$ is observable, the positive definite solution of (1)
associated with the matrix $\Delta$ touches the boundary of the solution set
in the sense that we are unable to add any further positive semidefinite
matrix to $\Delta$. Note that $\Delta$ is not unique, since there are many
different ways to move the eigenvalues of $H_{0}$ to the imaginary axis.

We may move one pair of eigenvalues at a time. In the situation that $F$ and
$-F^{H}$ do not have common eigenvalues, the above procedure may be applied to
perturb a single eigenvalue of $F$ as well as the corresponding one in
$-F^{H}$. In this case, we may assume that $F=\mathop{\rm
diag}\nolimits(F_{11},F_{22})$ where $F_{22}$ has a single eigenvalue
$\lambda$ that is different from those of $F_{11}$. Partition
$G=\left[\begin{array}[]{cc}G_{11}&G_{21}^{H}\\\
G_{21}&G_{22}\end{array}\right]$ conformably. If we restrict

$\Delta=\left[\begin{array}[]{cc|cc}0&0&0&0\\\
0&\Delta_{11}&0&\Delta_{21}^{H}\\\ \hline\cr 0&0&0&0\\\
0&\Delta_{21}&0&\Delta_{22}\end{array}\right]\geq 0,$

then we have

$H(t)=H_{0}+tJ\Delta=\left[\begin{array}[]{cc|cc}F_{11}&0&G_{11}&G_{21}^{H}\\\
0&F_{22}+t\Delta_{21}&G_{21}&G_{22}+t\Delta_{22}\\\ \hline\cr
0&0&-F_{11}^{H}&0\\\
0&-t\Delta_{11}&0&-(F_{22}+t\Delta_{21})^{H}\end{array}\right].$

With such a perturbation $\Delta$, the eigenvalues of $F_{11}$ and
$-F_{11}^{H}$ remain the same and the changes take place in the reduced
problem

$\left[\begin{array}[]{cc}F_{22}&G_{22}\\\
0&-F_{22}^{H}\end{array}\right]+tJ\left[\begin{array}[]{cc}\Delta_{11}&\Delta_{21}^{H}\\\
\Delta_{21}&\Delta_{22}\end{array}\right].$

For this submatrix, we may use exactly the same procedure to move the
eigenvalues $\lambda$ and $-\bar{\lambda}$ (from $-F_{22}^{H}$) to the
imaginary axis. If $F$ and $-F^{H}$ have common eigenvalues, then we may
perform a symplectic similarity transformation on $H_{0}$ so that the
resulting matrix is still Hamiltonian block upper triangular as in (49), but
the new $F$ and $-F^{H}$ do not share any eigenvalues. Then we are able to
move a single eigenvalue of the new $F$ to the imaginary axis again.

##  4 Conclusion

We have analyzed the solution sets of the algebraic Riccati inequality (1) and
the limiting algebraic Riccati equation (2). Using eigenvalue perturbation
theory we have shown how this set can be characterized via eigenvalue
perturbation results for the associated Hamiltonian matrix. The analysis shows
that there is always a perturbation for the solution of the Riccati inequality
that leads to a unique solution where the associated Hamiltonian matrix has
all eigenvalues on the imaginary axis and still has a unique Lagrangian
invariant subspace.

## References

  * [1] D. Bankmann, V. Mehrmann, Y. Nesterov, and P. Van Dooren.  Computation of the analytic center of the solution set of the linear matrix inequality arising in continuous- and discrete-time passivity analysis.  Vietnam J. Mathematics, 48:633–660, 2020.
  * [2] C. Beattie, V. Mehrmann, and P. Van Dooren.  Robust port-Hamiltonian representations of passive systems.  Automatica, (100):182–186, 2019.
  * [3] C. Beattie, V. Mehrmann, and H. Xu.  Port-Hamiltonian realizations of linear time invariant systems.  http://arxiv.org/abs/2201.05355, 2022.
  * [4] P. Benner.  Numerical solution of special algebraic riccati equations via an exact line search method.  In 1997 European Control Conference (ECC), pages 3136–3141. IEEE, 1997.
  * [5] S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan.  Linear Matrix Inequalities in Systems and Control Theory.  SIAM, Philadelphia, 1994.
  * [6] H. Faßbender, D.S. Mackey, N. Mackey, and H. Xu.  Hamiltonian square roots of skew-hamiltonian matrices.  Linear Algebra Appl., 287:125–159, 1999.
  * [7] G. Freiling, V. Mehrmann, and H. Xu.  Existence, uniqueness and parametrization of Lagrangian invariant subspaces.  SIAM J. Matrix Anal. Appl., 23:1045–1069, 2002.
  * [8] N. Gillis, V. Mehrmann, and P. Sharma.  Computing nearest stable matrix pairs.  Numer. Lin. Alg. Appl., 25:e2153, 2018.  https://doi.org/10.1002/nla.2153.
  * [9] H. Kano and T. Nishimura.  Solution structure of algebraic matrix riccati equations with nonnegative-definite quadratic and constant terms.  In Proceedings of the ISCIE International Symposium on Stochastic Systems Theory and its Applications, volume 1994, pages 43–48, 1994\.
  * [10] P. Lancaster and L. Rodman.  The Algebraic Riccati Equation.  Oxford University Press, Oxford, 1995.
  * [11] V.B. Lidskii.  Perturbation theory of non-conjugate operators.  USSR Comput. Math. and Math. Physics, 6:73–85, 1966.
  * [12] W.-W. Lin, V. Mehrmann, and H. Xu.  Canonical forms for Hamiltonian and symplectic matrices and pencils.  Linear Algebra Appl., 301–303:469–533, 1999.
  * [13] V. Mehrmann.  The Autonomous Linear Quadratic Control Problem, Theory and Numerical Solution, volume 163 of Lecture Notes in Control and Inform. Sci. Springer-Verlag, Heidelberg, July 1991.
  * [14] V. Mehrmann and P. Van Dooren.  Optimal robustness of port-hamiltonian systems.  SIAM J. Matrix Anal. Appl., 41:134–151, 2020.
  * [15] V. Mehrmann and B. Unger.  Control of port-Hamiltonian differential-algebraic systems and applications.  Acta Numerica, pages 395–515, 2023.
  * [16] V. Mehrmann and H. Xu.  Perturbation of purely imaginary eigenvalues of Hamiltonian matrices under structured perturbations.  Electron. J. Linear Algebra, 17:234–257, 2008.
  * [17] J. Moro, J.V. Burke, and M.L. Overton.  On the Lidskii–Vishik–Lyusternik perturbation theory for eigenvalues of matrices with arbitrary Jordan structure.  SIAM J. Matrix Anal. Appl., 18:793–817, 1997.
  * [18] P. Van Dooren.  The computation of Kronecker’s canonical form of a singular pencil.  Linear Algebra Appl., 27:103–121, 1979.
  * [19] J. C. Willems.  Least squares stationary optimal control and the algebraic Riccati equation.  IEEE Trans. Automat. Control, AC-16(6):621–634, 1971.
  * [20] J. C. Willems.  Dissipative dynamical systems – Part I: General theory.  Arch. Ration. Mech. Anal., 45:321–351, 1972.
  * [21] J. C. Willems.  Dissipative dynamical systems – Part II: Linear systems with quadratic supply rates.  Arch. Ration. Mech. Anal., 45:352–393, 1972.
  * [22] H. Xu.  Invariant subspace perturbation of a matrix with jordan blocks.  https://arxiv.org/abs/2311.12219, page , 2023.