A short note on the ratio between sign-real and sign-complex spectral radius of a real square matrix

A short note on the ratio between sign-real and sign-complex spectral radius of a real square matrix

Linear Algebra and its Applications 529 (2017) 126–132 Contents lists available at ScienceDirect Linear Algebra and its Applications www.elsevier.co...

264KB Sizes 1 Downloads 24 Views

Linear Algebra and its Applications 529 (2017) 126–132

Contents lists available at ScienceDirect

Linear Algebra and its Applications www.elsevier.com/locate/laa

A short note on the ratio between sign-real and sign-complex spectral radius of a real square matrix Florian Bünger Institute for Reliable Computing, Hamburg University of Technology, Am Schwarzenberg-Campus 3, Hamburg 21071, Germany

a r t i c l e

i n f o

Article history: Received 11 April 2017 Accepted 19 April 2017 Available online 24 April 2017 Submitted by V. Mehrmann MSC: 15A42 15A18

a b s t r a c t For a real (n × n)-matrix A the sign-real and the sign-complex spectral radius – invented by Rump – are respectively defined as ρR (A) := max{|λ| | |Ax| = |λx|, λ ∈ R, x ∈ Rn \{0}}, ρC (A) := max{|λ| | |Ax| = |λx|, λ ∈ C, x ∈ Cn \{0}}.

Keywords: Sign-real spectral radius Sign-complex spectral radius Spectral radius Eigenvalue inequalities

For n ≥ 2 we prove ρR (A) ≥ ζn ρC (A) where the constant  1 − cos(π/n) ζn := is best possible. 1 + cos(π/n) © 2017 Elsevier Inc. All rights reserved.

1. Introduction Let n ∈ N := {1, 2, . . . } and K ∈ {R, C}. For a square matrix A ∈ Kn,n the so-called generalized spectral radius is defined by ρK (A) := max{|λ| | |Ax| = |λx|, λ ∈ K, x ∈ Kn \{0}}.1

1

E-mail address: fl[email protected] The equality |Ax| = |λx| is meant componentwise.

http://dx.doi.org/10.1016/j.laa.2017.04.022 0024-3795/© 2017 Elsevier Inc. All rights reserved.

(1)

F. Bünger / Linear Algebra and its Applications 529 (2017) 126–132

127

For K = R it is called sign-real and for K = C sign-complex spectral radius. The generalized spectral radius was invented and investigated by Rump [3–8].2 The new concept was used and extended, for example, by Goldberger and Neumann [1], Peña [2], Varga [9], Zalar [10], and Zangiabadi and Afshin [11,12]. Rump gave many equivalent definitions of the generalized spectral radius, e.g. the Max–Min-characterization [8], Theorem 2.4: ρK (A) =

max

min

x∈Kn \{0} xi =0

|(Ax)i | . |xi |

(2)

Here we are interested in bounding the ratio ρR (A)/ρC (A) between sign-real and sign-complex spectral radius from below independent of a specific real A, i.e., we are searching for the maximum constant ζn ∈ R≥0 that fulfills ρR (A) ≥ ζn ρC (A) for all A ∈ Rn,n .

(3)

First, note that the one-dimensional case n = 1 is trivial since sign-real and sign-complex spectral radius of a real (1 × 1)-matrix coincide. Therefore we will assume n ≥ 2 from now on. Next, note that bounding the ratio ρR (A)/ρC (A) from above yields 1 as best possible upper bound since by definition ρR (A) ≤ ρC (A) and ρR (A) = ρC (A) for real diagonal matrices A. In [8], Theorem 6.1, Rump proved that the skew-symmetric Toeplitz matrix ⎛

0

⎜ ⎜ −1 A := (sign(j − i))1≤i,j≤n = ⎜ . ⎝ . . −1

1 .. . ..

. ...

... .. . .. −1

.

⎞ 1 .. ⎟ .⎟ ⎟ ⎠ 1 0

(4)

has sign-real spectral radius ρR (A) = 1 and sign-complex spectral radius  sin(π/n) = ρ (A) = ρ(A) = A2 = 1 − cos(π/n) C

1 + cos(π/n) =: ζn−1 , 1 − cos(π/n)

(5)

where ρ(A) denotes the common spectral radius, i.e., the maximum modulus of all eigenvalues. Thus ρR (A)/ρC (A) = 1/ρC (A) = ζn for the matrix in (4) and n ≥ 2. The main goal of this short note is to prove that ζn as defined in (5) fulfills (3). This is demonstrated in the following main theorem: Theorem 1. For n ∈ N≥2 and every A ∈ Rn,n we have ρR (A) ≥ ζn ρC (A) 2

R The notation of the sign-real spectral radius changes from ρS 0 (A) in earlier papers to ρ (A).

(6)

F. Bünger / Linear Algebra and its Applications 529 (2017) 126–132

128

where  ζn :=

1 − cos(π/n) ∈ 1 + cos(π/n)



1.5 2 , . n n

(7)

The constant ζn is best possible for all n ≥ 2. 2. Proof of Theorem 1 Theorem 1 will follow from the next three lemmas. Lemma 2. For n ∈ N≥2 and ξ := cos

π n

we have ζ :=

1−ξ 1+ξ



 1.5 n

 , n2 .

Proof. For n = 2 we have ξ= 0 and ζ = 1 ∈ [0.75, 1] = [1.5, 2]/n. For n = 3 we have ξ = cos(π/3) = 0.5 and ζ = 1/3 ∈ [1/2, 2/3] = [1.5, 2]/n. Now, let n ≥ 4. The function −2  f : [0, 1] → R, z → 1−z 1+z has derivative f (z) = (1+z)2 < 0 and is therefore monotonically decreasing. For x := π/n the Taylor series expansion of the cosine supplies the ξ-inclusion 2 2 4 ξ1 := 1 − x2 ≤ ξ ≤ 1 − x2 + x24 =: ξ2 . Thus, ζ 2 = f (ξ) ≤ f (ξ1 ) = =

2−

x2 2

=

4 x2

1 = −1

4 π2

1 −

1 n2

·

1 ≤ n2

1 16 4 · ≤ 2 , (8/π)2 − 1 n2 n x2 2



4 π2

1 −

1 16

·

1 n2 (8)

x4 24

1 1 1 · 2 = 4 4 1 n 2− + − 2 2 − 1 π2 n x2 1 − x12 π 2 1 − 12n 2     π2 1 π2 1 π2 π2 2.25 1− · 1 − · 2 ≥ 2 . ≥ ≥ (9) 4 12n2 n2 4 12 · 16 n n

ζ = f (ξ) ≥ f (ξ2 ) = 2

x2 2

x2 2

x4 24

=

Taking square roots, (8) and (9) imply the assertion. 2 Lemma 3. Let ri , si ∈ R2 , i ∈ I := {1, . . . , n}, be a collection of n pairs of vectors in the Euclidean plane. Define J := {i ∈ I | ri = 0 = si } and suppose that the undirected  angles ωj ∈ [0, π] for j ∈ J between rj and sj fulfill j∈J ωj ≤ π. Then there exists a unit vector y ∈ R2 such that (riT y)(sTi y) ≥ 0

for all i ∈ I.

(10)

In other words, each pair ri , si lies either in the left or in the right closed half space with separating line L := {x ∈ R2 | xT y = 0} having normal vector y.

F. Bünger / Linear Algebra and its Applications 529 (2017) 126–132

129

Proof. Condition (10) clearly holds true for all i ∈ I\J and arbitrary y. The union of the open double cones Cj := {x ∈ R2 | (rjT x)(sTj x) < 0}, j ∈ J, contains non-closed arc   lines on the unit circle S of total arc length j∈J 2ωj ≤ 2π. Thus S  := S\ j∈J Cj = ∅, and any y ∈ S  fulfills (10). 2 Lemma 4. Let A ∈ Rn,n , n ≥ 2, λ ∈ C\{0}, and u, v ∈ Rn such that w = u + iv = 0 and √ |Aw| = |λw|, where i := −1. Then there are α, β ∈ R such that x = αu + βv = 0 and  |Ax| ≥

1 − cos(π/n) · |λx| , 1 + cos(π/n)

(11)

whereby this inequality is meant componentwise. Proof. If u, v are linearly dependent, then w = ηz for some z ∈ {u, v}\{0} and η ∈ C\{0}, so that |Az| = |λz|. Thus (11) holds true for x := z since 1−cos(π/n) 1+cos(π/n) ≤ 1 by Lemma 2. Thus we can assume that u, v are linearly independent. Since λ = 0 we can divide A by |λ| in order to assume also that |λ| = 1. Then Aw = Sw for a complex diagonal matrix S with |S| = I, where I denotes the (n × n)-identity matrix. Decomposing S into real and imaginary part gives S = P + iQ, P = diag(ϕ1 , . . . , ϕn ), Q = diag(ψ1 , . . . , ψn ) ∈ Rn,n , P 2 + Q2 = |S|2 = I, i.e., ϕ2k + ψk2 = 1 for all k = 1, . . . , n. From Au + iAv = Aw = Sw = (P u − Qv) + i(Qu + P v) it follows that M := (Au, Av) = (P u − Qv, Qu + P v) ∈ Rn,2 . Thus, for arbitrary y := (α, β)T ∈ R2 \{0} we have x := (u, v)y = αu + βv ∈ Rn \{0} and Ax = M y. Set ξ := cos nπ and ζ := 1−ξ 1+ξ ∈ (0, 1], see Lemma 2. The inequality |Ax| ≥ ζ|x|, which we have to prove, holds true if, and only if, ((Ax)k + ζxk )((Ax)k − ζxk ) = (Ax)2k − ζ 2 x2k ≥ 0

(12)

for all k = 1, . . . , n. Condition (12) is equivalent to 0 ≤ ((Ax)k + ζxk )((Ax)k − ζxk ) = [(M + ζ(u, v))y]k [(M − ζ(u, v))y]k . For fixed k ∈ {1, . . . , n} let a := ak := (Mk,1 , Mk,2 ) = (ϕk uk − ψk vk , ψk uk + ϕk vk ) be the k-th row of M and b := bk := (uk , vk ) the k-th row of (u, v). Then,

(13)

F. Bünger / Linear Algebra and its Applications 529 (2017) 126–132

130

a22 = b22 = u2k + vk2 ,

(14)

abT = ϕk (u2k + vk2 ), a ±

ζb22

=

a22



2

b22

(15) ± 2ζab = (1 + ζ ± T

2

2ζϕk )(u2k

+

vk2 ),

(a + ζb)(a − ζb)T = a22 − ζ 2 b22 = (1 − ζ 2 )(u2k + vk2 ).

(16) (17)

Define r := rk := (a + ζb)T and s := sk := (a − ζb)T and suppose that r = 0 = s. From (16) and (17) it follows that the cosine of the undirected angle ω = ωk ∈ [0, π] between r and s computes as3 cos(ω) =

π  (a + ζb)(a − ζb)T 1 − ζ2 1 − ζ2 . = ≥ = ξ = cos a + ζb2 a − ζb2 1 + ζ2 n (1 + ζ 2 )2 − 4ζ 2 ϕ2k

This implies ω ∈ [0, π/n]. Hence, for J := {k ∈ {1, . . . , n} | rk = 0 =  sk } we proved  2 k∈J ωk ≤ |J| π/n ≤ π. Therefore, Lemma 3 supplies a unit vector y ∈ R such that (13) holds true for all k ∈ {1, . . . , n}. 2 For proving Theorem 1 take some A ∈ Rn,n , n ≥ 2, and choose λ ∈ C and w ∈ Cn \{0} such that |Aw| = |λw| and |λ| = ρC (A). If λ = 0, then clearly (6) holds true. If λ = 0, then Lemma 4 and (2) with K = R also yield (6). The constant ζn is best possible for all n ≥ 2 because the matrix A := (sign(j − i))1≤i,j≤n stated in (4) fulfills (6) with equality.   2 Finally, the inclusion ζn ∈ 1.5 n , n stated in (7) was established in Lemma 2. 2 3. Conclusions Corollary 5. For n ≥ 2 and ζn as defined in (7) we have νn := max{μ ∈ R | ρR (A) ≥ μ ρ(A)

for all A ∈ Rn,n } = ζn ,

(18)

where ρ(A) denotes the common spectral radius of A. Proof. Theorem 1 says ζn = max{μ ∈ R | ρR (A) ≥ μ ρC (A) for all A ∈ Rn,n }. By (1), ρC ≥ ρ holds true so that ζn ≤ νn . On the other hand, the matrix A stated in (4) fulfills ρR (A) = 1 and ρ(A) = ζn−1 , see (5), so that ζn = ρR (A)/ρ(A) ≥ νn . 2 We close with listing sharp enclosures for all ratios x/y, x, y ∈ {ρ, ρR , ρC }, x = y.4 3

This inequality indicates that purely imaginary eigenvalues (P = 0) are somehow the worst case. Since x/y ∈ [a, b] for 0 ≤ a < b ≤ +∞ is equivalent to y/x ∈ [b−1 , a−1 ] with 1/0 := +∞ and 1/ +∞ := 0 it suffices to state only one of these reciprocal pairs. 4

F. Bünger / Linear Algebra and its Applications 529 (2017) 126–132

131

Remark 6. For n ≥ 2 and ζn as defined in (7) the following inclusions hold true: a) b) c)

ρR (A) ∈ [ζn , 1] ρC (A) ρ(A) ∈ [0, ζn−1 ] ρR (A) ρ(A) ∈ [0, 1] ρC (A)

with convention

0 0

for all A ∈ Rn,n , for all A ∈ Rn,n , for all A ∈ Cn,n ,

:= 1. All stated intervals are as tight as possible.

Proof. The stated inclusions follow from ρ, ρR ≤ ρC (see (1)), Theorem 1, Corollary 5, and [8], Theorem 3.3. The latter says that ρK (A) = 0 for A ∈ Kn,n , K ∈ {R, C}, if, and only if, A is acyclic, i.e., it is permutationally similar to a strictly upper triangular matrix. In particular this means that ρK (A) = 0 implies ρ(A) = 0 and, if A is real, ρR (A) = 0, if, and only if, ρC (A) = 0. Thus, if one of the denominators in a), b), c) is zero, then also the numerator is zero so that by convention the ratio becomes 00 = 1 ≤ ζn−1 , see (7). Furthermore, the matrix A stated in (4) fulfills matrix I satisfies ρ(I) = ρR (I) = ρC (I) = 1 so that  A :=

1 1

−1 −1

ρR (A) ρC (A) ρR (I) ρC (I)

ρR (A) ρ(A) and the identity ρ(I) . Finally, for ρC (I)

= ζn = =1=



we have ρC (A) = ρR (A) = 2 and ρ(A) = 0, cf. [3], p. 15. Padding with zeros this remains ˆ ˆ A) ρ(A) true for the extended (n × n)-matrix Aˆ := diag(A, 0n−2 ) so that ρρ( R (A) ˆ = 0 = ρC (A) ˆ . This shows that all interval bounds in a), b), c) are attained. 2 Acknowledgements I thank Prof. S.M. Rump for fruitful comments and suggestions. References [1] A. Goldberger, M. Neumann, Perron–Frobenius theory of seminorms: a topological approach, Linear Algebra Appl. 399 (2005) 245–284. [2] J. Peña, A characterization of the distance to infeasibility under block-structured perturbations, Linear Algebra Appl. 370 (2003) 193–216. [3] S.M. Rump, Theorems of Perron–Frobenius type for matrices without sign restrictions, Linear Algebra Appl. 266 (1997) 1–42. [4] S.M. Rump, Almost sharp bounds for the componentwise distance to the nearest singular matrix, Linear Multilinear Algebra 42 (1997) 93–107. [5] S.M. Rump, Bounds for the componentwise distance to the nearest singular matrix, SIAM J. Matrix Anal. Appl. 18 (1) (1997) 83–103. [6] S.M. Rump, The sign-real spectral radius and cycle products, Linear Algebra Appl. 279 (1998) 177–180.

132

F. Bünger / Linear Algebra and its Applications 529 (2017) 126–132

[7] S.M. Rump, Variational characterizations of the sign-real and the sign-complex spectral radius, Electron. J. Linear Algebra 9 (2002) 112–117. [8] S.M. Rump, Perron–Frobenius theory for complex matrices, Linear Algebra Appl. 363 (2003) 251–273. [9] R.S. Varga, Matrix Iterative Analysis, Springer-Verlag, Berlin, Heidelberg, 2009. [10] B. Zalar, Linear operators preserving the sign-real spectral radius, Linear Algebra Appl. 301 (1999) 99–112. [11] M. Zangiabadi, H.R. Afshin, A new concept for numerical radius: the sign-real numerical radius, U.P.B. Sci. Bull., Ser. A 76 (3) (2014) 91–98. [12] M. Zangiabadi, H.R. Afshin, Perron–Frobenius theory on the numerical range for some classes of real matrices, J. Mahani Math. Res. Cent. 2 (2) (2013) 1–15.