Linear System Matrices of Rational Transfer Functions

Abstract

In this paper we derive new sufficient conditions for a linear system matrix $S(\lambda ):=\begin{bmatrix} T(\lambda ) \;&{}\; -U(\lambda ) \\ V(\lambda ) \;&{}\; W(\lambda ) \end{bmatrix},$ where $T(\lambda )$ is assumed regular, to be strongly irreducible. In particular, we introduce the notion of strong minimality, and the corresponding conditions are shown to be sufficient for a polynomial system matrix to be strongly minimal. A strongly irreducible or minimal system matrix has the same structural elements as the rational matrix $R(\lambda ):= W(\lambda ) + V(\lambda )T(\lambda )^{-1}U(\lambda ),$ which is also known as the transfer function connected to the system matrix $S(\lambda )$. The pole structure, zero structure and null space structure of $R(\lambda )$ can be then computed with the staircase algorithm and the QZ algorithm applied to pencils derived from $S(\lambda )$. We also show how to derive a strongly minimal system matrix from an arbitrary linear system matrix by applying to it a reduction procedure, that only uses unitary equivalence transformations. This implies that numerical errors performed during the reduction procedure remain bounded. Since we use unitary transformations in both the reduction procedure and the computation of the eigenstructure, this guarantees that we computed the exact eigenstructure of a perturbed linear system matrix, but where the perturbation is of the order of the machine precision.

1 Introduction

Already in the seventies, Rosenbrock [6] introduced the concept of a polynomial system matrix

$$\begin{aligned} S(\lambda ):=\left[ \begin{array}{ccc} T(\lambda ) \;&{}\; -U(\lambda ) \\ V(\lambda ) \;&{}\; W(\lambda ) \end{array}\right] , \end{aligned}$$

(1)

where $T(\lambda )$ is assumed to be regular. He showed that the finite pole and zero structure of its transfer function matrix $R(\lambda )= W(\lambda ) + V(\lambda )T(\lambda )^{-1}U(\lambda )$ can be retrieved from the polynomial matrices $T(\lambda )$ and $S(\lambda )$, respectively, provided it is irreducible or minimal, meaning that the matrices

$$\begin{aligned} \left[ \begin{array}{ccc} T(\lambda ) \;&\; -U(\lambda ) \end{array}\right] , \quad \left[ \begin{array}{ccc} T(\lambda ) \\ V(\lambda ) \end{array}\right] , \end{aligned}$$

(2)

have, respectively, full row and column rank for all finite $\lambda$. This was already well known for state-space models of a proper transfer function $R_p(\lambda )$, where the system matrix takes the special form

$$S_p(\lambda ):=\left[ \begin{array}{ccc} \lambda I-A \;&{}\; -B \\ C \;&{}\; D \end{array}\right] $$

where (A, B) is controllable and (A, C) is observable, meaning that $S_p(\lambda )$ is minimal. That is, $\left[ \begin{array}{ccc} \lambda I-A \;&\; -B \end{array}\right]$ and $\left[ \begin{array}{ccc} \lambda I-A \\ C \end{array}\right]$ both satisfy the conditions in (2), respectively. The poles of such a proper transfer function are all finite and are the eigenvalues of A, while the finite zeros are the finite generalized eigenvalues of the pencil $S_p(\lambda )$. The main advantage of using state-space models is that there are algorithms to compute the eigenstructure using unitary transformations only. There are also algorithms available to derive a minimal state-space model from a non-minimal one, and these algorithms are also based on unitary transformations only [8].

When allowing generalized state space models, then all transfer functions can be realized by a system matrix of the type

$$\begin{aligned} S_g(\lambda ):=\left[ \begin{array}{ccc} \lambda E-A \;&{}\; -B \\ C \;&{}\; D \end{array}\right] , \end{aligned}$$

(3)

since the matrix E is allowed to be singular. Moreover, when the pencils

$$\begin{aligned} \left[ \begin{array}{ccc} \lambda E-A \;&\; -B \end{array}\right] , \left[ \begin{array}{ccc} \lambda E-A \\ C \end{array}\right] , \end{aligned}$$

(4)

have, respectively, full row rank and column rank for all finite $\lambda$, then we retrieve the irreducibility or minimality conditions of Rosenbrock in (2), which imply that the finite poles of $R(\lambda ):=D+C(\lambda E -A)^{-1}B$ are the finite eigenvalues of $\lambda E-A$ and the finite zeros of $R(\lambda )$ are the finite zeros of $S_g(\lambda )$. It was shown in [10] that when imposing also the conditions that the pencil in (3) is strongly irreducible, meaning that the matrices in (4) have full row rank for all finite and infinite $\lambda$, then also the infinite pole and zero structure of $R(\lambda )$ can be retrieved from the infinite structure of $\lambda E-A$ and $S_g(\lambda )$, respectively, and that the left and right minimal indices of $R(\lambda )$ and $S_g(\lambda )$ are also the same. Moreover, a reduction procedure to derive a strongly irreducible generalized state-space model from a reducible one was also given in [8], and it is also based on unitary transformations only.

In [11] these results were then extended to arbitrary polynomial models, but the procedure required irreducibility tests that were more involved. In this paper we will show that these conditions can again be simplified (and also made more uniform) when the system matrix is linear, i.e.,

$$\begin{aligned} S(\lambda ):=\left[ \begin{array}{ccc} A(\lambda ) \;&{}\; -B(\lambda ) \\ C(\lambda ) \;&{}\; D(\lambda ) \end{array}\right] :=\left[ \begin{array}{ccc} \lambda A_1 -A_0 \;&{}\; B_0- \lambda B_1 \\ \lambda C_1-C_0 \;&{}\; \lambda D_1-D_0 \end{array}\right] . \end{aligned}$$

(5)

We will define the notion of strongly minimal polynomial system matrix, and we will prove that the strong minimality conditions imply the strong irreducibility conditions in [11]. We remark that, although the notions of irreducible or minimal polynomial system matrix refer to the same conditions in (2), the conditions for a polynomial system matrix to be strongly irreducible or strongly minimal are different in general. We will also show that when the strong minimality conditions are not satisfied, we can reduce the system matrix to one where they are satisfied, and this without modifying the transfer function. Such a procedure was already derived in [9], but only for linear system matrices that were already minimal at finite points. In this paper we thus extend this to arbitrary linear system matrices.

In the next Section we briefly recall the background material for this paper and introduce the basic notation. In Sect. 3 we also recall the definition of strongly irreducible polynomial system matrix in [11], and we introduce the notion of strong minimality. In addition, we establish the relation between them. We then give, in Sect. 4, an algorithm to construct a strongly minimal linear system matrix from an arbitrary one, and we discuss the computational aspects in Sect. 5. Finally, we end with some numerical experiments in Sect. 6 and some concluding remarks in Sect. 7.

2 Background

We will restrict ourselves here to polynomial and rational matrices with coefficients in the field of complex numbers $\mathbb {C}$. The set of $m\times n$ polynomial matrices, denoted by $\mathbb {C}[\lambda ]^{m\times n}$ and the set of $m\times n$ rational matrices, denoted by $\mathbb {C}(\lambda )^{m\times n}$, can both be viewed as matrices over the field of rational functions with complex coefficients, denoted by $\mathbb {C}(\lambda )$.

Every rational matrix can have poles and zeros and has a right and a left null space (these can be trivial, i.e., equal to $\{0\}$). Via the local Smith-McMillan form, one can associate structural indices to the poles and zeros, and via the notion of minimal polynomial bases for rational vector spaces, one can associate so called right and left minimal indices to the right and left null spaces. We briefly recall here these different types of indices. Since we assumed (for simplicity) that the coefficients of the rational matrix are in $\mathbb {C}$, the poles and zeros are in the same set.

Definition 1

A square rational matrix $M(\lambda )\in \mathbb {C}(\lambda )^{m\times m}$ is said to be regular at a point $\lambda _0\in \mathbb {C}$ if the matrix $M(\lambda _0)$ is bounded (i.e., $M(\lambda _0)\in \mathbb {C}^{m\times m}$) and is invertible. This is equivalent to both rational matrices $M(\lambda )$ and $M(\lambda )^{-1}$ having a convergent Taylor expansion around the point $\lambda =\lambda _0$. Namely,

$$\begin{aligned} M(\lambda ):= & {} M_{0}+(\lambda -\lambda _0)M_{1}+(\lambda -\lambda _0)^2M_2+(\lambda -\lambda _0)^3M_3+\cdots ,\\ M(\lambda )^{-1}:= & {} M_{0}^{-1}+(\lambda -\lambda _0)H_{1}+(\lambda -\lambda _0)^2H_2+(\lambda -\lambda _0)^3H_3+\cdots . \end{aligned}$$

If $\lambda =\infty$, $M(\lambda )$ is said to be biproper or regular at infinity if the Taylor expansions above are in terms of $1/\lambda$ instead of the factor $(\lambda -\lambda _0).$

Definition 2

Let $R(\lambda )$ be an arbitrary $m\times n$ rational matrix of normal rank r. Then its local Smith-McMillan form at a point $\lambda _0\in \mathbb {C}$ is the diagonal matrix obtained under rational left and right transformations $M_{\ell }(\lambda )$ and $M_r(\lambda )$, that are regular at $\lambda _0$:

$$\begin{aligned} M_{\ell }(\lambda )R(\lambda )M_r(\lambda ) = \left[ \begin{array}{cc} \text {diag}((\lambda -\lambda _{0})^{d_{1}} ,\ldots , (\lambda -\lambda _{0})^{d_{r}}) &{} 0 \\ 0&{} 0_{(m-r)\times (n-r)} \end{array}\right] , \end{aligned}$$

(6)

where $d_1\le d_2 \le \cdots \le d_r$. If $\lambda _0=\infty$, the basic factor $(\lambda -\lambda _0)$ is replaced by $\frac{1}{\lambda }$ and the transformation matrices are then biproper. The latter can be viewed as a change of variable $\mu =\frac{1}{\lambda }$ which transform $\lambda _0=\infty$ to $\mu _0=0$.

Remark 1

The normal rank of a rational matrix is the size of its largest nonidentically zero minor. The indices $d_i$ are unique and are called the structural indices of $R(\lambda )$ at $\lambda _0$. In particular, the strictly positive indices correspond to a zero at $\lambda _0,$ and the strictly negative indices correspond to a pole at $\lambda _0$. The zero degree is defined as the sum of all structural indices of all zeros (infinity included), and the polar degree is the sum of all structural indices (in absolute value) of all poles (infinity included).

Example 1

Let us consider the $2\times 2$ rational matrix

$$\begin{aligned} R(\lambda ) = \left[ \begin{array}{cc} e_5(\lambda ) \;&{}\; 0 \\ c/\lambda \;&{}\; e_1(\lambda ) \end{array}\right] \end{aligned}$$

(7)

where $e_5(\lambda )$ is a monic polynomial of degree 5 and $e_1(\lambda )$ is a monic polynomial of degree 1, with $e_5(0)\ne 0$ and $e_1(0)\ne 0$. If $c\ne 0$, the only poles are 0 and infinity, and the corresponding local Smith-McMillan forms for these two points are

$$ \lambda _0=0 : \text {diag}(\lambda ^{-1},\lambda ^1), \quad \lambda _0=\infty \; (\mu _0=0) : \text {diag}(\mu ^{-5},\mu ^{-1}), $$

indicating that $\lambda _0=0$ is a zero as well as a pole. The other finite zeros are the six finite roots of $e_5(\lambda )$ and $e_1(\lambda )$. The polar degree and the zero degree for this example are thus both equal to 7. When $c=0$, the pole and zero at $\lambda =0$ disappear and the matrix is polynomial instead of rational. The polar and zero degree are then both equal to 6.

The above definitions of pole and zero structure of a rational matrix $R(\lambda )$ are those that are commonly used in linear systems theory (see [6]) and are due to McMillan. They describe the spectral properties of a rational matrix. But when applying them to matrix pencils $S(\lambda )$ we may wonder if they coincide with definitions of eigenvalues and generalized eigenvalues and their multiplicities, i.e. the Kronecker structure of $S(\lambda )$ (see [3]).

Definition 3

The Kronecker canonical form of an arbitrary $m\times n$ pencil $\lambda B-A$ of normal rank r is a block diagonal form obtained via invertible transformations S and T :

$$ S(\lambda B-A)T = \text {diag}(L^T_{\eta _1}(\lambda ), \ldots , L^T_{\eta _{m-r}}(\lambda ), \lambda I_{r_f} - A_J, \lambda N - I_{r_\infty }, L_{\epsilon _1}(\lambda ), \ldots , L_{\epsilon _{n-r}}(\lambda ) )$$

where $A_J$ is in Jordan form, N is nilpotent and in Jordan form, and

$$L_k(\lambda ):=\left[ \begin{array}{cccc} \lambda &{} 1 \\ &{} \ddots &{} \ddots \\ &{} &{} \lambda &{} 1 \end{array}\right] $$

is a $k\times (k+1)$ singular pencil. The finite eigenvalues of $(\lambda B-A)$ are the $r_f$ eigenvalues of $A_J$ and its $r_\infty$ infinite eigenvalues are the generalized eigenvalues of $\lambda N-I_{r_\infty }$.

For this comparison, we only need to look at zeros, since a pencil has only one pole (namely, infinity) and its multiplicity is the rank of the coefficient of $\lambda$. In other words, its polar structure is trivial. But what about the correspondence of the zero structure of $S(\lambda )$ (in the McMillan sense) and the eigenvalue structure of $S(\lambda )$ (in the sense of Kronecker)? It turns out that for finite eigenvalues of $S(\lambda )$ there is a complete isomorphism with the zero structure of $S(\lambda )$: every Jordan block of size k at an eigenvalue $\lambda _0$ in the Kronecker canonical form of $S(\lambda )$ corresponds to an elementary divisor $(\lambda -\lambda _0)^k$ in the Smith-McMillan form of $S(\lambda )$. But for $\lambda =\infty$, there is a difference. It is well known (see [10]) that a Kronecker block of size k at $\lambda =\infty$ corresponds to an elementary divisor $(\frac{1}{\lambda })^{(k-1)}$ in the Smith-McMillan form. For the point at infinity there is thus a shift of 1 in the structural indices. For this reason we want to make a clear distinction between both index sets. Whenever we talk about zeros, we refer to the McMillan structure, and whenever we talk about eigenvalues, we refer to the Kronecker structure.

It is well known that every rational vector subspace $\mathcal {V}$, i.e., every subspace $\mathcal {V} \subseteq \mathbb {C}(\lambda )^n$ over the field $\mathbb {C}(\lambda )$, has bases consisting entirely of polynomial vectors. Among them some are minimal in the following sense introduced by Forney [2]: a minimal basis of $\mathcal {V}$ is a basis of $\mathcal {V}$ consisting of polynomial vectors whose sum of degrees is minimal among all bases of $\mathcal {V}$ consisting of polynomial vectors. The fundamental property [2, 5] of such bases is that the ordered list of degrees of the polynomial vectors in any minimal basis of $\mathcal {V}$ is always the same. Therefore, these degrees are an intrinsic property of the subspace $\mathcal {V}$ and are called the minimal indices of $\mathcal {V}$. This leads to the definition of the minimal bases and indices of a rational matrix. An $m\times n$ rational matrix $R(\lambda )$ of normal rank r smaller than m and/or n has non-trivial left and/or right rational null-spaces, respectively, over the field $\mathbb {C}(\lambda )$:

$$\begin{aligned} \mathcal{N}_{\ell }(R)\!\!:= & {} \!\left\{ y(\lambda )^T \in \mathbb {C}(\lambda )^{1 \times m} \,:\,y(\lambda )^T R(\lambda )\equiv 0^T\right\} ,\\ \mathcal{N}_r(R)\!\!:= & {} \!\left\{ x(\lambda )\in \mathbb {C}(\lambda )^{n \times 1} \,:\, R(\lambda )x(\lambda )\equiv 0\right\} . \end{aligned}$$

Rational matrices with non-trivial left and/or right null-spaces are said to be singular. If the rational subspace $\mathcal{N}_{\ell }(R)$ is non-trivial, it has minimal bases and minimal indices, which are called the left minimal bases and indices of $R(\lambda )$. Analogously, the right minimal bases and indices of $R(\lambda )$ are those of $\mathcal{N}_{r}(R)$, whenever this subspace is non-trivial. Notice that an $m\times n$ rational matrix of normal rank r has $m-r$ left minimal indices $\{ \eta _1, \ldots , \eta _{m-r}\}$, and $n-r$ right minimal indices $\{ \epsilon _1, \ldots , \epsilon _{n-r}\}$.

The McMillan degree $\delta (R)$ of a rational matrix $R(\lambda )$ is the polar degree introduced in Remark 1. The following degree sum theorem was proven in [10], and relates the McMillan degree to the other structural elements of $R(\lambda )$: to the zero degree $\delta _z(R)$, to the left nullspace degree $\delta _\ell (R)$, that is the sum of all left minimal indices, and to the right nullspace degree $\delta _r(R)$, that is the sum of all right minimal indices.

Theorem 1

Let $R(\lambda )\in \mathbb {C}(\lambda )^{m\times n}$. Then

$$ \delta (R) := \delta _p(R)= \delta _z(R)+ \delta _\ell (R)+ \delta _r(R).$$

3 Strong Irreducibility and Minimality

In this section we recall the strong irreducibility conditions in [11] for polynomial system matrices, and we introduce the notion of strong minimality. Then, we study the relation between them for the case of linear system matrices.

Definition 4

A polynomial system matrix $S(\lambda )$ as in (1) is said to be strongly controllable and strongly observable, respectively, if the polynomial matrices

$$\begin{aligned} \left[ \begin{array}{ccc} T(\lambda ) \;&{}\; -U(\lambda ) \;&{}\; 0 \\ V(\lambda ) \;&{}\; W(\lambda ) \;&{}\;-I \end{array}\right] , \quad \mathrm {and} \quad \left[ \begin{array}{ccc} T(\lambda ) \;&{}\; -U(\lambda ) \\ V(\lambda ) \;&{}\; W(\lambda ) \\ 0 \;&{}\; I \end{array}\right] , \end{aligned}$$

(8)

have no finite or infinite zeros. If both conditions are satisfied, $S(\lambda )$ is said to be strongly irreducible.

Let us now consider the transfer function matrix $R(\lambda )= W(\lambda ) + V(\lambda )T(\lambda )^{-1}U(\lambda )$ of the polynomial system matrix in (1). In such a case, we also say that the system quadruple $\{T(\lambda ),U(\lambda ),V(\lambda ),W(\lambda )\}$ realizes $R(\lambda ).$ Moreover, we say that the system quadruple is strongly irreducible if the polynomial system matrix is strongly irreducible. It was shown in [11] that the pole/zero and null space structure of $R(\lambda )$ can be retrieved from a strongly irreducible system quadruple $\{T(\lambda ),U(\lambda ),V(\lambda ),W(\lambda )\}$ as follows.

Theorem 2

If the polynomial system matrix $S(\lambda )$ in (1) is strongly irreducible, then

• 1. the zero structure of $R(\lambda )$ at finite and infinite $\lambda$ is the same as the zero structure of $S(\lambda )$ at finite and infinite $\lambda$,

• 2. the pole structure of $R(\lambda )$ at finite $\lambda$ is the same as the zero structure at $\lambda$ of $T(\lambda )$,

• 3. the pole structure of $R(\lambda )$ at infinity is the same as the zero structure at infinity of

  $$ \left[ \begin{array}{ccc} T(\lambda ) \;&{}\; -U(\lambda ) \;&{}\; 0 \\ V(\lambda ) \;&{}\; W(\lambda ) \;&{}\; -I \\ 0 \;&{}\; I \;&{}\; 0 \end{array}\right] , $$

• 4. the left and right minimal indices of $R(\lambda )$ and $S(\lambda )$ are the same.

If one specializes this to the generalized state space model (3) one retrieves the results of [10], which are simpler and only involve the pencils $(\lambda E-A)$, (3) and (4). We now show that the above conditions can be simplified when the system matrices are linear as in (5). First, we present the definition of strongly minimal polynomial system matrix.

Definition 5

Let d be the degree of the polynomial system matrix $S(\lambda )$ in (1). $S(\lambda )$ is said to be strongly E-controllable and strongly E-observable, respectively, if the polynomial matrices

$$\begin{aligned} \left[ \begin{array}{cc} T(\lambda ) \;&\; -U(\lambda ) \end{array}\right] , \quad \mathrm {and} \quad \left[ \begin{array}{c} T(\lambda ) \\ V(\lambda ) \end{array}\right] , \end{aligned}$$

(9)

have no finite or infinite¹ eigenvalues, considered as polynomial matrices of grade d. If both conditions are satisfied, $S(\lambda )$ is said to be strongly minimal.

The letter E in the definition of strong E-controllability and E-observability refers to the condition of the matrices in (9) not having eigenvalues, finite or infinite. We prove in Proposition 1 that the strong irreducibility conditions hold if the strong minimality conditions are satisfied. For this, we need to recall Lemma 1 of [10], which we give here in its transposed form. Then, we prove Theorems 3 and 4, and Proposition 1 as a corollary of them.

Lemma 1

The zero structure at infinity of the pencil $\left[ \begin{array}{c|c}\lambda K_1-K_0 \;&\; -L_0 \end{array}\right]$ where $K_1$ has full column rank, is isomorphic to the zero structure at zero of the pencil $\left[ \begin{array}{c|c}K_1- \mu K_0 \;&\; -L_0 \end{array}\right]$. Moreover, if the pencil has full row normal rank, then it has no zeros at infinity, provided the constant matrix $\left[ \begin{array}{c|c}K_1 \;&\; -L_0 \end{array}\right]$ has full row rank.

Proof

The first part is proven in [10]. The second part is a direct consequence of the first part, when filling in $\mu =0$. $\square$

Theorem 3

The pencil

$$\begin{aligned} \left[ \begin{array}{ccc} \lambda A_1 -A_0 \;&{}\; B_0- \lambda B_1 \;&{}\; 0 \\ \lambda C_1-C_0 \;&{}\; \lambda D_1-D_0 \;&{}\; -I \end{array}\right] , \end{aligned}$$

(10)

where $\lambda A_1 -A_0$ is regular, has no zeros at infinity if the pencil

$$\begin{aligned} \left[ \begin{array}{ccc} \lambda A_1 -A_0 \;&\; B_0- \lambda B_1 \end{array}\right] \end{aligned}$$

(11)

has no eigenvalues at infinity.

Proof

Clearly the pencils in (10) and (11) have full row normal rank since $\lambda A_1 -A_0$ is regular. We can thus apply the result of Lemma 1 as follows. If we use an invertible matrix V to “compress” the columns of the coefficient of $\lambda$ in the following pencil

$$ \left[ \begin{array}{cc|c} \lambda A_1 -A_0 \;&{}\; B_0- \lambda B_1 \;&{}\; 0 \\ \lambda C_1-C_0 \;&{}\; \lambda D_1-D_0 \;&{}\; -I \end{array}\right] \left[ \begin{array}{c|c} V \;&{}\; 0 \\ \hline 0 \;&{}\; I \end{array}\right] = \left[ \begin{array}{cc|c} \lambda K_1 -K_0 \;&{}\; -L_0 \;&{}\; 0 \\ \lambda \widehat{K}_1-\widehat{K}_0 \;&{}\; -\widehat{L}_0 \;&{}\; -I \end{array}\right] , $$

such that the matrix $\left[ \begin{array}{c} K_1\\ \widehat{K}_1 \end{array}\right]$ has full column rank, then this pencil has no zeros at infinity provided the constant matrix $\left[ \begin{array}{cc|c} K_1 \;&{}\; -L_0 \;&{}\; 0 \\ \widehat{K}_1 \;&{}\; -\widehat{L}_0 \;&{}\; -I \end{array}\right]$ has full row rank. But if $\left[ \begin{array}{ccc} \lambda A_1 -A_0 \;&\; B_0- \lambda B_1 \end{array}\right]$ has no infinite eigenvalues, it follows that $\left[ \begin{array}{cc} A_1 \;&\; - B_1 \end{array}\right]$ has full row rank. And since $\left[ \begin{array}{cc} A_1 \;&\; - B_1 \end{array}\right] V= \left[ \begin{array}{cc} K_1 \;&\; 0 \end{array}\right]$, $K_1$ must have full row rank as well (in fact, it is invertible). It then follows from Lemma 1 that the pencil in (10) has no zeros at infinity. $\square$

In the next theorem, we state without proof the transposed version of Theorem 3.

Theorem 4

The pencil

$$\begin{aligned} \left[ \begin{array}{ccc} \lambda A_1 -A_0 \;&{}\; B_0- \lambda B_1 \\ \lambda C_1-C_0 \;&{}\; \lambda D_1-D_0 \\ 0 \;&{}\; I \end{array}\right] , \end{aligned}$$

where $\lambda A_1 -A_0$ is regular, has no zeros at infinity if the pencil

$$\begin{aligned} \left[ \begin{array}{ccc} \lambda A_1 -A_0 \\ \lambda C_1-C_0 \end{array}\right] \end{aligned}$$

(12)

has no eigenvalues at infinity.

Let us now consider a linear system matrix

$$\begin{aligned} L(\lambda ) := \lambda L_1-L_0 := \left[ \begin{array}{ccc} \lambda A_1 -A_0 \;&{}\; B_0- \lambda B_1 \\ \lambda C_1-C_0 \;&{}\; \lambda D_1-D_0 \end{array}\right] , \end{aligned}$$

(13)

with $\lambda A_1 -A_0$ regular. Notice that if $L(\lambda )$ is minimal (i.e., satisfies (2)) and, in addition, satisfies the conditions in (11) and (12), then it is strongly minimal. By Theorems 3 and 4, we have that these conditions imply strong irreducibility on linear system matrices. We state such result in Proposition 1.

Proposition 1

A linear system matrix as in (13) is strongly irreducible if it is strongly minimal.

Remark 2

Notice that conditions (11) and (12) are only sufficient, not necessary. But they are easy to test, and also to obtain after a reduction procedure, as we show in Sect. 4.

Theorems 3 and 4 and Proposition 1 can be extended to polynomial system matrices. However, we do not state these results here since, in this paper, we are focusing on linear system matrices. If we recapitulate the results of this section, we obtain the following theorem.

Theorem 5

A linear system pencil $L(\lambda )$ as in (13), realizing the transfer function $R(\lambda ):=(\lambda D_1-D_0)+(\lambda C_1-C_0)( \lambda A_1-A_0)^{-1}( \lambda B_1-B_0)$, is strongly irreducible if it is strongly minimal. Moreover, if $L(\lambda )$ is strongly irreducible then

• 1. the zero structure of $R(\lambda )$ at finite and infinite $\lambda$ is the same as the zero structure of $L(\lambda )$ at finite and infinite $\lambda$,

• 2. the left and right minimal indices of $R(\lambda )$ and $L(\lambda )$ are the same,

• 3. the finite polar structure of $R(\lambda )$ is the same as the finite zero structure of $\lambda A_1-A_0$, and

• 4. the infinite polar structure of $R(\lambda )$ is the same as the infinite zero structure of the pencil

  $$\begin{aligned} \left[ \begin{array}{ccc} \lambda A_1 -A_0 \;&{}\; - \lambda B_1 \;&{}\; 0 \\ \lambda C_1 \;&{}\; \lambda D_1 \;&{}\; -I \\ 0 \;&{}\; I \;&{}\; 0 \end{array}\right] . \end{aligned}$$

  (14)

Remark 3

It follows from this theorem and the degree sum theorem in Theorem 1 that the rank of $L_1$ equals the McMillan degree of $R(\lambda )$, and that there can be no linear system matrix for $R(\lambda )$ with a smaller rank of $L_1$ that satisfies Theorem 5.

It may look strange that there is such a difference in the treatment of finite and infinite poles of $R(\lambda )$ in Theorem 5, but it should be pointed out that the matrices $(B_1, C_1, D_1)$ contribute to the infinite polar structure of $R(\lambda )$, and not to the finite polar structure. Notice that in (14) we have eliminated the matrices $B_0,C_0$ and $D_0$ with strict equivalence transformations using the identity matrices as pivots.

4 Reducing to a Strongly Minimal Linear System Matrix

In this section we give an algorithm to reduce an arbitrary linear system matrix to a strongly minimal one. Given a linear system quadruple $\{A(\lambda ),B(\lambda ),C(\lambda ),D(\lambda )\},$ where $A(\lambda )\in \mathbb {C}(\lambda )^{d\times d}$, $B(\lambda )\in \mathbb {C}(\lambda )^{d\times n}$, $C(\lambda )\in \mathbb {C}(\lambda )^{m\times d}$, $D(\lambda )\in \mathbb {C}(\lambda )^{m\times n}$ and $A(\lambda )$ is assumed to be regular, we describe first how to obtain a strongly E-controllable quadruple $\{A_c(\lambda ),B_c(\lambda ), C_c(\lambda ),D_c(\lambda )\}$ of smaller state dimension $(d-r)$. For that, our reduction procedure deflates finite and infinite “uncontrollable eigenvalues” by proceeding in three different steps. Then the reduction to a strongly E-observable one is dual and can be obtained by mere transposition of the system matrix and application of the first method for obtaining a strongly E-controllable system.

Step 1: We first show that there exist unitary transformations U and V that yield a decomposition of the type

$$\begin{aligned} \left[ \begin{array}{cc} U \;&{}\; 0 \\ 0 \;&{}\; I_m \end{array}\right] \left[ \begin{array}{cc} A(\lambda ) \;&{}\; - B(\lambda ) \\ C(\lambda ) \;&{}\; D(\lambda ) \end{array}\right] \left[ \begin{array}{cc} V \;&{}\; 0 \\ 0 \;&{}\; I _n \end{array}\right] = \left[ \begin{array}{ccc} X(\lambda ) \widehat{W}_{11} \;&{}\;0 \;&{}\; X(\lambda ) W_{13} \\ \widetilde{Y}(\lambda ) \;&{}\; \widetilde{A}(\lambda ) \;&{}\; - \widetilde{B}(\lambda ) \\ \widetilde{Z}(\lambda ) \;&{}\; \widetilde{C}(\lambda ) \;&{}\; D(\lambda ) \end{array}\right] , \end{aligned}$$

(15)

where $\widehat{W}_{11}\in \mathbb {C}^{r\times r}$ and $W_{13}\in \mathbb {C}^{r\times n}$ are constant, and $\widehat{W}_{11}$ is invertible. This will allow us in step 2 to deflate the block $X(\lambda )$ and construct a lower order model that is strongly E-controllable. In order to prove this, we start from the generalized Schur decomposition for singular pencils (see [7])

$$\begin{aligned} U \left[ \begin{array}{cc} A(\lambda ) \;&\; - B(\lambda ) \end{array}\right] W^*= \left[ \begin{array}{ccc} X(\lambda )\;&{}\; 0 \;&{}\; 0 \\ Y(\lambda ) \;&{}\; \widehat{A}(\lambda ) \;&{}\; -\widehat{B}(\lambda ) \end{array}\right] , \end{aligned}$$

(16)

where $X(\lambda ) \in \mathbb {C}[\lambda ]^{r\times r}$ is the regular part of $\begin{bmatrix} A(\lambda ) \;&\; -B(\lambda )\end{bmatrix},$ $\widehat{A}(\lambda ) \in \mathbb {C}[\lambda ]^{(d-r)\times (d-r)}$, and $\begin{bmatrix} \widehat{A}(\lambda ) \;&\; -\widehat{B}(\lambda )\end{bmatrix}$ has no finite or infinite eigenvalues anymore. The decomposition in (16) can be obtained by using unitary transformations U and W. If we partition U as $\left[ \begin{array}{c}U_1 \\ U_2 \end{array}\right] ,$ with $U_1\in \mathbb {C}^{r\times d}$, then

$$ U_1\left[ \begin{array}{c|c} A(\lambda ) \;&\; - B(\lambda ) \end{array}\right] = \left[ \begin{array}{cc|c} X(\lambda )W_{11} \;&\; X(\lambda )W_{12} \;&\; X(\lambda )W_{13} \end{array}\right] , $$

where $W_{11}\in \mathbb {C}^{r\times r}$, $W_{12}\in \mathbb {C}^{r\times (d-r)}$ and $W_{13}\in \mathbb {C}^{r\times n}$ are the corresponding submatrices of W. Since $A(\lambda )$ is regular, $X(\lambda )\begin{bmatrix}W_{11} \;&\; W_{12} \end{bmatrix}$ must be full normal rank, and hence $\begin{bmatrix}W_{11} \;&\; W_{12} \end{bmatrix}$ must be full row rank as well. Therefore, there must exist a unitary matrix V such that $\begin{bmatrix}W_{11} \;&\; W_{12}\end{bmatrix}V= \begin{bmatrix}\widehat{W}_{11} \;&\; 0 \end{bmatrix}$, where $\widehat{W}_{11}$ is invertible. Hence, we have

$$\begin{aligned} \left[ \begin{array}{cc} U \;&{}\; 0 \\ 0 \;&{}\; I_{m} \end{array}\right] \left[ \begin{array}{cc} A(\lambda ) \;&{}\; -B(\lambda ) \\ C(\lambda ) \;&{}\; D(\lambda ) \end{array}\right] \left[ \begin{array}{cc} V \;&{}\; 0 \\ 0 \;&{}\; I_{n} \end{array}\right] = \left[ \begin{array}{ccc} X(\lambda ) \widehat{W}_{11} \;&{}\; 0 \;&{}\; X(\lambda ) W_{13} \\ \widetilde{Y}(\lambda ) \;&{}\; \widetilde{A}(\lambda ) \;&{}\; - \widetilde{B}(\lambda ) \\ \widetilde{Z}(\lambda ) \;&{}\; \widetilde{C}(\lambda ) \;&{}\; D(\lambda ) \end{array}\right] , \end{aligned}$$

where

$$ W \left[ \begin{array}{cc} V \;&{}\; 0 \\ 0 \;&{}\; I_{n} \end{array}\right] = \left[ \begin{array}{ccc} \widehat{W}_{11} \;&{}\; 0 \;&{}\; W_{13}\\ \widehat{W}_{21} \;&{}\; \widehat{W}_{22} \;&{}\; W_{23} \\ \widehat{W}_{31} \;&{}\; \widehat{W}_{32} \;&{}\; W_{33}\end{array}\right] . $$

Step 2: We now define $E := -\widehat{W}_{11}^{-1}W_{13}$ and perform the following non-unitary transformation on the pencil:

$$ \left[ \begin{array}{ccc} X(\lambda )\widehat{W}_{11} \;&{}\; 0 \;&{}\; X(\lambda ) W_{13} \\ \widetilde{Y}(\lambda ) \;&{}\; \widetilde{A}(\lambda ) \;&{}\; - \widetilde{B}(\lambda ) \\ \widetilde{Z}(\lambda ) \;&{}\; \widetilde{C}(\lambda ) \;&{}\; D(\lambda ) \end{array}\right] \! \left[ \begin{array}{ccc} I_{r} \;&{}\; 0 \;&{}\; E \\ 0 \;&{}\; I_{d-r} \;&{}\; 0 \\ 0 \;&{}\; 0 \;&{}\; I_{n} \end{array}\right] \! = \! \left[ \begin{array}{ccc} X(\lambda )\widehat{W}_{11} \;&{}\; 0 \;&{}\; 0 \\ \widetilde{Y}(\lambda ) \;&{}\; \widetilde{A}(\lambda ) &{} \widetilde{Y}(\lambda )E- \widetilde{B}(\lambda ) \\ \widetilde{Z}(\lambda ) \;&{}\; \widetilde{C}(\lambda ) \;&{}\; \widetilde{Z}(\lambda )E +D(\lambda ) \end{array}\right] . $$

We have obtained an equivalent system representation in which the (1, 1)-block, $X(\lambda )\widehat{W}_{11},$ can be deflated since it does not contribute to the transfer function. We then obtain a smaller linear system pencil:

$$ \left[ \begin{array}{cc} \widetilde{A}(\lambda ) \;&{}\; \widetilde{Y}(\lambda )E- \widetilde{B}(\lambda ) \\ \widetilde{C}(\lambda ) \;&{}\; \widetilde{Z}(\lambda )E+D(\lambda ) \end{array}\right] , $$

that has the same transfer function. One can also perform this elimination by another unitary transformation $\widetilde{W}$ constructed to eliminate $W_{13}$:

$$\begin{aligned} \left[ \begin{array}{ccc} \widehat{W}_{11} \;&\; 0 \;&\; W_{13} \end{array}\right] \left[ \begin{array}{ccc} \widetilde{W}_{11} &{} 0 &{} \widetilde{W}_{13} \\ 0 \;&{}\; I_{d-r} \;&{}\; 0 \\ \widetilde{W}_{31} \;&{}\; 0 \;&{}\; \widetilde{W}_{33} \end{array}\right] =\left[ \begin{array}{ccc} I_{r} \;&\; 0 \;&\; 0 \end{array}\right] , \end{aligned}$$

(17)

implying $\widetilde{W}_{11}=\widehat{W}_{11}^*$ , $\widetilde{W}_{31}=W_{13}^*$, and $\widetilde{W}_{13}=-\widehat{W}_{11}^{-1}W_{13}\widetilde{W}_{33}$. This then yields

$$ \left[ \begin{array}{ccc} X(\lambda )\widehat{W}_{11} \;&{}\; 0 \;&{}\; X(\lambda )W_{13} \\ \widetilde{Y}(\lambda ) \;&{}\; \widetilde{A}(\lambda ) \;&{}\; - \widetilde{B}(\lambda ) \\ \widetilde{Z}(\lambda ) \;&{}\; \widetilde{C}(\lambda ) \;&{}\; D(\lambda ) \end{array}\right] \left[ \begin{array}{ccc} \widetilde{W}_{11} \;&{}\; 0 \;&{}\; \widetilde{W}_{13} \\ 0 \;&{}\; I_{d-r} \;&{}\; 0 \\ \widetilde{W}_{31} \;&{}\; 0 \;&{}\; \widetilde{W}_{33} \end{array}\right] $$

$$ = \left[ \begin{array}{ccc} X(\lambda ) \;&{}\; 0 \;&{}\; 0 \\ \widetilde{Y}(\lambda )\widetilde{W}_{11} -\widetilde{B}(\lambda )\widetilde{W}_{31} \;&{}\; \widetilde{A}(\lambda ) \;&{}\; \widetilde{Y}(\lambda )\widetilde{W}_{13} - \widetilde{B}(\lambda )\widetilde{W}_{33} \\ \widetilde{Z}(\lambda )\widetilde{W}_{11}+D(\lambda )\widetilde{W}_{31} \;&{}\; \widetilde{C}(\lambda ) \;&{}\; \widetilde{Z}(\lambda )\widetilde{W}_{13}+D(\lambda )\widetilde{W}_{33} \end{array}\right] . $$

Notice that the new transfer function has now changed, but only by postmultiplication by the constant matrix $\widetilde{W}_{33}$, which moreover is invertible. This follows from

$$ \left[ \begin{array}{c} E\\ I_{n} \end{array}\right] \widetilde{W}_{33}= \left[ \begin{array}{c} \widetilde{W}_{13}\\ \widetilde{W}_{33} \end{array}\right] , $$

expressing that both matrices span the null-space of the same matrix $\left[ \begin{array}{cc}\widehat{W}_{11} \;&\; W_{13} \end{array}\right]$ and where the right hand side matrix has full rank since it has orthonormal columns. This also implies that

$$ \left[ \begin{array}{cc} \widetilde{A}(\lambda ) \;&{}\; \widetilde{Y}(\lambda )E- \widetilde{B}(\lambda ) \\ \widetilde{C}(\lambda ) \;&{}\; \widetilde{Z}(\lambda ) E+D(\lambda ) \end{array}\right] \left[ \begin{array}{cc} I_{d-r} \;&{}\; 0 \\ 0 \;&{}\; \widetilde{W}_{33}\end{array}\right] = \left[ \begin{array}{cc} \widetilde{A}(\lambda ) \;&{}\; \widetilde{Y}(\lambda )\widetilde{W}_{13}- \widetilde{B}(\lambda )\widetilde{W}_{33} \\ \widetilde{C}(\lambda ) \;&{}\; \widetilde{Z}(\lambda ) \widetilde{W}_{13}+D(\lambda )\widetilde{W}_{33} \end{array}\right] ,$$

which shows that their Schur complements are related by the constant matrix $\widetilde{W}_{33}$.

Step 3: Finally, we show that the submatrix

$$ \left[ \begin{array}{cc} \widetilde{A}(\lambda ) \;&\; \widetilde{Y}(\lambda )E- \widetilde{B}(\lambda ) \end{array}\right] \left[ \begin{array}{cc} I_{d-r} \;&{}\; 0 \\ 0 \;&{}\; \widetilde{W}_{33}\end{array}\right] = \left[ \begin{array}{cc} \widetilde{A}(\lambda ) \;&\; \widetilde{Y}(\lambda )\widetilde{W}_{13}- \widetilde{B}(\lambda )\widetilde{W}_{33} \end{array}\right] , $$

has no finite or infinite eigenvalues anymore. For this, we first point out that the following product of unitary matrices has the form given below

$$ W \left[ \begin{array}{ccc} V \;&{}\; 0 \\ 0 \;&{}\; I_{n} \end{array}\right] \left[ \begin{array}{ccc} \widetilde{W}_{11} \;&{}\; 0 \;&{}\; \widetilde{W}_{13} \\ 0 \;&{}\; I_{d-r} \;&{}\; 0 \\ \widetilde{W}_{31} \;&{}\; 0 \;&{}\; \widetilde{W}_{33} \end{array}\right] =: \left[ \begin{array}{ccc} I_{r} \;&{}\; 0 \;&{}\; 0 \\ 0 \;&{}\; \widetilde{V}_{22} \;&{}\; \widetilde{V}_{23} \\ 0 \;&{}\; \widetilde{V}_{32} \;&{}\; \widetilde{V}_{33} \end{array}\right] =: \left[ \begin{array}{ccc} I_{r} \;&{}\; 0 \\ 0 \;&{}\; \widetilde{V} \end{array}\right] $$

because the identity (17) implies that the first block column equals $\begin{bmatrix} I_r \;&\; 0 \;&\; 0 \end{bmatrix}$. This then implies the equality

$$ \left[ \begin{array}{ccc} X(\lambda ) \;&{}\; 0 \;&{}\; 0 \\ \widetilde{Y}(\lambda )\widetilde{W}_{11} -\widetilde{B}(\lambda )\widetilde{W}_{31} \;&{}\; \widetilde{A}(\lambda ) \;&{}\; \widetilde{Y}(\lambda )\widetilde{W}_{13} - \widetilde{B}(\lambda )\widetilde{W}_{33} \end{array}\right] $$

$$ =\left[ \begin{array}{ccc} X(\lambda ) \;&{}\; 0 \;&{}\; 0 \\ Y(\lambda ) \;&{}\; \widehat{A}(\lambda ) \;&{}\; -\widehat{B}(\lambda ) \end{array}\right] \left[ \begin{array}{ccc} I_{r} \;&{}\; 0 \\ 0 \;&{}\; \widetilde{V} \end{array}\right] , $$

which in turn implies that $\left[ \begin{array}{cc} \widetilde{A}(\lambda ) \;&\; \widetilde{Y}(\lambda )\widetilde{W}_{13}- \widetilde{B}(\lambda )\widetilde{W}_{33} \end{array}\right]$ has no finite or infinite eigenvalues. We thus have shown that the system matrix

$$ S_c(\lambda ) := \left[ \begin{array}{cc} A_c(\lambda ) \;&{}\; - B_c(\lambda ) \\ C_c(\lambda ) \;&{}\; D_c(\lambda ) \end{array}\right] := \left[ \begin{array}{cc} \widetilde{A}(\lambda ) \;&{}\; \widetilde{Y}(\lambda )\widetilde{W}_{13} - \widetilde{B}(\lambda )\widetilde{W}_{33} \\ \widetilde{C}(\lambda ) \;&{}\; \widetilde{Z}(\lambda )\widetilde{W}_{13}+D(\lambda )\widetilde{W}_{33} \end{array}\right] $$

is now strongly E-controllable and that its transfer function $R_c(\lambda )$ equals $R(\lambda )\widetilde{W}_{33},$ where $R(\lambda )$ is the transfer function of the original quadruple and $\widetilde{W}_{33}$ is invertible. We summarize the result obtained by the three-step procedure above in Theorem 6, where we denote $d-r$ by $d_c$, to indicate that it is the size of $A_c(\lambda )$ in the new strongly E-controllable system, and r is replaced by $d_{\overline{c}}$, so that $d=d_{\overline{c}}+d_c$.

Theorem 6

Let $\{A(\lambda ),B(\lambda ),C(\lambda ),D(\lambda )\}$ be a linear system quadruple, with $A(\lambda )\in \mathbb {C}[\lambda ]^{d\times d}$ regular, realizing the rational matrix $R(\lambda ):=C(\lambda )A(\lambda )^{-1}B(\lambda )+D(\lambda ) \in \mathbb {C}(\lambda )^{m\times n}.$ Then there exist unitary transformations $U,V \in \mathbb {C}^{d\times d}$ and $\widetilde{W}\in \mathbb {C}^{(d+n)\times (d+n)}$ such that the following identity holds

$$\begin{aligned} \left[ \begin{array}{cc} U \;&{}\; 0 \\ 0 \;&{}\; I_m \end{array}\right] \! \left[ \begin{array}{cc} A(\lambda ) \;&{}\; - B(\lambda ) \\ C(\lambda ) \;&{}\; D(\lambda ) \end{array}\right] \! \left[ \begin{array}{cc} V \;&{}\; 0 \\ 0 \;&{}\; I _n \end{array}\right] \! \widetilde{W} = \! \left[ \begin{array}{ccc} X_{\overline{c}}(\lambda ) \;&{}\; 0 \;&{}\; 0 \\ Y_{\overline{c}}(\lambda ) \;&{}\; A_c(\lambda ) \;&{}\; -B_c(\lambda ) \\ Z_{\overline{c}}(\lambda ) \;&{}\; C_c(\lambda ) \;&{}\; D_c(\lambda ) \end{array}\right] , \end{aligned}$$

where $\widetilde{W}$ is of the form $\widetilde{W}:= \left[ \begin{array}{ccc} \widetilde{W}_{11} \;&{}\; 0 \;&{}\; \widetilde{W}_{13} \\ 0 \;&{}\; I_{d_c} \;&{}\; 0 \\ \widetilde{W}_{31} \;&{}\; 0 \;&{}\; \widetilde{W}_{33} \end{array}\right] \in \mathbb {C}^{(d_{\overline{c}}+d_c +n)\times (d_{\overline{c}} +d_c +n)},$ $d_{\overline{c}}$ is the number of (finite and infinite) eigenvalues of $\left[ \begin{array}{cc}A(\lambda ) \;&\; -B(\lambda ) \end{array}\right] ,$ and $X_{\overline{c}}(\lambda )\in \mathbb {C}[\lambda ]^{d_{\overline{c}}\times d_{\overline{c}}}$ is a regular pencil. Moreover,

• (a) the eigenvalues of $\left[ \begin{array}{cc}A(\lambda ) \;&\; -B(\lambda ) \end{array}\right]$ are the eigenvalues of $X_{\overline{c}}(\lambda )$,

• (b) $\left[ \begin{array}{cc}A_c(\lambda ) \;&\; -B_c(\lambda ) \end{array}\right] \in \mathbb {C}[\lambda ]^{d_c\times (d_c +n)}$ has no (finite or infinite) eigenvalues,

• (c) the quadruple $\{A_c(\lambda ),B_c(\lambda ),C_c(\lambda ),D_c(\lambda )\}$ is a realization of the transfer function $R_c(\lambda ):=R(\lambda )\widetilde{W}_{33}$, with $\widetilde{W}_{33}\in \mathbb {C}^{n\times n}$ invertible, and

• (d) if $\left[ \begin{array}{cc}A(\lambda ) \\ C(\lambda ) \end{array}\right]$ has no finite or infinite eigenvalues, then $\left[ \begin{array}{cc}A_c(\lambda ) \\ C_c(\lambda ) \end{array}\right]$ also has no finite or infinite eigenvalues.

Remark 4

Notice that conditions (b) and (d) in Theorem 6 imply that the system quadruple $\{A_c(\lambda ),B_c(\lambda ),C_c(\lambda ),D_c(\lambda )\}$ is strongly minimal.

Proof

The decomposition and the three properties (a), (b) and (c) were shown in the discussion above. The only part that remains to be proven is property (d). This follows from the identity (15), which yields

$$ \left[ \begin{array}{cc} U \;&{}\; 0 \\ 0 \;&{}\; I_{m} \end{array}\right] \left[ \begin{array}{cc} A(\lambda ) \\ C(\lambda ) \end{array}\right] V = \left[ \begin{array}{cc} X(\lambda ) \widehat{W}_{11} \;&{}\; 0 \\ \widetilde{Y}(\lambda ) \;&{}\; A_c(\lambda ) \\ \widetilde{Z}(\lambda ) \;&{}\; C_c(\lambda ) \end{array}\right] . $$

This clearly implies that if $\left[ \begin{array}{cc}A(\lambda ) \\ C(\lambda ) \end{array}\right]$ has full rank for all $\lambda$ (including infinity), then so does $\left[ \begin{array}{cc}A_c(\lambda ) \\ C_c(\lambda ) \end{array}\right]$. $\square$

We state below a dual theorem that constructs, from an arbitrary linear system quadruple $\{A(\lambda ),B(\lambda ),C(\lambda ),D(\lambda )\},$ a subsystem $\{A_o(\lambda ),B_o(\lambda ),C_o(\lambda ),D_o(\lambda )\}$ where $\left[ \begin{array}{cc}A_o(\lambda ) \\ C_o(\lambda ) \end{array}\right]$ has no finite or infinite eigenvalues. Its proof is obtained by applying the previous theorem on the transposed system $\{A^T(\lambda ),C^T(\lambda ),B^T(\lambda ),D^T(\lambda )\}$ and then transposing back the result.

Theorem 7

Let $\{A(\lambda ),B(\lambda ),C(\lambda ),D(\lambda )\}$ be a linear system quadruple, with $A(\lambda )\in \mathbb {C}[\lambda ]^{d\times d}$ regular, realizing the rational matrix $R(\lambda ):=C(\lambda )A(\lambda )^{-1}B(\lambda )+D(\lambda ) \in \mathbb {C}(\lambda )^{m\times n}.$ Then there exist unitary transformations $U,V \in \mathbb {C}^{d\times d}$ and $\widetilde{W}\in \mathbb {C}^{(d+m)\times (d+m)}$ such that the following identity holds

$$\begin{aligned} \widetilde{W} \left[ \begin{array}{cc} U \;&{}\; 0 \\ 0 \;&{}\; I_m \end{array}\right] \! \left[ \begin{array}{cc} A(\lambda ) \;&{}\; - B(\lambda ) \\ C(\lambda ) \;&{}\; D(\lambda ) \end{array}\right] \! \left[ \begin{array}{cc} V \;&{}\; 0 \\ 0 \;&{}\; I _n \end{array}\right] \! = \! \left[ \begin{array}{ccc} X_{\overline{o}}(\lambda ) \;&{}\; Y_{\overline{o}}(\lambda ) \;&{}\; Z_{\overline{o}}(\lambda ) \\ 0 \;&{}\; A_o(\lambda ) \;&{}\; -B_o(\lambda ) \\ 0 \;&{}\; C_o(\lambda ) \;&{}\; D_o(\lambda ) \end{array}\right] , \end{aligned}$$

where $\widetilde{W}$ is of the form $\widetilde{W}:=\left[ \begin{array}{ccc} \widetilde{W}_{11} \;&{}\; 0 \;&{}\; \widetilde{W}_{13} \\ 0 \;&{}\; I_{d_o} \;&{}\; 0 \\ \widetilde{W}_{31} \;&{}\; 0 \;&{}\; \widetilde{W}_{33} \end{array}\right] \in \mathbb {C}^{(d_{\overline{o}} +d_o+m)\times (d_{\overline{o}} +d_o+m)},$ $d_{\overline{o}}$ is the number of (finite and infinite) eigenvalues of $\left[ \begin{array}{cc}A(\lambda ) \\ C(\lambda ) \end{array}\right]$, and $X_{\overline{o}}(\lambda )\in \mathbb {C}[\lambda ]^{d_{\overline{o}}\times d_{\overline{o}}}$ is a regular pencil. Moreover,

• (a) the eigenvalues of $\left[ \begin{array}{cc}A(\lambda ) \\ C(\lambda ) \end{array}\right]$ are the eigenvalues of $X_{\overline{o}}(\lambda ),$

• (b) $\left[ \begin{array}{cc}A_o(\lambda ) \\ C_o(\lambda ) \end{array}\right] \in \mathbb {C}[\lambda ]^{(d_o+m)\times d_o}$ has no (finite or infinite) eigenvalues,

• (c) the quadruple $\{A_o(\lambda ),B_o(\lambda ),C_o(\lambda ),D_o(\lambda )\}$ is a realization of the transfer function $R_o(\lambda ):=\widetilde{W}_{33}R(\lambda )$, with $\widetilde{W}_{33} \in \mathbb {C}^{m\times m}$ invertible, and

• (d) if $\left[ \begin{array}{cc}A(\lambda ) \;&\; -B(\lambda ) \end{array}\right]$ has no finite or infinite eigenvalues then $\left[ \begin{array}{cc}A_o(\lambda ) \;&\; -B_o(\lambda ) \end{array}\right]$ also has no finite or infinite eigenvalues.

In order to extract from the system quadruple $\{A(\lambda ),B(\lambda ),C(\lambda ),D(\lambda )\}$ a subsystem $\{A_{co}(\lambda ),B_{co}(\lambda ),C_{co}(\lambda ),D_{co}(\lambda )\}$ that is both strongly E-controllable and E-observable (and hence also strongly minimal), we only need to apply the above two theorems one after the other. The resulting subsystem would then be a realization of the transfer function $R_{co}=C_{co}(\lambda )A_{co}(\lambda )^{-1}B_{co}(\lambda )+D_{co}(\lambda ) = W_\ell R(\lambda ) W_r \in \mathbb {C}(\lambda )^{m\times n}$. Since the transfer function was changed only by left and right transformations that are constant and invertible, the left and right nullspace will be transformed by these invertible transformations, but their minimal indices will be unchanged.

5 Computational Aspects

In this section we give a more “algorithmic” description of the procedure described in Sect. 4 to reduce a given system quadruple $\{A(\lambda ),B(\lambda ),C(\lambda ),D(\lambda )\}$ to a strongly E-controllable quadruple $\{A_c(\lambda ),B_c(\lambda ),C_c(\lambda ),D_c(\lambda )\}$ of smaller size. We describe the essence of the three steps that were discussed in that section.

Step 1 : Compute the staircase reduction of the submatrix $\left[ \begin{array}{cc} A(\lambda ) \;&\; - B(\lambda ) \end{array}\right]$

$$ U \left[ \begin{array}{cc} A(\lambda ) \;&\; - B(\lambda ) \end{array}\right] W^*= \left[ \begin{array}{c|cc} X(\lambda )\;&{}\; 0 \;&{}\;0 \\ \hline Y(\lambda ) \;&{}\; \hat{A}(\lambda ) \;&{}\; -\hat{B}(\lambda ) \end{array}\right] . $$

Step 2 : Compute the unitary matrices V and $\widetilde{W}$ to compress the first block row of W

$$ \left[ \begin{array}{ccc} W_{11} \;&\; W_{12} \;&\; W_{13} \end{array}\right] \left[ \begin{array}{cc} V \;&{}\; 0 \\ 0 \;&{}\; I_{n} \end{array}\right] \left[ \begin{array}{ccc} \widetilde{W}_{11} \;&{}\; 0 \;&{}\; \widetilde{W}_{13} \\ 0 \;&{}\; I_{d-r} \;&{}\; 0 \\ \widetilde{W}_{31} \;&{}\; 0 \;&{}\; \widetilde{W}_{33} \end{array}\right] =\left[ \begin{array}{ccc} I_{r} \;&\; 0 \;&\; 0 \end{array}\right] , $$

where V does the compression $\begin{bmatrix}W_{11} \;&\; W_{12} \end{bmatrix}V=\begin{bmatrix}\widetilde{W}_{11}^{*} \;&\; 0\end{bmatrix}$ of the first two blocks and $\widetilde{W}$ does the further reduction of the first block row to $\begin{bmatrix}I_r \;&\; 0 \;&\; 0\end{bmatrix}$.

Step 3 : Display the uncontrollable part $X(\lambda )$ using the transformations U, V and $\widetilde{W}$

$$ \left[ \begin{array}{cc} U \;&{}\; 0 \\ 0 \;&{}\; I_{m} \end{array}\right] \left[ \begin{array}{cc} A(\lambda ) \;&{}\; -B(\lambda ) \\ C(\lambda ) \;&{}\; D(\lambda ) \end{array}\right] \left[ \begin{array}{cc} V \;&{}\; 0 \\ 0 \;&{}\; I_{n} \end{array}\right] \widetilde{W}= \left[ \begin{array}{ccc} X_{\overline{c}}(\lambda ) \;&{}\; 0 \;&{}\; 0 \\ \times \;&{}\; A_c(\lambda ) \;&{}\; -B_c(\lambda ) \\ \times \;&{}\; C_c(\lambda ) \;&{}\; D_c(\lambda ) \end{array}\right] , $$

where we have used the notations introduced in Sect. 4, and the resulting $\times$ entries are of no interest because they do not contribute to the transfer function $R_c(\lambda ):=C_c(\lambda )A_c(\lambda )^{-1}B_c(\lambda )+D_c(\lambda )$.

The computational complexity of these three steps is cubic in the dimensions of the matrices that are involved, provided that the staircase algorithm is implemented in an efficient manner [1]. But it is also important to point out that the reduction procedure to extract a strongly minimal linear system matrix from an arbitrary one, can be done with unitary transformations only, and that only one staircase reduction is needed when one knows that the pencil $\left[ \begin{array}{cc} A(\lambda ) \;&\; - B(\lambda ) \end{array}\right]$ has normal rank equal to its number of rows. Indeed, this pencil then does not have any left null space or left minimal indices and only the regular part has to be separated from the right null space structure. This can be obtained by performing one staircase reduction on the rotated pencil $\left[ \begin{array}{cc} \widetilde{A}(\mu ) \;&\; - \widetilde{B}(\mu ) \end{array}\right]$, where the coefficient matrices

$$ \left[ \begin{array}{cc} \widetilde{A}_0 \\ \widetilde{A}_1 \end{array}\right] = \left[ \begin{array}{cc} c I \;&{}\; s I \\ -sI \;&{}\; cI \end{array}\right] \left[ \begin{array}{cc} A_0 \\ A_1 \end{array}\right] , \quad \left[ \begin{array}{cc} \widetilde{B}_0 \\ \widetilde{B}_1 \end{array}\right] = \left[ \begin{array}{cc} c I \;&{}\; s I \\ -sI \;&{}\; cI \end{array}\right] \left[ \begin{array}{cc} B_0 \\ B_1 \end{array}\right] , \quad c^2+s^2=1 $$

correspond to a change of variable $\lambda = (c\mu -s)/(s\mu +c)$. If one now chooses the rotation such that the rotated pencil has no eigenvalues at $\mu =\infty$, then only the finite spectrum has to be separated from the right minimal indices, which can be done with one staircase reduction [7].

6 Numerical Results

We illustrate the results of this paper with a polynomial example and a rational one.

Example 2

We consider the $2\times 2$ polynomial matrix $P(\lambda )=\text {diag}(e_1(\lambda ), e_5(\lambda ))$, where $e_5(\lambda )$ is a polynomial of degree 5 with coefficients $[ 9.6367e-01, \;\; -5.4026e-07, \;\; 2.6333e-01, \;\; -1.1101e-04, \;\; -2.9955e-04, \;\; 4.4650e-02]$, ordered by descending powers of $\lambda$, and $e_1(\lambda )$ is a polynomial of degree 1 with coefficients $[-2.1886e-03, \;\;-1.0000e+00]$, that were randomly chosen. Expanding this fifth order polynomial matrix as

$$ P(\lambda )=P_0+ P_1\lambda + \cdots + P_5 \lambda ^5,$$

a linear system matrix $S_P(\lambda )$ of $P(\lambda )$ is given by the following $10\times 10$ pencil:

$$ S_P(\lambda ) = \left[ \begin{array}{cccc|c} I_2 \;&{}\; -\lambda I_2 &{} &{} &{} P_1 \\ &{} I_2 \;&{}\; -\lambda I_2 &{} &{} P_2 \\ &{} &{} I_2 \;&{}\; -\lambda I_2 &{} P_3 \\ &{} &{} &{} I_2 \;&{}\; P_4 + \lambda P_5 \\ \hline -\lambda I_2 &{} &{} &{} &{} P_0 \end{array}\right] . $$

The six finite Smith zeros of $P(\lambda )$ are clearly those of the scalar polynomials $e_1(\lambda )$ and $e_5(\lambda )$. These are also the finite zeros of $S_P(\lambda ),$ since $S_P(\lambda )$ is minimal. However, $S_P(\lambda )$ is not strongly minimal if $P_5$ is singular and, in fact, it has 4 eigenvalues at infinity (in the sense of [4]). But in the McMillan sense, $P(\lambda )$ has no infinite zeros. The deflation procedure that we derived in this paper precisely gets rid of the extraneous infinite eigenvalues of $S_P(\lambda )$. The numerical tests show that the sensitivity of the true McMillan zeros also can benefit from this.

In this example we compare the roots computed by four different methods:

• 1. computing the roots of the scalar polynomials and appending four $\infty$ roots,

• 2. computing the generalized eigenvalues of $S_P(\lambda )$,

• 3. computing the roots of $QS_P(\lambda )Z$ for random orthogonal matrices Q and Z,

• 4. computing the roots of the minimal pencil obtained by our method.

The first column are the so-called “correct” eigenvalues $\lambda _i$, corresponding to the first method, the next three columns are the corresponding errors $\delta ^{(k)}_i := |\lambda _i-\hat{\lambda }^{(k)}_i|$, $k=2,3,4$, of the above three methods.² The extraneous eigenvalues that are deflated in our approach are put between brackets (Table 1).

Table 1 The correct generalized $\lambda _i$ and the corresponding accuracies $\delta ^{k}_i$ for the three different calculations

We notice that for the largest finite eigenvalue of the order of $10^2$ the QZ algorithm applied to $S_P(\lambda )$ gets 14 digits of relative accuracy but, when deflating the four uncontrollable eigenvalues at $\infty$, our method recovers a relative accuracy of 16 digits.

Example 3

The second example is the rational matrix $R(\lambda )$ in (7) with $c=1$.

$$ R(\lambda ) = \left[ \begin{array}{cc} e_5(\lambda ) \;&{}\; 0 \\ 1/\lambda \;&{}\; e_1(\lambda ) \end{array}\right] =P_0+ P_1\lambda + \cdots + P_5 \lambda ^5 + \left[ \begin{array}{cc} 0 \;&{}\; 0 \\ 1/\lambda \;&{}\; 0 \end{array}\right] ,$$

by using the notation of the example above. In this case, $e_5(\lambda )$ has the row vector $[ 4.7865e-02, \;\; 1.4279e-04, \;\; 2.4361e-03, \;\; -1.5336e-02, \;\; -9.9155e-01, \;\; 1.1948e-01 ]$ as coefficients, and $e_1(\lambda )$ has the row vector $[6.5250e-03, \;\; 9.9997e-01 ]$. We consider the $12 \times 12$ linear system matrix

$$ S_R(\lambda ) = \left[ \begin{array}{ccccc|c} \lambda I_2 -A &{} &{} &{} &{} &{} -B \\ &{} I_2 \;&{}\; -\lambda I_2 &{} &{} &{} P_1 \\ &{} &{} I_2 \;&{}\; -\lambda I_2 &{} &{} P_2 \\ &{} &{} &{} I_2 \;&{}\; -\lambda I_2 &{} P_3 \\ &{} &{} &{} &{} I_2 \;&{}\; P_4 + \lambda P_5 \\ \hline C &{} -\lambda I_2 &{} &{} &{} &{} P_0 \end{array}\right] , $$

where

$$ A= \left[ \begin{array}{cc} 0 \;&{}\; 0 \\ 1 \;&{}\; 0 \end{array}\right] , \quad B= \left[ \begin{array}{cc} 0 \;&{}\; 0 \\ 1 \;&{}\; 0 \end{array}\right] \quad C= \left[ \begin{array}{cc} 0 \;&{}\; 0 \\ 0 \;&{}\; 1 \end{array}\right] $$

is a non-minimal realization of the strictly proper rational function $1/\lambda$. In fact, the matrix A in the realization triple (A, B, C) has two eigenvalues at $\lambda =0,$ of which one is uncontrollable since $1/\lambda$ only has a pole at 0 of order 1. This is an artificial example since we could have realized the strictly proper part by using a minimal triple (A, B, C) by removing the uncontrollable eigenvalue, but this is precisely what our reduction procedure does simultaneously for finite and infinite uncontrollable eigenvalues. The quantities given in the following table are defined as in the previous example, except that we added two roots at 0 corresponding to the “exact” eigenvalues (Table 2).

Table 2 The correct generalized $\lambda _i$ and the corresponding accuracies $\delta ^{k}_i$ for the three different calculations

In this example the QZ algorithm applied to $S_R(\lambda )$ recovers well all generalized eigenvalues. When applying the QZ algorithm to an orthogonally equivalent pencil $QS_R(\lambda )Z$, the Jordan block at 0 gets perturbed to two roots of the order of the square root of the machine precision, which can be expected. But when deflating the uncontrollable eigenvalue at 0, this Jordan block is reduced to a single eigenvalue and part of the accuracy gets restored.

These two examples show that deflating uncontrollable eigenvalues may improve the sensitivity of the remaining eigenvalues which may improve the accuracy of their computation.

7 Conclusion

In this paper we looked at quadruple realizations $\{A(\lambda ),B(\lambda ),C(\lambda ),D(\lambda )\}$ for a given rational transfer function $R(\lambda )=C(\lambda )A(\lambda )^{-1}B(\lambda )+D(\lambda )$, where the matrices $A(\lambda ), B(\lambda ), C(\lambda )$ and $D(\lambda )$ are pencils, and where $A(\lambda )$ is assumed to be regular. We showed that under certain minimality assumptions on this quadruple, the poles, zeros and left and right null space structure of the rational matrix $R(\lambda )$ can be recovered from the generalized eigenstructure of two block pencils constructed from the quadruple. We also showed how to obtain such a minimal quadruple from a non-minimal one, by applying a reduction procedure that is based on the staircase algorithm. These results extend those previously obtained for generalized state space systems and polynomial matrices.