Regularizing algorithm for mixed matrix pencils

Van Dooren [7] gave an algorithm that for each pair (A, B) of complex matrices of the same size constructs its regularizing decomposition; that is, it constructs a matrix pair that is simultaneously equivalent to (A, B) and has the form

(A₁,B₁) ⊕ … ⊕ (A_t,B_t) ⊕ (A,B)

in which (A,B) is a pair of nonsingular matrices and each other summand has one of the forms:

$\begin{matrix} \begin{matrix} \begin{matrix} (F_{n}), G_{n}), & (F_{n}^{T}, G_{n}^{T}), \end{matrix} & (I_{n}, J_{n} (0)), \end{matrix} & (J_{n} (0), I_{n}), \end{matrix}$ $$\begin{array}{} \displaystyle ({F_n},{G_n}),\quad (F_n^T,G_n^T),\quad ({I_n},{J_n}(0)),\quad ({J_n}(0),{I_n}), \end{array}$$

where J_n(0) is the singular Jordan block and

$F_{n} : = [\begin{matrix} 0 & 0 \\ 1 & ⋱ \\ ⋱ & 0 \\ 0 & 1 \end{matrix}], G_{n} : = [\begin{matrix} 1 & 0 \\ 0 & ⋱ \\ ⋱ & 1 \\ 0 & 0 \end{matrix}]$ $$\begin{array}{} \displaystyle {F_n}: = \left[ {\begin{array}{*{20}{c}} 0&{}&0\\ 1& \ddots &{}\\ {}& \ddots &0\\ 0&{}&1 \end{array}} \right],\quad \quad {G_n}: = \left[ {\begin{array}{*{20}{c}} 1&{}&0\\ 0& \ddots &{}\\ {}& \ddots &1\\ 0&{}&0 \end{array}} \right] \end{array}$$ are n × (n − 1) matrices; n ≥ 1. Note that (F₁,G₁) = (0₁₀,0₁₀); we denote by 0_mn the zero matrix of size m × n, where m,n ∈ {0,1,2,...}. The algorithm uses only unitary transformations, which improves its computational stability.

We extend Van Dooren’s algorithm to square complex matrices up to consimilarity transformations $A \mapsto {SA \bar{S}}^{- 1}$ $\begin{array}{} \displaystyle A \mapsto SA{\bar S^{ - 1}} \end{array}$ and to pairs of m × n matrices up to transformations $(A, B) \mapsto (S A R, S B \bar{R})$ $\begin{array}{} \displaystyle (A,B) \mapsto (SAR,SB\bar R) \end{array}$, in which S and R are nonsingular matrices.

A regularizing algorithm for matrices of undirected cycles of linear mappings was constructed by Sergeichuk [6] and, independently, by Varga [8]. A regularizing algorithm for matrices under congruence was constructed by Horn and Sergeichuk [5].

All matrices that we consider are complex matrices.

Regularizing unitary algorithm for matrices under consimilarity

Two matrices A and B are consimilar if there exists a nonsingular matrix S such that $S A {\bar{S}}^{- 1} = B$ $\begin{array}{} \displaystyle SA{\bar S^{ - 1}} = B \end{array}$. Two matrices are consimilar if and only if they represent the same semilinear operator, but in different bases. Recall that a mapping 𝒜 : U → V between complex vector spaces is semilinear if

$A (a u_{1} + b u_{2}) = \bar{a} A u_{1} + \bar{b} A u_{2}$ $$\begin{array}{} \displaystyle {\cal A}(a{u_1} + b{u_2}) = \bar a{\cal A}{u_1} + \bar b{\cal A}{u_2} \end{array}$$

for all a,b ∈ ℂ and u₁,u₂ ∈ U.

The canonical form of a matrix under consimilarity is the following (see [3] or [4]):

Each square complex matrix is consimilar to a direct sum, uniquely determined up to permutation of direct summands, of matrices of the following types:

a Jordan block J_k(λ) with λ ≥ 0, and

$[\begin{matrix} 0 & 1 \\ μ & 0 \end{matrix}]$ $\begin{array}{} \displaystyle \left[ {\begin{array}{*{20}{c}} 0&1\\ \mu &0 \end{array}} \right] \end{array}$with μ ∉ ℝ or μ < 0.

Thus, each square matrix A is consimilar to a direct sum

$J_{n_{1}} (0) \oplus \dots \oplus J_{n_{k}} (0) \oplus \underline{A},$ $$\begin{array}{} J_{n_1}(0)\oplus\dots\oplus J_{n_k}(0)\oplus \underline A, \end{array}$$

in which A is nonsingular and is determined up to consimilarity; the other summands are uniquely determined up to permutation. This sum is called a regularizing decomposition of A. The following algorithm admits to construct a regularizing decomposition using only unitary transformations.

Algorithm 1

Let A be a singular n × n matrix. By unitary transformations of rows, we reduce it to the form

$\begin{matrix} S_{1} A = (\begin{matrix} 0_{r_{1} n} \\ A^{'} \end{matrix}), S_{1} i s u n i t a r y, \end{matrix}$ $$\begin{array}{} \displaystyle {S_1}A = \left[ {\begin{array}{*{20}{c}} {{0_{{r_1}n}}}\\ {A'} \end{array}} \right],\qquad {S_1}\; is\; unitary, \end{array}$$

in which the rows of A′ are linearly independent. Then we make the coninverse transformations of columns and obtain

$S_{1} A {\bar{S_{1}}}^{- 1} = [\begin{matrix} 0_{r_{1}} & 0 \\ ⋆ & A_{1} \end{matrix}]$ $$\begin{array}{} \displaystyle {S_1}A{\overline {{S_1}} ^{ - 1}} = \left[ {\begin{array}{*{20}{c}} {{0_{{r_1}}}}&0\\ \star &{{A_1}} \end{array}} \right] \end{array}$$

We apply the same procedure to A₁and obtain

$S_{2} A_{1} {\bar{S_{2}}}^{- 1} = [\begin{matrix} 0_{r_{2}} & 0 \\ ⋆ & A_{2} \end{matrix}], S_{2} i s u n i t a r y$ $$\begin{array}{} \displaystyle {S_2}{A_1}{\overline {{S_2}} ^{ - 1}} = \left[ {\begin{array}{*{20}{c}} {{0_{{r_2}}}}&0\\ \star &{{A_2}} \end{array}} \right],\qquad {S_2}\;is\; unitary, \end{array}$$

in which the rows of [*A₂] are linearly independent.

We repeat this procedure until we obtain

$\begin{matrix} S_{t} A_{t - 1} {\bar{S_{t}}}^{- 1} = (\begin{matrix} 0_{r_{t}} & 0 \\ ⋆ & A_{t} \end{matrix}), S_{t} i s u n i t a r y \end{matrix}$ $$\begin{array}{}{S}_tA_{t-1}\bar{S_t}^{-1}= \begin{bmatrix} 0_{r_t} & 0 \\ \star & A_t \\ \end{bmatrix}, \qquad S_t \;is\; unitary, \end{array}$$

in which A_t is nonsingular. The result of the algorithm is the sequence r₁,r₂,...,r_t,A_t.

For a matrix A and a nonnegative integer n, we write

$A^{(n)} : = {\begin{matrix} 0_{00}, & i f n = 0; \\ A \oplus \dots \oplus A (n summands), & i f n \geq 1 . \end{matrix}$ $$\begin{array}{} \displaystyle {A^{(n)}}: = \{ \begin{array}{*{20}{c}} {{0_{00}},} \hfill & {{\rm{if }}n = 0;} \hfill \\ {A \oplus \ldots \oplus A\,(n\; {\rm{summands}}),} \hfill & {{\rm{if }}n \ge 1.} \hfill \\ \end{array} \end{array}$$

Theorem 1

Let r₁,r₂,...,r_t,A_t be the sequence obtained by applying Algorithm 1 to a square complex matrix A. Then

r₁ ≥ r₂ ≥ ... ≥ r_t

and A is consimilar to

$J_{1}^{(r_{1} - r_{2})} \oplus J_{2}^{(r_{2} - r_{3})} \oplus \dots \oplus J_{t - 1}^{(r_{t - 1} - r_{t})} \oplus J_{t}^{(r_{t})} \oplus A_{t}$ $$\begin{array}{} \displaystyle {J_1}^{({r_1} - {r_2})} \oplus {J_2}^{({r_2} - {r_3})} \oplus \cdots \oplus J_{t - 1}^{({r_{t - 1}} - {r_t})} \oplus J_t^{({r_t})} \oplus {A_t} \end{array}$$(1)

in which J_k := J_k(0) and A_t is determined by A up to consimilarity and the other summands are uniquely determined.

Proof. Let 𝒜 : V → V be a semilinear operator whose matrix in some basis is A. Let W := 𝒜 V be the image of 𝒜. Then the matrix of the restriction 𝒜₁ : W → W of 𝒜 on W is A₁. Applying Algorithm 1 to A₁, we get the sequence r₂,...,r_t,A_t. Reasoning by induction on the length t of the algorithm, we suppose that r₂ ≥ r₃ ≥ ··· ≥ r_t and that A₁ is consimilar to

$J_{1}^{(r_{2} - r_{3})} \oplus \dots \oplus J_{t - 2}^{(r_{t - 1} - r_{t})} \oplus J_{t - 1}^{(r_{t})} \oplus A_{t} .$ $$\begin{array}{} \displaystyle {J_1}^{({r_2} - {r_3})} \oplus \cdots \oplus J_{t - 2}^{({r_{t - 1}} - {r_t})} \oplus J_{t - 1}^{({r_t})} \oplus {A_t}. \end{array}$$(2)

Thus, 𝒜₁ : W → W is given by the matrix (2) in some basis of W.

The direct sum (2) defines the decomposition of W into the direct sum of invariant subspaces

$W = (W_{21} \oplus \dots \oplus W_{2, r_{2} - r_{3}}) \oplus \dots \oplus (W_{t 1} \oplus \dots \oplus W_{t r_{t}}) \oplus W^{'} .$ $$\begin{array}{} \displaystyle W = ({W_{21}} \oplus \ldots \oplus {W_{2,{r_2} - {r_3}}}) \oplus \cdots \oplus ({W_{t1}} \oplus \ldots \oplus {W_{t{r_t}}}) \oplus W'. \end{array}$$

Each W_pq is generated by some basis vectors e_pq2, e_pq3,...,e_pqp such that

$A : e_{p q 2} \mapsto e_{p q 3} \mapsto \dots \mapsto e_{p q p} \mapsto 0.$ $$\begin{array}{} \displaystyle {\cal A}:\;{e_{pq2}} \mapsto {e_{pq3}} \mapsto \cdots \mapsto {e_{pqp}} \mapsto 0. \end{array}$$

For each W_pq, we choose e_pq1 ∈ V such that 𝒜 e_pq1 = e_pq2. The set

${e_{p q p} | 2 \leq p \leq t, 1 \leq q \leq r_{p} - r_{p + 1}} (r_{t + 1} : = 0)$ $$\begin{array}{} \displaystyle \{ {e_{pqp}}{\mkern 1mu} |{\mkern 1mu} 2 \le p \le t,\;1 \le q \le {r_p} - {r_{p + 1}}\} \quad ({r_{t + 1}}: = 0) \end{array}$$

consists of r₂ basis vectors belonging to the kernel of 𝒜; we supplement this set to a basis of the kernel of 𝒜 by some vectors e₁₁₁,...,e_{1_,r1−r2,1}.

The set of vectors e_pqs supplemented by the vectors of some basis of W′ is a basis of V . The matrix of 𝒜 in this basis has the form (1) because

$A : e_{p q 1} \mapsto e_{p q 2} \mapsto e_{p q 3} \mapsto \dots \mapsto e_{p q p} \mapsto 0$ $$\begin{array}{} \displaystyle {\cal A}:\;{e_{pq1}} \mapsto {e_{pq2}} \mapsto {e_{pq3}} \mapsto \cdots \mapsto {e_{pqp}} \mapsto 0 \end{array}$$

for all p = 1,...,t and q = 1,...,r_p − r_p+1. This completes the proof of Theorem 1.

Example 1

Let a square matrix A define a semilinear operator 𝒜 : V → V and let the singular part of its regularizing decomposition be J₂ ⊕ J₃ ⊕ J₄. This means that V possesses a set of linear independent vectors forming the Jordan chains

$\begin{matrix} A : & e_{1} \mapsto e_{2} \mapsto e_{3} \mapsto e_{4} \mapsto 0 \\ f_{1} \mapsto f_{2} \mapsto f_{3} \mapsto 0 \\ g_{1} \mapsto g_{2} \mapsto 0 \end{matrix}$ $$\begin{array}{} \displaystyle \begin{array}{*{20}{c}} {A:} \hfill & {{e_1} \mapsto {e_2} \mapsto {e_3} \mapsto {e_4} \mapsto 0} \hfill & {} \hfill \\ {} \hfill & {{f_1} \mapsto {f_2} \mapsto {f_3} \mapsto 0} \hfill & {} \hfill \\ {} \hfill & {{g_1} \mapsto {g_2} \mapsto 0} \hfill & {} \hfill \\ \end{array} \end{array}$$(3)

Applying the first step of Algorithm 1, we get A₁whose singular part corresponds to the chains

$\begin{matrix} A : & e_{2} \mapsto e_{3} \mapsto e_{4} \mapsto 0 \\ f_{3} \mapsto f_{3} \mapsto 0 \\ g_{2} \mapsto 0 \end{matrix}$ $$\begin{array}{} \displaystyle \begin{array}{*{20}{c}} {A:} \hfill & {{e_2} \mapsto {e_3} \mapsto {e_4} \mapsto 0} \hfill & {} \hfill \\ {} \hfill & {{f_3} \mapsto {f_3} \mapsto 0} \hfill & {} \hfill \\ {} \hfill & {{g_2} \mapsto 0} \hfill & {} \hfill \\ \end{array} \end{array}$$

On the second step, we delete e₂, f₂,g₂and so on. Thus, r_i is the number of vectors in the ith column of (3): r₁ = 3, r₂ = 3, r₃ = 2,r₄ = 1. We get the singular part of regularizing decomposition of A:

$J_{1}^{(r_{1} - r_{2})} \oplus \dots \oplus J_{t - 1}^{(r_{t - 1} - r_{t})} \oplus J_{t}^{(r_{t})} = J_{1}^{(3 - 3)} \oplus J_{2}^{(3 - 2)} \oplus J_{3}^{(2 - 1)} \oplus J_{4}^{(1)} = J_{2} \oplus J_{3} \oplus J_{4} .$ $$\begin{array}{} \displaystyle {J_1}^{({r_1} - {r_2})} \oplus \cdots \oplus J_{t - 1}^{({r_{t - 1}} - {r_t})} \oplus J_t^{({r_t})} = {J_1}^{(3 - 3)} \oplus {J_2}^{(3 - 2)} \oplus J_3^{(2 - 1)} \oplus J_4^{(1)} = {J_2} \oplus {J_3} \oplus {J_4}. \end{array}$$

In particular, if

(4)

then we can apply Algorithm 1 using only transformations of permutational similarity and obtain

(all unspecified blocks are zero), which is the Weyr canonical form of (4), see [4].

Regularizing unitary algorithm for matrix pairs under mixed equivalence

We say that pairs of m × n matrices (A,B) and (A′,B′) are mixed equivalent if there exist nonsingular S and R such that

$(S A R, S B \bar{R}) = (A^{'}, B^{'}) .$ $$\begin{array}{} \displaystyle (SAR,SB\bar R) = (A',B'). \end{array}$$

The direct sum of matrix pairs (A,B) and (C,D) is defined as follows:

$(A, B) \oplus (C, D) = ([\begin{matrix} A & 0 \\ 0 & C \end{matrix}], [\begin{matrix} B & 0 \\ 0 & D \end{matrix}]) .$ $$\begin{array}{} \displaystyle (A,B) \oplus (C,D) = \left( {\left[ {\begin{array}{*{20}{c}} A&0\\ 0&C \end{array}} \right],\:\left[ {\begin{array}{*{20}{c}} B&0\\ 0&D \end{array}} \right]} \right). \end{array}$$

The canonical form of a matrix pair under mixed equivalence was obtained by Djoković [2] (his result was extended to undirected cycles of linear and semilinear mappings in [1]):

Each pair (A,B) of matrices of the same size is mixed equivalent to a direct sum, determined uniquely up to permutation of summands, of pairs of the following types:

$(I_{n}, J_{n} (λ)), (I_{n}, (\begin{matrix} 0 & 1 \\ μ & 0 \end{matrix})), (J_{n} (0), I_{n}), (F_{n}, G_{n}), (F_{n}^{T}, G_{n}^{T}),$ $$\begin{array}{} \displaystyle ({I_n},{J_n}(\lambda )),\,({I_n},(\begin{array}{*{20}{c}} 0 & 1 \\ \mu & 0 \\ \end{array})),({J_n}(0),{I_n}),({F_n},{G_n}),\,(F_n^T,G_n^T), \end{array}$$

in which λ ≥ 0 and μ ∉ ℝ or μ < 0.

Thus, (A,B) is mixed equivalent to a direct sum of a pair (A,B) of nonsingular matrices and summands of the types:

$(I_{n}, J_{n} (0)), (J_{n} (0), I_{n}), (F_{n}, G_{n}), (F_{n}^{T}, G_{n}^{T}),$ $$\begin{array}{} \displaystyle ({I_n},{J_n}(0)),\,({J_n}(0),{I_n}),({F_n},{G_n}),\,(F_n^T,G_n^T), \end{array}$$

in which (A,B) is determined up to mixed equivalence and the other summands are uniquely determined up to permutation. This sum is called a regularizing decomposition of (A,B). The following algorithm admits to construct a regularizing decomposition using only unitary transformations.

Algorithm 2

Let (A,B) be a pair of matrices of the same size in which the rows of A are linearly dependent. By unitary transformations of rows, we reduce A to the form

$S_{1} A = [\begin{matrix} 0 \\ A^{'} \end{matrix}], S_{1} i s u n i t a r y,$ $$\begin{array}{} \displaystyle {S_1}A = \left[ {\begin{array}{*{20}{c}} 0\\ {A'} \end{array}} \right],\quad \quad {S_1}\;is\; unitary, \end{array}$$

in which the rows of A′ are linearly independent. These transformations change B:

$S_{1} B = [\begin{matrix} B^{'} \\ B^{″} \end{matrix}] .$ $$\begin{array}{} \displaystyle {S_1}B = \left[ {\begin{array}{*{20}{c}} {B'} \\ {B''} \\ \end{array}} \right]. \end{array}$$

By unitary transformations of columns, we reduce B′ to the form $[B_{1^{'}} 0]$ $\begin{array}{} \displaystyle [{B'_1}0] \end{array}$in which the columns of $B_{1}^{'}$ $\begin{array}{} \displaystyle {B'_1} \end{array}$are linearly independent, and obtain

$B R_{1} = [\begin{matrix} B_{1}^{'} & 0 \\ ⋆ & B_{1} \end{matrix}], R_{1} i s u n i t a r y .$ $$\begin{array}{} \displaystyle B{R_1} = \left[ {\begin{array}{*{20}{c}} {B_1^\prime }&0\\ \star &{{B_1}} \end{array}} \right],\quad \quad {R_1}\;is\; unitary. \end{array}$$

These transformations change A:

$S_{1} A \bar{R_{1}} = [\begin{matrix} 0_{k_{1} l_{1}} & 0 \\ ⋆ & A_{1} \end{matrix}] .$ $$\begin{array}{} \displaystyle {S_1}A\overline {{R_1}} = \left[ {\begin{array}{*{20}{c}} {{0_{{k_1}{l_1}}}}&0\\ \star &{{A_1}} \end{array}} \right]. \end{array}$$

We apply the same procedure to (A₁,B₁) and obtain

$(S_{2} A_{1} \bar{R_{2}}, S_{2} B_{1} R_{2}) = ([\begin{matrix} 0_{k_{2} l_{2}} & 0 \\ ⋆ & A_{2} \end{matrix}], [\begin{matrix} B_{2^{'}} & 0 \\ ⋆ & B_{2} \end{matrix}]),$ $$\begin{array}{} \displaystyle ({S_2}{A_1}\overline {{R_2}} ,{S_2}{B_1}{R_2}) = \left( {\left[ {\begin{array}{*{20}{c}} {{0_{{k_2}{l_2}}}}&0\\ \star &{{A_2}} \end{array}} \right],\left[ {\begin{array}{*{20}{c}} {{B_{2'}}}&0\\ \star &{{B_2}} \end{array}} \right]} \right), \end{array}$$

in which the rows of [* A₂] are linearly independent, S₂and R₂are unitary, and the columns of $B_{2}^{'}$ $\begin{array}{} \displaystyle B_2^\prime \end{array}$are linearly independent.

We repeat this procedure until we obtain

$(S_{t} A_{t - 1} {\bar{R}}_{t}, S_{t} B_{t - 1} R_{t}) = ([\begin{matrix} 0_{k_{t} l_{t}} & 0 \\ ⋆ & A_{t} \end{matrix}], [\begin{matrix} B_{t}^{'} & 0 \\ ⋆ & B_{t} \end{matrix}]),$ $$\begin{array}{} \displaystyle ({S_t}{A_{t - 1}}{\bar R_t},{S_t}{B_{t - 1}}{R_t}) = \left( {\left[ {\begin{array}{*{20}{c}} {{0_{{k_t}{l_t}}}}&0\\ \star &{{A_t}} \end{array}} \right],\left[ {\begin{array}{*{20}{c}} {B_t^\prime }&0\\ \star &{{B_t}} \end{array}} \right]} \right), \end{array}$$

in which the rows of A_t are linearly independent. The result of the algorithm is the sequence

(k₁,l₁), (k₂,l₂), ... (k_t,l_t), (A_t,B_t).

For a matrix pair (A,B) and a nonnegative integer n, we write

${(A, B)}^{(n)} : = {\begin{matrix} (0_{00}, 0_{00}), & if n = 0; \\ (A, B) \oplus \dots \oplus (A, B) (n summands), & if n \geq 1. \end{matrix}$ $$\begin{array}{} \displaystyle {(A,B)^{(n)}}: = \{ \begin{array}{*{20}{c}} {({0_{00}},{0_{00}}),} \hfill & {{\rm{if }}n = 0;} \hfill \\ {(A,B) \oplus \ldots \oplus (A,B)(n\; \rm{summands}),} \hfill & {{\rm{if }}n \ge 1.} \hfill \\ \end{array} \end{array}$$

Theorem 2

Let (A,B) be a pair of complex matrices of the same size. Let us apply Algorithm 2 to (A,B) and obtain

(k₁,l₁), (k₂,l₂), ..., (k_t,l_t), (A_t,B_t).

Let us apply Algorithm 2 to $(\underline{A}, \underline{B}) : = (B_{t}^{T}, A_{t}^{T})$ $\begin{array}{} \displaystyle (,): = (B_t^T,A_t^T) \end{array}$and obtain

(k₁,l₁), (k₂,l₂), ..., (k_t,l_t), (A_t,B_t).

Then (A,B) is mixed equivalent to

$\begin{matrix} (F_{1}, G_{1})^{(k_{1} - l_{1})} \oplus \cdot \cdot \cdot \oplus (F_{t - 1}, G_{t - 1})^{(k_{t - 1} - l_{t - 1})} \oplus (F_{t}, G_{t})^{(k_{t} - l_{t})} \\ \oplus (J_{1}, I_{I})^{(l_{1} - k_{2})} \oplus \cdot \cdot \cdot \oplus (J_{t - 1}, I_{t - 1})^{(l_{t - 1} - k_{t})} \oplus (J_{t}, I_{t})^{(l_{t})} \\ \oplus (F_{1}^{T}, G_{1}^{T})^{({\underline{k}}_{1} - {\underline{l}}_{1})} \oplus \cdot \cdot \cdot \oplus {(F_{\underline{t} - 1}^{T}, G_{\underline{t} - 1}^{T})}^{({\underline{k}}_{\underline{t} - 1} - {\underline{l}}_{\underline{t} - 1})} \oplus {(F_{\underline{t}}^{T}, G_{\underline{t}}^{T})}^{(k_{\underline{t}} - l_{\underline{t}})} \\ \oplus (I_{1}, J_{1})^{({\underline{l}}_{1} - {\underline{k}}_{2})} \oplus \cdot \cdot \cdot \oplus (I_{\underline{t} - 1}, J_{\underline{t} - 1})^{({\underline{l}}_{\underline{t} - 1} - {\underline{k}}_{\underline{t}})} \oplus (I_{\underline{t}}, J_{\underline{t}})^{(l_{\underline{t}})} \\ \oplus ({\underline{B}}_{\underline{t}}^{T}, {\underline{A}}_{\underline{t}}^{T}) \end{matrix}$ $$\begin{array}{} \displaystyle \begin{array}{*{20}{l}} {\begin{array}{*{20}{l}} {{{\left( {{F_1},{G_1}} \right)}^{\left( {{k_1} - {l_1}} \right)}} \oplus \cdot \cdot \cdot \oplus {{\left( {{F_{t - 1}},{G_{t - 1}}} \right)}^{\left( {{k_{t - 1}} - {l_{t - 1}}} \right)}} \oplus {{\left( {{F_t},{G_t}} \right)}^{\left( {{k_t} - {l_t}} \right)}}}\\ { \oplus {{\left( {{J_1},{I_1}} \right)}^{\left( {{l_l} - {k_2}} \right)}} \oplus \cdot \cdot \cdot \oplus {{\left( {{J_{t - 1}},{I_{t - 1}}} \right)}^{\left( {{l_{t - 1}} - {k_t}} \right)}} \oplus {{\left( {{J_t},{I_t}} \right)}^{{l_t}}}}\\ { \oplus {{\left( {{\rm{ }}F_1^T,{\rm{ }}G_1^T} \right)}^{\left( {{k_1} - {l_1}} \right)}} \oplus \cdot \cdot \cdot \oplus {{\left( {{\rm{ }}F_{ - 1}^T,{\rm{ }}G_{ - 1}^T} \right)}^{\left( {{{}_{ - 1}} - {l_{ - 1}}} \right)}} \oplus {{\left( {{\rm{ }}F_{}^T,{\rm{ }}G_{}^T} \right)}^{\left( {{k_{}} - {l_{}}} \right)}}} \end{array}}\\ { \oplus {{\left( {{I_1},{J_1}} \right)}^{\left( {{{}_1} - {{}_2}} \right)}} \oplus \cdot \cdot \cdot \oplus {{\left( {{I_{ - 1}},{J_{ - 1}}} \right)}^{\left( {{{}_{ - 1}} - {{}_{}}} \right)}} \oplus {{\left( {{I_{}},{J_{}}} \right)}^{\left( {{{}_{}}} \right)}}}\\ { \oplus \left( {_{}^T,_{}^T} \right)} \end{array} \end{array}$$

(all exponents in parentheses are nonnegative). The pair $({\underline{B}}_{\underline{t}}^{T}, {\underline{A}}_{\underline{t}}^{T})$ $\begin{array}{} \displaystyle \left( {_{}^T,_{}^T} \right) \end{array}$consists of nonsingular matrices; it is determined up to mixed equivalence. The other summands are uniquely determined by (A,B).

The rows of A_t in Theorem 2 are linearly independent, and so the columns of $\underline{B} : = A_{t}^{T}$ $\begin{array}{} \displaystyle : = A_t^T \end{array}$ are linearly independent. As follows from Algorithm 2, the columns of B_t are linearly independent too. Since the rows of A_t are linearly independent and the columns of B_t are linearly independent, we have that the matrices in (A_t,B_t) have the same size, these matrices are square, and so they are nonsingular. The pairs $(I_{n}, J_{n}^{T})$ $\begin{array}{} \displaystyle (I_n,J_n^T) \end{array}$ and $(G_{n}^{T}, F_{n}^{T})$ $\begin{array}{} \displaystyle (G_n^T,F_n^T) \end{array}$ are permutationally equivalent to (I_n,J_n) and $(F_{n}^{T}, G_{n}^{T})$ $\begin{array}{} \displaystyle (F_n^T,G_n^T) \end{array}$. Therefore, the following lemma implies Theorem 2.

Lemma 1

Let (A,B) be a pair of complex matrices of the same size. Let us apply Algorithm 2 to (A,B) and obtain

(k₁,l₁), (k₂,l₂), ..., (k_t,l_t), (A_t,B_t).

Then (A,B) is mixed equivalent to

$\begin{matrix} {(F_{1}, G_{1})}^{(k_{1} - l_{1})} \oplus \dots \oplus {(F_{t - 1}, G_{t - 1})}^{(k_{t - 1} - l_{t - 1})} \oplus {(F_{t}, G_{t})}^{(k_{t} - l_{t})} \\ \oplus {(J_{1}, I_{1})}^{(l_{1} - k_{2})} \oplus \dots \oplus {(J_{t - 1}, I_{t - 1})}^{(l_{t - 1} - k_{t})} \\ \oplus {(J_{t}, I_{t})}^{(l_{t})} \oplus (A_{t}, B_{t}) \end{matrix}$ $$\begin{array}{} \displaystyle \begin{array}{*{20}{l}} {{{({F_1},{G_1})}^{({k_1} - {l_1})}} \oplus \ldots \oplus {{({F_{t - 1}},{G_{t - 1}})}^{({k_{t - 1}} - {l_{t - 1}})}} \oplus {{({F_t},{G_t})}^{({k_t} - {l_t})}}}\\ { \oplus {{({J_1},{I_1})}^{({l_1} - {k_2})}} \oplus \ldots \oplus {{({J_{t - 1}},{I_{t - 1}})}^{({l_{t - 1}} - {k_t})}}}\\ { \oplus {{({J_t},{I_t})}^{({l_t})}} \oplus ({A_t},{B_t})} \end{array} \end{array}$$(5)

(all exponents in parentheses are nonnegative). The rows of A_t are linearly independent. The pair (A_t,B_t) is determined up to mixed equivalence. The other summands are uniquely determined by (A,B).

Proof. We write

(A,B) ⇒ (k₁,l₁,(A₁,B₁))

if k₁,l₁, (A₁,B₁) are obtained from (A,B) in the first step of Algorithm 2.

First we prove two statements.

Statement 1: If

$\begin{matrix} (A, B) \Rightarrow (k_{1}, l_{1}, (A_{1}, B_{1})), \\ (\tilde{A}, \tilde{B}) \Rightarrow ({\tilde{k}}_{1}, {\tilde{l}}_{1}, ({\tilde{A}}_{1}, {\tilde{B}}_{1})), \end{matrix}$ $$\begin{array}{} \displaystyle \begin{array}{*{20}{c}} {\left( {A,B} \right) \Rightarrow \left( {{k_1},{l_1},\left( {{A_1},{B_1}} \right)} \right),}\\ {\left( {\widetilde A,\widetilde B} \right) \Rightarrow \left( {{{\widetilde k}_1},{{\widetilde l}_1},\left( {{{\widetilde A}_1},{{\widetilde B}_1}} \right)} \right),} \end{array} \end{array}$$(6)

and (A,B) is mixed equivalent to $(\tilde{A}, \tilde{B})$ $\begin{array}{} \displaystyle \left( {\widetilde A,\widetilde B} \right) \end{array}$, then $k_{1} = {\tilde{k}}_{1}, l_{1} = {\tilde{l}}_{1}$ $\begin{array}{} \displaystyle {k_1} = {\tilde k_1},{l_1} = {\tilde l_1} \end{array}$and (A₁, B₁) is mixed equivalent to $({\tilde{A}}_{1}, {\tilde{B}}_{1})$ $\begin{array}{} \displaystyle \left( {{{\widetilde A}_1},{{\widetilde B}_1}} \right) \end{array}$.

Let m be the number of rows in A. Then

$k_{1} = m - rank A = m - rank \tilde{A} = {\tilde{k}}_{1} .$ $$\begin{array}{} \displaystyle {k_1} = m - {\rm{rank }}A = m - {\rm{rank }}\tilde A = {\tilde k_1}. \end{array}$$

Since (A,B) and $(\tilde{A}, \tilde{B})$ $\begin{array}{} \displaystyle \left( {\widetilde A,\widetilde B} \right) \end{array}$ are mixed equivalent and they are reduced by mixed equivalence transformations to

$([\begin{matrix} 0_{k_{1} l_{1}} & 0 \\ X & A_{1} \end{matrix}], [\begin{matrix} B_{1}^{'} & 0 \\ Y & B_{1} \end{matrix}]), ([\begin{matrix} 0_{k_{\underset{~}{1}} {\tilde{l}}_{1}} & 0 \\ X & {\tilde{A}}_{1} \end{matrix}], [\begin{matrix} {\tilde{B}}_{1}^{'} & 0 \\ \tilde{Y} & {\tilde{B}}_{1} \end{matrix}]),$ $$\begin{array}{} \displaystyle (\left[ {\begin{array}{*{20}{c}} {{0_{{k_1}{l_1}}}} & 0 \\ X & {{A_1}} \\ \end{array}} \right],[\left[ {\begin{array}{*{20}{c}} {{{B'}_1}} & 0 \\ Y & {{B_1}} \\ \end{array}} \right]]),\quad (\left[ {\begin{array}{*{20}{c}} {{0_{{k_1}{{\tilde l}_1}}}} & 0 \\ {\tilde X} & {{{\tilde A}_1}} \\ \end{array}} \right],\left[ {\begin{array}{*{20}{c}} {{{\tilde B'}_1}} & 0 \\ {\tilde Y} & {{{\tilde B}_1}} \\ \end{array}} \right]), \end{array}$$(7)

there exist nonsingular S and R such that

$(S [\begin{matrix} 0_{k_{1} l_{1}} & 0 \\ X & A_{1} \end{matrix}], S [\begin{matrix} B_{1}^{'} & 0 \\ Y & B_{1} \end{matrix}]) = ([\begin{matrix} 0_{k_{\underset{~}{1}} {\tilde{l}}_{1}} & 0 \\ X & {\tilde{A}}_{1} \end{matrix}], [\begin{matrix} {\tilde{B}}_{1}^{'} & 0 \\ \tilde{Y} & {\tilde{B}}_{1} \end{matrix}] \begin{matrix} \tilde{R} \end{matrix}),$ $$\begin{array}{} \left(S \begin{bmatrix} 0_{k_1l_1} & 0 \\ X & A_{1} \\ \end{bmatrix},\ S \begin{bmatrix} B_1' & 0 \\ Y & B_{1} \\ \end{bmatrix} \right) =\left( \begin{bmatrix} 0_{{k}_1\tilde{l}_1} & 0 \\ \widetilde{X} & \widetilde{A}_1 \\ \end{bmatrix} R,\ \begin{bmatrix} \widetilde{B}_1' & 0 \\ \widetilde{Y} & \widetilde{B}_1 \\ \end{bmatrix}\bar{R} \right). \end{array}$$(8)

Equating the first matrices of these pairs, we find that S has the form

$S = [\begin{matrix} S_{11} & 0 \\ S_{21} & S_{22} \end{matrix}], S_{11} is k_{1} \times k_{1} .$ $$\begin{array}{} \displaystyle S = \left[ {\begin{array}{*{20}{c}} {{S_{11}}}&0\\ {{S_{21}}}&{{S_{22}}} \end{array}} \right],\quad \quad {S_{11}}{\rm{\;is\;}}{k_1} \times {k_1}. \end{array}$$

Equating the second matrices of the pairs (8), we find that

$S_{11} [B_{1}^{'} 0] = [{\tilde{B}}_{1}^{'} 0] \tilde{R},$ $$\begin{array}{} \displaystyle {S_{11}}[{B'_1}0] = [{\tilde B'_1}0]\tilde R, \end{array}$$(9)

and so

$l_{1} = rank [B_{1}^{'} 0] = rank [{\tilde{B}}_{1}^{'} 0] = {\tilde{I}}_{1},$ $$\begin{array}{} \displaystyle {l_1} = {\rm{rank }}\left[ {{{B'}_1}0} \right] = {\rm{rank }}\left[ {{{\tilde B'}_1}0} \right] = {\tilde I_1}, \end{array}$$

Since $B_{1}^{'}$ $\begin{array}{} \displaystyle B_1^\prime \end{array}$ and ${\tilde{B}}_{1}^{'}$ $\begin{array}{} \displaystyle {\tilde B'_1} \end{array}$ are k₁ × l₁ and have linearly independent columns, (9) implies that R is of the form

$R = [\begin{matrix} R_{11} & 0 \\ R_{21} & R_{22} \end{matrix}], R_{11} is l_{1} \times l_{1} .$ $$\begin{array}{} \displaystyle R = \left[ {\begin{array}{*{20}{c}} {{R_{11}}}&0\\ {{R_{21}}}&{{R_{22}}} \end{array}} \right],\quad \quad {R_{11}}{\rm{\;is\;}}{l_1} \times {l_1}. \end{array}$$

Equating the (2,2) entries in the matrices (8), we get

$S_{22} A_{1} = {\tilde{A}}_{1} R_{22}, S_{22} B_{1} = {\tilde{B}}_{1} {\bar{R}}_{22},$ $$\begin{array}{} \displaystyle {S_{22}}{A_1} = {\tilde A_1}{R_{22}},\quad \quad {S_{22}}{B_1} = {\tilde B_1}{\bar R_{_{22}}}, \end{array}$$

hence (A₁,B₁) and $({\tilde{A}}_{1}, {\tilde{B}}_{1})$ $\begin{array}{} \displaystyle ({\tilde A_1},{\tilde B_1}) \end{array}$, are mixed equivalent, which completes the proof of Statement 1.

Statement 2: If (6), then

$(A, B) \oplus (\tilde{A}, \tilde{B}) \Rightarrow (k_{1} + {\tilde{k}}_{1}, l_{1} + {\tilde{l}}_{1}, (A_{1} \oplus {\tilde{A}}_{1}, B_{1} \oplus {\tilde{B}}_{1})) .$ $$\begin{array}{} \displaystyle (A,B) \oplus (\tilde A,\tilde B) \Rightarrow ({k_1} + {\tilde k_1},{l_1} + {\tilde l_1},({A_1} \oplus {\tilde A_1},{B_1} \oplus {\tilde B_1})). \end{array}$$

Indeed, if (A,B) and $(\tilde{A}, \tilde{B})$ $\begin{array}{} \displaystyle (\tilde A,\tilde B) \end{array}$ are reduced to (7), then $(A, B) \oplus (\tilde{A}, \tilde{B})$ $\begin{array}{} \displaystyle (A,B) \oplus (\tilde A,\tilde B) \end{array}$ is reduced to

$([\begin{matrix} 0_{k_{1} l_{1}} \oplus 0_{{\tilde{k}}_{1} {\tilde{l}}_{1}} & 0 \oplus 0 \\ X \oplus \tilde{X} & A_{1} \oplus {\tilde{A}}_{1} \end{matrix}], [\begin{matrix} B_{1}^{'} \oplus {\tilde{B}}_{1}^{'} & 0 \oplus 0 \\ Y \oplus \tilde{Y} & B_{1} \oplus {\tilde{B}}_{1} \end{matrix}]),$ $$\begin{array}{} \displaystyle (\left[ {\begin{array}{*{20}{c}} {{0_{{k_1}{l_1}}} \oplus {0_{{{\tilde k}_1}{{\tilde l}_1}}}} & {0 \oplus 0} \\ {X \oplus \tilde X} & {{A_1} \oplus {{\tilde A}_1}} \\ \end{array}} \right],\left[ {\begin{array}{*{20}{c}} {{{B'}_1} \oplus {{\tilde B'}_1}} & {0 \oplus 0} \\ {Y \oplus \tilde Y} & {{B_1} \oplus {{\tilde B}_1}} \\ \end{array}} \right]), \end{array}$$

which is permutationally equivalent to

$([\begin{matrix} 0_{k_{1} l_{1}} & 0 \\ X & A_{1} \end{matrix}], [\begin{matrix} B_{1}^{'} & 0 \\ Y & B_{1} \end{matrix}]) \oplus ([\begin{matrix} 0_{{\tilde{k}}_{1} {\tilde{l}}_{1}} & 0 \\ \tilde{X} & {\tilde{A}}_{1} \end{matrix}], [\begin{matrix} {\tilde{B}}_{1}^{'} & 0 \\ \tilde{Y} & {\tilde{B}}_{1} \end{matrix}]) .$ $$\begin{array}{} \displaystyle (\left[ {\begin{array}{*{20}{c}} {{0_{{k_1}{l_1}}}} & 0 \\ X & {{A_1}} \\ \end{array}} \right],\left[ {\begin{array}{*{20}{c}} {B_1^\prime } & 0 \\ Y & {{B_1}} \\ \end{array}} \right]) \oplus (\left[ {\begin{array}{*{20}{c}} {{0_{{{\tilde k}_1}{{\tilde l}_1}}}} & 0 \\ {\tilde X} & {{{\tilde A}_1}} \\ \end{array}} \right],\left[ {\begin{array}{*{20}{c}} {\tilde B_1^\prime } & 0 \\ {\tilde Y} & {{{\tilde B}_1}} \\ \end{array}} \right]). \end{array}$$

We are ready to prove Lemma 1 for any pair (A,B). Due to Statement 1, we can replace (A,B) by any mixed equivalent pair. In particular, we can take

$(A, B) = {(F_{1}, G_{1})}^{(r_{1})} \oplus \dots \oplus {(F_{t}, G_{t})}^{(r_{t})} \oplus {(J_{1}, I_{1})}^{(s_{1})} \oplus \dots \oplus {(J_{t}, I_{t})}^{(s_{t})} \oplus (C, D)$ $$\begin{array}{} \displaystyle (A,B) = {({F_1},{G_1})^{({r_1})}} \oplus \ldots \oplus {({F_t},{G_t})^{({r_t})}} \oplus {({J_1},{I_1})^{({s_1})}} \oplus \ldots \oplus {({J_t},{I_t})^{({s_t})}} \oplus (C,D) \end{array}$$(10)

for some nonnegative t,r₁,...,r_t,s₁,...,r_t and some pair (C,D) in which C has linearly independent rows.

Clearly,

$(J_{i}, I_{i}) \Rightarrow {\begin{matrix} (1, 1, (J_{i - 1}, I_{i - 1})), & if i \neq 1; \\ (1, 1, (0_{00}, 0_{00})), & if i = 1, \end{matrix}$ $$\begin{array}{} \displaystyle ({J_i},{I_i}) \Rightarrow \{ \begin{array}{*{20}{l}} {(1,1,({J_{i - 1}},{I_{i - 1}})),}&{{\rm{if\;}}i \ne 1;}\\ {(1,1,({0_{00}},{0_{00}})),}&{{\rm{if\;}}i = 1,} \end{array} \end{array}$$

and

$(F_{i}, G_{i}) \Rightarrow {\begin{matrix} (1, 1, (F_{i - 1}, G_{i - 1})), & if i \neq 1; \\ (1, 0, (0_{00}, 0_{00})), & if i = 1. \end{matrix}$ $$\begin{array}{} \displaystyle ({F_i},{G_i}) \Rightarrow \{ \begin{array}{*{20}{l}} {(1,1,({F_{i - 1}},{G_{i - 1}})),}&{{\rm{if\;}}i \ne 1;}\\ {(1,0,({0_{00}},{0_{00}})),}&{{\rm{if\;}}i = 1.} \end{array} \end{array}$$

Due to Statement 2,

k₁ = m – rank A is the number of all summands of the types (J_i,I_i) and (F_i,G_i),

l₁ is the number of all summands of the types (J_i,I_i) and (F_i,G_i), except for (F₁,G₁),

and

$(A_{1}, B_{1}) = {(F_{1}, G_{1})}^{(r_{2})} \oplus \dots \oplus {(F_{t - 1}, G_{t - 1})}^{(r_{t})} \oplus {(J_{1}, I_{1})}^{(s_{2})} \oplus \dots \oplus {(J_{t - 1}, I_{t - 1})}^{(s_{t})} \oplus (C, D) .$ $$\begin{array}{} \displaystyle ({A_1},{B_1}) = {({F_1},{G_1})^{({r_2})}} \oplus \ldots \oplus {({F_{t - 1}},{G_{t - 1}})^{({r_t})}} \oplus {({J_1},{I_1})^{({s_2})}} \oplus \ldots \oplus {({J_{t - 1}},{I_{t - 1}})^{({s_t})}} \oplus (C,D). \end{array}$$(11)

We find that k₁ − l₁ is the number of summands of the type (F₁,G₁).

Applying the same reasoning to (11) instead of (10) we get that

k₂ is the number of all summands of the types (J_i,I_i) and (F_i,G_i) with i ≥ 2,

l₁ is the number of all summands of the types (J_i,I_i) with i ≥ 2 and (F_i,G_i) with i ≥ 3,

(A₂,B₂) = (F₁,G₁)^(r₃) ⊕ ··· ⊕ (F_t−2,G_t−2)^(r_t) ⊕ (J₁,I₁)^(s₃) ⊕ ··· ⊕ (C,D).

We find that k₂ − l₂ is the number of summands of the type (F₂,G₂), and that l₁ − k₂ is the number of summands of the type (J₁,I₁), and so on, until we obtain (5).

The fact that the pair (A_t,B_t) in (5) is determined up to mixed equivalence and the other summands are uniquely determined by (A,B) follows from Statement 1 (or from the canonical form of a matrix pair up to mixed equivalence). This concludes the proof of Lemma 1 and Theorem 1.

eISSN:: 2444-8656
Sprache:: Englisch

Zeitrahmen der Veröffentlichung:: Volume Open
Fachgebiete der Zeitschrift:: Biologie, andere, Mathematik, Angewandte Mathematik, Allgemeines, Physik

Zeitschrift RSS Feed

Regularizing algorithm for mixed matrix pencils

Online veröffentlicht: 18. Apr. 2017

Seitenbereich: 123 - 130

Eingereicht: 06. Feb. 2017

Akzeptiert: 18. Apr. 2017

DOI: https://doi.org/10.21042/AMNS.2017.1.00010

SchlüsselwörterRegularizing algorithm, Matrix pencils, Consimilarity, Unitary transformations, Canonical forms

© 2017 Tetiana Klymchuk, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Schlüsselwörter
Regularizing algorithm, Matrix pencils, Consimilarity, Unitary transformations, Canonical forms