Advanced
ON POSITIVE SEMIDEFINITE PRESERVING STEIN TRANSFORMATION
ON POSITIVE SEMIDEFINITE PRESERVING STEIN TRANSFORMATION
Journal of Applied Mathematics & Informatics. 2015. Jan, 33(1_2): 229-234
Copyright © 2015, Korean Society of Computational and Applied Mathematics
  • Received : July 17, 2014
  • Accepted : October 18, 2014
  • Published : January 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
YOON J. SONG

Abstract
In the setting of semidefinite linear complementarity problems on S n , we focus on the Stein Transformation SA ( X ) := X AXAT for A R n × n that is positive semidefinite preserving and show that such transformation is strictly monotone if and only if it is nondegenerate. We also show that a positive semidefinite preserving SA has the Ultra-GUS property if and only if 1 ∉ σ ( A ) σ ( A ). AMS Mathematics Subject Classifiation : 90C33, 93D05.
Keywords
1. Introduction
In this paper, we focus on the so-called semidefinite linear complementarity problem (SDLCP) introduced by Gowda and Song [4] : Let S n denote the space of all real symmetric n × n matrices, and
PPT Slide
Lager Image
be the set of symmetric positive semidefinite matrices in S n . With the inner product defined by ⟨ Z, W ⟩ := tr ( Z W ), ∀ Z , W S n , the space S n becomes a Hilbert space. Clearly,
PPT Slide
Lager Image
is a closed convex cone in S n . Given a linear transformation L : S n S n and a matrix Q S n , the semidefinite linear complementarity problem , denoted by SDLCP( L, Q ), is the problem of finding a matrix X S n such that
PPT Slide
Lager Image
Specializing L to the Stein transformation SA ( X ) := X AXAT , various authors tried to characterize GUS -property in terms of the matrix A R n × n . The most recent result is by Balaji [1] when A is a 2 × 2 matrix. When we translate the statements of Theorem 6 of [1] to SA : S 2 S 2 , then SA is GUS if and only if I ± A is positive semidefinite. However, Tao [14] showed that this is not true in general (see Example 4.1 of [14] ). The results of this paper states that when SA is positive semidefinite preserving, then SA is Ultra-GUS if and only if I ± A is positive definite.
We list out needed definitions below.
  • (a) A matrixM∈Rn×nis called
  • –positive semidefiniteif ⟨Mx, x⟩ ≥ 0 for allx∈Rn. IfMis symmetric positive semidefinite, we use the notationM≽ 0. The notationM≼ 0 means −M≽ 0. Note that a nonsymmetric matrixMis positive semidefinite if and only if the symmetric matrixM+MTis positive semidefinite.
  • –positive definiteif ⟨Mx, x⟩ > 0 for all nonzerox∈Rn. IfMis symmetric positive definite, we use the notationM≻ 0.
  • Definition of various properties below are from[4],[13],[14],[2],[8],[7],[9],[6]. A linear transformationL:Sn→Snhas the
  • (b)P-property if [XL(X) =L(X)X≼ 0] ⇒X= 0
  • (c)Globally Uniquely Solvable (GUS)-property if for allQ∈Sn, SDLCP(L, Q) in (1) has a unique solution.
  • (d) A linear transformationL:Sn→Snis calledmonotoneif ⟨L(X),X⟩ ≥ 0 ∀X∈Sn;strictly monotoneif ⟨L(X),X⟩ > 0 for all nonzeroX∈Sn.
  • (e) A linear transformationL:Sn→Snis calledcopositve onif ⟨L(X),X⟩ ≥ 0 ∀X≽ 0;strictly copositive onif ⟨L(X),X⟩ > 0 for all nonzeroX≽ 0.
  • (f) A linear transformationL:Sn→Snis said to have theCone-Gus-propertyif for allQ≽ 0, SDLCP(L, Q) has a unique solution.
  • (g)P′2-propertyif [X≽ 0;XL(X)X≼ 0] ⇒X= 0.
  • (h)P2-propertyif [X, Y≽ 0; (X−Y)L(X−Y)(X+Y) ≼ 0] ⇒X= 0.
  • (i)nondegenrateif [XL(X) =L(X)X= 0] ⇒X= 0.
  • (j)Z-propertyif [X, Y≽ 0; ⟨X, Y⟩ = 0] ⇒ ⟨X,L(X)⟩ ≤ 0.
  • (k)Lyapunov-likeif bothLand −Lhave theZ-property.
  • (l)positive semidefinite preservingif
  • (m) Ultra-T-property if and only ifand all its principal subtransformations have theTproperties where
PPT Slide
Lager Image
  • (n) Corresponding to anyα⊆ {1, 2, · · · ,n}, we define a linear transformationLαα:S|α|→S|α|by
PPT Slide
Lager Image
  • where, corresponding toZ∈S|α|,X∈Snis the unique matrix such thatXαα=Zandxij= 0 for all (i, j) ∉α×α.We call Lααthe principal subtransformation of L corresponding to α.
Next, we list out some well known matrix theoretic properties that are needed in the paper [10] .
  • (a)X≽ 0 ⇒UXUT≽ 0 for any orthogonal matrixU.
  • (b)X≽ 0,Y≽ 0 ⇒ ⟨X, Y⟩ ≥ 0.
  • (c)X≽ 0,Y≽ 0, ⟨X, Y⟩ = 0 ⇒XY=YX= 0.
  • (d)X∈Sn, ⟨X, Y⟩ ≥ 0 ∀Y≽ 0 ⇒X≽ 0. This says that the coneis self-dual.
  • (e) GivenXandYinSnwithXY=YX. there exist an orthogonal matrixU, diagonal matricesDandEsuch thatX=UDUTandY=UEUT.
Finally, we state the known results (interpreting for the case of L = SA ) that are necessary for the paper. In the following and throughout the paper, σ ( A ) denotes the spectrum of A , the set of all eigenvalues of an n × n matrix A ; and ρ ( A ) denotes the spectral radius of A , the maximum distance from the origin to an eigenvalue of A in the complex plane.
  • (a) Example 3 of[8]: ForA∈Rn×n,SAhas theZ-property .
  • (b) Theorem 11 of[3]:ρ(A) < 1 ⇔SA∈Q⇔SA∈P
  • (c) Theorem 28 of[11]:SAis nondegenerate if and only if 1 ∉σ(A)σ(A).
  • (d) Theorem 5 of[6]:SA∈P2if and only ifSAis Ultra-GUS.
  • (e) Theorem 3.3 of[14]:SA∈P'2if and only ifSAis Ultra Cone-Gus.
  • (f) Table on p56 of[11]: ForSA,
  • strictly monotone ⇒P2⇒GUS⇒P⇒ nondegenerate.
  • (g) Theorem 2.1 of[12]:SAis (strictly) monotone if and only if for all orthogonal matricesU,νr(UAUT◦UAUT) (<) ≤ 1 whereνr(A) := max{|xTAx| : ∥x∥ = 1,x∈Rn} and ◦ denotes the Hadamard product.
2. Characterization of Ultra-GUS property of a positive semidefinite preservingSA
We start with a Lemma.
Lemma 2.1. For A R n × n , suppose SA is nondegenerate and copositive on
PPT Slide
Lager Image
. Then SA is Cone-Gus.
Proof . Let X be a solution to SDLCP( SA , − Q ) where Q ≼ 0. It suffices to show X = 0 to prove SA is Cone-Gus. Since
X ( SA ( X ) − Q ) = 0, we have XSA ( X ) = XQ , and SA ( X ) X = QX . Since SA is copositive on
PPT Slide
Lager Image
, ⟨ X, SA ( X )⟩ ≥ 0, but ⟨ X, Q ⟩ ≤ 0, and hence ⟨ X, Q⟩ = 0 = ⟨ X , − Q ⟩. Since both X , − Q ≽ 0, XQ = 0 = QX . Then X = 0 follows from the nondegeneracy of SA . □
Note that if SA is positive semidefinite preserving, then SA is Lyapunovlike. (This is because SA Z and ⟨ X , SA ( X )⟩ ≥ 0 for all X ≽ 0.) Then by Theorem 3.5 [13] , SA is Cone-Gus if and only if SA is GUS. Since every positive semidefinite preserving SA is copositive on
PPT Slide
Lager Image
, we get the following
Theorem 2.2. If 1 ∉ σ ( A ) σ ( A ) and
PPT Slide
Lager Image
then SA is GUS.
We now show that if SA is nondegenerate and positive semidefinite preserving, then SA is not only GUS, but also Ultra-GUS.
Lemma 2.3. For A R n × n , suppose SA is nondegenerate and positive semidefinite preserving. Then SA is Ultra-GUS.
Proof . First we show that SA P′2 . Assume the contrary and let 0 ≠ X ≽ 0 be such that XSA ( X ) X ≼ 0. But SA is positive semidefinite preserving, so tr ( XSA ( X ) X ) = 0. Let X = UDUT where
PPT Slide
Lager Image
with D + ≻ 0 diagonal and U orthogonal. Then
PPT Slide
Lager Image
Let
PPT Slide
Lager Image
Note that M ≽ 0. Then the matrix product
PPT Slide
Lager Image
Thus,
0 = tr ( XSA ( X ) X ) = tr ( D + MD + ) = tr ( M ( D + ) 2 )
with D + nonsingular, so M = 0, which implies N = 0. Therefore,
PPT Slide
Lager Image
So D and UTSA ( X ) U commute with the product 0 where both are in
PPT Slide
Lager Image
. Hence XSA ( X ) = 0 = SA ( X ) X . Then X = 0 by nondegeneracy of SA .
As we noted earlier (right after Lemma 1), SA is Lyapunov-like. So by Theorem 6.1 [14] , P'2 = P2 , that is, Ultra Cone-Gus = Ultra GUS. This completes the proof. □
Now we characterize Ultra-GUS property of a positive semidefinite preserving SA .
Lemma 2.4. For A R n × n , let SA be positive semidefinite preserving. Then the following are equivalent.
  • (a) 1 ∉σ(A)σ(A).
  • (b)SAis Ultra-Gus.
  • (c)SAis strictly monotone.
Proof . The statement (a) ⇒ (b) is exactly Theorem 3.
Assume (b). Since P2 ⇒ nondegeneracy of SA , we get (a).
Finally, (b) and (c) are equivalent because SA is Lyapunov-like, and so by Theorem 6.1 of [14] , SA P2 if and only if SA is strictly monotone. This completes the proof. □
Remark 2.1. In our previous paper [12] , the strict monotonicity of SA was characterized in terms of its real numerical radius (Theorem 2.1 of [12] ). Hence if SA is positive semidefinite preserving, then 1 ∉ σ ( A ) σ ( A ) if and only if νr ( UAUT UAUT ) < 1 for all U orthogonal. We now show that under the assumption of positive semidefinite preservedness, both of these are equivalent to the (easier-to-check) statement, I ± A positive definite.
Theorem 2.5. If SA is positive semidefinite preserving, then the following are all true or all false:
  • (a)I±A is positive definite.
  • (b)ρ(A) < 1
  • (c) 1 ∉σ(A)σ(A)
  • (d)νr(UAUT◦UAUT) < 1for all U orthogonal.
Proof . Assume (a). Note that I ± UTAU = UT ( I ± A ) U is also positive definite for all orthogonal matrices U , and hence the ( k, k )-entry of UTAU ([ UTAU ] kk ) is less than 1 in absolute value. We will show first that SA is strictly copositive on
PPT Slide
Lager Image
. Suppose there exists 0 ≠ X ≽ 0 with ⟨ X , SA ( X )⟩ = 0. Let X = UDUT = U ( d 1 E 11 + · · · + dnEnn ) UT , where di ≥ 0 for all i and dk > 0 for some k . The matrix Eii is a diagonal matrix with all entries being 0 except the unit ( i, i )-entry. Then
PPT Slide
Lager Image
Since SA is positive semidefinite preserving, so is SUTAU , then
didj SUTAU ( Eii ), Ejj ⟩ ≥ 0 for each i and j . In particular,
PPT Slide
Lager Image
but the last term is positive because ⟨ SUTAU ( Ekk ), Ekk ⟩ = 1 − ([ UTAU ] kk ) 2 > 0. Then ⟨ X , SA ( X )⟩ > 0 which is a contradiction. Hence SA is strictly copositive on
PPT Slide
Lager Image
. Then by Theorem 3.2 of [14] , SA P'2 . Since P'2 = P2 for this SA (see the proof of Theorem 3) and P2 P , we get (b).
Since P ⇒ nondegenerate, we have (b) ⇒ (c).
The statement (c) ⇔ (d) is done in Theorem 4.
Finally, assume (d). Then ⟨ X , SA ( X )⟩ > 0 for all 0 ≠ X S n . So, without loss of generality, 0 < ⟨ uuT , SA ( uuT )⟩ for all 0 ≠ u Rn with ∥ u ∥ = 1. Then, ⟨ uuT , SA ( uuT )⟩ = 1 − (⟨ u, Au ⟩) 2 > 0. So, I ± A is positive definite and the proof is complete. □
Remark 2.2. Theorem 6 offers a way of checking when SA is not positive semidefinite perserving. For example,
PPT Slide
Lager Image
satisfies (b), but not (a) of Theorem 6, so SA is not positive semidefinite preserving.
3. Conclusion
In an attempt to find a characterization of GUS -property of the Stein transformation, Balaji showed that for SA : S 2 S 2 , SA is GUS if and only if I ± A is positive semidefinite (Theorem 6 [1] ). Nevertheless, this does not generalize to S n as Tao showed in his Example 4.1 [13] . In this paper, we showed SA : S n S n that is positive semidefinite preserving is Ultra-GUS if and only if I ± A is positive definite. Still much to be done to characterize the GUS -property of a general Stein transformation and that is the author’s future work.
Acknowledgements
The author is grateful toProfessor M.S. Gowdaof University of Maryland Baltimore County, USA, for introducing Malik’s thesis[9]to the author and for reading the proofs. The author is grateful for referee’s comments as well.
BIO
Yoon J. Song received her M.Sc. and Ph.D. at University of Maryland Baltimore County, USA. She has been at Soongsil University since 2010. Her research interests are semidefinite complementarity problems in optimization.
Department of Mathematics, Soongsil University, Seoul 156-743, Korea.
e-mail: yoonjsong@ssu.ac.kr
References
Balaji R. 2014 Some second order cone complementarity results, Research Report Indian Institute of Technology-Madras India
Chandrashekaran A. , Parthasarathy T. , Vetrivel V. (2010) On the P2’ and P2-properties in the semidefinite linear complementarity problem Linear Alg. and Its Appl. 432 134 - 143    DOI : 10.1016/j.laa.2009.07.031
Gowda M.S. , Parthasarathy T. (2000) Complementarity forms of Theorems of Lyapunov and Stein, and related results Linear Algebra Appl. 320 131 - 144    DOI : 10.1016/S0024-3795(00)00208-1
Gowda M.S. , Song Y. (2000) On semidefinite linear complementarity problems Math. Program., Series A 88 575 - 587    DOI : 10.1007/PL00011387
Gowda M.S. , Song Y. (2001) Errata: On semidefinite linear complementarity problems Math. Prog., Series A 91 199 - 200
Gowda M.S. , Song Y. , Ravindran G. (2003) Some interconnections between strong monotonicity,GUSandPproperties in semidefinite linear complementarity problems Linear Algebra Appl. 370 355 - 368    DOI : 10.1016/S0024-3795(03)00425-7
Gowda M. , Sznajder R. (2007) Some global uniqueness and solvability results for linear complementarity problems over symmetric cones SIAM J. Optim. 18 461 - 481    DOI : 10.1137/06065943X
Gowda M.S. , Tao J. (2009) Z-transformations on proper and symmetric cones Math. Program. B 117 195 - 222    DOI : 10.1007/s10107-007-0159-8
Malik M. , Ph.D. Thesis 2004 Some geometrical aspects of the cone linear complementarity problem Indian Statistical Institute New Delhi Ph.D. Thesis
Ramana M. (1997) An exact duality theory for semidefinite programming and its complexity implications Math. Prog. 77 129 - 162
Song Y. , Ph.D. Thesis 2002 The P and globally uniquely solvable properties in semidefinite linear complementarity problems Department of Mathematics and Statistics, University of Maryland Baltimore County, Baltimore, Maryland 21250, USA Ph.D. Thesis
Song Y. , Shin S. (2014) On stein transformation in semidefinite linear complementarity problems J. Appl. Math. & Informatics 32 285 - 295    DOI : 10.14317/jami.2014.285
Tao J. (2010) Strict semimonotonicity property of linear transformations on Euclidean Jordan Algebras J. Optim. Theory Appl. 144 575 - 596    DOI : 10.1007/s10957-009-9611-7
Tao J. (2013) On the completely-Q property for linear transformations on Euclidean Jordan Algebras Linear Algebra Appl. 438 2054 - 2071    DOI : 10.1016/j.laa.2012.09.033