ON POSITIVE SEMIDEFINITE PRESERVING STEIN TRANSFORMATION

Journal of Applied Mathematics & Informatics.
2015.
Jan,
33(1_2):
229-234

- Received : July 17, 2014
- Accepted : October 18, 2014
- Published : January 30, 2015

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

In the setting of semidefinite linear complementarity problems on
S
^{n}
, we focus on the Stein Transformation
S_{A}
(
X
) :=
X
−
AXA^{T}
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
S_{A}
has the Ultra-GUS property if and only if 1 ∉
σ
(
A
)
σ
(
A
).
AMS Mathematics Subject Classifiation : 90C33, 93D05.
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
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,
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
Specializing
L
to the Stein transformation
S_{A}
(
X
) :=
X
−
AXA^{T}
, 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
S_{A}
:
S
^{2}
→
S
^{2}
, then
S_{A}
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
S_{A}
is positive semidefinite preserving, then
S_{A}
is Ultra-GUS if and only if
I
±
A
is positive definite.
We list out needed definitions below.
Next, we list out some well known matrix theoretic properties that are needed in the paper
[10]
.
Finally, we state the known results (interpreting for the case of
L
=
S_{A}
) 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.
Lemma 2.1.
For A
∈
R
^{n}
^{×}
^{n}
,
suppose S_{A} is nondegenerate and copositive on
.
Then S_{A} is Cone-Gus.
Proof
. Let
X
be a solution to SDLCP(
S_{A}
, −
Q
) where
Q
≼ 0. It suffices to show
X
= 0 to prove
S_{A}
is Cone-Gus. Since
X
(
S_{A}
(
X
) −
Q
) = 0, we have
XS_{A}
(
X
) =
XQ
, and
S_{A}
(
X
)
X
=
QX
. Since
S_{A}
is copositive on
, ⟨
X, S_{A}
(
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
S_{A}
. □
Note that if
S_{A}
is positive semidefinite preserving, then
S_{A}
is Lyapunovlike. (This is because
S_{A}
∈
Z
and ⟨
X
,
S_{A}
(
X
)⟩ ≥ 0 for all
X
≽ 0.) Then by Theorem 3.5
[13]
,
S_{A}
is Cone-Gus if and only if
S_{A}
is GUS. Since every positive semidefinite preserving
S_{A}
is copositive on
, we get the following
Theorem 2.2.
If
1 ∉
σ
(
A
)
σ
(
A
)
and
then S_{A} is GUS.
We now show that if
S_{A}
is nondegenerate and positive semidefinite preserving, then
S_{A}
is not only GUS, but also Ultra-GUS.
Lemma 2.3.
For A
∈
R
^{n}
^{×}
^{n}
,
suppose S_{A} is nondegenerate and positive semidefinite preserving. Then S_{A} is Ultra-GUS.
Proof
. First we show that
S_{A}
∈
P′_{2}
. Assume the contrary and let 0 ≠
X
≽ 0 be such that
XS_{A}
(
X
)
X
≼ 0. But
S_{A}
is positive semidefinite preserving, so
tr
(
XS_{A}
(
X
)
X
) = 0. Let
X
=
UDU^{T}
where
with
D
^{+}
≻ 0 diagonal and
U
orthogonal. Then
Let
Note that
M
≽ 0. Then the matrix product
Thus,
0 =
tr
(
XS_{A}
(
X
)
X
) =
tr
(
D
^{+}
MD
^{+}
) =
tr
(
M
(
D
^{+}
)
^{2}
)
with
D
^{+}
nonsingular, so
M
= 0, which implies
N
= 0. Therefore,
So
D
and
U^{T}S_{A}
(
X
)
U
commute with the product 0 where both are in
. Hence
XS_{A}
(
X
) = 0 =
S_{A}
(
X
)
X
. Then
X
= 0 by nondegeneracy of
S_{A}
.
As we noted earlier (right after Lemma 1),
S_{A}
is Lyapunov-like. So by Theorem 6.1
[14]
,
P'_{2}
=
P_{2}
, that is, Ultra Cone-Gus = Ultra GUS. This completes the proof. □
Now we characterize Ultra-GUS property of a positive semidefinite preserving
S_{A}
.
Lemma 2.4.
For A
∈
R
^{n}
^{×}
^{n}
,
let S_{A} be positive semidefinite preserving. Then the following are equivalent.
Proof
. The statement (a) ⇒ (b) is exactly Theorem 3.
Assume (b). Since
P_{2}
⇒ nondegeneracy of
S_{A}
, we get (a).
Finally, (b) and (c) are equivalent because
S_{A}
is Lyapunov-like, and so by Theorem 6.1 of
[14]
,
S_{A}
∈
P_{2}
if and only if
S_{A}
is strictly monotone. This completes the proof. □
Remark 2.1.
In our previous paper
[12]
, the strict monotonicity of
S_{A}
was characterized in terms of its real numerical radius (Theorem 2.1 of
[12]
). Hence if
S_{A}
is positive semidefinite preserving, then 1 ∉
σ
(
A
)
σ
(
A
) if and only if
ν_{r}
(
UAU^{T}
◦
UAU^{T}
) < 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 S_{A} is positive semidefinite preserving, then the following are all true or all false:
Proof
. Assume (a). Note that
I
±
U^{T}AU
=
U^{T}
(
I
±
A
)
U
is also positive definite for all orthogonal matrices
U
, and hence the (
k, k
)-entry of
U^{T}AU
([
U^{T}AU
]
_{kk}
) is less than 1 in absolute value. We will show first that
S_{A}
is strictly copositive on
. Suppose there exists 0 ≠
X
≽ 0 with ⟨
X
,
S_{A}
(
X
)⟩ = 0. Let
X
=
UDU^{T}
=
U
(
d
_{1}
E
_{11}
+ · · · +
d_{n}E_{nn}
)
U^{T}
, where
d_{i}
≥ 0 for all
i
and
d_{k}
> 0 for some
k
. The matrix
E_{ii}
is a diagonal matrix with all entries being 0 except the unit (
i, i
)-entry. Then
Since
S_{A}
is positive semidefinite preserving, so is
S_{UTAU}
, then
d_{i}d_{j}
⟨
S_{UTAU}
(
E_{ii}
),
E_{jj}
⟩ ≥ 0 for each
i
and
j
. In particular,
but the last term is positive because ⟨
S_{UTAU}
(
E_{kk}
),
E_{kk}
⟩ = 1 − ([
U^{T}AU
]
_{kk}
)
^{2}
> 0. Then ⟨
X
,
S_{A}
(
X
)⟩ > 0 which is a contradiction. Hence
S_{A}
is strictly copositive on
. Then by Theorem 3.2 of
[14]
,
S_{A}
∈
P'_{2}
. Since
P'_{2}
=
P_{2}
for this
S_{A}
(see the proof of Theorem 3) and
P_{2}
⇒
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
,
S_{A}
(
X
)⟩ > 0 for all 0 ≠
X
∈
S
^{n}
. So, without loss of generality, 0 < ⟨
uu^{T}
,
S_{A}
(
uu^{T}
)⟩ for all 0 ≠
u
∈
R^{n}
with ∥
u
∥ = 1. Then, ⟨
uu^{T}
,
S_{A}
(
uu^{T}
)⟩ = 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
S_{A}
is not positive semidefinite perserving. For example,
satisfies (b), but not (a) of Theorem 6, so
S_{A}
is not positive semidefinite preserving.
GUS
-property of the Stein transformation, Balaji showed that for
S_{A}
:
S
^{2}
→
S
^{2}
,
S_{A}
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
S_{A}
:
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.
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

Stein Transformation
;
Semidefinite Linear Complementarity Problems (SDLCP)
;
P2-property
;
P'2-property
;
strictly monotone
;
nondegenerate
;
GUS-property

1. Introduction

In this paper, we focus on the so-called
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- (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 α.

- (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.

- (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.
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- (a) 1 ∉σ(A)σ(A).
- (b)SAis Ultra-Gus.
- (c)SAis strictly monotone.

- (a)I±A is positive definite.
- (b)ρ(A) < 1
- (c) 1 ∉σ(A)σ(A)
- (d)νr(UAUT◦UAUT) < 1for all U orthogonal.

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

3. Conclusion

In an attempt to find a characterization of
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

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**

Citing 'ON POSITIVE SEMIDEFINITE PRESERVING STEIN TRANSFORMATION
'

@article{ E1MCA9_2015_v33n1_2_229}
,title={ON POSITIVE SEMIDEFINITE PRESERVING STEIN TRANSFORMATION}
,volume={1_2}
, url={http://dx.doi.org/10.14317/jami.2015.229}, DOI={10.14317/jami.2015.229}
, number= {1_2}
, journal={Journal of Applied Mathematics & Informatics}
, publisher={Korean Society of Computational and Applied Mathematics}
, author={SONG, YOON J.}
, year={2015}
, month={Jan}