On Pair of Almost Diagonal Skew-Symmetric and Symmetric Positive

Definite Matrix

Vjeran Hari

Department of Mathematics, University of Zagreb, Bijenička cesta 30, 41001 Zagreb, Croatia and Noah H. Rhee Department of Mathematics, University of Missouri-Kansas City, Kansas City, MO 64110-2499

Abstract

Let A be skew-symmetric, B symmetric positive definite, and let the pair (A, B) have multiple eigenvalues. If A is close to Murnaghan form and B is close to diagonal form, then certain principal submatrices of A and B are specially related. In this paper we describe this relationship and quantify it under the usual asymptotic conditions. If B = I, the identity matrix, the result describes a special structure of a skewsymmetric matrix almost in Murnaghan form. We then briefly discuss how Paardekooper method for skew-symmetric matrices asymptotically behaves in the presence of multiple eigenvalues.

Subject Classifications: AMS (MOS): 65F15; CR: 5.14

Introduction

With prevailing trend of parallel processing diagonalization methods for solving eigenvalue problems came into renewed interest of numerical analysts. In order to study the asymptotic convergence rate of such methods it is necessary to obtain some knowledge of the structure of the underlying almost diagonal matrices.

In this paper we study an “almost diagonal” pair (A, B) with skew-symmetric A and symmetric positive definite B. By an almost diagonal pair we mean a pair whose component matrices are almost diagonal. That is, A is almost in Murnaghan form [8] and B is almost diagonal. We also assume that the pair (A, B) has multiple eigenvalues. Then we show that certain linear combinations composed of the elements of A and B are quadratically small in respect to the average off-diagonal elements of A and B. We provide bounds similar to those in [12, 4]. The discovered property has a major influence on the asymptotic behavior of diagonalization methods for the generalized skew-symmetric eigenvalue problem. We note that skew-symmetric eigenvalue problems appear in praxis (e.g. structural mechanics) [1, 11].

If B = I, the identity matrix, our general result reveals a special structure of a skew-symmetric matrix almost in Murnaghan form (cf. [2]). We show how that structure affects the asymptotic convergence of the Paardekooper method for reducing a skew-symmetric matrix to its Murnaghan form.

The paper is organized in two sections. In Section 1 we derive general estimates for the pair (A, B). In Section 2 we specialize the general result for the case B = I. Then we use it to show the failure of the quadratic convergence of the Paardekooper method in the case of multiple eigenvalues. We provide examples which confirm our conclusion.

1 Almost Diagonal Pair (A, B)

Let (A, B) be a pair with skew-symmetric A = (a_{ij}) and symmetric positive definite B = (b_{ij}), both of order n. Consider the block partition

A = [ \begin{matrix}A_{11} & ⋯ & A_{1k} \\ ⋮ & ... & ⋮ \\ A_{k1} & ⋯ & A_{kk} \end{matrix} ] , B = [ \begin{matrix}B_{11} & ⋯ & B_{1k} \\ ⋮ & ... & ⋮ \\ B_{k1} & ⋯ & B_{kk} \end{matrix} ] ,  (1.1)

where all A_{ij}, B_{ij} are 2 × 2 except possibly the border blocks A_{ik}, B_{ik} (A_{ki}, B_{ki}), 1 ≤ i ≤ k − 1, and A_{kk}, B_{kk} which are 2 × 1 (1 × 2) and 1 × 1 when n is odd. Thus, k = [\frac{n+1}{2}] where generally, [α] denotes the largest integer ≤ α. To simplify notation and analysis we assume

a_{12} ≥ a_{34} ≥ ⋯ ≥ a_{2k′−1,2k′} ≥ 0,  (1.2)
b_{11} = b_{22} = ⋯ b_{nn} = 1,  (1.3)

where k′ = [\frac{n}{2}]. Later we shall relax the assumption (1.2). The requirements (1.2) and (1.3) can be achieved by the transformation

A ⟶ F^{T} A F , B ⟶ F^{T} B F ,  (1.4)

where F = DΦΠ with D = diag(\frac{1}{\sqrt{b_{11}}} , …, \frac{1}{\sqrt{b_{nn}}}), Φ = diag(1, σ_{1}, 1, σ_{2}, ⋯) (if n is odd the last diagonal element is 1) and Π a suitable permutation matrix. Here σ_{i} = sign(a_{2i−1,2i}), 1 ≤ i ≤ k′, where sign(x) = 1 if x ≥ 0 and −1 otherwise. Note that (1.4) as an equivalence transformation on matrix pairs preserves the eigenvalues and links the eigenvectors via F.

We denote the eigenvalues of (A, B) by ±ıν_{j} (with ν_{j} ≥ 0), 1 ≤ j ≤ k′, and ıν_{k} = 0 when n is odd. Here ı = \sqrt{−1}. Note that either n = 2k′ = 2k or n = 2k′ + 1 = 2k − 1, hence k = k′ + 1 for n odd.

We shall transform (A, B) to (H, M) with Hermitian H and Hermitian positive definite M and then apply to (H, M) the result [4] on pairs of almost diagonal Hermitian matrices. Note that ıA is Hermitian and the eigenvalues of (ıA, B) are ±ν_{j} (ν_{j} ≥ 0), 1 ≤ j ≤ k′, and ν_{k} = 0 when n is odd. However, the diagonal elements of A are zero. So, in order to use the estimates from [4], we have to perform additional transformations. Since

ı Q̂^{∗} [ \begin{matrix}0 & α \\ −α & 0 \end{matrix} ] Q̂ = [ \begin{matrix}α & 0 \\ 0 & −α \end{matrix} ] , Q̂^{∗} [ \begin{matrix}1 & β \\ β & 1 \end{matrix} ] Q̂ = [ \begin{matrix}1 & β \\ β & 1 \end{matrix} ] ,

where

Q̂ = \frac{\sqrt{2}}{2} [ \begin{matrix}ı & 1 \\ 1 & ı \end{matrix} ] ,

we define

Q = diag (Q̂_{1}, …, Q̂_{k}) , Q̂_{j} = \{ \begin{matrix}Q̂ & if & 1 ≤ j ≤ k′ \\ [1] & if & j = k, n = 2k − 1 . \end{matrix}  (1.5)

Here Q̂^{∗} denotes the complex conjugate transpose of Q̂. Let

Ã = Q^{∗}(ıA)Q , B̃ = Q^{∗}BQ.  (1.6)

The diagonal elements of Ã are a_{12}, −a_{12}, …, a_{2k′−1,2k′}, −a_{2k′−1,2k′} (and 0 if n is odd), while the diagonal elements of B̃ remain ones.

Lemma 1.1 Let (Ã_{ij}) and (B̃_{ij}) denote the partition (1.1) of Ã and B̃, respectively.

(i) If A_{ij} = [ \begin{matrix}a_{1} & a_{2} \\ a_{3} & a_{4} \end{matrix} ], B_{ij} = [ \begin{matrix}b_{1} & b_{2} \\ b_{3} & b_{4} \end{matrix} ], then

Ã_{ij} = \frac{1}{2} [ \begin{matrix}a_{2} − a_{3} + ı(a_{1} + a_{4}) & a_{1} − a_{4} + ı(a_{2} + a_{3}) \\ a_{4} − a_{1} + ı(a_{2} + a_{3}) & a_{3} − a_{2} + ı(a_{1} + a_{4}) \end{matrix} ] ,
B̃_{ij} = \frac{1}{2} [ \begin{matrix}b_{1} + b_{4} + ı(b_{3} − b_{2}) & b_{2} + b_{3} + ı(b_{4} − b_{1}) \\ b_{2} + b_{3} + ı(b_{1} − b_{4}) & b_{1} + b_{4} + ı(b_{2} − b_{3}) \end{matrix} ] .

(ii) If n = 2k − 1 and A_{ik} = [ \begin{matrix}a_{1} \\ a_{2} \end{matrix} ], B_{ik} = [ \begin{matrix}b_{1} \\ b_{2} \end{matrix} ], then

Ã_{ik} = \frac{\sqrt{2}}{2} [ \begin{matrix}a_{1} + ıa_{2} \\ a_{2} + ıa_{1} \end{matrix} ] , B̃_{ik} = \frac{\sqrt{2}}{2} [ \begin{matrix}b_{2} − ıb_{1} \\ b_{1} − ıb_{2} \end{matrix} ] .

In this case Ã_{kk} = [0] = A_{kk}, B̃_{kk} = [1] = B_{kk}.

Proof. The both assertions follow from the relations (1.6) and (1.5). In particular, (i) follows from the fact that Ã_{ij} = Q̂^{∗}(ıA_{ij})Q̂, B̃_{ij} = Q̂^{∗}B_{ij}Q̂, and (ii) follows from Ã_{ik} = Q̂^{∗}(ıA_{ik})·1, B̃_{ik} = Q̂^{∗}B_{ik}·1, Ã_{kk} = 1·[0]·1, B̃_{kk} = 1·B_{kk}·1.

Our final transformation will order the diagonal elements of Ã nonincreasingly. Let π be a permutation of {1, 2, …, n} defined by

π = \{ \begin{matrix}( \begin{matrix}1 & 2 & ⋯ & k′ & k′ + 1 & k′ + 2 & ⋯ & 2k′ \\ 1 & 3 & ⋯ & 2k′ − 1 & 2k′ & 2k′ − 2 & ⋯ & 2 \end{matrix} ) , n = 2k′, \\ ( \begin{matrix}1 & 2 & ⋯ & k′ + 1 & k′ + 2 & ⋯ & 2k′ & 2k′ + 1 \\ 1 & 3 & ⋯ & 2k′ + 1 & 2k′ & ⋯ & 4 & 2 \end{matrix} ) , n = 2k′ + 1, \end{matrix}

and let I_{n} = [e_{1}, …, e_{n}] be identity. If permutation matrix P is defined by

P e_{i} = e_{π(i)}, 1 ≤ i ≤ n,  (1.7)

then the diagonal elements of

H = P^{T} Ã P, M = P^{T} B̃ P  (1.8)

satisfy

\begin{aligned}h_{11} & ≥ & h_{22} & ≥ & ⋯ & ≥ & h_{nn}, \\ m_{11} & = & m_{22} & = & ⋯ & = & m_{nn} & = & 1, \end{aligned}

respectively. Note that the numbers h_{ii}, 1 ≤ i ≤ n are distributed symmetrically with respect to the origin.

Lemma 1.2 Let H = (h_{ij}), Ã = (ã_{ij}). Then

h_{ij} = \{ \begin{matrix}ã_{2i−1,2j−1}, 1 ≤ i, j ≤ k \\ ã_{2(n+1−i),2(n+1−j)}, k + 1 ≤ i, j ≤ n \\ ã_{2i−1,2(n+1−j)}, 1 ≤ i ≤ k, k + 1 ≤ j ≤ n \\ ã_{2(n+1−i),2j−1}, k + 1 ≤ i ≤ n, 1 ≤ j ≤ k. \end{matrix}

The same relationship holds between the elements of M and B̃.

Proof. The relations (1.8) and (1.7) imply h_{ij} = ã_{π(i),π(j)}, m_{ij} = b̃_{π(i),π(j)} for all i, j. Hence the proof follows directly from the definition of π.

Lemma 1.2 implies that in the partition

H = [ \begin{matrix}H_{1} & H_{2} \\ H_{2}^{∗} & H_{3} \end{matrix} ] \begin{matrix}k \\ n − k \end{matrix}  (1.9)
k n − k

H_{1} (H_{3}) contains exactly the elements ã_{2i−1,2j−1}, 1 ≤ i, j ≤ k (ã_{2(n+1−i),2(n+1−j)}, k + 1 ≤ i, j ≤ n), while H_{2} (H_{2}^{∗}) contains the elements ã_{2i−1,2(n+1−j)}, 1 ≤ i ≤ k, k + 1 ≤ j ≤ n (ã_{2(n+1−i),2j−1}, k + 1 ≤ i ≤ n, 1 ≤ j ≤ k). Thus, H_{1} (H_{3}) collects the first (second) diagonal elements of 2 × 2 blocks Ã_{ij}, 1 ≤ i, j ≤ k′. If n is odd H_{1} also collects the first elements of 2 × 1 / 1 × 2 blocks Ã_{ik} / Ã_{ki}, 1 ≤ i ≤ k′, and Ã_{kk} = [0] appears in the bottom right corner of H_{1} (cf. Example 1.3).

Example 1.3 For n = 6 and n = 7 we express H in terms of the elements of Ã.

[ \begin{matrix}ã_{11} & ã_{13} & ã_{15} & ã_{16} & ã_{14} & ã_{12} \\ ã_{31} & ã_{33} & ã_{35} & ã_{36} & ã_{34} & ã_{32} \\ ã_{51} & ã_{53} & ã_{55} & ã_{56} & ã_{54} & ã_{52} \\ ã_{61} & ã_{63} & ã_{65} & ã_{66} & ã_{64} & ã_{62} \\ ã_{41} & ã_{43} & ã_{45} & ã_{46} & ã_{44} & ã_{42} \\ ã_{21} & ã_{23} & ã_{25} & ã_{26} & ã_{24} & ã_{22} \end{matrix} ] , [ \begin{matrix}ã_{11} & ã_{13} & ã_{15} & ã_{17} & ã_{16} & ã_{14} & ã_{12} \\ ã_{31} & ã_{33} & ã_{35} & ã_{37} & ã_{36} & ã_{34} & ã_{32} \\ ã_{51} & ã_{53} & ã_{55} & ã_{57} & ã_{56} & ã_{54} & ã_{52} \\ ã_{71} & ã_{73} & ã_{75} & ã_{77} & ã_{76} & ã_{74} & ã_{72} \\ ã_{61} & ã_{63} & ã_{65} & ã_{67} & ã_{66} & ã_{64} & ã_{62} \\ ã_{41} & ã_{43} & ã_{45} & ã_{47} & ã_{46} & ã_{44} & ã_{42} \\ ã_{21} & ã_{23} & ã_{25} & ã_{27} & ã_{26} & ã_{24} & ã_{22} \end{matrix} ]

n = 6  n = 7

The eigenvalues of (H, M) are those of (ıA, B). We shall number them nonincreasinly. For n even, we assume

ν_{1} = ⋯ = ν_{s_{1}} > ν_{s_{1}+1} = ⋯ = ν_{s_{2}} > ⋯ > ν_{s_{r−1}+1} = ⋯ = ν_{s_{r}} ≥
−ν_{s_{r}} = ⋯ = −ν_{s_{r−1}+1} > ⋯ > −ν_{s_{1}} = ⋯ = −ν_{1}.

For n odd we assume

ν_{1} = ⋯ = ν_{s_{1}} > ⋯ > ν_{s_{r−1}+1} = ⋯ = ν_{s_{r}−1} = ν_{s_{r}}(= 0) = −ν_{s_{r}−1} = ⋯
= −ν_{s_{r−1}+1} > ⋯ > −ν_{s_{1}} = ⋯ = −ν_{1},

where s_{r} = k. Thus, for i = 1, …, r − 1 (and i = r provided that ν_{s_{r}} > 0)

n_{i} = s_{i} − s_{i−1} (s_{0} = 0)

is the multiplicity of ν_{s_{i}} and −ν_{s_{i}}. If ν_{s_{r}} = 0 and n even (odd) its multiplicity is n_{r} = 2(s_{r} − s_{r−1}) (n_{r} = 2(s_{r} − s_{r−1}) − 1). Note that if ν_{s_{r}} = 0, there are 2r − 1 distinct eigenvalues regardless of whether n is even or odd. On the other hand ν_{s_{r}} > 0 implies 2r distinct eigenvalues and n even. So, let

σ = \{ \begin{matrix}2r & if & ν_{s_{r}} > 0, \\ 2r − 1 & if & ν_{s_{r}} = 0, \end{matrix}

and let us partition partition H and M according to the the multiplicities of the eigenvalues of (H, M) in the order n_{1}, n_{2}, n_{3}, …, n_{3} n_{2}, n_{1}:

H = [ \begin{matrix}H_{11} & ⋯ & H_{ir} & ⋯ & H_{1σ} \\ ⋮ & ... & ⋮ & & ⋮ \\ H_{r1} & ⋯ & H_{rr} & ⋯ & H_{rσ} \\ ⋮ & & ⋮ & ... & ⋮ \\ H_{σ1} & ⋯ & H_{σr} & ⋯ & H_{σσ} \end{matrix} ] , M = [ \begin{matrix}M_{11} & ⋯ & M_{ir} & ⋯ & M_{1σ} \\ ⋮ & ... & ⋮ & & ⋮ \\ M_{r1} & ⋯ & M_{rr} & ⋯ & M_{rσ} \\ ⋮ & & ⋮ & ... & ⋮ \\ M_{σ1} & ⋯ & M_{σr} & ⋯ & M_{σσ} \end{matrix} ] .

Here H_{11}, M_{11} and H_{σ,σ}, M_{σ,σ} are of order n_{1} and so forth. We see that H_{1} (H_{3}) from (1.9) includes diagonal blocks H_{11}, …,H_{r−1,r−1} (H_{r+1,r+1}, …,H_{σσ}). H_{1} includes H_{rr} provided that ν_{s_{r}} > 0 or if H_{rr} is 1 × 1. Otherwise, H_{rr} is divided between H_{1} and H_{3}, and H_{1} includes [\frac{n_{r}+1}{2}] diagonal elements of H_{rr}.

Let

3δ_{i} = min{ν_{s_{i−1}} − ν_{s_{i}} , ν_{s_{i}} − ν_{s_{i+1}}} , 1 ≤ i ≤ r,

where we assume ν_{0} = ∞ and

ν_{s_{r+1}} = \{ \begin{matrix}−ν_{s_{r−1}} & , & ν_{s_{r}} = 0, \\ −ν_{s_{r}} & , & ν_{s_{r}} > 0. \end{matrix}

Then 3δ_{i} is the local gap in the spectrum associated with ν_{s_{i}} and −ν_{s_{i}}. The minimal gap is 3δ where (see Figure 1)

δ = min_{1≤i≤r} δ_{i} .

[figure: −ν_{s_{3}}; ν_{s_{3}}; ν_{s_{2}}; −ν_{s_{2}}; −ν_{s_{1}}; ν_{s_{1}}; 0; ^{3δ}; n even, r = 3, δ = δ_{r}; −ν_{s_{2}}; ν_{s_{2}}; ν_{s_{1}}; −ν_{s_{1}}; 0; ν_{s_{3}}; ^{3δ}; ^{3δ}; n odd, r = 3, δ = δ_{r}]

Figure 1: The minimal gap in the spectrum of (H, M)

For any square matrices X and Y of order n, we define

S(X, Y) = \sqrt{S^{2}(X) + S^{2}(Y)}

where S(X) = ∥X − diag(X)∥. Here ∥ · ∥ denotes the Euclidean matrix norm (∥A∥^{2} = trace(A^{∗}A)) and diag(X) = diag(x_{11}, …, x_{nn}), where X = (x_{ij}). If A is skew-symmetric we use notation S(A) for ∥A − diag(A_{11}, …, A_{kk})∥, where A_{ii} are from the partition (1.1). With this assumption we have

S(A, B) = S(Ã, B̃) = S(H, M).  (1.10)

The spectral norm is denoted by ∥ · ∥_{2}.

Lemma 1.4 Let

C_{i} = D_{i} + E_{i} = \{ \begin{matrix}H − ν_{s_{i}}M, & 1 ≤ i ≤ r \\ H + ν_{s_{σ+1−i}}M, & r + 1 ≤ i ≤ σ \end{matrix} ,

where D_{i} = diag(C_{i}). If

max{∥E_{i}∥_{2} , ∥E_{σ+1−i}∥_{2}} < δ_{i}, 1 ≤ i ≤ r  (1.11)

then

∥H_{ii} − ν_{s_{i}}M_{ii}∥ ≤ \frac{1}{δ_{i}} ∑_{j≠i^{j=1}}^{σ} ∥H_{ij} − ν_{s_{i}}M_{ij}∥^{2}, 1 ≤ i ≤ r,  (1.12)

∥H_{ii} + ν_{s_{σ+1−i}}M_{ii}∥ ≤ \frac{1}{δ_{σ+1−i}} ∑_{j≠i^{j=1}}^{σ} ∥H_{ij} + ν_{s_{σ+1−i}}M_{ij}∥^{2}, r + 1 ≤ i ≤ σ (1.13)

and

2 ∑_{i=1}^{r} ∥H_{ii} −ν_{s_{i}}M_{ii}∥^{2} +2 ∑_{i=r+1}^{σ} ∥H_{ii} +ν_{s_{σ+1−i}}M_{ii}∥^{2} ≤ [\frac{1 + ν_{1}^{2}}{δ} S^{2}(H, M)]^{2} . (1.14)

Proof. The relations (1.12) and (1.13) follow directly from [4, Lemma 2.1]. The relation (1.14) follows from [4, Corollary 3.2].

Our aim is to reformulate Lemma 1.4 in terms of the elements of A and B. We start with the condition (1.11). By the Cauchy-Schwarz inequality and the relation (1.10) we have for 1 ≤ i ≤ r

max{∥E_{i}∥, ∥E_{σ+1−i}∥} = max{S(H − ν_{s_{i}}M), S(H + ν_{s_{i}}M)}
≤ \sqrt{1 + ν_{s_{i}}^{2}}S(H, M) = \sqrt{1 + ν_{s_{i}}^{2}}S(A, B). (1.15)

Since the spectral norm is not larger than the Euclidean norm, we see from the inequality (1.15) that the condition (1.11) can be replaced by

S(A, B) < min_{1≤i≤r} \frac{δ_{i}}{\sqrt{1 + ν_{s_{i}}^{2}}} ,  (1.16)

or by even a more stringent one: S(A, B) < δ/\sqrt{1 + ν_{1}^{2}}. Let us partition Ã and B̃ according to 2n_{1}, 2n_{2},…, 2n_{r−1}, 2n_{r} (if ν_{s_{r}} = 0, replace 2n_{r} by n_{r}):

Ã = [ \begin{matrix}Ã_{11} & ⋯ & Ã_{1r} \\ ⋮ & ... & ⋮ \\ Ã_{r1} & ⋯ & Ã_{rr} \end{matrix} ] , B̃ = [ \begin{matrix}B̃_{11} & ⋯ & B̃_{1r} \\ ⋮ & ... & ⋮ \\ B̃_{r1} & ⋯ & B̃_{rr} \end{matrix} ] .  (1.17)

From Lemma 1.2 (cf. Example 1.3) we conclude that the elements of H_{ii}, M_{ii} (H_{σ+1−i,σ+1−i}, M_{σ+1−i,σ+1−i}) are those elements of Ã_{ii}, B̃_{ii}, respectively, which have odd (even) subscripts, provided that ν_{s_{i}} > 0. So, let Odd(X) (Even(X)) denote the submatrix of X obtained on the intersection of rows and columns with odd (even) subscripts.

Example 1.5 Let n > 4, ν_{1} = ν_{2} > ν_{3} ≥ · · ·. Then n_{1} = 2 and

Odd (Ã_{11} − ν_{1}B̃_{11}) = [ \begin{matrix}ã_{11} − ν_{1}b̃_{11} & ã_{13} − ν_{1}b̃_{13} \\ ã_{31} − ν_{1}b̃_{31} & ã_{33} − ν_{1}b̃_{33} \end{matrix} ] ,
Even (Ã_{11} + ν_{1}B̃_{11}) = [ \begin{matrix}ã_{22} + ν_{1}b̃_{22} & ã_{24} + ν_{1}b̃_{24} \\ ã_{42} + ν_{1}b̃_{42} & ã_{44} + ν_{1}b̃_{44} \end{matrix} ] .

Lemma 1.6 Let the condition (1.16) hold and let Ã_{ij}, B̃_{ij}, 1 ≤ i, j ≤ r be defined by the relations (1.17) and (1.6) .

(i) If ν_{s_{r}} = 0, then ∥Ã_{rr}∥ ≤ \frac{1}{δ_{r}} ∑_{j=1}^{r−1} ∥Ã_{rj}∥^{2} .

(ii) If ν_{s_{i}} > 0, then ∥Odd (Ã_{ii} − ν_{s_{i}} B̃_{ii}) ∥ + ∥Even (Ã_{ii} + ν_{s_{i}} B̃_{ii}) ∥

≤ \frac{1 + ν_{s_{i}}^{2}}{δ_{i}} [S^{2}(Ã_{ii}, B̃_{ii}) + ∑_{j≠i^{j=1}}^{r} (∥Ã_{ij}∥^{2} + ∥B̃_{ij}∥^{2})] .

Proof. (i) In this case the relation (1.12) implies

∥H_{rr}∥ ≤ \frac{1}{δ_{r}} ∑_{j≠r^{j=1}}^{σ} ∥H_{rj}∥^{2}.

This inequality proves (i) since by Lemma 1.2 we have

∥H_{rr}∥ = ∥Ã_{rr}∥ and ∑_{j=1}^{σ} ∥H_{rj}∥^{2} = ∑_{j=1}^{r−1} ∥Ã_{rj}∥^{2}.

(ii) Applying the Cauchy-Schwarz inequality (in a similar way as in the relation (1.15)) to the relations (1.12), (1.13) we obtain

∥H_{ii} − ν_{s_{i}}M_{ii}∥ + ∥H_{σ+1−i,σ+1−i} + ν_{s_{i}}M_{σ+1−i,σ+1−i}∥ ≤ \frac{1 + ν_{s_{i}}^{2}}{δ_{i}} ·

· [∑_{j≠i^{j=1}}^{σ} (∥H_{ij}∥^{2} + ∥M_{ij}∥^{2}) + ∑_{j≠σ+1−i^{j=1}}^{σ} (∥H_{σ+1−i,j}∥^{2} + ∥M_{σ+1−i,j}∥^{2})] . (1.18)

By Lemma 1.2 we have

H_{ii} − ν_{s_{i}}M_{ii} = Odd (Ã_{ii} − ν_{s_{i}} B̃_{ii}) ,  (1.19)
H_{σ+1−i,σ+1−i} + ν_{s_{i}}M_{σ+1−i,σ+1−i} = J_{n_{i}}Even (Ã_{ii} + ν_{s_{i}} B̃_{ii}) J_{n_{i}}, (1.20)

where J_{n_{i}} = [e_{n_{i}}, e_{n_{i}−1}, …, e_{1}]. Here e_{t} is the t’th column of I_{n_{i}}. Applying the Euclidean matrix norm we see that the left-hand side of the inequality (1.18) equals ∥Odd (Ã_{ii} − ν_{s_{i}} B̃_{ii}) ∥ + ∥Even (Ã_{ii} + ν_{s_{i}} B̃_{ii}) ∥. By Lemma 1.2 the righthand side of the inequality (1.18) equals (for illustration take i = 1, n_{1} = 2 in Example 1.3)

\frac{1 + ν_{s_{i}}^{2}}{δ_{i}} [∑_{j=1}^{r} (∥Ã_{ij}∥^{2} + ∥B̃_{ij}∥^{2}) − ∥Odd \binom{}{Ã_{ii}} ∥^{2} − ∥Odd \binom{}{B̃_{ii}} ∥^{2}

−∥Even \binom{}{Ã_{ii}} ∥^{2} − ∥Even \binom{}{B̃_{ii}} ∥^{2}] .

Hence, the assertion (ii) easily follows.

To step back from (Ã, B̃) to (A, B) we have to express ∥Odd (Ã_{ii} − ν_{s_{i}} B̃_{ii}) ∥

and ∥Even (Ã_{ii} + ν_{s_{i}} B̃_{ii}) ∥ in terms of the elements of A and B. To this end we define nonnegative quantities ω_{i}(A, B), 1 ≤ i ≤ r, and ω(A, B) in the following way:

ω_{r}^{2}(A, B) = ∥A_{rr}∥^{2} , if ν_{s_{r}} = 0,  (1.21)

ω_{i}^{2}(A, B) = ∑_{s_{i−1}+1≤p<q≤s_{i}} {[a_{2p−1,2q} − a_{2p,2q−1} − ν_{s_{i}}(b_{2p−1,2q−1} + b_{2p,2q})]^{2}

+ [a_{2p−1,2q−1} + a_{2p,2q} + ν_{s_{i}}(b_{2p−1,2q} − b_{2p,2q−1})]^{2}} + 2 ∑_{p=s_{i−1}+1}^{s_{i}} (a_{2p−1,2p} − ν_{s_{i}})^{2} ,

if ν_{s_{i}} > 0, 1 ≤ i ≤ r,  (1.22)
ω^{2}(A, B) = ∑_{i=1}^{r} ω_{i}^{2}(A, B).  (1.23)

Here (A_{ij}), (B_{ij}) is the partition (1.17) of A, B, respectively.

Lemma 1.7 Let A be a skew-symmetric and B a symmetric positive definite matrix for which the assumptions (1.2) and (1.3) hold. If the condition (1.16) holds, then

ω_{r}(A, B) ≤ \frac{1}{δ_{r}} ∑_{j=1}^{r−1} ∥A_{rj}∥^{2} if ν_{s_{r}} = 0,  (1.24)

ω_{i}(A, B) ≤ \frac{1 + ν_{s_{i}}^{2}}{δ_{i}} [S^{2}(A_{ii}, B_{ii}) + ∑_{j≠i^{j=1}}^{r} (∥A_{ij}∥^{2} + ∥B_{ij}∥^{2})] , \begin{matrix}ν_{s_{i}} > 0 \\ 1 ≤ i ≤ r \end{matrix} (1.25)

ω(A, B) ≤ \frac{1 + ν_{1}^{2}}{\sqrt{2}δ} S^{2}(A, B).  (1.26)

Proof. Since each Q̂_{j} from (1.5) is unitary and since each Ã_{ij} (B̃_{ij}) contains a whole number of blocks A_{st} (B_{st}), we have

∥Ã_{ij}∥ = ∥A_{ij}∥, ∥B̃_{ij}∥ = ∥B_{ij}∥, 1 ≤ i, j ≤ r.  (1.27)

Hence (1.24) follows directly from Lemma 1.6 (i).

To prove (1.25) we first note that skew-symmetry property of A_{ii} implies

S(Ã_{ii}, B̃_{ii}) = S(A_{ii}, B_{ii}), 1 ≤ i ≤ r.  (1.28)

By Lemma 1.1 we have

2(ã_{2p−1,2q−1} − ν_{s_{i}}b̃_{2p−1,2q−1}) = [a_{2p−1,2q} − a_{2p,2q−1} + ı(a_{2p−1,2q−1} + a_{2p,2q})]

−ν_{s_{i}} [b_{2p−1,2q−1} + b_{2p,2q} + ı(b_{2p,2q−1} − b_{2p−1,2q})]
= [a_{2p−1,2q} − a_{2p,2q−1} − ν_{s_{i}}(b_{2p−1,2q−1} + b_{2p,2q})]
+ı [a_{2p−1,2q−1} + a_{2p,2q} − ν_{s_{i}}(b_{2p,2q−1} − b_{2p−1,2q})]

and

2(ã_{2p,2q} + ν_{s_{i}}b̃_{2p,2q}) = [a_{2p,2q−1} − a_{2p−1,2q} + ı(a_{2p−1,2q−1} + a_{2p,2q})]

+ν_{s_{i}} [b_{2p−1,2q−1} + b_{2p,2q} + ı(b_{2p−1,2q} − b_{2p,2q−1})]
= [a_{2p,2q−1} − a_{2p−1,2q} + ν_{s_{i}}(b_{2p−1,2q−1} + b_{2p,2q})]
+ı [a_{2p−1,2q−1} + a_{2p,2q} + ν_{s_{i}}(b_{2p−1,2q} − b_{2p,2q−1})] .

From the above equalities equalities we obtain for s_{i−1} + 1 ≤ p, q ≤ s_{i}, with ν_{s_{i}} > 0,

2|ã_{2p−1,2q−1} − ν_{s_{i}}b̃_{2p−1,2q−1}|^{2} + 2|ã_{2p,2q} + ν_{s_{i}}b̃_{2p,2q}|^{2}
= [a_{2p−1,2q} − a_{2p,2q−1} − ν_{s_{i}}(b_{2p−1,2q−1} + b_{2p,2q})]^{2}
+ [a_{2p−1,2q−1} + a_{2p,2q} + ν_{s_{i}}(b_{2p−1,2q} − b_{2p,2q−1})]^{2} . (1.29)

If p = q the relation (1.29) together with the assumptions on A and B implies 2|ã_{2p−1,2p−1} − ν_{s_{i}}b̃_{2p−1,2p−1}|^{2} + 2|ã_{2p,2p} + ν_{s_{i}}b̃_{2p,2p}|^{2}

= [a_{2p−1,2p} − (−a_{2p−1,2p}) − ν_{s_{i}}(1 + 1)]^{2} + [0 + 0 + ν_{s_{i}}(b_{2p−1,2p} − b_{2p−1,2p})]^{2}

= 4(a_{2p−1,2p} − ν_{s_{i}})^{2}, s_{i−1} + 1 ≤ p ≤ s_{i}, ν_{s_{i}} > 0.  (1.30)

Since Odd (Ã_{ii} − ν_{s_{i}} B̃_{ii}) and Even (Ã_{ii} + ν_{s_{i}} B̃_{ii}) are Hermitian the relations (1.29) and (1.30) yield

∥Odd (Ã_{ii} − ν_{s_{i}} B̃_{ii}) ∥^{2} + ∥Even (Ã_{ii} + ν_{s_{i}} B̃_{ii}) ∥^{2}

= 2 ∑_{s_{i−1}+1≤p<q≤s_{i}} (|ã_{2p−1,2q−1} − ν_{s_{i}}b̃_{2p−1,2q−1}|^{2} + |ã_{2p,2q} + ν_{s_{i}}b̃_{2p,2q}|^{2})

+ ∑_{p=s_{i−1}+1}^{s_{i}}[(|ã_{2p−1,2p−1} − ν_{s_{i}}b̃_{2p−1,2p−1}|^{2} + |ã_{2p,2p} + ν_{s_{i}}b̃_{2p,2p}|^{2})

= ∑_{s_{i−1}+1≤p<q≤s_{i}} {[a_{2p−1,2q} − a_{2p,2q−1} − ν_{s_{i}}(b_{2p−1,2q−1} + b_{2p,2q})]^{2}

+ [a_{2p−1,2q−1} + a_{2p,2q} + ν_{s_{i}}(b_{2p−1,2q} − b_{2p,2q−1})]^{2}} + 2 ∑_{p=s_{i−1}+1}^{s_{i}} (a_{2p−1,2p} − ν_{s_{i}})^{2}

= ω_{i}^{2}(A, B),  1 ≤ i ≤ r, ν_{s_{i}} > 0.  (1.31)

The assertion (1.25) follows by Lemma 1.6(ii) and by the relations (1.31), (1.27) and (1.28).

To prove the assertion (1.26), note that in case ν_{s_{r}} > 0, the left-hand side of (1.14) can be written as

2 ∑_{i=1}^{r} [∥Odd (Ã_{ii} − ν_{s_{i}} B̃_{ii}) ∥^{2} + ∥Even (Ã_{ii} + ν_{s_{i}} B̃_{ii}) ∥^{2}] .

This follows by the relations (1.19) and (1.20). By (1.31) and (1.23) this sum equals 2ω^{2}(A, B). If ν_{s_{r}} = 0, the last, r’th term, in the above sum is replaced by ∥Ã_{rr}∥^{2} = ∥A_{rr}∥^{2} which is by definition ω_{r}^{2}(A, B). So, the sum again equals 2ω^{2}(A, B).

Finally, we relax the assumption (1.2)

Theorem 1.8 Let A be a skew-symmetric matrix satisfying

| a_{12} |≥| a_{34} |≥ ⋯ ≥| a_{2k′−1,2k′} |,  (1.32)

and let B be a symmetric positive definite matrix satisfying (1.3). If the condition (1.16) is fulfilled, then the relations (1.24)—(1.26) hold provided that ω_{i}(A, B), 1 ≤ i ≤ r, and ω(A, B) are replaced by ω_{i}( ΦAΦ, ΦBΦ), 1 ≤ i ≤ r and ω( ΦAΦ, ΦBΦ), respectively.

Proof. The proof follows by applying Lemma 1.7 to the pair (ΦAΦ, ΦBΦ). Since S(A, B), S(A_{ii}, B_{ii}), ∥A_{ij}∥, ∥B_{ij}∥ are invariant under the transformation with Φ, the right-hand sides in the inequalities (1.24)–(1.26) remain unchanged (see the sign matrix definition after the relation (1.4)).

As a result of the transformation with (A, B) ⟶ (ΦAΦ, ΦBΦ), the elements

a_{2p−1,2q−1}, b_{2p−1,2q−1}  remain unchanged,
a_{2p−1,2q}, b_{2p−1,2q} become σ_{q} · a_{2p−1,2q}, σ_{q} · b_{2p−1,2q},
a_{2p,2q−1}, b_{2p,2q−1} become σ_{p} · a_{2p,2q−1}, σ_{p} · b_{2p,2q−1},
a_{2p,2q}, b_{2p,2q} become σ_{p} · σ_{q} · a_{2p,2q}, σ_{p} · σ_{q} · b_{2p,2q}.

Here σ_{i} = sign(a_{2i−1,2i}), 1 ≤ i ≤ k′. By (1.22) and the above rules one easily defines ω_{i}(ΦAΦ, ΦBΦ), 1 ≤ i ≤ r.

Corollary 1.9 Suppose the conditions of Theorem 1.8 hold. Then

∑_{i=1}^{r} ∑_{p=s̄_{i−1}+1}^{s̄_{i}} (| a_{2p−1,2p} | −ν_{s_{i}})^{2} ≤ [\frac{1 + ν_{1}^{2}}{2δ} S^{2}(A, B)]^{2} ,  (1.33)

where s̄_{i} = s_{i} for all i except r when n is odd. Then s̄_{r} = s_{r} − 1 = k′. The empty sum is considered zero.

Proof. The inequality (1.33) follows directly from Theorem 1.8 and the relations (1.21)—(1.23). Note also that σ_{p}a_{2p−1,2p} =| a_{2p−1,2p} |.

Corollary 1.9 obviously holds in the case of simple eigenvalues of the pair (A, B). We end this section by paraphrasing Theorem 1.8 and Corollary 1.9 in the following way:

Suppose a skew-symmetric A satisfies (1.32) and a positive definite B has unit diagonal. If ε = S(A, B) is sufficiently small, then for all s_{i−1} + 1 ≤ p, q ≤ s_{i} with ν_{s_{i}} > 0, 1 ≤ i ≤ r, holds

σ_{q}a_{2p−1,2q} − σ_{p}a_{2p,2q−1} = ν_{s_{i}}(b_{2p−1,2q−1} + σ_{p}σ_{q}b_{2p,2q}) + O(ε^{2}),
a_{2p−1,2q−1} + σ_{p}σ_{q}a_{2p,2q} = ν_{s_{i}}(σ_{p}b_{2p,2q−1} − σ_{q}b_{2p−1,2q}) + O(ε^{2}),
| a_{2p−1,2p} | = ν_{s_{i}} + O(ε^{2}).

If ν_{s_{r}} = 0, then ∥A_{rr}∥ = O(ε^{2}).

2 Almost Murnaghan Form

In this section we specialize the obtained result to the case B = I_{n} and then use it in connection with a method for reducing A to its Murnaghan form^{1}.

Let B = I_{n}. Then ±ıν_{s_{i}} are the the eigenvalues of the skew-symmetric matrix A with multiplicities n_{i}, 1 ≤ i ≤ r. If we denote ω_{i}(A, I_{n}) by Ω_{i}(A), 1 ≤ i ≤ r, and ω(A, I_{n}) by Ω(A), Theorem 1.8 takes the following simple form.

1A proper application of Theorem 1.8 would assume a method for simultaneous diagonalisation of A and B. In a subsequent paper [10] we shall consider such a method.

Theorem 2.1 Let A be a skew-symmetric matrix of order n satisfying the condition (1.32). If

S(A) < δ,

then

Ω_{r}(ΦAΦ) ≤ \frac{1}{δ_{r}} ∑_{j=1}^{r−1} ∥A_{rj}∥^{2}, ν_{s_{r}} = 0,  (2.1)

Ω_{i}(ΦAΦ) ≤ \frac{1}{δ_{i}} [S^{2}(A_{ii}) + ∑_{j≠i^{j=1}}^{r} ∥A_{ij}∥^{2}] , \begin{matrix}ν_{s_{i}} > 0 \\ 1 ≤ i ≤ r \end{matrix}  (2.2)

Ω(ΦAΦ) ≤ \frac{1}{\sqrt{2}δ} S^{2}(A),  (2.3)

where (A_{rj}) is the partition (1.17) of A.

Proof. Since B = I_{n} we have M = I_{n}. Therefore the inequality in (1.15) implies max{∥E_{i}∥_{2}, ∥E_{σ+1−i}∥_{2}} ≤ S(A). Hence the condition (1.11) in Lemma 1.4 can be replaced by S(A) < δ. The assertions (2.1)–(2.3) follow directly from Theorem 1.8 and by examining the proof of Lemma 1.7 with B = I_{n}.

Theorem 2.1 reveals a special structure of the skew-symmetric matrix A which is almost in Murnaghan form. This stucture was first found in [2]. Since

Ω_{i}(ΦAΦ) = ∑_{s_{i−1}+1≤p<q≤s_{i}}[(σ_{q}a_{2p−1,2q} − σ_{p}a_{2p,2q−1})^{2} + (a_{2p−1,2q−1} + σ_{p}σ_{q}a_{2p,2q})^{2}]

+ 2 ∑_{p=s_{i−1}+1}^{s_{i}} (σ_{p}a_{2p−1,2p} − ν_{s_{i}})^{2} , 1 ≤ i ≤ r, ν_{s_{i}} > 0,

Theorem 2.1 implies that for sufficiently small ε = S(A) and all s_{i−1} + 1 ≤ p, q ≤ s_{i} with ν_{s_{i}} > 0, 1 ≤ i ≤ r holds

σ_{q}a_{2p−1,2q} − σ_{p}a_{2p,2q−1} = O(ε^{2}), p ≠ q,  (2.4)
a_{2p−1,2q−1} + σ_{p}σ_{q}a_{2p,2q} = O(ε^{2}), p ≠ q,  (2.5)
| a_{2p−1,2p} | −ν_{s_{i}} = O(ε^{2}).  (2.6)

If ν_{s_{r}} = 0, the order of magnitude of any element of A_{rr} is O(ε^{2}), since Ω_{r}(ΦAΦ) = ∥A_{rr}∥. Note that the relations (2.4) and (2.5) do not force ∥A_{pq}∥ to be O(ε^{2}). In general we have ∥A_{pq}∥ = O(ε) (see Example 2.2). In the following we analyse how this fact and the relations (2.4)–(2.6) influence the asymptotic convergence of the Paardekooper method [9] for skew-symmetric matrices.

An Application to Paardekooper Method

Paardekooper method is a Jacobi-type method for reducing a skew-symmet-ric matrix to its Murnaghan form. It operates on blocks from the partition (1.1) in a similar way as the standard symmetric Jacobi method operates on matrix elements. One step of the method uses an orthogonal similarity transformation (cf. [9])

A′ = ℑ_{pq}^{T} A ℑ_{pq}, p < q,

to make A′_{pq} zero. The matrix ℑ_{pq} is called [3, 6] Jacobi annihilator of A_{pq}, and A_{pq} is called pivot submatrix. If A_{pq} is 2 × 2, then

ℑ_{pq} = R_{pq}^{1}R_{pq}^{2}R_{pq}^{3}R_{pq}^{4}, i < j,

where R_{pq}^{t}, 1 ≤ t ≤ 4, are rotation matrices. Let R(l, m; ϕ), l < m, stand for the rotation in the (l, m) plane by the angle ϕ, and with the four essential elements r_{ll} = r_{mm} = cos ϕ, r_{lm} = −r_{ml} = sin ϕ. Then (cf. [9])

\begin{matrix}R_{pq}^{1} = R(2p − 1, 2q − 1; ϕ_{1}), \\ R_{pq}^{2} = R(2p, 2q; ϕ_{2}), \end{matrix} \begin{matrix}R_{pq}^{3} = R(2p − 1, 2q; ϕ_{3}), \\ R_{pq}^{4} = R(2p, 2q − 1; ϕ_{4}). \end{matrix}

The rotation R_{pq}^{1} [R_{pq}^{3}] modifies the elements at positions (2p−1, 2q), (2p,2q − 1) [(2p−1, 2q −1), (2p, 2q)] in such a way that R_{pq}^{2} [R_{pq}^{4}] can annihilate them. The skew-simmetry property ensures that zeros obtained at positions (2p − 1, 2q), (2p, 2q − 1) are not violated by the transformations R_{pq}^{3} and R_{pq}^{4}. To simplify notation we set (cf. [9, 3]).

A_{pp} = [ \begin{matrix}0 & α \\ −α & 0 \end{matrix} ] , A_{pq} = [ \begin{matrix}x & v \\ w & y \end{matrix} ] , A_{qq} = [ \begin{matrix}0 & β \\ −β & 0 \end{matrix} ] .

Then the angles are computed from the formulas

tan 2ϕ_{1} = \frac{2(αw − βv)}{α^{2} − β^{2} + v^{2} − w^{2}} , − \frac{π}{4} ≤ ϕ_{1} ≤ \frac{π}{4} ,  (2.7)
tan ϕ_{2} = −\frac{v cos ϕ_{1} − β sin ϕ_{1}}{α cos ϕ_{1} + w sin ϕ_{1}} , − \frac{π}{2} ≤ ϕ_{2} ≤ \frac{π}{2} .  (2.8)

Suppose that A_{pp}, A_{pq} and A_{qq} are transformed by the plane rotations R_{pq}^{1} and R_{pq}^{2} (half step) into

Ã_{pp} = [ \begin{matrix}0 & α̃ \\ −α̃ & 0 \end{matrix} ] , Ã_{pq} = [ \begin{matrix}x & 0 \\ 0 & y \end{matrix} ] , Ã_{qq} = [ \begin{matrix}0 & β̃ \\ −β̃ & 0 \end{matrix} ] .

Note that x and y have not been changed. The angles ϕ_{3} and ϕ_{4} are computed from

tan 2ϕ_{3} = \frac{2(α̃y + β̃x)}{α̃^{2} − β̃^{2} + x^{2} − y^{2}} , − \frac{π}{4} ≤ ϕ_{3} ≤ \frac{π}{4} ,
tan ϕ_{4} = −\frac{x cos ϕ_{3} + β̃ sin ϕ_{3}}{α̃ cos ϕ_{3} + y sin ϕ_{3}} , − \frac{π}{2} ≤ ϕ_{2} ≤ \frac{π}{2} .

If n = 2k − 1, A_{pk} is 2 × 1. In this case only two rotations suffice to annihilate A_{pk}. The appropriate angle formulas can be found in [9, 3]. It is known (see [6]) that the row-cyclic (pivot submatrices are chosen by rows) Paardekooper method converges asymptotically quadratically, provided the eigenvalues of A are at most double. As numerical examples show (see Example 2.4) the method fails to converge quadratically when multiplicities of some eigenvalues of A are larger than two. To analyse such a behaviour we make a qualitative analysis using the estimates from Theorem 2.1. In the following lemma we consider what happens with rotations angles when S(A) shrinks to zero.

Lemma 2.2 Let the assumptions of Theorem 2.1 hold. If the pivot submatrix A_{pq} lies within a diagonal block A_{ii} for which ν_{s_{i}} > 0, then

ϕ_{1}, ϕ_{2}, ϕ_{3}, ϕ_{4} = O(1) as S(A) → 0.

Proof. Let ε = S(A). For simplicity we use notation σ_{x} for sign(x). We can assume (cf. Example 2.3) that x, y, v, w = O(ε) and α, β = O(1). From the relations (2.4)–(2.6) we have

σ_{β}v − σ_{α}w = O(ε^{2}) ⟺ v = σ_{α·β}w + O(ε^{2}),  (2.9)
x + σ_{α}σ_{β}y = O(ε^{2}) ⟺ x = −σ_{α·β}y + O(ε^{2}),  (2.10)
σ_{α}α − σ_{β}β = O(ε^{2}) ⟺ α = σ_{α·β}β + O(ε^{2}).  (2.11)

Using the relations (2.9) and (2.11) we obtain

αw − βv = [σ_{α·β}β + O(ε^{2})]w − β[σ_{α·β}w + O(ε^{2})]
= O(ε^{2}) · w − β · O(ε^{2}) = O(ε^{2}) · O(ε) + O(1) · O(ε^{2}) = O(ε^{2}),
α^{2} − β^{2} = [σ_{α·β}β + O(ε^{2})]^{2} − β^{2} = O(1) · O(ε^{2}) + O(ε^{4}) = O(ε^{2}),
v^{2} − w^{2} = [σ_{α·β}w + O(ε^{2})]^{2} − w^{2} = O(ε) · O(ε^{2}) + O(ε^{4}) = O(ε^{3}).

Using these relations in the formula (2.7) for the angle ϕ_{1} we obtain

tan 2ϕ_{1} = \frac{2(αw − βv)}{α^{2} − β^{2} + v^{2} − w^{2}} = \frac{2O(ε^{2})}{O(ε^{2}) + O(ε^{3})} = \frac{O(ε^{2})}{O(ε^{2})}.

Thus, ϕ_{1} can be small and large, hence ϕ_{1} = O(1). Using this in the formula (2.8) for the angle ϕ_{2} we obtain

tan ϕ_{2} = −\frac{v cos ϕ_{1} − β sin ϕ_{1}}{α cos ϕ_{1} + w sin ϕ_{1}} = \frac{O(ε) · O(1) + O(1) · O(1)}{O(1) · O(1) + O(ε) · O(1)} = \frac{O(1)}{O(1)}.

Again, we can conclude that ϕ_{2} = O(1). In a similar way, using the relations (2.10) and (2.11) (after replacing α and β by α̃ and β̃, respectively) we can show that ϕ_{3}, ϕ_{4} = O(1). This conclusion is valid since affiliation^{2} of the diagonal blocks is preserved after each half step (see [6, Lemma 2.1]).

From the proof of Lemma 2.2 we also conclude that in the presence of multiple eigenvalues the formulas for tan ϕ_{1} and tan ϕ_{3} are prone to loss of significance errors.

Example 2.3 We have generated skew-symmetric matrix A of order 8 from the Murnaghan form M whose nontrivial entries are 1, 1, 1, 2 by the following orthogonal similarity transformation

A = R(2, 8, arcsin t)^{T} R(5, 7, arcsin t)^{T} P^{T} MP R(5, 7, arcsin t)R(2, 8, arcsin t).

2Block A_{pp} is affiliated with ıν_{j} (or simply with ν_{j}) if || a_{2p−1,2p} | −ν_{j} |< δ

Here

P = \frac{1}{\sqrt{1 + t^{2}}} [ \begin{matrix}0 & 1 & 0 & 0 & 0 & 0 & 0 & −t \\ 1 & 0 & 0 & 0 & 0 & −t & 0 & 0 \\ 0 & 0 & 0 & 1 & −t & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & −t & 0 \\ 0 & 0 & 0 & t & 1 & 0 & 0 & 0 \\ t & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & t & 0 & 0 & 0 & 1 & 0 \\ 0 & t & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} ] .

Hence in the partition (1.17) of A we have r = 2 and

A_{11} = [ \begin{matrix}0 & −\frac{\sqrt{1−t^{2}}+t^{2}}{1+t^{2}} & 0 & −\frac{t^{2}}{1+t^{2}} & −\frac{t\sqrt{1−t^{2}}}{1+t^{2}} & 0 \\ & 0 & \frac{2t^{2}(1−\sqrt{1−t^{2}})}{1+t^{2}} & 0 & \frac{2t^{2}(\sqrt{1−t^{2}}−1)}{1+t^{2}} & −^{\frac{t(\sqrt{1−t^{2}}+t^{2})}{1+t^{2}}} \\ & & 0 & −\frac{1}{1+t^{2}} & \frac{t\sqrt{1−t^{2}}}{1+t^{2}} & 0 \\ & & & 0 & \frac{t^{2}}{1+t^{2}} & \frac{t}{1+t^{2}} \\ & & skew-sym. & & 0 & \frac{\sqrt{1−t^{2}}}{1+t^{2}} \\ & & & & & 0 \end{matrix} ] ,

A_{12} = [ \begin{matrix}−\frac{t^{2}}{1+t^{2}} & \frac{t(\sqrt{1−t^{2}}−1)}{1+t^{2}} \\ \frac{2t\sqrt{1−t^{2}}(1−\sqrt{1−t^{2}})}{1+t^{2}} & 0 \\ \frac{t^{2}}{1+t^{2}} & \frac{2t(\sqrt{1−t^{2}}+t^{2})}{1+t^{2}} \\ −\frac{t\sqrt{1−t^{2}}}{1+t^{2}} & 0 \\ \frac{t^{2}}{1+t^{2}} & −^{\frac{2t(\sqrt{1−t^{2}}+t^{2})}{1+t^{2}}} \\ −\frac{t}{1+t^{2}} & \frac{t^{2}(1−\sqrt{1−t^{2}})}{1+t^{2}} \end{matrix} ] , A_{22} = [ \begin{matrix}0 & \frac{2\sqrt{1−t^{2}}(\sqrt{1−t^{2}}+t^{2})}{1+t^{2}} \\ skew-s. & 0 \end{matrix} ] .

Note that δ = 1/3 and S(A) = O(t) as t → 0. Hence the condition S(A) < δ is fulfilled for sufficiently small t. Under that condition we see that A_{11}, A_{22}, A_{33} and A_{44} are affiliated with the eigenvalues 1 and 2, respectively. Note that ∥A_{13}∥, ∥A_{23}∥ = O(t), and that the relations (2.9)—(2.11) are satisfied for 2 × 2 blocks of A_{11}.

Suppose, we apply the row-cyclic Paardekooper method to A. By A^{(r)} = (a_{ij}^{(r)}) we denote the matrix obtained from A after r rotational transformations and by ϕ_{pq} the angle used in the (p, q) plane. We also denote tan ϕ_{pq}, sin ϕ_{pq} and cos ϕ_{pq} by t_{pq}, s_{pq} and c_{pq}, respectively.

Because of the row-cyclic strategy the first pivot submatrix is A_{12}. From the formula (2.7) we obtain

tan 2ϕ_{13} = 2\frac{−(\sqrt{1 − t^{2}} + t^{2}) · 2t^{2}(1 − \sqrt{1 − t^{2}}) − t^{2} · 1}{[(\sqrt{1 − t^{2}} + t^{2})^{2} − 1^{2}] + [t^{4} − 4t^{4}(1 − \sqrt{1 − t^{2}})^{2}]} = −2 + O(t^{4}),

whence

t_{13} = \frac{1 − \sqrt{5}}{2} + O(t^{4}), c_{13} = \begin{matrix}√ & \overline{2} \\ √ & \overline{5 − \sqrt{5}} \end{matrix} + O(t^{4}), s_{13} = −\begin{matrix}√ & \overline{3 − \sqrt{5}} \\ √ & \overline{5 − \sqrt{5}} \end{matrix}. + O(t^{4}).

(2.12)

Using the relations (2.8) and (2.12) we obtain

t_{24} = \frac{t^{2}c_{13} − s_{13}}{−(\sqrt{1 − t^{2}} + t^{2})c_{13} + 2t^{2}(1 − \sqrt{1 − t^{2}})s_{13}} = \frac{1 − \sqrt{5}}{2} + O(t^{2}),

whence

c_{24} = \begin{matrix}√ & \overline{2} \\ √ & \overline{5 − \sqrt{5}} \end{matrix} + O(t^{2}), s_{24} = −\begin{matrix}√ & \overline{3 − \sqrt{5}} \\ √ & \overline{5 − \sqrt{5}} \end{matrix} + O(t^{2}).  (2.13)

Note that ϕ_{14} = ϕ_{23} = 0, since a_{13} = a_{24} = 0. By the relations (2.12) and (2.13) we have

a_{16}^{(4)} = 0, a_{56}^{(4)} = a_{56} = \frac{\sqrt{1 − t^{2}}}{1 + t^{2}} ,  (2.14)
a_{25}^{(4)} = \frac{2t^{2}(\sqrt{1 − t^{2}} − 1)c_{24} − t^{2}s_{24}}{1 + t^{2}} = \begin{matrix}√ & \overline{3 − \sqrt{5}} \\ √ & \overline{5 − \sqrt{5}} \end{matrix}t^{2} + O(t^{4}),  (2.15)

a_{35}^{(4)} = \frac{t\sqrt{1 − t^{2}}(c_{13} − s_{13})}{1 + t^{2}} = \frac{\sqrt{2} + \sqrt{3 − \sqrt{5}}}{\sqrt{5 − \sqrt{5}}}t + O(t^{3}),  (2.16)

a_{12}^{(4)} = (a_{12}c_{13} + a_{23}s_{13})c_{24} − (a_{14}c_{13} − a_{34}s_{13})s_{24} = −1 + \frac{5 − 2\sqrt{5}}{5 − \sqrt{5}}t^{2} + O(t^{4}).

(2.17)

Hence, after the annihilation of A_{12} we have A_{23} = O(t). Because of the rowcyclic strategy A_{13}^{(4)} is the next pivot submatrix. Using the relations (2.7), (2.14), (2.15) and (2.17) we have

tan 2ϕ_{15} = \frac{2(a_{12}^{(4)}a_{25}^{(4)} − a_{56}^{(4)}a_{16}^{(4)})}{(a_{12}^{(4)})^{2} − (a_{56}^{(4)})^{2} + (a_{16}^{(4)})^{2} − (a_{25}^{(4)})^{2}} = −\frac{4\sqrt{5 − 2\sqrt{5}}}{5 + \sqrt{5}} + O(t^{2}),

whence

s_{15} = \frac{5 + \sqrt{5} − \sqrt{22(5 − \sqrt{5})}}{\sqrt{44(5 − \sqrt{5}) − 2(5 + \sqrt{5})\sqrt{22(5 − \sqrt{5})}}} + O(t^{2})  (2.18)

Note that a_{13}^{(4)} = 0. Hence, the relations (2.16) and (2.18) imply

a_{13}^{(5)} = a_{13}^{(4)}c_{15} + a_{35}^{(4)}s_{15} = a_{35}^{(4)}s_{15}
= \frac{\sqrt{2} + \sqrt{3 − \sqrt{5}}}{\sqrt{5 − \sqrt{5}}} · \frac{5 + \sqrt{5} − \sqrt{22(5 − \sqrt{5})}}{\sqrt{44(5 − \sqrt{5}) − 2(5 + \sqrt{5})\sqrt{22(5 − \sqrt{5})}}} t + O(t^{3}).

Since S(A) = O(t), we see that contributions to A_{12}^{(4)} (comming from the later rotations) can be of order S(A).

Let us now argue the failure of the quadratic convergence of the row-cyclic Paardekooper method. Let the assumptions of Theorem 2.1 hold. Suppose ν_{s_{1}} = 3 so that A_{11} has order 6. After the annihilation of A_{12} we have A′_{12} = O i.e.

A_{11} = [ \begin{matrix}A_{11} & A_{12} & A_{13} \\ A_{21} & A_{22} & A_{23} \\ A_{31} & A_{32} & A_{33} \end{matrix} ] , A′_{11} = [ \begin{matrix}A′_{11} & O & A′_{13} \\ O & A′_{22} & A′_{23} \\ A′_{31} & A′_{32} & A_{33} \end{matrix} ] .

Because of the row-cyclic strategy A′_{13} is the pivot submatrix. Since affiliation of the diagonal blocks is preserved, Lemma 2.2 shows that some angles involved in ℑ_{13} can be large. When A′_{13} is annihilated, the zero block in A′_{11} gets a contribution from the elements of A′_{23}. Since in general ∥A′_{23}∥ = O(ε) (see Example 2.3) where ε = S(A) , the contribution to the zero block can be O(ε). This shows that there might be a 2 x 2 submatrix which comes back to its former order of magnitude after annihilation. And this contradicts to the basic concept which ensures the quadratic convergence.

In the following numerical example, computation has been done on VAX 6000 Model 500 using quadruple precision eps ≈ 9.63x10^{−35}.

Example 2.4 We have generated a skew-symmetric matrix A of order 32 from the Murnaghan form whose nontrivial entries are 2,2,2,2,2,2,2,2, 1,1,1,1, 1,1,1,1 by a series of about 2.5n^{2} similarity transformations with plane rotations. In the matrix generation we have used the row-cyclic ordering and the sines of the rotation angles ϕ are randomly chosen from the interval [−1/400, 1/400] (cos ϕ have been computed by the formula \sqrt{1 − sin^{2} ϕ}). This angle choice ensures that A is almost in Murnaghan form. Obviously, δ = 1/3 up to the arithmetic precision. Since S(A) ≈ 0.2332 (see the table below), the condition S(A) < δ is fulfilled. We have checked that A_{11}, …, A_{88} and A_{99}, …, A_{16,16} are affiliated with 2 and 1, respectively. We have applied the row-cyclic Paardekooper method to A. In the following table we list for each of the first 10 cycles S(A) and for all angles ϕ_{1}, ϕ_{2}, ϕ_{3}, ϕ_{4} (measured in radians), the largest value encountered during the cycle.

cycle  S(A)  max_{cycle} ϕ_{1} max_{cycle} ϕ_{2} max_{cycle} ϕ_{3} max_{cycle} ϕ_{4}
0 2.332 · 10^{−1}
1 4.424 · 10^{−2}  0.7795  0.7833  0.7281  0.7317
2 4.987 · 10^{−3}  0.7813  0.7807  0.5799  0.5801
3 1.020 · 10^{−3}  0.7790  0.7790  0.6793  0.6793
4 2.369 · 10^{−6}  0.7595  0.7595  0.6063  0.6064
5 1.407 · 10^{−7}  0.6067  0.6067  0.5649  0.5649
6 5.139 · 10^{−11} 0.7380  0.7380  0.7582  0.7582
7 8.382 · 10^{−13} 0.7854  0.7854  0.4386  0.4386
8 6.091 · 10^{−16} 0.7854  0.7854  0.3037  0.3073
9 8.355 · 10^{−17} 0.7854  0.7854  0.7732  0.7732
10 1.780 · 10^{−17} 0.7854  0.7854  0.7854  0.7854

This table clearly shows the failure of the quadratic convergence of the row-cyclic Paardekooper method. It also confirms the assertions of Lemma 2.2.

The failure of the quadratic convergence and possible angle determination instabilities in the presence of nonzero eigenvalues whose multiplicities are greater than two suggests a possible modification of the Paardekooper method in order to restore the quadratic convergence. A modified Paardekooper method in this direction is proposed in [2] and its quadratic convergence proved under a general cyclic strategy. The work [10] on an improved modified algorithm which can be extended to cope with the pair (A, B) where B is positive definite is in progress.

References

[1] K. K. Gupta: On a Combined Strum Sequence and Inverse Iteration Technique for Eigenproblem of Spinning Structures, International Journal for Numerical Methods in Engineering 7: 509–518 (1973).

[2] V. Hari: Convergence of the Paardekooper Method for Diagonalization of Skewsymmetric matrices, M.S.Thesis, University of Zagreb, 1980 (Croatian language).

[3] V. Hari: On Quadratic Convergence of the Paardekooper Method I, Glasnik Matematički 67: 183–195, 1982.

[4] V. Hari: On Pairs of Almost Diagonal Matrices. Linear Algebra and Its Applications 148: 193–223, 1991.

[5] V. Hari: On Sharp Quadratic Convergence Bounds for the Serial Jacobi Methods, Numeri. Math. 60: 375–406, 1991.

[6] V. Hari and N. H. Rhee: On Quadratic Convergence of the Paardekooper Method II, Technical Report, University of Zagreb, 1992.

[7] A. J. Hoffman and H. W. Wielandt: The Variation of the Spectrum of a Normal Matrix, Duke Math. J. 20: 37–39, 1953.

[8] F. D. Murnaghan and A. Winter: A Canonical Form for Real Matrices under Orthogonal Transformations, USA Nat. Acad. Sci. 17: 417–420, 1931.

[9] M. H. C. Paardekooper: An Eigenvalue Algorithm for Skew-symmetric Matrices, Numer.Math. 17: 189–202, 1971.

[10] N. H. Rhee and V. Hari: A Block-Jacobi Method for Simultaneous Diagonalization of Skew-Symmetric and Symmetric Positive Definite Matrix. In preparation.

[11] R. A. Rosanoff et al. : Numerical Conditions of Stiffness Matrix Formulations for Frame Structures, Proceedings of the 2nd Conference on Matrix Methods in Structural Mechanics, WPAFB Dayton, Ohio, 1968.

[12] J. H. Wilkinson: Almost Diagonal Matrices with Multiple or Close Eigenvalues. Linear Algebra and Its Applications 1: 1–12, 1968.