Minimum Norm Regularization of Descriptor Systems by Output Feedback

Delin Chu ^{∗} and Volker Mehrmann ^{†}

Fakultät für Mathematik TU Chemnitz-Zwickau D-09107 Chemnitz, FRG email: chu.delin@mathematik.tu-chemnitz.de email: mehrmann@mathematik.tu-chemnitz.de

ABSTRACT

We study the regularization problem for linear, constant coefficient descriptor systems Eẋ = Ax + Bu, y_{1} = Cx, y_{2} = Γẋ by proportional and derivative mixed output feedback. Necessary and sufficient conditions are given, which guarantee that there exist output feedbacks such that the closed-loop system is regular, has index at most one and E +BGΓ has a desired rank, i.e. there is a desired number of differential and algebraic equations. To resolve the freedom in the choice of the feedback matrices we then discuss how to obtain the desired regularizing feedback of minimum norm and show that this approach leads to useful results in the sense of robustness only if the rank of E is decreased. Numerical procedures are derived to construct the desired feedback gains. These numerical procedures are based on orthogonal matrix transformations which can be implemented in a numerically stable way.

Keywords: Descriptor system, output feedback, mixed feedback, regularization, condensed form, index, orthogonal transformations.

AMS subject classification: 93B05, 93B40, 93B52, 65F35

1. Introduction

We consider linear, time-invariant descriptor systems of the form

Eẋ(t) = Ax(t) + Bu(t), x(t_{0}) = x^{0},
y_{1}(t) = Cx(t),  (1)
y_{2}(t) = Γẋ,

where E, A ∈ R^{n×n}, B ∈ R^{n×m}, C ∈ R^{p×n}, Γ ∈ R^{q×n}. In this paper we always assume without loss of generality that B is full column rank, and that C and Γ have full row rank. If this is not the case then the system can be easily transformed so that this is the case.

Descriptor systems of the form (1) have been studied extensively in the last 20 years, since they allow automatic model generation, see [3, 7, 14, 15] and the references therein.

Existence and uniqueness of (classical) solutions to (1) are guaranteed if (E, A) is regular, i.e., if det(αE −βA) ≠ 0 for some (α, β) ∈ C^{2}. The index of system (1) denoted by ind(E, A), is the dimension of the largest block associated with an infinite eigenvalue in the Kronecker canonical form of (E, A) [9].

Systems that are regular and of index at most one can be separated into purely dynamical and algebraic parts (fast and slow modes), and in theory the algebraic part can be eliminated to give a reduced-order standard system. The reduction process, however, may be ill-conditioned for numerical computation and lead to large errors in the reduced order system. If the system is not regular or if ind(E, A) > 1, then impulses can arise in the response of the system if the control is not sufficiently smooth [10, 18]. Since the linear constant coefficient system is usually only a model that approximates a nonlinear model, disturbances in the real application will in general lead to impulsive solutions if the system is of index higher than one. Therefore, an appropriate feedback control should be chosen to ensure that the closed-loop system is regular and of index at most one and if there are several such feedbacks then we need to specify how the non-uniqueness can be resolved.

We therefore study the following problem: Problem 1. The output

feedback regularization problem OFR. For a system of the form (1) and an integer r ≤ n, give necessary and sufficient conditions to ensure the existence of feedback matrices F ∈ R^{m×p}, G ∈ R^{m×q}, such that the closedloop system pencil (E + BGΓ, A + BF C) is regular, has index at most one and rank(E + BGΓ) = r. This problem has already been discussed in

a series of papers, see [2, 3, 6, 15, 16, 17] and the references therein. All the previous characterizations, however, are not complete, since the set of possible ranks for E + BGΓ has not been completely characterized. We will give the complete characterization.

For certain choices of ranks, reliable numerical methods for constructing the regularizing feedbacks are presented in [1, 2, 3, 6]. There is, however, usually still freedom in the choice of the feedbacks which can be resolved in many different ways. A natural choice would be to use minimum norm feedbacks, which would be a least squares approach. This approach has not been investigated previously. For this reason we also study the following problem.

Problem 2. The minimum norm output feedback regularization problem MNOFR. For a system of the form (1) and an integer r ≤ n, characterize inf∥ [ F G ] ∥ for all matrices F, G such that (E + BGΓ, A+BF C) is regular, has index at most one and rank(E +BGΓ) = r. (Here ∥ ∥ can be any consistent matrix norm. )

We will show that it is in general not a good idea to use the minumum norm feedback, since it does not lead to a robust regularization, in particular, when the chosen integer r is larger or equal to rank(E).

The main ingredients for the analysis of the system properties as well as for the construction of the appropriate feedbacks are condensed forms under orthogonal equivalence transformations which can be implemented via numerically stable methods. We will describe such forms in Section 2. In Section 3 we then discuss the complete solution of Problem OFR and we discuss the minimum norm problem MNOFR in Section 4.

We use the following notation:

We denote a full column rank matrix with its columns spanning the right nullspace of the matrix M by S_{∞}(M) and with its columns spanning the left nullspace of M by T_{∞}(M), respectively. Furthermore we use the following abbreviations:

r_{e} := rank(E), r_{a} := rank(A), r_{b} := rank(B), r_{γ} := rank(Γ),
r_{eb} := rank [ E B ] , r_{eγ} := rank [ \begin{matrix}E \\ Γ \end{matrix} ] , r_{ebγ} := rank [ \begin{matrix}E & B \\ Γ & 0 \end{matrix} ] .

(2)

In all the following discussions the rank of the closed loop matrix E + BGΓ will be allowed to vary in order to have more freedom in the choice of feedbacks. The set of all possible ranks for this matrix is easily characterized, e.g. [6], as

Π_{ebγ} := {rank(E + BGΓ)|G ∈ R^{m×q}}  (3)
= {r|r is an integer and r_{eb} + r_{eγ} − r_{ebγ} ≤ r ≤ min(r_{eb}, r_{eγ})}.

2. Condensed Forms

In this section for systems of the form (1) three useful condensed forms are discussed. The forms we describe here are slight modifications of the condensed forms in [2, 3, 6, 15].

Theorem 3. Let E ∈ R^{n×n}, B ∈ R^{n×m}, Γ ∈ R^{q×n}. Then there exist orthogonal matrices U, V, P and W such that

UEV =  [ \begin{matrix}& t_{1} & t_{2} & t_{3} & s̃_{4} & s̃_{5} \\ t_{1} & E_{11} & 0 & 0 & 0 & 0 \\ t_{2} & E_{21} & E_{22} & 0 & 0 & 0 \\ t_{3} & E_{31} & E_{32} & E_{33} & E_{34} & 0 \\ t_{4} & E_{41} & E_{42} & 0 & E_{44} & 0 \\ t_{5} & 0 & 0 & 0 & 0 & 0 \end{matrix} ],

UBP =  [ \begin{matrix}& t_{3} & t_{4} \\ t_{1} & 0 & 0 \\ t_{2} & 0 & 0 \\ t_{3} & B_{31} & B_{32} \\ t_{4} & 0 & B_{42} \\ t_{5} & 0 & 0 \end{matrix} ],  (4)

W ΓV =  [ \begin{matrix}& t_{1} & t_{2} & t_{3} & s̃_{4} & s̃_{5} \\ s̃_{4} & Γ_{11} & Γ_{12} & 0 & Γ_{14} & 0 \\ t_{1} & Γ_{21} & 0 & 0 & 0 & 0 \end{matrix} ],

with nonsingular blocks E_{11}, Γ_{21}, E_{22}, E_{33}, B_{31}, B_{42}, Γ_{14}.

Proof. See [3, 6].

From this condensed form we immediately obtain a relationship between the ranks introduced in (2) and the block sizes t_{i}, s̃_{i}.

Corollary 4. Let E ∈ R^{n×n}, B ∈ R^{n×m}, Γ ∈ R^{q×n} be in the condensed form (4). Then

\begin{aligned}t_{1} & = & r_{γ} + r_{eb} − r_{ebγ}, \\ t_{2} & = & r_{ebγ} − r_{b} − r_{γ}, \\ t_{3} & = & r_{b} + r_{eγ} − r_{ebγ}, \\ t_{4} & = & r_{ebγ} − r_{eγ}, \\ t_{5} & = & n − r_{eb} \\ s̃_{4} & = & r_{ebγ} − r_{eb}, \\ s̃_{5} & = & n − r_{eγ} \end{aligned}  (5)

and

\begin{aligned}r_{ebγ} & = & t_{1} + t_{2} + t_{3} + t_{4} + s̃_{4}, \\ r_{eγ} & = & t_{1} + t_{2} + t_{3} + s̃_{4}, \\ r_{eb} & = & t_{1} + t_{2} + t_{3} + t_{4}, \\ r_{b} & = & m = t_{3} + t_{4}, \\ r_{γ} & = & q = t_{1} + s̃_{4}. \end{aligned}  (6)

Using partly nonorthogonal equivalence transformations, the condensed from (4) can be significantly simplified.

Corollary 5. Let E ∈ R^{n×n}, B ∈ R^{n×m}, Γ ∈ R^{q×n}. Then there exist nonsingular matrices X, Y and orthogonal matrices P, W such that

\begin{aligned}XEY & = & [ \begin{matrix}I_{t_{1}} & 0 & 0 & 0 & 0 \\ 0 & I_{t_{2}} & 0 & 0 & 0 \\ 0 & 0 & I_{t_{3}} & 0 & 0 \\ 0 & 0 & 0 & Ẽ_{44} & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} ] , \\ W ΓY & = & [ \begin{matrix}0 & 0 & 0 & Is̃_{4} & 0 \\ I_{t_{1}} & 0 & 0 & 0 & 0 \end{matrix} ] , XBP = [ \begin{matrix}0 & 0 \\ 0 & 0 \\ I_{t_{3}} & 0 \\ 0 & I_{t_{4}} \\ 0 & 0 \end{matrix} ] . \end{aligned}  (7)

Moreover, the transformations can be chosen such that Ẽ_{44} ∈ R^{t_{4}×s̃_{4}} and

Ẽ_{44} = \{ \begin{matrix}[ \begin{matrix}σ_{1} & … & 0 & 0 \\ 0 & ... & 0 & 0 \\ 0 & … & σ_{t_{4}} & 0 \end{matrix} ]  if s̃_{4} ≥ t_{4} \\ [ \begin{matrix}σ_{1} & … & 0 \\ 0 & ... & 0 \\ 0 & … & σs̃_{4} \\ 0 & 0 & 0 \end{matrix} ]  if t_{4} ≥ s̃_{4} \end{matrix}  (8)

with σ_{1} ≥ … ≥ σ_{t} ≥ 0, where t = min(t_{4}, s̃_{4}).

Proof. The proof is a direct consequence of Theorem 3. After performing a restricted singular value decomposition, see [19] of B_{42}^{−1}E_{44}Γ_{14}^{−1} one uses the nonsingular blocks to eliminate all other blocks.

Note that (7) is actually itself a restricted singular value decomposition of the triple (E, B, Γ).

If E, B, Γ are in the condensed form (7), then we immediately have a characterization of the following spaces, which are needed to describe the complete solution of problem OFR.

\begin{aligned}S_{eγ} & := & S_{∞}([ \begin{matrix}E \\ Γ \end{matrix} ]), T_{eb} := T_{∞}([ E B ]), \\ S̃_{eb} & := & S_{∞}(T_{∞}^{T}(B)E), T̃_{eγ} := T_{∞}(ES_{∞}(Γ)), \\ T̃_{eγ}^{0} & := & T_{∞}([ \begin{matrix}E \\ 0_{p×n} \end{matrix} ] S_{∞}(Γ)). \end{aligned}  (9)

Although these spaces look complicated they can be easily characterized in term of the condensed form (7), see Appendix B. Now we further split the fourth block column of E, Γ and the first block row of Γ.

Lemma 6. Let E, A, B, C, Γ be as in (1). Then there exist nonsingular matrices X, Y and orthogonal matrices P, W such that

XEY =  [ \begin{matrix}& t_{1} & t_{2} & t_{3} & s_{4} & s_{5} & s_{6} & s_{7} \\ t_{1} & I_{t_{1}} & 0 & 0 & 0 & 0 & 0 & 0 \\ t_{2} & 0 & I_{t_{2}} & 0 & 0 & 0 & 0 & 0 \\ t_{3} & 0 & 0 & I_{t_{3}} & E_{34} & E_{35} & E_{36} & 0 \\ t_{4} & 0 & 0 & 0 & E_{44} & E_{45} & E_{46} & 0 \\ t_{5} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ],

W ΓY =  [ \begin{matrix}& t_{1} & t_{2} & t_{3} & s_{4} & s_{5} & s_{6} & s_{7} \\ s_{4} & 0 & 0 & 0 & I_{s_{4}} & 0 & 0 & 0 \\ s_{5} & 0 & 0 & 0 & 0 & I_{s_{5}} & 0 & 0 \\ s_{6} & 0 & 0 & 0 & 0 & 0 & I_{s_{6}} & 0 \\ t_{1} & I_{t_{1}} & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ],

XBP =  [ \begin{matrix}& t_{3} & t_{4} \\ t_{1} & 0 & 0 \\ t_{2} & 0 & 0 \\ t_{3} & I_{t_{3}} & 0 \\ t_{4} & 0 & I_{t_{4}} \\ t_{5} & 0 & 0 \end{matrix} ],  (10)

XAY =  [ \begin{matrix}& t_{1} & t_{2} & t_{3} & s_{4} & s_{5} & s_{6} & s_{7} \\ t_{1} & A_{11} & A_{12} & A_{13} & A_{14} & A_{15} & A_{16} & A_{17} \\ t_{2} & A_{21} & A_{22} & A_{23} & A_{24} & A_{25} & A_{26} & A_{27} \\ t_{3} & A_{31} & A_{32} & A_{33} & A_{34} & A_{35} & A_{36} & A_{37} \\ t_{4} & A_{41} & A_{42} & A_{43} & A_{44} & A_{45} & A_{46} & A_{47} \\ t_{5} & A_{51} & A_{52} & A_{53} & A_{54} & A_{55} & A_{56} & A_{57} \end{matrix} ],

CY = \left[{t_{1} t_{2} t_{3} s_{4} s_{5} s_{6} s_{7} \atop p C_{1} C_{2} C_{3} C_{4} C_{5} C_{6} C_{7}}\right],

where

s_{6} := min(r_{ebγ} − r_{eb}, rank(T_{eb}^{T}AS̃_{eb}) − rank(T_{eb}^{T}AS_{eγ})),
s_{5} := min(r_{ebγ} − r_{eb}, rank((T̃_{eγ}^{0})^{T} [ \begin{matrix}A \\ C \end{matrix} ] S̃_{eb})

− rank((T̃_{eγ}^{0})^{T} [ \begin{matrix}A \\ C \end{matrix} ] S_{eγ})) − s_{6},

s_{4} := r_{ebγ} − r_{eb} − s_{5} − s_{6},

(11) and furthermore

rank [ A_{56} A_{57} ] = s_{6} + rank(A_{57}) = s_{6} + rank(T_{eb}^{T}AS_{eγ}),

rank [ \begin{matrix}A_{15} & A_{16} & A_{17} \\ A_{45} & A_{46} & A_{47} \\ A_{55} & A_{56} & A_{57} \\ C_{5} & C_{6} & C_{7} \end{matrix} ] = s_{5} + s_{6} + rank [ \begin{matrix}A_{17} \\ A_{47} \\ A_{57} \\ C_{7} \end{matrix} ]

= s_{5} + s_{6} + rank((T̃_{eγ}^{0})^{T} [ \begin{matrix}A \\ C \end{matrix} ] S_{eγ}).

(12)

Proof. By Corollary 5 there exist matrices X, Y, P, W such that XEY, XBP, W ΓY are in the condensed form (7). Partition

XAY = [ \begin{matrix}Ã_{11} & Ã_{12} & Ã_{13} & Ã_{14} & Ã_{15} \\ Ã_{21} & Ã_{22} & Ã_{23} & Ã_{24} & Ã_{25} \\ Ã_{31} & Ã_{32} & Ã_{33} & Ã_{34} & Ã_{35} \\ Ã_{41} & Ã_{42} & Ã_{43} & Ã_{44} & Ã_{45} \\ Ã_{51} & Ã_{52} & Ã_{53} & Ã_{54} & Ã_{55} \end{matrix} ] , CY = [ C̃_{1} C̃_{2} C̃_{3} C̃_{4} C̃_{5} ]

(13)

accordingly. Consider the submatrix [ Ã_{53} Ã_{54} Ã_{55} ] of XAY. It is easy to see that there exists a matrix K_{0} of appropriate dimensions such that

rank([ Ã_{54} + Ã_{53}K_{0} Ã_{55} ]) = max_{K}(rank [ Ã_{54} + Ã_{53}K Ã_{55} ])
= s_{6} + rank(Ã_{55})
= s_{6} + rank(T_{eb}^{T}AS_{eγ})

and

rank [ \begin{matrix}Ã_{14} + Ã_{13}K_{0} & Ã_{15} \\ Ã_{44} + Ã_{43}K_{0} & Ã_{45} \\ Ã_{54} + Ã_{53}K_{0} & Ã_{55} \\ C̃_{4} + C̃_{3}K_{0} & C̃_{5} \end{matrix} ] = max_{K}(rank [ \begin{matrix}Ã_{14} + Ã_{13}K & Ã_{15} \\ Ã_{44} + Ã_{43}K & Ã_{45} \\ Ã_{54} + Ã_{53}K & Ã_{55} \\ C̃_{4} + C̃_{3}K & C̃_{5} \end{matrix} ])

= s_{5} + s_{6} + [ Ã_{15} ; Ã_{45} ; Ã_{55} ; C̃_{5} ] = s_{5} + s_{6} + rank((T̃_{eγ}^{0})^{T} [ \begin{matrix}A \\ C \end{matrix} ] S_{eγ}).

Finally there exists an orthogonal matrix V such that

[ \begin{matrix}A_{14} & A_{15} & A_{16} \\ A_{24} & A_{25} & A_{26} \\ A_{34} & A_{35} & A_{36} \\ A_{44} & A_{45} & A_{46} \\ A_{54} & A_{55} & A_{56} \\ C_{4} & C_{5} & C_{6} \end{matrix} ] := [ \begin{matrix}Ã_{14} + Ã_{13}K_{0} \\ Ã_{24} + Ã_{23}K_{0} \\ Ã_{34} + Ã_{33}K_{0} \\ Ã_{44} + Ã_{43}K_{0} \\ Ã_{54} + Ã_{53}K_{0} \\ C̃_{4} + C̃_{3}K_{0} \end{matrix} ] V

is partitioned so that the following conditions are satisfied.

rank [ A_{56} Ã_{55} ] = s_{6} + rank(Ã_{55}),

rank [ \begin{matrix}A_{15} & A_{16} & Ã_{15} \\ A_{45} & A_{46} & Ã_{45} \\ A_{55} & A_{56} & Ã_{55} \\ C_{5} & C_{6} & C̃_{5} \end{matrix} ] = s_{5} + s_{6} + rank [ Ã_{15} ; Ã_{45} ; Ã_{55} ; C̃_{5} ] .

Leaving of the ˜ in the first three block columns and setting

[ \begin{matrix}A_{17} \\ A_{27} \\ A_{37} \\ A_{47} \\ A_{57} \\ C_{7} \end{matrix} ] := [ Ã_{15} ; Ã_{25} ; Ã_{35} ; Ã_{45} ; Ã_{55} ; C̃_{5} ] , W := [ \begin{matrix}V^{T} \\ & I_{t_{1}} \end{matrix} ] W,

Y := Y [ \begin{matrix}I_{t_{1}+t_{2}} \\ & I_{t_{3}} & K_{0} \\ & & Is̃_{4} \\ & & & Is̃_{5} \end{matrix} ] [ \begin{matrix}I_{t_{1}+t_{2}+t_{3}} \\ & V \\ & & Is̃_{5} \end{matrix} ] ,

we have obtained the desired condensed from.

Corollary 7. Given a system (E, A, B, C, Γ) in condensed form (10). Then for any K_{1}, K_{2}, K_{3} of appropriate dimensions, the following two inequalities hold:

rank([ A_{54} A_{55} A_{56} A_{57} ] + A_{53} [ K_{1} K_{2} K_{3} 0 ])
≤ rank [ A_{56} A_{57} ] ,  (14)

rank([ \begin{matrix}A_{14} & A_{15} & A_{16} & A_{17} \\ A_{44} & A_{45} & A_{46} & A_{47} \\ A_{54} & A_{55} & A_{56} & A_{57} \\ C_{4} & C_{5} & C_{6} & C_{7} \end{matrix} ] + [ \begin{matrix}A_{13} \\ A_{43} \\ A_{53} \\ C_{3} \end{matrix} ] [ K_{1} K_{2} K_{3} 0 ])

≤ rank [ \begin{matrix}A_{15} & A_{16} & A_{17} \\ A_{45} & A_{46} & A_{47} \\ A_{55} & A_{56} & A_{57} \\ C_{5} & C_{6} & C_{7} \end{matrix} ] .  (15)

Furthermore we have the following equivalences

rank [ A_{56} A_{57} ] = n − r_{eb} iff
rank(T_{eb}^{T}AS̃_{eb}) = n − r_{eb} and  (16)
n − r_{ebγ} ≤ rank(T_{eb}^{T}AS_{eγ}).

rank [ \begin{matrix}A_{17} \\ A_{47} \\ A_{57} \\ C_{7} \end{matrix} ] = n − r_{eγ} iff rank((T̃_{eγ}^{0})^{T} [ \begin{matrix}A \\ C \end{matrix} ] S_{eγ}) = n − r_{eγ} (17)

Proof. The proof is an immediate consequence of Lemma 6.

In this section we have introduced three condensed forms. Condensed form (4) uses only orthogonal tranformations and thus can be implemented as a numerically stable procedure. We will use this form to design a numerical algorithm to compute regularizing feedbacks for the solution of Problem OFR.

Condensed forms (7) and (10) follow directly from (4), but since they are obtained via non-orthogonal transformations usually there do not exist backward stable procedures to compute these forms. However, condensed forms (7), (10) are important, since they provide the basis for the solvability theory for problem OFR. The form (10) is not unique, but (7) is essentially unique (except for permutations). This form will be used to establish algebraic characterizations for Problem MNOFR.

3. Output Feedback Regularization

In this section we give necessary and sufficient conditions for problem OFR.

Theorem 8. Given a system of the form (1) with E, A ∈ R^{n×n}, B ∈ R^{n×m}, C ∈ R^{p×n}, Γ ∈ R^{q×n}. Let r be any integer satisfying

r_{eb} + r_{eγ} − r_{ebγ} + s_{4} ≤ r ≤ r_{eb} + r_{eγ} − r_{ebγ} + s_{4} + s_{5}  (18)

with s_{4}, s_{5} given by (11). There exist feedback matrices F ∈ R^{m×p} and G ∈ R^{m×q}, such that (E + BGΓ, A + BF C) is regular, has index at most one and rank(E + BGΓ) = r if and only if the following three conditions hold

rank(T_{eb}^{T}AS̃_{eb}) = n − r_{eb},  (19)
rank((T̃_{eγ}^{0})^{T} [ \begin{matrix}A \\ C \end{matrix} ] S_{eγ}) = n − r_{eγ},  (20)
rank(T_{eb}^{T}AS_{eγ}) ≥ n − r_{ebγ}.  (21)

Proof. Without loss of generality, we may assume that the system matrices (E, A, B, C, Γ) are in the condensed form (10). We partition any F ∈ R^{m×p}, and G ∈ R^{m×q} as

F = [ \begin{matrix}F_{11} \\ F_{21} \end{matrix} ] , G = [ \begin{matrix}G_{11} & G_{12} & G_{13} & G_{14} \\ G_{21} & G_{22} & G_{23} & G_{24} \end{matrix} ]

compatible with the partitioning in B, C, and Γ.

Necessity. Let F, G be such that (E + BGΓ, A + BF C) is regular, has index at most one and rank(E + BGΓ) = r. Then a simple calculation yields that

rank [ E_{44} + G_{21} E_{45} + G_{22} E_{46} + G_{23} ] = r − (t_{1} + t_{2} + t_{3}).

Hence, there exists an orthogonal matrix Q = [ Q_{1} Q_{2} ], such that

[ E_{44} + G_{21} E_{45} + G_{22} E_{46} + G_{23} ] [ Q_{1} Q_{2} ] = [ Ê_{44} 0 ] ,

where Ê_{44} has full column rank r − (t_{1} + t_{2} + t_{3}) and Q is partititioned compatibly. Let K_{1} := E_{34} + G_{11}, K_{2} := E_{35} + G_{12} and K_{3} := E_{36} + G_{13} and set

[ \begin{matrix}A_{14} − A_{13}K_{1} & A_{15} − A_{13}K_{2} & A_{16} − A_{13}K_{3} \\ A_{24} − A_{23}K_{1} & A_{25} − A_{23}K_{2} & A_{26} − A_{23}K_{3} \\ A_{34} − A_{33}K_{1} & A_{35} − A_{33}K_{2} & A_{36} − A_{33}K_{3} \\ A_{44} − A_{43}K_{1} & A_{45} − A_{43}K_{2} & A_{46} − A_{43}K_{3} \\ A_{54} − A_{53}K_{1} & A_{55} − A_{53}K_{2} & A_{56} − A_{53}K_{3} \\ C_{4} − C_{3}K_{1} & C_{5} − C_{3}K_{2} & C_{6} − C_{3}K_{3} \end{matrix} ] Q_{2} = [ \begin{matrix}Φ_{1} \\ Φ_{2} \\ Φ_{3} \\ Φ_{4} \\ Φ_{5} \\ Ψ \end{matrix} ] .

Then, we have that

n = rank [ E + BGΓ (A + BF C)S_{∞}(E + BGΓ) ]

= rank [ \begin{matrix}t_{1} & t_{2} & t_{3} & r − t_{1} − t_{2} − t_{3} & n − r − s_{7} & s_{7} \\ I_{t_{1}} & 0 & 0 & 0 & Φ_{1} & A_{17} \\ 0 & I_{t_{2}} & 0 & 0 & Φ_{2} & A_{27} \\ G_{14} & 0 & I_{t_{3}} & 0 & Φ_{3} + F_{11}Ψ & A_{37} + F_{11}C_{7} \\ G_{24} & 0 & 0 & Ê_{44} & Φ_{4} + F_{21}Ψ & A_{47} + F_{21}C_{7} \\ 0 & 0 & 0 & 0 & Φ_{5} & A_{57} \end{matrix} ].

This implies that the submatrix

[ \begin{matrix}I_{t_{1}} & 0 & Φ_{1} & A_{17} \\ G_{24} & Ê_{44} & Φ_{4} + F_{21}Ψ & A_{47} + F_{21}C_{7} \\ 0 & 0 & Φ_{5} & A_{57} \end{matrix} ]

is nonsingular. Therefore, Lemma 6 implies that

rank [ Φ_{5} A_{57} ] = n − r_{eb}  (22)

and

rank [ \begin{matrix}Φ_{1} & A_{17} \\ Φ_{4} & A_{47} \\ Φ_{5} & A_{57} \\ Ψ & C_{7} \end{matrix} ] = n − r.  (23)

Then (14) implies that

n − r_{eb} = rank [ Φ_{5} A_{57} ] ≤ rank [ A_{56} A_{57} ] ≤ n − r_{eb}.  (24)

This together with (16) yields conditions (19) and (21). Condition (23) implies that

rank [ \begin{matrix}A_{17} \\ A_{47} \\ A_{57} \\ C_{7} \end{matrix} ] = n − r_{eγ}.  (25)

This together with (17) yields (20).

Moreover, conditions (15) and (23) together yield

n − r = rank [ \begin{matrix}Φ_{1} & A_{17} \\ Φ_{4} & A_{47} \\ Φ_{5} & A_{57} \\ Ψ & C_{7} \end{matrix} ] ≤ rank [ \begin{matrix}A_{15} & A_{16} & A_{17} \\ A_{45} & A_{46} & A_{47} \\ A_{55} & A_{56} & A_{57} \\ C_{5} & C_{6} & C_{7} \end{matrix} ] . (26)

Then (24) implies that the number of columns of Φ_{5} is at least n − r_{eb} − rank(A_{57}) = s_{6}. With r_{eγ} = t_{1} + t_{2} + t_{3} + s_{4} + s_{5} + s_{6} therefore, (25) and (26) and Lemma 6 yield that

t_{1} + t_{2} + t_{3} + s_{4} ≤ r ≤ t_{1} + t_{2} + t_{3} + s_{4} + s_{5}

which is (18).

Sufficiency. Let s̃:= r − t_{1} − t_{2} − t_{3} − s_{4} and partition the fifth block column of A and C as

[ \begin{matrix}A_{15} \\ A_{25} \\ A_{35} \\ A_{45} \\ A_{55} \\ C_{5} \end{matrix} ] = [ \begin{matrix}& s̃ & s_{5} − s̃ \\ t_{1} & Φ_{11} & Φ_{12} \\ t_{2} & Φ_{21} & Φ_{22} \\ t_{3} & Φ_{31} & Φ_{32} \\ t_{4} & Φ_{41} & Φ_{42} \\ t_{5} & Φ_{51} & Φ_{52} \\ p & Ψ_{1} & Ψ_{2} \end{matrix} ]

Then, (16) implies that [ Φ_{52} A_{56} A_{57} ] has full row rank n − r_{eb}, and (17) and (12) imply that

[ \begin{matrix}Φ_{12} & A_{16} & A_{17} \\ Φ_{42} & A_{46} & A_{47} \\ Φ_{52} & A_{56} & A_{57} \\ Ψ_{2} & C_{6} & C_{7} \end{matrix} ]

has full column rank n − r. But then there exist Δ_{1}, Δ̃_{2}, Δ_{4} and F_{21} such that the matrix

[ \begin{matrix}t_{1} & s_{4} & s̃ & s_{5} − s̃ & s_{6} & s_{7} \\ I_{t_{1}} & 0 & 0 & Φ_{12} & A_{16} & A_{17} \\ Δ_{4} & Δ_{1} & Δ̃_{2} & Φ_{42} + F_{21}Ψ_{2} & A_{46} + F_{21}C_{6} & A_{47} + F_{21}C_{7} \\ 0 & 0 & 0 & Φ_{52} & A_{56} & A_{57} \end{matrix} ]

is nonsingular. Set

G := [ \begin{matrix}s_{4} & s_{5} & s_{6} & t_{1} \\ −E_{34} & −E_{35} & −E_{36} & 0 \\ −E_{44} & −E_{45} & −E_{46} & 0 \end{matrix} ] + [ \begin{matrix}s_{4} & s̃ & s_{5} − s̃ & s_{6} & t_{1} \\ 0 & 0 & 0 & 0 & 0 \\ Δ_{1} & Δ̃_{2} & 0 & 0 & Δ_{4} \end{matrix} ],
F := [ \begin{matrix}0 \\ F_{21} \end{matrix} ] .

Then it follows that (E + BGΓ, A + BF C) is regular, has index at most one, and rank(E + BGΓ) = r.

As direct corollaries of Theorem 8 we obtain the characterizations in the special cases C = Γ, C = 0, respectively and even the state feedback case Γ = 0, C = I.

Corollary 9. [6] Given a system of the form (1) with Γ = C and let r be an integer satisfying

r_{eb} + r_{eγ} − r_{ebγ} ≤ r ≤ r_{eγ} − s_{6}  (27)

with s_{6} as in (11). There exist feedback matrices F, G such that (E + BGΓ, A+BF Γ) is regular, has index at most one, and rank(E +BGΓ) = r if and only if the three conditions (19), (21) and

rank(T̃_{eγ}^{T}AS_{eγ}) = n − r_{eγ}  (28)

hold.

Proof. Since Γ = C, by the condensed form (10) it is easy to verify that

rank(T̃_{eγ}^{T}AS_{eγ}) = rank((T̃_{eγ}^{0})^{T} [ \begin{matrix}A \\ Γ \end{matrix} ] S_{eγ}), s_{4} = 0, s_{5} = r_{ebγ} − r_{eb} − s_{6}.

Hence, Corollary 9 follows directly from Theorem 8.

Corollary 10. Given a system of the form (1) with C = 0 and let r be an integer satisfying

r_{eγ} − min(r_{ebγ} − r_{eb}, rank(T̃_{eγ}^{T}AS̃_{eb}) − rank(T̃_{eγ}^{T}AS_{eγ}))
≤ r ≤ r_{eγ} − s_{6}  (29)

with s_{6} as in (11). There exists a feedback G such that (E + BGΓ, A) is regular, has index at most one and rank(E + BGΓ) = r if and only if the three conditions (19), (21) and (28) hold.

Proof. Since C = 0, we have from the condensed form (10) that

rank(T̃_{eγ}^{T}AS_{eγ}) = rank((T̃_{eγ}^{0})^{T} [ \begin{matrix}A \\ 0 \end{matrix} ] S_{eγ}),

s_{4} = r_{ebγ} − r_{eb} − min(r_{ebγ} − r_{eb}, rank(T̃_{eγ}^{T}AS̃_{eb}) − rank(T̃_{eγ}^{T}AS_{eγ}))

and

r_{eb} + r_{eγ} − r_{ebγ} + s_{4} + s_{5} = r_{eγ} − s_{6}

Thus, Corollary 10 follows directly from Theorem 8.

Corollary 11. [2] Given a system of the form (1) with Γ = 0, C = I. There exists a feedback F such that (E, A + BF C) is regular and has index at most one if and only if (21) holds.

Proof. Since Γ = 0, C = I, we have from the condensed form (4) that t_{1} = t_{4} = s̃_{4} = 0. Then (21) holds if and only if rank [ E AS_{∞}(E) B ] = n, which is equivalent to the existence of the state feedback F such that (E, A + BF C) is regular and has index at most one, see [2].

A numerical procedure to compute feedbacks with the properties described in Theorem 8, Corollaries 9 and 10 is described in Algorithm 2 in Appendix A.

Note that the possible ranks rank(E +BGΓ) depend on the relationship between C and Γ as the previous characterizations demonstrate. But as will show in the next section it does not make much sense to increase or keep the rank of E, if we require a robust regularization.

4. Minimum Norm Feedback

In this section, algebraic characterizations for minimum norm feedback matrices F, G which solve problem OFR are given. We introduce the following notation. Let Ω(E, A, B, C, Γ, r) := {(F, G) |F ∈ R^{m×p}, G ∈ R^{m×q}, rank(E + BGΓ) = r, (E + BGΓ, A + BF C) is regular and of index at most one }. Furthermore define the distances

δ(E, A, B, C, Γ, r) := inf{∥ [ F G ] ∥ |(F, G) ∈ Ω(E, A, B, C, Γ, r)},
δ_{1}(E, A, B, Γ, r) := δ(E, A, B, Γ, Γ, r),
δ_{2}(E, A, B, Γ, r) := δ(E, A, B, Γ, 0, r).

In order to give the characterization, we need the following three Lemmas.

Lemma 12. Let E, A ∈ R^{n×n}, B ∈ R^{n×m}, C ∈ R^{p×n}, Γ ∈ R^{m×q} and let r ≤ n be an integer satisfying (18). Assume that (E, B, Γ) are given in the condensed form (7) and that A, C are partitioned accordingly as in (13). Denote by U_{r} the set of matrices Q ∈ R^{(r_{ebγ}−r_{eb})×(r_{eγ}−r)} satifying Q^{T} Q = I_{r_{eγ−r}},

rank [ Ã_{53} Ã_{54}Q Ã_{55} ] = n − r_{eb}  (30)

and

rank [ \begin{matrix}Ã_{13} & Ã_{14}Q & Ã_{15} \\ Ã_{43} & Ã_{44}Q & Ã_{45} \\ Ã_{53} & Ã_{54}Q & Ã_{55} \\ C̃_{3} & C̃_{4}Q & C̃_{5} \end{matrix} ] ≥ n − r.  (31)

Then

δ(E, A, B, C, Γ, r) = inf{∥Ẽ_{44}Q∥ Q ∈ U_{r}}.  (32)

Proof. Note first that r_{ebγ} − r_{eb} ≥ r_{eγ} − r. Let ŝ_{4} := r − t_{1} − t_{2} − t_{3} = r_{ebγ} + r − r_{eb} − r_{eγ}. Then for any Q_{2} ∈ U_{r} let Q_{1} ∈ R^{(r_{ebγ}−r_{eb})×ŝ_{4}} be such that [ Q_{1} Q_{2} ] is orthogonal.

For any ϵ > 0, there exists G̃_{11} (depending on ϵ), such that ∥G̃_{11}∥ < ϵ,

[ Ã_{54}Q_{2} − Ã_{53}G̃_{11} Ã_{55} ] has full row rank n − r_{eb}  (33)

and

[ \begin{matrix}Ã_{14}Q_{2} − Ã_{13}G̃_{11} & Ã_{15} \\ Ã_{44}Q_{2} − Ã_{43}G̃_{11} & Ã_{45} \\ Ã_{54}Q_{2} − Ã_{53}G̃_{11} & Ã_{55} \\ C̃_{4}Q_{2} − C̃_{3}G̃_{11} & C̃_{5} \end{matrix} ] has full column rank.  (34)

Set

Z_{Q} := [ \begin{matrix}I_{t_{1}} & 0 & Ã_{14}Q_{2} − Ã_{13}G̃_{11} & Ã_{15} \\ 0 & Ẽ_{44}Q_{1} & Ã_{44}Q_{2} − Ã_{43}G̃_{11} & Ã_{45} \\ 0 & 0 & Ã_{54}Q_{2} − Ã_{53}G̃_{11} & Ã_{55} \end{matrix} ] .

Then there exist matrices G̃_{21}, F̃_{21}, G̃_{22} (all depending on ϵ), such that ∥ [ G̃_{21} F̃_{21} G̃_{22} ] ∥ < ϵ and

rank(Z_{Q}+[ \begin{matrix}0 \\ I_{t_{4}} \\ 0 \end{matrix} ] [ G̃_{21} F̃_{21} G̃_{22} ] [ \begin{matrix}0 & Iŝ_{4} & 0 & 0 \\ 0 & 0 & C̃_{4}Q_{2} − C̃_{3}G̃_{11} & C̃_{5} \\ I_{t_{1}} & 0 & 0 & 0 \end{matrix} ])

= n − t_{2} − t_{3}.  (35)

Let G_{11} := [ 0 G̃_{11} ] [ Q_{1} Q_{2} ]^{T}, G_{21} := [ G̃_{21} −Ẽ_{44} ] [ Q_{1} Q_{2} ]^{T},

and G_{22} = G̃_{22}. Then with G_{Q} := [ \begin{matrix}G_{11} & 0 \\ G_{21} & G_{22} \end{matrix} ], and F_{Q} := [ \begin{matrix}0 \\ F_{21} \end{matrix} ] , we

obtain that (E + BG_{Q}Γ, A + BF_{Q}C) is regular, has index at most one and rank(E + BG_{Q}Γ) = r. This implies that

δ(E, A, B, C, Γ, r) ≤ lim_{ϵ→0} ∥ [ G_{Q} F_{Q} ] ∥ = ∥Ẽ_{44}Q_{2}∥,  (36)

and hence

δ(E, A, B, C, Γ, r) ≤ inf{∥Ẽ_{44}Q∥ |Q ∈ U_{r}}.

To prove (32) we show that the opposite inequality in (36) also holds. For any ϵ > 0, there exist matrices F, G (depending on ϵ), such that (E+BGΓ, A+BF C) is regular, has index at most one, rank(E+BGΓ) = r, and

∥ [ F G ] ∥ < δ(E, A, B, C, Γ, r) + ϵ.

Then there exists an orthogonal matrix [ Q_{1} Q_{2} ] with Q_{2} ∈ R^{(r_{ebγ}−r_{eb})×(r_{eγ}−r)}, such that

G_{21}Q_{2} = −Ẽ_{44}Q_{2}

and (35) holds with G̃_{21} = G_{21}Q_{2} and G̃_{11} = G_{11}Q_{2}. Hence (33) and (34) hold and thus Q_{2} ∈ U_{r}. This implies that

inf{∥Ẽ_{44}Q∥ Q ∈ U_{r}} ≤ lim_{ϵ→0} ∥Ẽ_{44}Q_{2}∥
≤ lim_{ϵ→0} ∥ [ F G ] ∥ = δ(E, A, B, C, Γ, r).

This finishes the proof.

Lemma 13. Given a real matrix Φ of the form

Φ := [ \begin{matrix}& μ_{1} & μ_{2} \\ τ_{1} & Φ_{1} & Φ_{2} \\ τ_{2} & Ψ_{1} & Ψ_{2} \end{matrix} ],

where rank([ Φ_{1} Φ_{2} ]) = τ_{1}. Let

k_{1} := τ_{1} − rank(Φ_{2}), k_{2} := rank([ \begin{matrix}Φ_{2} \\ Ψ_{2} \end{matrix} ]), k_{3} := rank(Φ) − k_{1} − k_{2}.

Assume that l, t are given positive integers such that

l ≤ μ_{1}, k_{1} + k_{2} ≤ t ≤ rank(Φ).

Then there exist orthogonal matrices U_{1} ∈ R^{τ_{1}×τ_{1}}, U_{2} ∈ R^{(τ_{1}+τ_{2}−k_{1})×(τ_{1}+τ_{2}−k_{1})}, V_{1} ∈ R^{μ_{1}×μ_{1}} and V_{2} ∈ R^{(μ_{1}−k_{1})×(μ_{1}−k_{1})}, such that

[ \begin{matrix}I_{k_{1}} \\ & U_{2} \end{matrix} ] [ \begin{matrix}U_{1} \\ & I_{τ_{2}} \end{matrix} ] [ \begin{matrix}Φ_{1} & Φ_{2} \\ Ψ_{1} & Ψ_{2} \end{matrix} ] [ \begin{matrix}V_{1} \\ & I_{μ_{2}} \end{matrix} ] [ \begin{matrix}I_{k_{1}} \\ & V_{2} \\ & & I_{μ_{2}} \end{matrix} ]

=  [ \begin{matrix}& k_{1} & k_{3} & μ_{1} − k_{1} − k_{3} & μ_{2} \\ k_{1} & Σ_{1} & 0 & 0 & 0 \\ k_{2} & Ψ_{21} & Ψ_{22} & Ψ_{23} & Ψ_{24} \\ τ_{1} + τ_{2} − k_{1} − k_{2} & Ψ_{31} & Ψ_{32} & 0 & 0 \end{matrix} ],  (37)

where Σ_{1} is nonsingular, Ψ_{24} has full row rank and Ψ_{32} has full column rank.

Furthermore, for any orthogonal matrix Q ∈ R^{μ_{1}×l}, partition

[ \begin{matrix}I_{k_{1}} \\ & V_{2}^{T} \end{matrix} ] V_{1}^{T} Q :=  [ \begin{matrix}k_{1} & Q_{1} \\ k_{3} & Q_{2} \\ μ_{1} − k_{1} − k_{3} & Q_{3} \end{matrix} ].

Then

rank [ Φ_{1}Q Φ_{2} ] = τ_{1}, rank [ \begin{matrix}Φ_{1}Q & Φ_{2} \\ Ψ_{1}Q & Ψ_{2} \end{matrix} ] ≥ t

if and only if

rank(Q_{1}) = k_{1}, rank [ \begin{matrix}Q_{1} \\ Q_{2} \end{matrix} ] ≥ t − k_{2}.

Proof. The proof for the first part is given constructively via Algorithm 3 in Appendix A. The second part follows trivially from the first.

The next lemma is needed to determine the infimum in (32).

Lemma 14. Given a real matrix M of the form

M :=\left[{z_{1} z_{2} z_{3} \atop v M_{1} M_{2} M_{3}}\right].

Let l, t be given positive integers such that

l ≤ min(v, z_{1} + z_{2} + z_{3}), z_{1} ≤ t ≤ min(z_{1} + z_{2}, l),

and let

U_{t,l} := \{Q = [ \begin{matrix}& l \\ z_{1} & Q_{1} \\ z_{2} & Q_{2} \\ z_{3} & Q_{3} \end{matrix} ]∥ Q^{T} Q = I_{l} rank(Q_{1}) = z_{1}, rank [ \begin{matrix}Q_{1} \\ Q_{2} \end{matrix} ] ≥ t\}.

Then

inf{∥MQ∥ | Q ∈ U_{t,l}} = σ_{z_{1}+z_{2}+z_{3}−l+1}(M).

Proof.

It is well known [11] that

inf{∥MQ∥ |Q ∈ R^{(z_{1}+z_{2}+z_{3})×l}, Q^{T} Q = I_{l}} = σ_{z_{1}+z_{2}+z_{3}−l+1}(M)

and thus inf{∥MQ∥ |Q ∈ U_{t,l}} ≥ σ_{z_{1}+z_{2}+z_{3}−l+1}(M). Hence it suffices to show that

inf{∥MQ∥ | Q ∈ U_{t,l}} ≤ σ_{z_{1}+z_{2}+z_{3}−l+1}(M).  (38)

To see this, let

Q̃ = [ \begin{matrix}& l \\ z_{1} & Q̃_{1} \\ z_{2} & Q̃_{2} \\ z_{3} & Q̃_{3} \end{matrix} ], Q̃^{T} Q̃ = I_{l}

be such that ∥MQ̃∥ = σ_{z_{1}+z_{2}+z_{3}−t+1}(M).

If rank(Q̃_{1}) = z_{1} and rank [ Q̃_{1} ; Q̃_{2} ] ≥ t, then (38) follows. Otherwise, if

rank(Q̃_{1}) < z_{1} or [ Q̃_{1} ; Q̃_{2} ] < t, then we can assume w.l.o.g. that

Q̃_{1} = P̃_{1} [ \begin{matrix}Π_{1} & 0 & 0 \\ 0 & 0_{z_{1}−τ_{1}} & 0 \end{matrix} ] ,

and

Q̃_{2} = [ Q_{21} Q_{22} Q_{23} ] , Q̃_{3} = [ Q_{31} Q_{32} Q_{33} ] ,

where P̃_{1} is orthogonal and Π_{1} ∈ R^{τ_{1}×τ_{1}} is nonsingular.

For any ϵ with 0 < ϵ < 1, set

Q̂_{1}(ϵ) := P̃_{1} \left[{Π_{1}  0 \atop 0 ϵI_{z_{1}−τ_{1}} 0}\right] ,
Q̂_{2}(ϵ) := [ Q_{21} (1 − ϵ)Q_{22} Q_{23} ] ,
Q̂_{3}(ϵ) := [ Q_{31} (1 − ϵ)Q_{32} Q_{33} ] .

Then rank(Q̂_{1}(ϵ)) = z_{1} and there exist orthogonal matrices P̂_{2}(ϵ), V̂_{2}(ϵ) such that

[ \begin{matrix}Q̂_{1}(ϵ) \\ Q̂_{2}(ϵ) \end{matrix} ] = P̂_{2}(ϵ) [ \begin{matrix}Π_{2}(ϵ) & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ] V̂_{2}(ϵ),
Q̂_{3}(ϵ) = [ Q̂_{31}(ϵ) Q̂_{32}(ϵ) Q̂_{33}(ϵ) ] V̂_{2}(ϵ),

where Π_{2}(ϵ) ∈ R^{τ_{2}×τ_{2}} is nonsingular. Let δ_{ϵ} satisfy that 0 < δ_{ϵ} < ϵ and rank(Q_{1}(ϵ)) = z_{1}, where Q(ϵ), Q_{1}(ϵ), Q_{2}(ϵ) and Q_{3}(ϵ) are defined as follows.

Q(ϵ) := [ \begin{matrix}Q_{1}(ϵ) \\ Q_{2}(ϵ) \\ Q_{3}(ϵ) \end{matrix} ]

with

[ \begin{matrix}& l \\ z_{1} & Q_{1}(ϵ) \\ z_{2} & Q_{2}(ϵ) \end{matrix} ] := P̂_{2}(ϵ) [ \begin{matrix}Π_{2}(ϵ) & 0 & 0 \\ 0 & δ_{ϵ}I_{z_{1}+z_{2}−τ_{2}} & 0 \end{matrix} ] V̂_{2}(ϵ)
Q_{3}(ϵ) := [ Q̂_{31}(ϵ) (1 − δ_{ϵ})Q̂_{32}(ϵ) Q̂_{33}(ϵ) ] V̂_{2}(ϵ).

Since rank(Q_{1}(ϵ)) = z_{1}, rank [ \begin{matrix}Q_{1}(ϵ) \\ Q_{2}(ϵ) \end{matrix} ] ≥ t, Q^{T} (ϵ)Q(ϵ) = I_{l}, and

lim_{ϵ→0} ∥Q(ϵ) − Q̃∥ = 0

it follows that

inf{∥MQ∥ | Q ∈ Ũ_{t,l} } ≤ lim_{ϵ→0} ∥MQ(ϵ)∥ = ∥MQ̃∥ = σ_{z_{1}+z_{2}+z_{3}−l+1}(M),

which implies (38).

Since for any nonsingular matrices X, Y and orthogonal matrices P, W as in (7), X, Y do not affect ∥ [ F G ] ∥, where F, G are such that (E + BGΓ, A+BF C) is regular, has index at most one and rank (E + BGΓ) = r, we can characterize the minimum norm regularization via the condensed form (7), in particular, via the restricted singular values of (E, B, Γ), i.e., the singular values of Ẽ_{44} in (7).

Theorem 15. Let E, A ∈ R^{n×n}, B ∈ R^{n×m}, C ∈ R^{p×n}, Γ ∈ R^{m×q} and let Ẽ_{44} be as in (7), (8).

1. If conditions (19)–(21) hold and r satisfies (18), then

δ(E, A, B, C, Γ, r) = σ_{r−t_{1}−t_{2}−t_{3}+1}.

2. If Γ = C, conditions (19), (21) and (28) hold and r satisfies (27),

then

δ_{1}(E, A, B, Γ, r) = σ_{r−t_{1}−t_{2}−t_{3}+1}.

3. If Γ = C, conditions (19), (21) and (28) hold and r satisfies (29),

then

δ_{2}(E, A, B, Γ, r) = σ_{r−t_{1}−t_{2}−t_{3}+1}.

In particular, we have in all three cases that if r ≥ r_{e} then

δ(E, A, B, C, Γ, r) = 0,
δ_{1}(E, A, B, Γ, r) = 0,
δ_{2}(E, A, B, Γ, r) = 0.

Proof. The result follows directly by applying Lemma 12, Lemma 13 and Lemma 14.

Note that this result also covers the state feedback case C = I, Γ = 0. Theorem 15 shows that it does not make sense to consider the minimum

norm regularizing feedback if r ≥ r_{e}, since we will be arbitrarily close to a system which is not regular and of index at most one. This certainly is not a robust regularization. Thus although minimum norm feedbacks are very important in other control problems, like pole placement or stabilization, since they remove ambiguity in the solution in a least squares sense, for the problem of regularization they do not lead to a useful solution.

If, however, we decrease the rank of E, i.e., we choose r < r_{e}, then the situation may be more satisfactory. In this case the minimal norm of the feedback is given by the appropriate restricted singular value of (E, B, Γ) and if this value is large enough, then there is some hope that the regularization will be robust, i.e., we are reasonably far away from a pencil that is non-regular or has an index larger than one. It is still an open problem how to obtain the exact distance of a closed loop system from the nearest non-regular pencil, see [4, 5]. This is the reason, why it is currently not clear how to choose the most robust regularization. This topic is currently under invertigation. Heuristic procedures to obtain a system that is robustly regular and of index at most one are discussed in [8, 12, 13].

5. Conclusions

We have given necessary and sufficient conditions for Problem OFR. The results characterize the relation among mixed feedback, combined derivative and proportional feedback and derivative feedback for the regularization of descriptor systems. Numerical procedures to compute the desired feedback gains are discussed in Appendix A.

Furthermore we have given algebraic characterizations of the minimum norm regularizing feedback and shown that this is not a good approach if the rank of E is increased.

REFERENCES

1 A. Bunse-Gerstner, V. Mehrmann, and N.K. Nichols. Numerical methods for the regularization of descriptor system by output feedback. Technical Report 987, Institute for Mathematics and Its Applications, University of Minnesota, 1992.

2 A. Bunse-Gerstner, V. Mehrmann, and N.K. Nichols. Regularization of descriptor systems by derivative and proportional state feedback. SIAM J. Matrix Anal. Appl., 13:46–67, 1992.

3 A. Bunse-Gerstner, V. Mehrmann, and N.K. Nichols. Regularization of descriptor systems by output feedback. IEEE Trans. Automat. Control, AC–39:1742–1747, 1994.

4 R. Byers, C. He, and V. Mehrmann. Where is the nearest nonregular pencil. Technical Report SFB393/96-09, Sonderforschungsbereich 393, TU Chemnitz-Zwickau, Fakultät für Mathematik, D-09107 Chemnitz, 1996. Submitted for publication.

5 R. Byers and N. K. Nichols. On the stability radius of generalized

state-space systems. Linear Algebra Appl., 188/189:113–134, 1993. 6 D.L. Chu, H.C. Chan, and D.W.C. Ho. Regularization of singular

systems by derivative and proportional output feedback. Technical Report Ma 94-10, Dept. of Mathematics, City Univ. of Hong-Kong, Kowloon, Hong-Kong, 1994. To appear in SIAM J. Matrix Anal. and Appl.

7 L. Dai. Singular Control Systems, volume 118 of Lecture Notes in

Control and Information Sciences. Springer-Verlag, Berlin, 1989. 8 L. Elsner, C. He, and V. Mehrmann. Completion of a matrix so

that the inverse has minimum norm. Application to the regularization of descriptor control problems. In P. Van Dooren and B. Wyman, editors, Linear Algebra for Control Theory, pages 75–86. Springer Verlag, New York, 1993.

9 F.R. Gantmacher. Theory of Matrices, volume II. Chelsea, New York,

1959. 10 T. Geerts. Solvability conditions, consistency, and weak consistency

for linear differential-algebraic equations and time-invariant linear systems: The general case. Linear Algebra Appl., 181:111–130, 1993.

11 G.H. Golub and C.F. Van Loan. Matrix Computations. The Johns

Hopkins University Press, Baltimore, Maryland, 2nd edition, 1989. 12 J. Kautsky, N. K. Nichols, and E. K-W. Chu. Robust pole assignment

in singular control sytems. Linear Algebra Appl., 121:9–37, 1989. 13 J. Kautsky, N. K. Nichols, and P. Van Dooren. Robust pole assign-

ment in linear state feedback. Internat. J. Control, 41:1129–1155, 14 V. Mehrmann. The Autonomous Linear Quadratic Control Problem:

Theory and Numerical Algorithms, volume 163 of Lecture Notes in Control and Information Sciences. Springer-Verlag, Heidelberg, 1991.

15 V. Mehrmann and N. K. Nichols. Mixed output feedback for descriptor systems. Technical Report SPC 95-37, DFG Forschergruppe SPC, Fakultät für Mathematik, TU Chemnitz-Zwickau, D-09107 Chemnitz, FRG, 1995. Submitted for publication.

16 R. Mukundan and W. Dayawansa. Feedback control of singular systems – proportional and derivative feedback of the state. Int. J. Syst. Sci., 14:615–632, 1983.

17 K. Özcaldiran and F.L. Lewis. On regularizability of singular systems.

IEEE Trans. Automat. Control, AC-35:1156–1160, 1990. 18 G.C. Verghese, B.C. Lévy, and T. Kailath. A general state space for

singular systems. IEEE Trans. Automat. Control, AC–26:811–831, 1981.

19 H. Zha. The restricted singular value decomposition of matrix triplets. SIAM J. Matrix Anal. Appl., 12:172–194, 1991.

Appendix A–Numerical Algorithms

In this appendix, we describe a numerical procedure to construct feedback gains F, G such that (E + BGΓ, A + BF C) is regular, has index at most one and rank(E + BGΓ) = r. The procedure is based on the condensed form (4). For algorithms to compute the condensed form (4), see [3, 6].

In the following algorithms we need row compressions, column compressions or simultaneous row and column compressions of matrices. Such compressions can be obtained in the usual way via QR-factorizations, rank revealing QR-factorizations, URV-decompositions or singular value decompositions, see [11].

Input: Matrices

[ \begin{matrix}& l_{1} & l_{2} \\ n_{1} & A_{11} & A_{12} \\ n_{2} & A_{21} & A_{22} \end{matrix} ], [ \begin{matrix}& m_{1} \\ n_{1} & B_{1} \\ n_{2} & B_{2} \end{matrix} ],

satisfying

rank [ A_{21} A_{22} B_{2} ] = n_{2},
rank(A_{21}) + l_{2} ≥ n_{2},
rank [ \begin{matrix}A_{11} \\ A_{21} \end{matrix} ] = l_{1}

and an integer t satisfying

n_{2} − rank(A_{21}) ≤ t ≤ min(rank [ \begin{matrix}A_{11} & A_{12} & B_{1} \\ A_{21} & A_{22} & B_{2} \end{matrix} ] − l_{1}, l_{2}).

Output: A matrix K ∈ R^{m_{1}×l_{2}} and an orthogonal matrix [ Q_{1} Q_{2} ] ∈ R^{l_{2}×l_{2}} with Q_{2} ∈ R^{l_{2}×t}, such that

rank [ A_{21} (A_{22} + B_{2}K)Q_{2} ] = n_{2},
rank [ \begin{matrix}A_{11} & (A_{12} + B_{1}K)Q_{2} \\ A_{21} & (A_{22} + B_{2}K)Q_{2} \end{matrix} ] = l_{1} + t.

Remark 16.

The main idea of this algorithm is to find K_{0} such that

rank [ A_{21} A_{22} + B_{2}K_{0} ] = n_{2}

and

rank [ \begin{matrix}A_{11} & A_{12} + B_{1}K_{0} \\ A_{21} & A_{22} + B_{2}K_{0} \end{matrix} ] = max_{K} rank [ \begin{matrix}A_{11} & A_{12} + B_{1}K \\ A_{21} & A_{22} + B_{2}K \end{matrix} ] .

Step 1: Perform a simultaneous row and column compression of A_{21}:

[ \begin{matrix}I_{n_{1}} \\ & U_{1}^{T} \end{matrix} ] [ \begin{matrix}A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix} ] [ \begin{matrix}V_{1} \\ & I_{l_{2}} \end{matrix} ] =:  [ \begin{matrix}& τ_{1} & l_{1} − τ_{1} & l_{2} \\ n_{1} & A_{11} & A_{12} & A_{13} \\ τ_{1} & Σ̃_{31} & 0 & A_{23} \\ n_{2} − τ_{1} & 0 & 0 & A_{33} \end{matrix} ]

with Σ̃_{31} nonsingular. Partition

[ \begin{matrix}I_{n_{1}} \\ & U_{1}^{T} \end{matrix} ] [ \begin{matrix}B_{1} \\ B_{2} \end{matrix} ] =: [ \begin{matrix}B_{1} \\ B_{2} \\ B_{3} \end{matrix} ]

analogously. Step 2: Perform a row compression of A_{12} ( note that by assumption it has full column rank):

[ \begin{matrix}U_{2}^{T} \\ & I_{n_{2}} \end{matrix} ] [ \begin{matrix}A_{11} & A_{12} & A_{13} \\ Σ̃_{31} & 0 & A_{32} \\ 0 & 0 & A_{33} \end{matrix} ] =:  [ \begin{matrix}& τ_{1} & l_{1} − τ_{1} & l_{2} \\ l_{1} − τ_{1} & A_{11} & Σ_{12} & A_{13} \\ n_{1} + τ_{1} − l_{1} & A_{21} & 0 & A_{23} \\ τ_{1} & Σ̃_{31} & 0 & A_{33} \\ n_{2} − τ_{1} & 0 & 0 & A_{43} \end{matrix} ]

with Σ_{12} nonsingular. Partition

[ \begin{matrix}U_{2}^{T} \\ & I_{n_{2}} \end{matrix} ] [ \begin{matrix}B_{1} \\ B_{2} \\ B_{3} \end{matrix} ] =: [ \begin{matrix}B_{1} \\ B_{2} \\ B_{3} \\ B_{4} \end{matrix} ]

analogously. Step 3: Perform a simultaneous row and column compression of A_{43}:

[ \begin{matrix}I_{n_{1}} \\ & I_{τ_{1}} \\ & & U_{3}^{T} \end{matrix} ] [ \begin{matrix}A_{11} & Σ_{12} & A_{13} \\ A_{21} & 0 & A_{23} \\ Σ̃_{31} & 0 & A_{33} \\ 0 & 0 & A_{43} \end{matrix} ] [ \begin{matrix}I_{l_{1}} \\ & V_{3} \end{matrix} ]

=:  [ \begin{matrix}& τ_{1} & l_{1} − τ_{1} & τ_{2} & l_{2} − τ_{2} \\ l_{1} − τ_{1} & A_{11} & Σ_{12} & A_{13} & A_{14} \\ n_{1} + τ_{1} − l_{1} & A_{21} & 0 & A_{23} & A_{24} \\ τ_{1} & Σ̃_{31} & 0 & A_{33} & A_{34} \\ τ_{2} & 0 & 0 & Σ̃_{43} & 0 \\ n_{2} − τ_{1} − τ_{2} & 0 & 0 & 0 & 0 \end{matrix} ],

with Σ̃_{43} nonsingular. Partition

[ \begin{matrix}I_{n_{1}} \\ & I_{τ_{1}} \\ & & U_{3}^{T} \end{matrix} ] [ \begin{matrix}B_{1} \\ B_{2} \\ B_{3} \\ B_{4} \end{matrix} ] =: [ \begin{matrix}B_{1} \\ B_{2} \\ B_{3} \\ B_{4} \\ B_{5} \end{matrix} ]

analogously. Step 4: Perform a column compression of B_{5} (note that by assumption B_{5} has full row rank):

[ \begin{matrix}B_{1} \\ B_{2} \\ B_{3} \\ B_{4} \\ B_{5} \end{matrix} ] W_{4} =: [ \begin{matrix}B_{11} & B_{12} \\ B_{21} & B_{22} \\ B_{31} & B_{32} \\ B_{41} & B_{42} \\ Σ_{51} & 0 \end{matrix} ] .

with Σ_{51} nonsingular.

Step 5: Perform a row compression of [ \begin{matrix}A_{21} & A_{23} \\ Σ̃_{31} & A_{33} \\ 0 & Σ̃_{43} \end{matrix} ]:

[ \begin{matrix}I_{l_{1}−τ_{1}} \\ & U_{5}^{T} \\ & & I_{n_{2}−τ_{1}−τ_{2}} \end{matrix} ] [ \begin{matrix}A_{11} & Σ_{12} & A_{13} & A_{14} \\ A_{21} & 0 & A_{23} & A_{24} \\ Σ̃_{31} & 0 & A_{33} & A_{34} \\ 0 & 0 & Σ̃_{43} & 0 \\ 0 & 0 & 0 & 0 \end{matrix} ]

=:  [ \begin{matrix}& τ_{1} & l_{1} − τ_{1} & τ_{2} & l_{2} − τ_{2} \\ l_{1} − τ_{1} & A_{11} & Σ_{12} & A_{13} & A_{14} \\ n_{1} + τ_{1} − l_{1} & 0 & 0 & 0 & A_{24} \\ τ_{1} & Σ_{31} & 0 & A_{33} & A_{34} \\ τ_{2} & 0 & 0 & Σ_{43} & A_{44} \\ n_{2} − τ_{1} − τ_{2} & 0 & 0 & 0 & 0 \end{matrix} ]

with Σ_{31} and Σ_{43} nonsingular. Partition

[ \begin{matrix}I_{l_{1}−τ_{1}} \\ & U_{5}^{T} \\ & & I_{n_{2}−τ_{1}−τ_{2}} \end{matrix} ] [ \begin{matrix}B_{11} & B_{12} \\ B_{21} & B_{22} \\ B_{31} & B_{32} \\ B_{41} & B_{42} \\ Σ_{51} & 0 \end{matrix} ] =: [ \begin{matrix}B_{11} & B_{12} \\ B_{21} & B_{22} \\ B_{31} & B_{32} \\ B_{41} & B_{42} \\ Σ_{51} & 0 \end{matrix} ]

analogously. Step 6: Perform a simultaneous row and column compression of A_{24}:

[ \begin{matrix}I_{l_{1}−τ_{1}} \\ & U_{6}^{T} \\ & & I_{n_{2}} \end{matrix} ] [ \begin{matrix}A_{11} & Σ_{12} & A_{13} & A_{14} \\ 0 & 0 & 0 & A_{24} \\ Σ_{31} & 0 & A_{33} & A_{34} \\ 0 & 0 & Σ_{43} & A_{44} \\ 0 & 0 & 0 & 0 \end{matrix} ] [ \begin{matrix}I_{l_{1}} \\ & I_{τ_{2}} \\ & & V_{6} \end{matrix} ]

=:  [ \begin{matrix}& τ_{1} & l_{1} − τ_{1} & τ_{2} & n_{2} − τ_{1} − τ_{2} & τ_{3} & l_{2} + τ_{1} − n_{2} − τ_{3} \\ l_{1} − τ_{1} & A_{11} & Σ_{12} & A_{13} & A_{14} & A_{15} & A_{16} \\ τ_{3} & 0 & 0 & 0 & 0 & Σ_{25} & 0 \\ n_{1} + τ_{1} − l_{1} − τ_{3} & 0 & 0 & 0 & 0 & 0 & 0 \\ τ_{1} & Σ_{31} & 0 & A_{43} & A_{44} & A_{45} & A_{46} \\ τ_{2} & 0 & 0 & Σ_{43} & A_{54} & A_{55} & A_{56} \\ n_{2} − τ_{1} − τ_{2} & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ]

with Σ_{25} ∈ R^{τ_{3}×τ_{3}} nonsingular. Partition

[ \begin{matrix}I_{l_{1}−τ_{1}} \\ & U_{6}^{T} \\ & & I_{n_{2}} \end{matrix} ] [ \begin{matrix}B_{11} & B_{12} \\ B_{21} & B_{22} \\ B_{31} & B_{32} \\ B_{41} & B_{42} \\ Σ_{51} & 0 \end{matrix} ] =: [ \begin{matrix}B_{11} & B_{12} \\ B_{21} & B_{22} \\ B_{31} & B_{32} \\ B_{41} & B_{42} \\ B_{51} & B_{52} \\ Σ_{51} & 0 \end{matrix} ]

analogously. Step 7: Perform a column compression of B_{32}:

[ \begin{matrix}B_{11} & B_{12} \\ B_{21} & B_{22} \\ B_{31} & B_{32} \\ B_{41} & B_{42} \\ B_{51} & B_{52} \\ Σ_{51} & 0 \end{matrix} ] [ \begin{matrix}I_{n_{2}−τ_{1}−τ_{2}} \\ & W_{7} \end{matrix} ]

=: [ \begin{matrix}n_{2} − τ_{1} − τ_{2} & μ_{b} & m_{1} + τ_{1} + τ_{2} − n_{2} − μ_{b} \\ B_{11} & B_{12} & B_{13} \\ B_{21} & B_{22} & B_{23} \\ B_{31} & B_{32} & 0 \\ B_{41} & B_{42} & B_{43} \\ B_{51} & B_{52} & B_{53} \\ Σ_{51} & 0 & 0 \end{matrix} ]

with B_{32} of full column rank. Step 8: Set

K := W_{4} [ \begin{matrix}I_{n_{2}−τ_{1}−τ_{2}} \\ & W_{7} \end{matrix} ] K̃ [ \begin{matrix}I_{τ_{2}} \\ & V_{6}^{T} \end{matrix} ] V_{3}^{T}

with

K̃ =  [ \begin{matrix}& τ_{2} & n_{2} − τ_{1} − τ_{2} & τ_{3} & l_{2} + τ_{1} − τ_{3} − n_{2} \\ n_{2} − τ_{1} − τ_{2} & 0 & I_{n_{2}−τ_{1}−τ_{2}} & 0 & 0 \\ μ_{b} & 0 & 0 & 0 & K̃_{24} \\ m_{1} + τ_{1} + τ_{2} − n_{2} − μ_{b} & 0 & 0 & 0 & 0 \end{matrix} ],

where

K̃_{24} = \{ \begin{matrix}[ \begin{matrix}I_{l_{2}+τ_{1}−τ_{3}−n_{2}} \\ 0 \end{matrix} ]  if l_{2} + τ_{1} − τ_{3} − n_{2} ≤ μ_{b}, \\ [ I_{μ_{b}} 0 ]  if l_{2} + τ_{1} − τ_{3} − n_{2} > μ_{b}. \end{matrix}

Set furthermore Q := [ Q_{1} Q_{2} ] with

Q_{1} := V_{3} [ \begin{matrix}I_{τ_{2}} \\ & V_{6} \end{matrix} ] [ \begin{matrix}0 \\ I_{l_{2}−t} \end{matrix} ] , Q_{2} := V_{3} [ \begin{matrix}I_{τ_{2}} \\ & V_{6} \end{matrix} ] [ \begin{matrix}I_{t} \\ 0 \end{matrix} ] .

Input: Matrices E, A ∈ R^{n×n}, B ∈ R^{n×m}, C ∈ R^{p×n}, Γ ∈ R^{q×n} and an integer r, satisfying conditions (19)–(21) and (18). Output: Feedback gains F ∈ R^{m×p}, G ∈ R^{m×q} such that (E + BGΓ, A + BF C) is regular, has index at most one, and rank(E + BGΓ) = r. Step 1: Compute orthogonal matrices U, V, P, W such that (UEV, UBP, W ΓV) is in the condensed form (4) and partition UAV, CV accordingly as in (13). Set ŝ_{4} := r − t_{1} − t_{2} − t_{3}.

Step 2: Use Algorithm 1 to compute a matrix K and an orthogonal matrix [ Q_{1} Q_{2} ] ∈ R^{s̃_{4}×s̃_{4}} with Q_{2} ∈ R^{s̃_{4}×(r_{eγ}−r)} such that the transformed submatrices

[ \begin{matrix}E_{34} − E_{33}K \\ E_{44} \end{matrix} ] [ Q_{1} Q_{2} ] =:  [ \begin{matrix}& ŝ_{4} & r_{eγ} − r \\ t_{3} & Θ_{34} & Θ_{35} \\ t_{4} & Θ_{44} & Θ_{45} \end{matrix} ],

[ \begin{matrix}A_{14} − A_{13}K \\ A_{24} − A_{23}K \\ A_{44} − A_{43}K \\ A_{54} − A_{53}K \end{matrix} ] [ Q_{1} Q_{2} ] =:  [ \begin{matrix}& ŝ_{4} & r_{eγ} − r \\ t_{1} & Φ_{14} & Φ_{15} \\ t_{2} & Φ_{24} & Φ_{25} \\ t_{4} & Φ_{44} & Φ_{45} \\ t_{5} & Φ_{54} & Φ_{55} \end{matrix} ],

Γ_{14} [ Q_{1} Q_{2} ] =: \left[{ŝ_{4} r_{eγ} − r \atop q − t_{1} Π_{14} Π_{15}}\right],

(C_{4} − C_{3}K) [ Q_{1} Q_{2} ] =: \left[{ŝ_{4} r_{eγ} − r \atop p Ψ_{4} Ψ_{5}}\right]

satisfy

rank [ Φ_{55} A_{55} ] = n − r_{eb}

and

rank [ \begin{matrix}0 & 0 & Φ_{15} & A_{15} \\ E_{22} & 0 & Φ_{25} & A_{25} \\ E_{42} & E_{44} & Φ_{45} & A_{45} \\ 0 & 0 & Φ_{55} & A_{55} \\ Γ_{12} & Γ_{14} & 0 & 0 \\ 0 & 0 & Ψ_{5} & C_{5} \end{matrix} ] = t_{2} + s̃_{4} + (n − r).

Remark 17. If we set

Y := [ \begin{matrix}I_{t_{1}} & 0 & 0 & 0 & 0 \\ 0 & I_{t_{2}} & 0 & 0 & 0 \\ 0 & 0 & I_{t_{3}} & 0 & 0 \\ −Γ_{14}^{−1}Γ_{11} & −Γ_{14}^{−1}Γ_{12} & 0 & Is̃_{4} & 0 \\ 0 & 0 & 0 & 0 & Is̃_{5} \end{matrix} ] [ \begin{matrix}I_{t_{1}} & 0 & 0 & 0 & 0 & 0 \\ 0 & I_{t_{2}} & 0 & 0 & 0 & 0 \\ 0 & 0 & I_{t_{3}} & KQ_{1} & KQ_{2} & 0 \\ 0 & 0 & 0 & Q_{1} & Q_{2} & 0 \\ 0 & 0 & 0 & 0 & 0 & Is̃_{5} \end{matrix} ]

and if for given F ∈ R^{m×p}, G ∈ R^{m×q} we set

[ \begin{matrix}t_{3} & F_{1} \\ t_{4} & F_{2} \end{matrix} ] := [ \begin{matrix}B_{31} & B_{32} \\ 0 & B_{42} \end{matrix} ] F

[ \begin{matrix}& t_{1} & ŝ_{4} & r_{eγ} − r \\ t_{3} & G_{31} & G_{34} & G_{35} \\ t_{4} & G_{41} & G_{44} & G_{45} \end{matrix} ] := [ \begin{matrix}B_{31} & B_{32} \\ 0 & B_{42} \end{matrix} ] G [ \begin{matrix}0 & Π_{14} & Π_{15} \\ Γ_{21} & 0 & 0 \end{matrix} ]
+ [ \begin{matrix}0 & Θ_{34} & Θ_{35} \\ 0 & Θ_{44} & Θ_{45} \end{matrix} ] ,

then we have that

U(E + BGΓ)Y =

[ \begin{matrix}E_{11} & 0 & 0 & 0 & 0 & 0 \\ E_{21} & E_{22} & 0 & 0 & 0 & 0 \\ E_{31} + G_{31} − E_{34}Γ_{14}^{−1}Γ_{11} & E_{32} − E_{34}Γ_{14}^{−1}Γ_{12} & E_{33} & G_{34} & G_{35} & 0 \\ E_{41} + G_{41} − E_{44}Γ_{14}^{−1}Γ_{11} & E_{42} − E_{44}Γ_{14}^{−1}Γ_{12} & 0 & G_{44} & G_{45} & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ] ,

U(A + BF C)Y =

Â_{11} Â_{12} A_{13}  Φ_{14}  Φ_{15}  A_{15}
Â_{21} Â_{22} A_{23}  Φ_{24}  Φ_{25}  A_{25}
Â_{31} Â_{32} A_{33} Φ_{34} + F_{1}Ψ_{4} Φ_{34} + F_{1}Ψ_{5} A_{35} + F_{1}C_{5}
Â_{41} Â_{42} A_{43} Φ_{44} + F_{2}Ψ_{4} Φ_{45} + F_{2}Ψ_{5} A_{45} + F_{2}C_{5}
Â_{51} Â_{52} A_{53}  Φ_{54}  Φ_{55}  A_{55}

with

[ \begin{matrix}Â_{11} & Â_{12} \\ Â_{21} & Â_{22} \\ Â_{31} & Â_{32} \\ Â_{41} & Â_{42} \\ Â_{51} & Â_{52} \end{matrix} ] = [ \begin{matrix}A_{11} & A_{12} \\ A_{21} & A_{22} \\ A_{31} & A_{32} \\ A_{41} & A_{42} \\ A_{51} & A_{52} \end{matrix} ] − [ \begin{matrix}A_{14} \\ A_{24} \\ A_{34} \\ A_{44} \\ A_{54} \end{matrix} ] Γ_{14}^{−1} [ Γ_{11} Γ_{12} ] .

It is easy to see that if

G_{35} = 0, G_{45} = 0

and if the rank of

E_{11}  0  0  0  Φ_{15}  A_{15}
E_{21}  E_{22}  0  0  Φ_{25}  A_{25}
E_{31} + G_{31} − E_{34}Γ_{14}^{−1}Γ_{11} E_{32} − E_{34}Γ_{14}^{−1}Γ_{12} E_{33} G_{34} Φ_{35} + F_{1}Ψ_{5} A_{35} + F_{1}C_{5}
E_{41} + G_{41} − E_{44}Γ_{14}^{−1}Γ_{11} E_{42} − E_{44}Γ_{14}^{−1}Γ_{12} 0 G_{44} Φ_{45} + F_{2}Ψ_{5} A_{45} + F_{2}C_{5}
0 0 0 0 Φ_{55} A_{55}

is n, then we have that (E + BGΓ, A + BF C) is regular, of index at most one and rank(E + BGΓ) = r. Note that (39) holds if and only if

rank [ \begin{matrix}E_{11} & 0 & 0 & 0 & 0 & Φ_{15} & A_{15} \\ E_{21} & E_{22} & 0 & 0 & 0 & Φ_{25} & A_{25} \\ E_{31} + G_{31} & E_{32} & E_{33} & E_{34} & G_{34} & Φ_{35} + F_{1}Ψ_{5} & A_{35} + F_{1}C_{5} \\ E_{41} + G_{41} & E_{42} & 0 & E_{44} & G_{44} & Φ_{45} + F_{2}Ψ_{5} & A_{45} + F_{2}C_{5} \\ 0 & 0 & 0 & 0 & 0 & Φ_{55} & A_{55} \\ Γ_{11} & Γ_{12} & 0 & Γ_{14} & 0 & 0 & 0 \end{matrix} ] = n+s̃_{4}

or equivalently that the rank of

[ \begin{matrix}E_{11} & 0 & 0 & 0 & Φ_{15} & A_{15} \\ E_{21} & E_{22} & 0 & 0 & Φ_{25} & A_{25} \\ E_{41} + G_{41} & E_{42} & E_{44} & G_{44} & Φ_{45} + F_{2}Ψ_{5} & A_{45} + F_{2}C_{5} \\ 0 & 0 & 0 & 0 & Φ_{55} & A_{55} \\ Γ_{11} & Γ_{12} & Γ_{14} & 0 & 0 & 0 \end{matrix} ]  (40)

= [ \begin{matrix}I_{t_{1}} \\ & I_{t_{2}} \\ & & I_{t_{4}} & 0 & 0 & G_{41} & G_{44} & F_{2} \\ & & & I_{t_{5}} \\ & & & & I_{q−t_{1}} \end{matrix} ] [ \begin{matrix}E_{11} & 0 & 0 & 0 & Φ_{15} & A_{15} \\ E_{21} & E_{22} & 0 & 0 & Φ_{25} & A_{25} \\ E_{41} & E_{42} & E_{44} & 0 & Φ_{45} & A_{45} \\ 0 & 0 & 0 & 0 & Φ_{55} & A_{55} \\ Γ_{11} & Γ_{12} & Γ_{14} & 0 & 0 & 0 \\ I_{t_{1}} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & Iŝ_{4} & 0 & 0 \\ 0 & 0 & 0 & 0 & Ψ_{5} & C_{5} \end{matrix} ]

is n + s̃_{4} − t_{3}. For the construction of F, G, it therefore suffices to study the submatrix product (40). The following construction is therefore only based on this submatrix. Step 3. Perform a column compression

[ Φ_{55} A_{55} ] V_{3} = [ 0 Σ_{4} ] and set

[ \begin{matrix}E_{11} & 0 & 0 & 0 & Φ_{15} & A_{15} \\ E_{21} & E_{22} & 0 & 0 & Φ_{25} & A_{25} \\ E_{41} & E_{42} & E_{44} & 0 & Φ_{45} & A_{45} \\ 0 & 0 & 0 & 0 & Φ_{55} & A_{55} \\ Γ_{11} & Γ_{12} & Γ_{14} & 0 & 0 & 0 \\ I_{t_{1}} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & Iŝ_{4} & 0 & 0 \\ 0 & 0 & 0 & 0 & Ψ_{5} & C_{5} \end{matrix} ] [ \begin{matrix}I_{t_{1}} \\ & I_{t_{2}} \\ & & Is̃_{4} \\ & & & Iŝ_{4} \\ & & & & V_{3} \end{matrix} ]

=:  [ \begin{matrix}& t_{1} & t_{2} & s̃_{4} & ŝ_{4} & n − r − t_{5} & t_{5} \\ t_{1} & E_{11} & 0 & 0 & 0 & Φ_{15} & Φ_{16} \\ t_{2} & E_{21} & E_{22} & 0 & 0 & Φ_{25} & Φ_{26} \\ t_{4} & E_{41} & E_{42} & E_{44} & 0 & Φ_{35} & Φ_{36} \\ t_{5} & 0 & 0 & 0 & 0 & 0 & Σ_{4} \\ s̃_{4} & Γ_{11} & Γ_{12} & Γ_{14} & 0 & 0 & 0 \\ t_{1} & I_{t_{1}} & 0 & 0 & 0 & 0 & 0 \\ ŝ_{4} & 0 & 0 & 0 & Iŝ_{4} & 0 & 0 \\ p & 0 & 0 & 0 & 0 & Ψ_{5} & Ψ_{6} \end{matrix} ]

with Σ_{4} nonsingular. Step 4: Perform a column compression of [ Γ_{11} Γ_{12} Γ_{14} ]:

[ \begin{matrix}E_{11} & 0 & 0 & 0 & Φ_{15} & Φ_{16} \\ E_{21} & E_{22} & 0 & 0 & Φ_{25} & Φ_{26} \\ E_{41} & E_{42} & E_{44} & 0 & Φ_{35} & Φ_{36} \\ 0 & 0 & 0 & 0 & 0 & Σ_{4} \\ Γ_{11} & Γ_{12} & Γ_{14} & 0 & 0 & 0 \\ I_{t_{1}} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & Iŝ_{4} & 0 & 0 \\ 0 & 0 & 0 & 0 & Ψ_{5} & Ψ_{6} \end{matrix} ] [ \begin{matrix}V_{4} \\ & Iŝ_{4} \\ & & I_{n−r−t_{5}} \\ & & & I_{t_{5}} \end{matrix} ]

=:  [ \begin{matrix}& t_{1} & t_{2} & s̃_{4} & ŝ_{4} & n − r − t_{5} & t_{5} \\ t_{1} & Θ_{11} & Θ_{12} & Θ_{13} & 0 & Φ_{15} & Φ_{16} \\ t_{2} & Θ_{21} & Θ_{22} & Θ_{23} & 0 & Φ_{25} & Φ_{26} \\ t_{4} & Θ_{31} & Θ_{32} & Θ_{33} & 0 & Φ_{35} & Φ_{36} \\ t_{5} & 0 & 0 & 0 & 0 & 0 & Σ_{4} \\ s̃_{4} & 0 & 0 & Σ_{5} & 0 & 0 & 0 \\ t_{1} & Λ_{1} & Λ_{2} & Λ_{3} & 0 & 0 & 0 \\ ŝ_{4} & 0 & 0 & 0 & Iŝ_{4} & 0 & 0 \\ p & 0 & 0 & 0 & 0 & Ψ_{5} & Ψ_{6} \end{matrix} ]

with Σ_{5} nonsingular.

Remark 18. Since [ \begin{matrix}E_{11} & 0 & 0 \\ E_{21} & E_{22} & 0 \\ Γ_{11} & Γ_{12} & Γ_{14} \end{matrix} ] is nonsingular, it follows that

also [ \begin{matrix}Θ_{11} & Θ_{12} \\ Θ_{21} & Θ_{22} \end{matrix} ] is nonsingular.

Step 5: Perform an RQ decomposition (see [11]) of [ \begin{matrix}Θ_{11} & Θ_{12} & Φ_{15} \\ Θ_{21} & Θ_{22} & Φ_{25} \end{matrix} ]:

[ \begin{matrix}Θ_{11} & Θ_{12} & Θ_{13} & 0 & Φ_{15} & Φ_{16} \\ Θ_{21} & Θ_{22} & Θ_{23} & 0 & Φ_{25} & Φ_{26} \\ Θ_{31} & Θ_{32} & Θ_{33} & 0 & Φ_{35} & Φ_{36} \\ 0 & 0 & 0 & 0 & 0 & Σ_{4} \\ 0 & 0 & Σ_{5} & 0 & 0 & 0 \\ Λ_{1} & Λ_{2} & Λ_{3} & 0 & 0 & 0 \\ 0 & 0 & 0 & Iŝ_{4} & 0 & 0 \\ 0 & 0 & 0 & 0 & Ψ_{5} & Ψ_{6} \end{matrix} ] [ \begin{matrix}V_{11} & V_{12} & 0 & 0 & V_{15} & 0 \\ V_{21} & V_{22} & 0 & 0 & V_{25} & 0 \\ 0 & 0 & Is̃_{4} & 0 & 0 & 0 \\ 0 & 0 & 0 & Iŝ_{4} & 0 & 0 \\ V_{51} & V_{52} & 0 & 0 & V_{55} & 0 \\ 0 & 0 & 0 & 0 & 0 & I_{t_{6}} \end{matrix} ]

=:  [ \begin{matrix}& t_{1} & t_{2} & s̃_{4} & ŝ_{4} & n − r − t_{5} & t_{5} \\ t_{1} & Σ_{1} & 0 & Θ_{13} & 0 & 0 & Φ_{16} \\ t_{2} & Θ_{21} & Σ_{2} & Θ_{23} & 0 & 0 & Φ_{26} \\ t_{4} & Θ_{31} & Θ_{32} & Θ_{33} & 0 & Φ_{35} & Φ_{36} \\ t_{5} & 0 & 0 & 0 & 0 & 0 & Σ_{4} \\ s̃_{4} & 0 & 0 & Σ_{5} & 0 & 0 & 0 \\ t_{1} & Λ_{1} & Λ_{2} & Λ_{3} & 0 & Λ_{5} & 0 \\ ŝ_{4} & 0 & 0 & 0 & Iŝ_{4} & 0 & 0 \\ p & Ψ_{1} & Ψ_{2} & Ψ_{3} & 0 & Ψ_{5} & Ψ_{6} \end{matrix} ]

with Σ_{1} and Σ_{2} nonsingular.

Remark 19. It remains to determine G_{41}, G_{44} and F_{2} such that the matrix

[ 0 Φ_{35} ] + [ G_{41} G_{44} F_{2} ] [ \begin{matrix}0 & Λ_{5} \\ Iŝ_{4} & 0 \\ 0 & Ψ_{5} \end{matrix} ]

is nonsingular. Step 6: Set

z_{1} := rank(Φ_{35})

and perform a simultaneous row and column compression of Φ_{35}:

[ \begin{matrix}U_{6} \\ & I_{t_{1}} \\ & & Iŝ_{4} \\ & & & I_{p} \end{matrix} ] [ \begin{matrix}0 & Φ_{35} \\ 0 & Λ_{5} \\ Iŝ_{4} & 0 \\ 0 & Ψ_{5} \end{matrix} ] [ \begin{matrix}Iŝ_{4} \\ & V_{6} \end{matrix} ]

=:  [ \begin{matrix}& ŝ_{4} & n − r − t_{5} − z_{1} & z_{1} \\ z_{1} & 0 & 0 & Σ_{3} \\ t_{4} − z_{1} & 0 & 0 & 0 \\ t_{1} & 0 & Λ_{52} & Λ_{53} \\ ŝ_{4} & Iŝ_{4} & 0 & 0 \\ p & 0 & Ψ_{52} & Ψ_{53} \end{matrix} ].

Step 7: Set

z_{2} := rank(Λ_{52}), z_{3} := n − r − t_{5} − z_{1} − z_{2}

and perform a simultaneous row and column compression of Λ_{52}:

[ \begin{matrix}I_{z_{1}} \\ & I_{t_{4}−z_{1}} \\ & & U_{7} \\ & & & Iŝ_{4} \\ & & & & I_{p} \end{matrix} ] [ \begin{matrix}0 & 0 & Σ_{3} \\ 0 & 0 & 0 \\ 0 & Λ_{52} & Λ_{53} \\ Iŝ_{4} & 0 & 0 \\ 0 & Ψ_{52} & Ψ_{53} \end{matrix} ] [ \begin{matrix}Iŝ_{4} \\ & V_{7} \\ & & I_{z_{1}} \end{matrix} ]

=:  [ \begin{matrix}& ŝ_{4} & z_{3} & z_{2} & z_{1} \\ z_{1} & 0 & 0 & 0 & Σ_{3} \\ t_{4} − z_{1} & 0 & 0 & 0 & 0 \\ z_{2} & 0 & 0 & Σ_{7} & Λ_{54} \\ t_{1} − z_{2} & 0 & 0 & 0 & Λ_{64} \\ ŝ_{4} & Iŝ_{4} & 0 & 0 & 0 \\ p & 0 & Ψ_{52} & Ψ_{53} & Ψ_{54} \end{matrix} ]

with Σ_{7} nonsingular and Ψ_{52} of full column rank. Step 8: Perform a row compression of Ψ_{52}:

[ \begin{matrix}I_{z_{1}} \\ & I_{t_{4}−z_{1}} \\ & & I_{z_{2}} \\ & & & I_{t_{1}−z_{2}} \\ & & & & Iŝ_{4} \\ & & & & & U_{8} \end{matrix} ] [ \begin{matrix}0 & 0 & 0 & Σ_{3} \\ 0 & 0 & 0 & 0 \\ 0 & 0 & Σ_{7} & Λ_{54} \\ 0 & 0 & 0 & Λ_{64} \\ Iŝ_{4} & 0 & 0 & 0 \\ 0 & Ψ_{52} & Ψ_{53} & Ψ_{54} \end{matrix} ]

=:  [ \begin{matrix}& ŝ_{4} & z_{3} & z_{2} & z_{1} \\ z_{1} & 0 & 0 & 0 & Σ_{3} \\ t_{4} − z_{1} & 0 & 0 & 0 & 0 \\ z_{2} & 0 & 0 & Σ_{7} & Λ_{54} \\ t_{1} − z_{2} & 0 & 0 & 0 & Λ_{64} \\ ŝ_{4} & Iŝ_{4} & 0 & 0 & 0 \\ z_{3} & 0 & Σ_{8} & Ψ_{53} & Ψ_{54} \\ p − z_{3} & 0 & 0 & Ψ_{63} & Ψ_{64} \end{matrix} ]

with Σ_{8} nonsingular. Step 9: Since ŝ_{4} + z_{1} + z_{2} + z_{3} = t_{4}, choose

Z := [ \begin{matrix}& z_{2} & t_{1} − z_{2} & ŝ_{4} & z_{3} & p − z_{3} \\ z_{1} & 0 & 0 & 0 & 0 & 0 \\ t_{4} − z_{1} & Z_{21} & 0 & Z_{23} & Z_{24} & 0 \end{matrix} ]

with

[ Z_{21} Z_{23} Z_{24} ] = I_{t_{4}−z_{1}}.

Remark 20. With Z chosen as in Step 9, we have that the matrix

[ \begin{matrix}0 & 0 & 0 & Σ_{3} \\ 0 & 0 & 0 & 0 \end{matrix} ] + Z [ \begin{matrix}0 & 0 & Σ_{7} & Λ_{54} \\ 0 & 0 & 0 & Λ_{64} \\ Iŝ_{4} & 0 & 0 & 0 \\ 0 & Σ_{8} & Ψ_{53} & Ψ_{54} \\ 0 & 0 & Ψ_{63} & Ψ_{64} \end{matrix} ]

is nonsingular. Step 10: Perform the following partitioning:

U_{6}^{T} Z [ \begin{matrix}I_{z_{2}} \\ & I_{t_{1}−z_{2}} \\ & & Iŝ_{4} \\ & & & U_{8} \end{matrix} ] [ \begin{matrix}U_{7} \\ & Iŝ_{4} \\ & & I_{p} \end{matrix} ] =: [ \begin{matrix}t_{1} & ŝ_{4} & p \\ G_{41} & G_{44} & F_{2} \end{matrix} ]

and determine F, G by solving the linear systems

[ \begin{matrix}B_{31} & B_{32} \\ 0 & B_{42} \end{matrix} ] F = [ \begin{matrix}0 \\ F_{2} \end{matrix} ]

and

[ \begin{matrix}B_{31} & B_{32} \\ 0 & B_{42} \end{matrix} ] G [ \begin{matrix}0 & Π_{14} & Π_{15} \\ Γ_{21} & 0 & 0 \end{matrix} ] = [ \begin{matrix}0 & 0 & 0 \\ G_{41} & G_{44} & 0 \end{matrix} ]−[ \begin{matrix}0 & Θ_{34} & Θ_{35} \\ 0 & Θ_{44} & Θ_{45} \end{matrix} ] .

Input: Matrix

Φ = [ \begin{matrix}& μ_{1} & μ_{2} \\ τ_{1} & Φ_{1} & Φ_{2} \\ τ_{2} & Ψ_{1} & Ψ_{2} \end{matrix} ]

satisfying

rank [ Φ_{1} Φ_{2} ] = τ_{1}.

Output: Orthogonal matrices U_{1}, U_{2}, V_{1}, V_{2} such that Φ is transformed to the form (37). Step 1: Perform a row compression of Φ_{2}:

[ \begin{matrix}U_{1} \\ & I_{τ_{2}} \end{matrix} ] [ \begin{matrix}Φ_{1} & Φ_{2} \\ Ψ_{1} & Ψ_{2} \end{matrix} ] =:  [ \begin{matrix}& μ_{1} & μ_{2} \\ k_{1} & Φ_{11} & 0 \\ τ_{1} − k_{1} & Φ_{21} & Φ_{22} \\ τ_{2} & Ψ_{1} & Ψ_{2} \end{matrix} ]

with Φ_{22} of full row rank.

Step 2: Perform a row compression of [ \begin{matrix}Φ_{22} \\ Ψ_{2} \end{matrix} ]:

[ \begin{matrix}I_{k_{1}} \\ & U_{2} \end{matrix} ] [ \begin{matrix}Φ_{11} & 0 \\ Φ_{21} & Φ_{22} \\ Ψ_{1} & Ψ_{2} \end{matrix} ] =:  [ \begin{matrix}& μ_{1} & μ_{2} \\ k_{1} & Φ_{11} & 0 \\ k_{2} & Ψ_{21} & Σ_{2} \\ τ_{1} + τ_{2} − k_{1} − k_{2} & Ψ_{31} & 0 \end{matrix} ]

with Σ_{2} full row rank. Step 3: Perform a column compression of Φ_{11}:

[ \begin{matrix}Φ_{11} & 0 \\ Ψ_{21} & Σ_{2} \\ Ψ_{31} & 0 \end{matrix} ] [ \begin{matrix}V_{1} \\ & I_{μ_{2}} \end{matrix} ] =:  [ \begin{matrix}& k_{1} & μ_{1} − k_{1} & μ_{2} \\ k_{1} & Σ_{1} & 0 & 0 \\ k_{2} & Ψ_{21} & Ψ_{22} & Σ_{2} \\ τ_{1} + τ_{2} − k_{1} − k_{2} & Ψ_{31} & Ψ_{32} & 0 \end{matrix} ]

with Σ_{1} nonsingular. Step 4: Perform a column compression of Ψ_{32}:

[ \begin{matrix}Σ_{1} & 0 & 0 \\ Ψ_{21} & Ψ_{22} & Σ_{2} \\ Ψ_{31} & Ψ_{32} & 0 \end{matrix} ] [ \begin{matrix}I_{k_{1}} \\ & V_{2} \\ & & I_{μ_{2}} \end{matrix} ]

=:  [ \begin{matrix}& k_{1} & k_{3} & μ_{1} − k_{1} − k_{3} & μ_{2} \\ k_{1} & Σ_{1} & 0 & 0 & 0 \\ k_{2} & Ψ_{21} & Ψ_{22} & Ψ_{23} & Σ_{2} \\ τ_{1} + τ_{2} − k_{1} − k_{2} & Ψ_{31} & Σ_{3} & 0 & 0 \end{matrix} ]

with Σ_{3} of full column rank.

Appendix B–A list of subspaces.

Assume that matrices (E, A, B, C, Γ) are in the forms (7) and (13). Then

S_{eγ} =  [ \begin{matrix}t_{1} & 0 \\ t_{2} & 0 \\ t_{3} & 0 \\ s̃_{4} & 0 \\ s̃_{5} & Is̃_{5} \end{matrix} ],

T_{eb} =  [ \begin{matrix}t_{1} & 0 \\ t_{2} & 0 \\ t_{3} & 0 \\ t_{4} & 0 \\ t_{5} & I_{t_{5}} \end{matrix} ],

S̃_{eb} =  [ \begin{matrix}t_{1} & 0 & 0 & 0 \\ t_{2} & 0 & 0 & 0 \\ t_{3} & I_{t_{3}} & 0 & 0 \\ s̃_{4} & 0 & Is̃_{4} & 0 \\ s̃_{5} & 0 & 0 & Is̃_{5} \end{matrix} ],

T̃_{eγ} =  [ \begin{matrix}t_{1} & I_{t_{1}} & 0 \\ t_{2} & 0 & 0 & 0 \\ t_{3} & 0 & 0 & 0 \\ t_{4} & 0 & I_{t_{4}} & 0 \\ t_{5} & 0 & 0 & I_{t_{5}} \end{matrix} ],

T̃_{eγ}^{0} =  [ \begin{matrix}t_{1} & I_{t_{1}} & 0 & 0 & 0 \\ t_{2} & 0 & 0 & 0 & 0 \\ t_{3} & 0 & 0 & 0 & 0 \\ t_{4} & 0 & I_{t_{4}} & 0 & 0 \\ t_{5} & 0 & 0 & I_{t_{5}} & 0 \\ p & 0 & 0 & 0 & I_{p} \end{matrix} ].