i
i
“Klep” — 2016/10/13 — 8:52 — page 81 — #1 i
i
i
i
i
i
MATRIČNO KONVEKSNE MNOŽICE
IGOR KLEP
Institut Jožef Stefan
Inštitut za matematiko, fiziko in mehaniko
Math. Subj. Class. (2010): 46L07, 13J30
V prispevku predstavimo matrično konveksne množice, ki so naravna posplošitev
konveksnosti za matrične prostore. Ogledali si bomo ustrezno različico matričnega Hahn-
Banachovega izreka in njegovo uporabo.
MATRIX CONVEX SETS
In this article we explore a natural extension of the notion of convexity to matrix
spaces, the so-called matrix convex sets. We shall give an appropriate analog of the
Hahn-Banach theorem and present some of its applications.
Uvod
Podmnožico K evklidskega prostora Rn imenujemo konveksna, če za po-
ljubni točki x, y ∈ K vsa daljica, ki povezuje x in y, leži v K. Funkcija
je konveksna, če je območje nad njenim grafom konveksna množica. Ta
preprost koncept izvira iz geometrije in se uporablja kot orodje v mnogih
znanostih. Konveksnost je pomembna v ekonomiji in financah (splošna te-
orija ravnotežja predvideva konveksne preference), statistiki in verjetnosti
(glej npr. Jensenovo neenakost) ter v matematični optimizaciji. Slednja
vsebuje kot samostojno vejo konveksno optimizacijo, ki je zaradi nedav-
nih prelomnic (metoda notranjih točk [13] in semidefinitno programiranje
oz. linearne matrične neenakosti [16]) aktualna tema v matematiki in raču-
nalnǐstvu. Konveksnost naredi optimizacijo zanesljivo, saj je vsak lokalni
minimum v tem primeru globalen.
V tem sestavku si bomo ogledali posplošitev pojma konveksnosti v ma-
tričnih prostorih. Pojem je vpeljal Wittstock [18], mi pa bomo sledili šoli
Effrosa [5].
Matrično konveksne množice
Simetrične in pozitivno semidefinitne matrike
Spomnimo, da je realna n×n matrika A = (aij)i,j simetrična, če je A = At,
kjer smo z At označili transponiranko matrike A. Z drugimi besedami, A
Obzornik mat. fiz. 63 (2016) 3 81
i
i
“Klep” — 2016/10/13 — 8:52 — page 82 — #2 i
i
i
i
i
i
Igor Klep
je simetrična, če za poljubna 1 ≤ i, j ≤ n velja aij = aji. Množico vseh
simetričnih n× n matrik bomo označili s Sn.
Lastne vrednosti simetrične matrike so vselej realne. Če so vse lastne
vrednosti nenegativne (oz. pozitivne), potem je A pozitivno semidefini-
tna (oz. definitna), kar označimo z A  0 (oz. A  0). Pozitivno semidefi-
nitnost lahko ekvivalentno vpeljemo na več načinov: simetrična matrika A
je pozitivno semidefinitna natanko takrat, ko velja katera koli izmed nasle-
dnjih izjav:
(i) 〈Av, v〉 = vtAv ≥ 0 za vse vektorje v ∈ Rn;
(ii) obstaja realna matrika B, za katero velja A = BtB;
(iii) obstaja simetrična realna matrika C, za katero velja A = C2;
(iv) vsi glavni minorji matrike A so nenegativni.
Povsem analogno lahko karakteriziramo tudi pozitivno definitne matrike.
Množica vseh pozitivno semidefinitnih n × n matrik tvori konveksen
stožec S0n v Sn. Na sliki 1 je predstavljen rob stožca vseh 2 × 2 pozitivno
semidefinitnih matrik ( x yy z ) kot podmnožica R3.
V nadaljevanju bo ključno vlogo imela Löwnerjeva delna ureditev
na Sn, ki jo porodi S0n : za A,B ∈ Sn,
A  B ⇐⇒ A−B  0.
(Kroneckerjev) tenzorski produkt matrik
Pogosto bomo posegali tudi po tenzorskem produktu matrik, zato si na
kratko oglejmo njegove lastnosti. Če je A = (aij)i,j matrika velikosti m× n
in B matrika velikosti p× q, potem je
A⊗B =
a11B · · · a1nB... . . . ...
am1B · · · amnB

matrika velikosti mp× nq. Kroneckerjev produkt je bilinearen, asociativen
in skoraj komutativen: obstajata permutacijski matriki P,Q, za kateri velja
B ⊗A = P (A⊗B)Q.
Če sta A,B kvadratni, smemo vzeti Q = P t. V tem primeru sta torej A⊗B
in B ⊗A ortogonalno ekvivalentni. Velja tudi
(A⊗B)(C ⊗D) = AC ⊗BD,
82 Obzornik mat. fiz. 63 (2016) 3
i
i
“Klep” — 2016/10/13 — 8:52 — page 83 — #3 i
i
i
i
i
i
Matrično konveksne množice
Slika 1
kadar sta produkta AC in BD definirana. Operatorska norma1 tenzorskega
produkta je produkt norm, transponiranka tenzorskega produkta pa je ten-
zorski produkt transponirank.
Matrično konveksne množice
Fiksirajmo naravno število g. Naš univerzum bodo g-terice realnih sime-
tričnih matrik vseh velikosti nad realnimi števili,
Sg :=
⋃
n∈N
Sgn.
Na Sg vpeljemo operacijo direktne vsote: za A ∈ Sgn in B ∈ Sgm postavimo
A⊕B :=
(
A 0
0 B
)
=
((A1 0
0 B1
)
, . . . ,
(
Ag 0
0 Bg
))
∈ Sgn+m.
1Operatorska norma n×m matrike W je definirana kot ‖W‖ := max{‖Wx‖ | x ∈
Rm, ‖x‖ = 1}. Operatorska norma je submultiplikativna: ‖VW‖ ≤ ‖V ‖ · ‖W‖, kadar je
produkt VW definiran.
81–99 83
i
i
“Klep” — 2016/10/13 — 8:52 — page 84 — #4 i
i
i
i
i
i
Igor Klep
Tako si lahko Sg mislimo kot neskončno disjunktno unijo ali pa kot stopni-
často množico. Podmnožica K ⊆ Sg je zaporedje
K =
(
K(n)
)
n
,
kjer je K(n) ⊆ Sgn.
Definicija 1. Podmnožico K ⊆ Sg imenujemo matrično konveksna, če
zadošča naslednjim pogojem:
(0) 0 ∈ K (vsebovanost izhodǐsča);
(1) K ⊕ K ⊆ K: za vse A,B ∈ K velja A ⊕ B ∈ K (zaprtost za direktne
vsote);
(2) (zaprtost za ∗-konjugiranje s skrčitvami) za vse n,m ∈ N, vsako skrči-
tev2 V ∈ Rn×m in vsak A = (A1, . . . , Ag) ∈ K(n) velja
V tAV := (V tA1V, . . . , V
tAgV ) ∈ K(m).
Omenimo, da je predpostavka (0) nebistvena, a jo tukaj privzamemo,
da se izognemo nekaterim tehničnim zapletom. Če (0) izpustimo, lahko v
(2) predpostavimo le zaprtje za ∗-konjugiranje z izometrijami V .
Opomba 2. Podmnožici K ⊆ Sg, ki zadošča aksiomu (1) in aksiomu (2) za
ortogonalne matrike V , pravimo prosta množica. Proste množice so domene
in kodomene prostih preslikav, s katerimi se ukvarja prosta analiza [17, 10].
Zgled 3. Preden se lotimo študija matrično konveksnih množic, si poglejmo
nekaj zgledov.
(a) Fiksirajmo g-terico simetričnih matrik Ω ∈ Sgn. Potem je
K := {V t(Iµ ⊗ Ω)V | µ ∈ N, V ∈ Rnµ×m je skrčitev, m ∈ N} (1)
matrično konveksna množica. Tukaj z ⊗ označujemo Kroneckerjev tenzorski
produkt matrik. Če zapǐsemo
V =
V1...
Vµ
 ,
2Matriki V rečemo skrčitev, če je njena operatorska norma ≤ 1. Ekvivalentno: ma-
trika I − V tV je pozitivno semidefinitna, I − V tV  0. Simetrična matrika S je skrčitev
natanko takrat, ko je −I  S  I.
84 Obzornik mat. fiz. 63 (2016) 3
i
i
“Klep” — 2016/10/13 — 8:52 — page 85 — #5 i
i
i
i
i
i
Matrično konveksne množice
kjer Vi ∈ Rn×m, potem je
V t(Iµ ⊗ Ω)V =
µ∑
j=1
V tj ΩVj ,
V tV  I pa se prepǐse v
∑
j V
t
j Vj  I.
Očitno je 0 ∈ K, saj lahko v (1) postavimo V = 0. Pokažimo sedaj, da
je K ⊕K ⊆ K. Vzemimo V t(Iµ ⊗ Ω)V, W t(Iν ⊗ Ω)W ∈ K. Tedaj je
V t(Iµ ⊗ Ω)V ⊕W t(Iν ⊗ Ω)W = (W ⊕ V )t(Iµ+ν ⊗ Ω)(W ⊕ V ) ∈ K.
Zaprtost K za ∗-konjugiranje s skrčitvami je še preprosteǰsa. Za V t(Iµ⊗
Ω)V ∈ K(n) in skrčitev W ∈Mn(R) velja
W tV t(Iµ ⊗ Ω)VW = (VW )t(Iµ ⊗ Ω)(VW ),
hkrati pa je
‖VW‖ ≤ ‖V ‖ · ‖W‖ ≤ 1
zaradi submultiplikativnosti operatorske norme.
Množica K je najmanǰsa konveksna množica, ki vsebuje Ω. Pravimo ji
matrično konveksna ogrinjača množice {Ω} in jo označimo s
K = mat-konv{Ω}.
(b) Vzemimo sedaj Ω1, . . . ,Ωr ∈ Sg. Tedaj je najmanǰsa matrično konve-
ksna množica K, ki vsebuje vse Ωj , enaka mat-konv{Ω1 ⊕ · · · ⊕ Ωr}.
Očitno je Ω1⊕· · ·⊕Ωr ∈ K, saj je K zaprta za direktne vsote. Hkrati pa
vsaka matrično konveksna množica, ki vsebuje Ω1 ⊕ · · · ⊕ Ωr, vsebuje tudi
vsak Ωj , saj velja npr.
Ω1 =

I
0
...
0

t
Ω1
Ω2
. . .
Ωe


I
0
...
0
 .
S tem smo pokazali, da so vse matrično konveksne množice, ki so napete s
končno mnogo tericami matrik, vselej napete kar s singletonom.
(c) Naj bo ε > 0. Definirajmo prosto ε-kroglo s sredǐsčem v izhodǐsču 0:
Nε :=
⋃
n∈N
{X ∈ Sgn | ‖X‖ ≤ ε} =
{
X ∈ Sg | ε2I 
∑
j
X2j
}
.
Preprosto je preveriti, da je Nε matrično konveksna množica.
81–99 85
i
i
“Klep” — 2016/10/13 — 8:52 — page 86 — #6 i
i
i
i
i
i
Igor Klep
(d) Vzemimo A = (A1, . . . , Ag) ∈ Sgd in tvorimo enični matrični šop veli-
kosti d:
Λ(x) := Id + x1A1 + · · ·+ xgAg. (2)
Matrični šop lahko seveda vrednotimo v Rg: za x ∈ Rg je Λ(x) identiteta
plus ustrezna linearna kombinacija matrik Aj . Veliko bolj zanimivo pa je
vrednotenje v Sn za n ≥ 2. Če so X1, . . . , Xg ∈ Sn, potem definiramo
Λ(X) = In ⊗ Id +X1 ⊗A1 + · · ·+Xg ⊗Ag ∈ Sdn.
Sedaj tvorimo linearno matrično neenakost Λ(x)  0 in njeno množico
rešitev, t. i. (prost) spektraeder
DΛ =
⋃
n∈N
{X ∈ Sgn | Λ(X)  0}.
Vse skalarne točke DΛ(1) = DΛ ∩ Rg tvorijo konveksno podmnožico Rg.
Množica DΛ je matrično konveksna. Res, Λ(0) = I  0, torej je 0 ∈
DΛ(1). Zaprtost DΛ za direktne vsote sledi iz
Λ(X ⊕ Y ) = Λ(X)⊕ Λ(Y ),
zaprtost za ∗-konjugiranje s skrčitvami pa iz
Λ(V tXV ) = I ⊗ I +
∑
j
(V tXjV )⊗Aj
= (V ⊗ I)t
(
I ⊗ I +
∑
j
Xj ⊗Aj
)
(V ⊗ I) + (I − V tV )⊗ I
= (V ⊗ I)tΛ(X)(V ⊗ I) + (I − V tV )⊗ I  0.
Matrični šop (2) po navadi označimo z ΛA(x).
(e) Oglejmo si konkretna primera prostih spektraedrov. Definirajmo
∆(x1, x2) := I3 +
0 1 01 0 0
0 0 0
x1 +
0 0 10 0 0
1 0 0
x2 =
 1 x1 x2x1 1 0
x2 0 1
 ,
Γ(x1, x2) := I2 +
(
1 0
0 −1
)
x1 +
(
0 1
1 0
)
x2 =
(
1 + x1 x2
x2 1− x1
)
.
86 Obzornik mat. fiz. 63 (2016) 3
i
i
“Klep” — 2016/10/13 — 8:52 — page 87 — #7 i
i
i
i
i
i
Matrično konveksne množice
Skalarne točke prostih spektraedrov D∆ in DΓ je preprosto izračunati npr. s
pomočjo minorjev (razdelek (Kroneckerjev) tenzorski produkt matrik). Ve-
lja
D∆(1) = {(X1, X2) ∈ R2 | X21 +X22 ≤ 1},
DΓ(1) = {(X1, X2) ∈ R2 | X21 +X22 ≤ 1}.
Množici D∆(1) in DΓ(1) sovpadata. Po drugi strani pa je preprosto videti((
1
2 0
0 0
)
,
(
0 34
3
4 0
))
∈ D∆ \ DΓ,
zato iz ∆(X1, X2)  0 ne sledi Γ(X1, X2)  0. Velja pa obratna implika-
cija: DΓ ⊂ D∆. To bomo podrobneje razložili v razdelku Uporaba Hahn-
Banachovega izreka, glej zgled 17.
Ker je 1 x1 x2x1 1 0
x2 0 1
 =
x1 1 0x2 0 1
1 0 0
t1 0 00 1 0
0 0 1− x21 − x22
x1 1 0x2 0 1
1 0 0

in je konjugacijska matrika obrnljiva,x1 1 0x2 0 1
1 0 0
−1 =
0 0 11 0 −x1
0 1 −x2
 ,
sledi
D∆ = {(X1, X2) ∈ S2 | 1−X21 −X22  0}.
(f) Iz matrično konveksnih množic lahko tvorimo nove matrično konveksne
množice, npr. s preseki, kartezičnimi produkti, zaprtji. Tukaj vse te kon-
strukcije izvajamo stopničeno; npr. zaprtje K ⊂ Sg je
K =
⋃
n∈N
K(n),
pri čemer K(n) ⊆ Sgn opremimo z inducirano evklidsko topologijo.
Projekcija matrično konveksne množice je ponovno matrično konveksna:
če je K ⊂ Sg+h matrično konveksna, potem je tudi
projg K :=
⋃
n∈N
{X ∈ Sgn | ∃Y ∈ Shn : (X,Y ) ∈ K}
matrično konveksna.
81–99 87
i
i
“Klep” — 2016/10/13 — 8:52 — page 88 — #8 i
i
i
i
i
i
Igor Klep
(g) Podajmo še eno konstrukcijo matrično konveksnih množic. Za podmno-
žico K ⊆ Sg označimo s
K◦ =
⋃
n∈N
{A ∈ Sgn | ∀X ∈ K : ΛA(X)  0}
njeno polaro. Opazimo, da bi lahko v definiciji namesto ΛA(X)  0
zahtevali ΛX(A)  0, saj sta matriki ΛA(X) in ΛX(A) ortogonalno ek-
vivalentni; prehodna matrika je celo permutacijska in realizira izomorfizem
A⊗B 7→ B⊗A.3 Preprosto je videti, da je K◦ matrično konveksna množica.
Opazimo tudi, da ◦ obrača inkluzije: če je K ⊆ K̃, potem velja K◦ ⊇ K̃◦.
(h) Vrnimo se k prostim kroglam iz (c). Za ε > 0 velja
N 1
gε
⊂ N ◦ε ⊂ N√g
ε
.
Pokažimo najprej prvo inkluzijo. Če je ‖A‖ ≤ 1gε , potem za vsak X ∈ Nε
velja
‖A1 ⊗X1 + · · ·+Ag ⊗Xg‖ ≤ gmax
j
‖Aj‖ ·max
k
‖Xk‖ ≤ 1.
Sledi
ΛA(X)  0,
zatorej je A ∈ N ◦ε .
Za desno inkluzijo vzemimo poljuben A ∈ N ◦ε . Potem za vsak Xj norme
ε velja
1 ≥ ‖Aj ⊗Xj‖ = ‖Aj‖ · ‖Xj‖ = ε‖Aj‖,
torej je ∥∥∥∑
j
A2j
∥∥∥ ≤ g
ε2
.
Osnovne lastnosti matrično konveksnih množic
Sedaj smo pripravljeni, da si ogledamo preproste lastnosti matrično konve-
ksnih množic. Najprej razložimo, od kod ime.
Lema 4. Naj bo K ⊂ Sg matrično konveksna. Tedaj je za vsak n ∈ N
množica K(n) = K ∩ Sgn konveksna.
3V angleščini tej preslikavi rečemo canonical shuffle.
88 Obzornik mat. fiz. 63 (2016) 3
i
i
“Klep” — 2016/10/13 — 8:52 — page 89 — #9 i
i
i
i
i
i
Matrično konveksne množice
Dokaz. Vzemimo realni števili s, t, za kateri velja s2 + t2 = 1, in naj bosta
X,Y ∈ K(n). Definirajmo skrčitev
V =
(
sIn
tIn
)
in poračunajmo:
s2X + t2Y = V t
(
X 0
0 Y
)
V = V t(X ⊕ Y )V ∈ K(n).
Naj bo K ⊂ Sg prosta množica. Pravimo, da je K zaprta za zožitve
na invariantne podprostore, če za vsak X ∈ K(n) in vsak podprostor
H ⊂ Rn dimenzije m, ki je invarianten za X, velja
X|H ∈ K(m). (3)
Strogo gledano X|H seveda ni m×m matrika, temveč le linearna preslikava
na m razsežnem podprostoru H ⊂ Rn. V izjavi (3) vsebovanost v K(m)
preverjamo s kakšno od matrik, ki jih tej linearni preslikavi priredimo glede
na ortonormirano bazo H. Ali je dobljena matrika element K(m), je neod-
visno od izbire baze, saj je množica K prosta in zato zaprta za ortogonalno
∗-konjugiranje.
Izrek 5. Naj bo 0 ∈ K ⊂ Sg prosta podmnožica, ki je zaprta za zožitve na
invariantne podprostore. Potem je K matrično konveksna natanko takrat,
ko je K(n) konveksna za vsak n ∈ N.
Dokaz. Implikacija (⇒) drži po preǰsnji lemi. Poglejmo si še obrat. Vze-
mimo X ∈ K(n), podprostor H ⊂ Rn in naj bo L ortogonalni komplement
H v Rn. Glede na direktno vsoto Rn = H⊕L naj ima X zapis
X =
(
A B
Bt C
)
.
Če z V označimo izometrijo H → Rn, potem je V ∗XV = A. Hkrati je(
A 0
0 C
)
=
1
2
(
A B
Bt C
)
+
1
2
(
1 0
0 −1
)(
A B
Bt C
)(
1 0
0 −1
)
element K(n), saj je K(n) konveksna in je matrika
(
1 0
0 −1
)
ortogonalna.
Ker je H invarianten podprostor za
(
A 0
0 C
)
, dobimo še A = V ∗XV ∈ K.
Od tod sledi, da je V ∗XV ∈ K za vsako izometrijo V .
81–99 89
i
i
“Klep” — 2016/10/13 — 8:52 — page 90 — #10 i
i
i
i
i
i
Igor Klep
Naj bo W : H → Rn poljubna skrčitev. Potem je
V : H → Rn ⊕H, x 7→
(
Wx,
√
I −W tWx
)
=
(
W,
√
I −W tW
)
x
izometrija. Ker je 0 ∈ K, za vsak X ∈ K(n) velja X ⊕ 0 ∈ K. Sledi
W tXW = V t
(
X 0
0 0
)
V ∈ K.
Zgled 6. Podajmo še primer nekonveksne proste množice v S2, katere ska-
larne točke tvorijo konveksno podmnožico v R2. (Nekomutativnemu) poli-
nomu p = 1− x41 − x22 priredimo prosto semialgebraično množico
Dp := {(X1, X2) ∈ S2 | p(X1, X2)  0}.
x1
x2
1
1
Slika 2. TV zaslon Dp(1) =
{
(x1, x2) ∈ R2 | 1− x41 − x22 ≥ 0
}
.
Čeprav je množica Dp(1) konveksna, Dp ni matrično konveksna. Z ne-
koliko računske spretnosti je možno pokazati, da podmnožica Dp(2) v 6-
razsežnem evklidskem prostoru S22 ni konveksna. Res, za
X1 =
(
1
2 −
1
4
−14 −
1
4
)
, Y1 =
(
2
7
5
6
5
6 0
)
, X2 =
(
1
2 −
1
4
−14
7
16
)
, Y2 =
(
3
10
5
6
5
6 0
)
velja (Xj , Yj) ∈ Dp(2) in
(
1
2(X1 +X2),
1
2(Y1 + Y2)
)
6∈ Dp(2).
90 Obzornik mat. fiz. 63 (2016) 3
i
i
“Klep” — 2016/10/13 — 8:52 — page 91 — #11 i
i
i
i
i
i
Matrično konveksne množice
Slika 3. »Tipičen« trirazsežni prerez TV zaslona Dp(2).
Rečemo, da je 0 v notranjosti podmnožice K ⊂ Sg, če je Nε ⊆ K za kak
ε > 0. Množica K je omejena, če obstaja N ∈ N, za katerega je ‖X‖ ≤ N
za vse X ∈ K. Ekvivalentno: K ⊂ NN . (Tukaj velja opozoriti, da je ta
zahteva močneǰsa od omejenosti vseh K(n).)
Lema 7. Denimo, da je K ⊂ Sg matrično konveksna. Potem so naslednje
trditve ekvivalentne:
(i) 0 ∈ Rg je v notranjosti množice K(1);
(ii) 0 ∈ Sgn je v notranjosti množice K(n) za kak n ∈ N;
(iii) 0 ∈ Sgn je v notranjosti množice K(n) za vse n ∈ N;
(iv) 0 je v notranjosti množice K.
Dokaz. Očitno velja (iv)⇒ (iii)⇒ (ii). Predpostavimo, da drži (ii). Potem
obstaja ε > 0 z Nε(n) ⊆ K(n). Ker je
Nε(1)⊕ · · · ⊕ Nε(1) ⊆ Nε(n),
in je Nε zaprt za ∗-konjugiranje s skrčitvami, je tudi Nε(1) ⊆ K(1), torej
velja (i).
81–99 91
i
i
“Klep” — 2016/10/13 — 8:52 — page 92 — #12 i
i
i
i
i
i
Igor Klep
Slika 4. Nekonveksen 2-razsežni prerez Dp(2).
Naj sedaj drži (i), tj. Nε(1) ⊆ K(1) za kak ε > 0. Trdimo, da je Nε/g2 ⊆
K. Vzemimo poljuben X ∈ Nε/g2 . Očitno je[
−ε
g
,
ε
g
]g
⊆ K(1).
Ker ima vsak Xj normo ≤ ε/g2, imajo v njegovi diagonalizaciji Xj =
U∗
(
λ1
. . .
λn
)
U vse λj absolutno vrednost ≤ ε/g2. Zato je (0, . . . , 0, gλk,
0, . . . , 0) ∈ K(1) in nato zaradi zaprtosti za direktne vsote
(
0, . . . , 0,
g
(
λ1
. . .
λn
)
, 0, . . . , 0
)
∈ K. Samo še ∗-konjugiramo z U in dobimo
(0, . . . , 0, gXj , 0, . . . , 0) ∈ K.
Sledi
X =
1
g
(
(gX1, 0, . . . , 0) + · · ·+ (0, . . . , 0, gXg)
)
∈ K.
Opomba 8. Pri študiju matrično konveksnih množic se po navadi omejimo
na takšne, ki vsebujejo 0 v notranjosti. Če ima K(1) kakšno notranjo točko,
npr. a ∈ Rn, potem preprosto s translacijo
K − a =
⋃
n∈N
{X − aIn | X ∈ K(n)}
92 Obzornik mat. fiz. 63 (2016) 3
i
i
“Klep” — 2016/10/13 — 8:52 — page 93 — #13 i
i
i
i
i
i
Matrično konveksne množice
prevedemo na takšen primer. Če K(1) nima notranje točke, potem pa leži
v kakšnem afinem podprostoru {` = 0} [3, Theorem 2.4]. Kratek račun
pokaže, da iz `K(1) = 0 sledi `|K = 0. Torej lahko iz enačbe ` = 0 izra-
zimo kakšno od spremenljivk in s tem preidemo na nižje razsežen ambientni
prostor. Postopek nadaljujemo, dokler K(1) nima notranje točke.
Trditev 9. Naj bo K ⊂ Sg.
(1) če je 0 v notranjosti množice K, potem je K◦ omejena;
(2) K ⊂ K◦◦; z drugimi besedami, za vse n ∈ N velja K(n) ⊂ K◦◦(n);
(3) K je omejena natanko takrat, ko je 0 v notranjosti množice K◦.
Dokaz. Če ima K izhodǐsče v notranjosti, potem je Nε ⊆ K za neki ε > 0.
Torej je K◦ ⊆ N ◦ε ⊂ N√g
ε
omejena. Tukaj smo za zadnjo inkluzijo uporabili
zgled 3(h).
Trditev (2) je tavtologija. Res, za X ∈ K(n) želimo pokazati ΛX(A)  0,
kadarkoli velja ΛA(Y )  0 za vse Y ∈ K. To pa je preprosta posledica
dejstva, da sta matriki ΛX(A) in ΛA(X) ortogonalno ekvivalentni.
Če je K omejena, potem je 0 očitno v notranjosti množice K◦. Obratno,
če je 0 v notranjosti množice K◦, potem iz (1) sledi, da je K◦◦ omejena. Ker
nam (2) pove, da velja K ⊂ K◦◦, je tudi K omejena.
Lema 10. Za podmnožico K ⊆ Sg+h si oglejmo njeno sliko projK ⊆ Sg pri
projekciji proj : Sg+h → Sg. Terica A ∈ Sg je element (projK)◦ tedaj in le
tedaj, ko je (A, 0) ∈ K◦.
Dokaz. A ∈ (projK)◦ natanko tedaj, ko za vse X ∈ projK velja ΛA(X)  0.
Slednje je ekvivalentno Λ(A,0)(X,Y )  0 za vse X ∈ projK in vse Y ∈ Sh,
kar je ekvivalentno Λ(A,0)(X,Y )  0 za vse (X,Y ) ∈ K. To pa se zgodi
natanko takrat, ko (A, 0) ∈ K◦.
Matrični Hahn-Banachov izrek
V tem razdelku si bomo ogledali eno glavnih orodij pri delu z matrično
konveksnimi množicami – analog Hahn-Banachovega izreka. Kot prva sta ga
dokazala Effros in Wikler [5], alternativni dokaz pa si bralec lahko ogleda v
[9]. Dokaz je razmeroma zapleten in predolg, da bi ga lahko tukaj predstavili.
Podrobneje pa si bomo pogledali nekaj posledic in uporab tega izreka.
81–99 93
i
i
“Klep” — 2016/10/13 — 8:52 — page 94 — #14 i
i
i
i
i
i
Igor Klep
Izrek 11 (Matrični Hahn-Banachov izrek). Naj bo K matrično konve-
ksna množica, katere stopnice K(n) so zaprte. Če X ′ ∈ Sgn ne leži v K(n),
potem obstaja eničen matrični šop Λ(x) velikosti n, za katerega je Λ(Y )  0
za vse Y ∈ K in Λ(X ′) 6 0.
Naslednja posledica pove, v kakšnem smislu lahko izrek 11 razumemo
kot matrični analog Hahn-Banachovega izreka. Hkrati nas prepriča, da so
prosti spektraedri ustrezni analogi polprostorov iz klasične konveksnosti za
univerzum Sg.
Posledica 12. Naj bo K zaprta matrično konveksna množica. Potem je K
enaka preseku vseh prostih spektraedrov, ki jo vsebujejo.
Nadaljnje lastnosti matrično konveksnih množic
Najmanǰso zaprto matrično konveksno množico, ki vsebuje K ⊂ Sg, bomo
označili z mat-konvK.
Trditev 13. Naj bo K ⊂ Sg.
(1) Če za neki m ∈ N velja 0 ∈ K(m), potem je K◦◦ = mat-konvK.
(2) Če je K zaprta matrično konveksna množica, tedaj velja K = K◦◦;
Dokaz. Začnimo s točko (1). Najprej opazimo, da je 0 ∈ mat-konvK(m), in
ker je mat-konvKmatrično konveksna, dobimo 0 ∈ mat-konvK(1). Denimo,
da W 6∈ mat-konvK. Potem nam izrek (11) da obstoj eničnega matričnega
šopa ΛA (kjer velikost matrik A ni večja od velikosti W ), ki loči W od
mat-konvK: ΛA(W ) 6 0 in ΛA(X)  0 za vse X ∈ mat-konvK. V poseb-
nem je A ∈ K◦. Ker sta matriki ΛW (A) in ΛA(W ) ortogonalno ekvivalentni,
sledi ΛW (A) 6 0 in W /∈ K◦◦. Torej je K◦◦ ⊂ mat-konvK. Obratna inkluzija
sledi iz trditve 9(2). Točka (2) je preprosta posledica točke (1).
Posledica 14. Če je K ⊂ Sg, potem je K◦◦ = mat-konv
(
K ∪ {0}
)
.
Dokaz. Ker je K◦ = (K ∪ {0})◦, sledi
K◦◦ = (K ∪ {0})◦◦.
Po trditvi 9(1) in (13) sedaj dobimo
mat-konv
(
K ∪ {0}
)
= (K ∪ {0})◦◦.
94 Obzornik mat. fiz. 63 (2016) 3
i
i
“Klep” — 2016/10/13 — 8:52 — page 95 — #15 i
i
i
i
i
i
Matrično konveksne množice
S pomočjo prostih spektraedrov, njihovih polar in projekcij lahko eks-
plicitno opǐsemo matrično konveksno ogrinjačo singletona, t. i. matrični ali
prosti polieder:
Izrek 15. Naj bo Ω ∈ Sgn.
(1) mat-konv{Ω} = D◦ΛΩ.
(2) Zapǐsimo Ω =
(
(ω`ij)
n
i,j=1
)
`=1,...,g
∈ Sgn. Tedaj je mat-konv{Ω} enaka⋃
m∈N
{(∑
i,j
ω`ijCij
)
`=1,...,g
| Cij ∈Mm(R),
C = (Cij)
n
i,j=1  0,
∑
i
Cii  In
}
. (4)
Dokaz. Oglejmo si najprej točko (2). Po zgledu 3(a) je X ∈ (mat-konv{Ω})
(m) natanko takrat, ko velja
X = V t(Iµ ⊗ Ω)V (5)
za neki µ ∈ N in nµ × m skrčitev V . Vešči bralec bo na desni strani
(5) prepoznal Choi-Krausov zapis povsem pozitivne preslikave. Linearna
preslikava τ med končnorazsežnimi podprostori realnih simetričnih matrik
je povsem pozitivna natanko tedaj, ko je oblike
τ(x) =
µ∑
j=1
V tj xVj = V
t(Iµ ⊗ x)V
za matrike (ustrezne velikosti) Vj [14, Proposition 4.7]. Tukaj smo z V ozna-
čili stolpec (V1, . . . , Vµ). V našem primeru velja še
∑
j V
t
j Vj  I, saj je V
v (5) skrčitev. Tako vidimo, da je g-terica X element (mat-konv{Ω})(m)
takrat in le takrat, ko je za vsak i matrika Xi slika τ(Ωi) povsem pozitivne
preslikave τ : Lin{I,Ω1, . . . ,Ωg} → Sm, ki pošlje I v skrčitev. Po Arveso-
novem razširitvenem izreku [14, Theorem 6.2] lahko τ razširimo do povsem
pozitivne preslikave τ̂ : Md(R) → Mm(R). Sedaj pa uporabimo Choijevo
matriko [14, Theorem 3.14]. Preslikava τ̂ : Md(R) → Mm(R) je povsem
pozitivna natanko takrat, ko je njena Choijeva matrika
C := (Cij)
n
i,j=1  0,
kjer je
Cij = τ̂(Eij).
81–99 95
i
i
“Klep” — 2016/10/13 — 8:52 — page 96 — #16 i
i
i
i
i
i
Igor Klep
Ker je
τ̂(Ω`) =
∑
i,j
ω`ij τ̂(Eij) =
∑
i,j
ω`ijCij ,
leži X v množici (4). S tem je točka (2) dokazana. Ugotovimo lahko tudi,
da je množica mat-konv{Ω} zaprta, celo kompaktna, saj je slika kompaktne
množice po (4).
Posvetimo se sedaj točki (1). Najprej dokažimo inkluzijo (⊂). Vzemimo
poljuben A = V t(I ⊗ Ω)V ∈ mat-konv{Ω}. Trdimo, da je A ∈ D◦ΛΩ . Za
vsak X ∈ DΛΩ velja
ΛA(X)
u∼= ΛX(A) = ΛX
(
V t(I ⊗ Ω)V
)
 (V ⊗ I)tΛX(Ω)(V ⊗ I)
= (V ⊗ I)tP tΛΩ(X)P (V ⊗ I)  0,
(6)
kjer smo z
u∼= označili ortogonalno ekvivalenco, P pa je ortogonalna matrika,
za katero velja P tΛΩ(X)P = ΛX(Ω). Pri tem prva neenakost v (6) sledi z
enakim računom kot v zgledu 3(d). Torej je A ∈ D◦ΛΩ .
Za obratno inkluzijo bomo uporabili matrični Hahn-Banachov izrek 11.
Denimo, da X 6∈ mat-konv{Ω}. Potem obstaja matrični šop ΛA, za katerega
velja
ΛA|mat-konv{Ω}  0, ΛA(X) 6 0.
Prva neenakost je ekvivalentna ΛA(Ω)  0 in s tem ΛΩ(A)  0. V posebnem
A ∈ DΛΩ . Hkrati pa velja
ΛX(A)
u∼= ΛA(X) 6 0,
torej X 6∈ D◦ΛΩ , kar smo želeli dokazati.
Razred prostih spektraedrov ni zaprt za polare; je pa polara spektraedra
projekcija spektraedra po izreku 15. Izkaže se, da je slednji razred zaprt za
polare [8].
Uporaba Hahn-Banachovega izreka
V tem razdelku si oglejmo presenetljivo uporabo izreka 11. Opisali bomo,
kdaj za enična matrična šopa ΛA in ΛB velja DΛA ⊂ DΛB . Ekvivalentno,
ΛB|DΛA  0.
Posledica 16 (Linearni Positivstellensatz [7]). Naj bo A ∈ Sgd in B ∈
Sge. Naslednji trditvi sta ekvivalentni:
96 Obzornik mat. fiz. 63 (2016) 3
i
i
“Klep” — 2016/10/13 — 8:52 — page 97 — #17 i
i
i
i
i
i
Matrično konveksne množice
(i) DΛA ⊂ DΛB ;
(ii) B ∈ mat-konv{A}, tj. obstaja µ ∈ N in skrčitev V , da velja
B = V t(Iµ ⊗A)V.
Dokaz. Uporabimo izrek 15, ki nam poda naslednjo verigo ekvivalenc:
DΛA ⊂ DΛB ⇐⇒ D
◦
ΛA
⊇ D◦ΛB
⇐⇒ mat-konv{A} ⊇ mat-konv{B} ⇐⇒ B ∈ mat-konv{A}.
Omenimo, da v točki (ii) posledice 16 lahko postavimo meje na µ. Brez
škode za splošnost lahko namreč zahtevamo µ ≤ de. Dokaz tega ni preza-
pleten, a uporabi teorijo povsem pozitivnih preslikav in ga zato izpuščamo.
Bralec lahko podrobnosti najde v [7]. Posledica ima vedno preprosto inter-
pretacijo v jeziku povsem pozitivnih preslikav: DΛA ⊂ DΛB natanko takrat,
ko obstaja povsem pozitivna preslikava, ki pošlje Ai 7→ Bi in slika I v skr-
čitev.
Zgled 17. Vrnimo se k zgledu 3(e). Pokažimo, da velja DΓ ⊆ D∆. Defini-
rajmo
V1 :=
[
1 1 0
0 0 1
]
in V2 :=
[
0 0 1
1 −1 0
]
.
Potem je
2∆(x1, x2) = V
t
1 Γ(x1, x2)V1 + V
t
2 Γ(x1, x2)V2,
kar s pomočjo posledice 16 da iskani zaključek.
Nadaljnje teme
Prispevek sklenemo s kratko diskusijo oz. kažipotom za nadaljnje teme.
Gleichstellensatz
Naravno vprašanje je, kdaj dva matrična šopa določata enak prost spektra-
eder, tj. DΛA = DΛB . Najprej opazimo, da je to vprašanje nekako ekviva-
lentno vprašanju obstoja vložitve med spektraedroma:
DΛA ⊂ DΛB ⇐⇒ DΛA⊕B = DΛA .
Rečemo, da je matrični šop ΛA minimalen, če za vse terice matrik B,
ki so manǰse velikosti od A, velja DΛA 6= DΛB . Z nekaj truda je mogoče
dokazati, da je dovolj, če minimalnost preverjamo le za »podšope« ΛA.
Tukaj podšop označuje skrčitev matričnega šopa ΛA na skupen invariantni
podprostor za A.
81–99 97
i
i
“Klep” — 2016/10/13 — 8:52 — page 98 — #18 i
i
i
i
i
i
Igor Klep
Izrek 18 (Linearni Gleichstellensatz [7]). Naj bosta A ∈ Sgd in B ∈ S
g
e.
Predpostavimo, da sta matrična šopa ΛA in ΛB minimalna. Potem sta
naslednji trditvi ekvivalentni:
(i) DΛA = DΛB ;
(ii) d = e in obstaja ortogonalna matrika U ∈Md(R), za katero velja
B = U tAU.
Izrek 18 poda geometrijsko karakterizacijo teric matrik glede na ortogo-
nalno konjugiranje. Dokaz tega izreka uporabi Arvesonovo nekomutativno
Choquetjevo teorijo [1, 2] in ga bomo izpustili. Bralec ga lahko najde v [7].
Na tem mestu omenimo še algebraično karakterizacijo teric matrik glede
na ortogonalno konjugiranje. Procesijev izrek [15] pove, da sta g-terici
A1, . . . , Ag ∈ Md(R) in B1, . . . , Bg ∈ Md(R) ortogonalno ekvivalentni na-
tanko takrat, ko velja
sledw(A,At) = sledw(B,Bt)
za vse besede w v x, xt dolžine d2.
Konveksni Positivstellensatz
Posledica 16 opǐse matrične šope ΛB, ki so pozitivno semidefinitni na spek-
traedru DΛA . V tem smislu gre za tipičen izrek iz realne algebraične geome-
trije [4], ki se ukvarja s polinomskimi neenakosti. Zanimiva je tudi naslednja
posplošitev na nekomutativne polinome p, ki so pozitivno semidefinitni na
prostem spektraedru DΛA .
Izrek 19 (Konveksni Positivstellensatz [6]). Naj bo p nekomutativen
matrični polinom in Λ enični matrični šop. Potem je p|DΛ  0 tedaj in le
tedaj, ko je
p = hth+
∑
f tjΛfj (7)
za matrične polinome (ne nujno kvadratne) h, fj. Če je stopnja p kvečjemu
2r+1, potem je v (7) stopnja h kvečjemu r+1, stopnje fj pa so vse omejene
z r.
Izrek 19 je »perfekten« Positivstellensatz, saj potrebuje le nenegativnost,
certifikat (7) ima optimalne meje na stopnje, možno pa je izpeljati tudi
meje na velikost matrik, ki jih potrebujemo za p|DΛ  0. Hkrati lahko
98 Obzornik mat. fiz. 63 (2016) 3
i
i
“Klep” — 2016/10/13 — 8:52 — page 99 — #19 i
i
i
i
i
i
Matrično konveksne množice
izrek razumemo kot nelinearno algebraično posplošitev povsem pozitivnih
preslikav. Dokaz [6] tega izreka je povsem drugačen od dokaza posledice 16,
ki smo ga predstavili zgoraj. Sloni namreč na separaciji konveksnih množic
in Gelfand-Naimark-Segalovi konstrukciji ter reši nekomutativen problem
momentov.
C∗-konveksnost
Matrični konveksnosti soroden pojem najdemo tudi v kontekstu C∗-algeber.
Tam govorimo o C∗-konveksnih množicah [12, 11].
LITERATURA
[1] W. B. Arveson, Subalgebras of C∗-algebras, Acta Math. 123 (1969), 141–224.
[2] W. B. Arveson, The noncommutative Choquet boundary, J. Amer. Math. Soc. 21
(2008), 1065–1084.
[3] A. Barvinok, A course in convexity, Amer. Math. Soc., 2002.
[4] J. Bochnack, M. Coste in M.-F. Roy, Real algebraic geometry, Ergebnisse der Mathe-
matik und ihrer Grenzgebiete 3, Springer, 1998.
[5] E. G. Effros in S. Winkler, Matrix convexity: operator analogues of the bipolar and
Hahn-Banach theorems, J. Funct. Anal. 144 (1997), 117–152.
[6] J. W. Helton, I. Klep in S. McCullough, The convex Positivstellensatz in a free
algebra, Adv. Math. 231 (2012), 516–534.
[7] J. W. Helton, I. Klep in S. McCullough, The matricial relaxation of a linear matrix
inequality, Math. Program. 138 (2013), 401–445.
[8] J. W. Helton, I. Klep in S. McCullough, The Tracial Hahn-Banach Theorem, Polar
Duals, Matrix Convex Sets, and Projections of Free Spectrahedra, sprejeto v objavo
v J. Eur. Math. Soc., http://arxiv.org/abs/1407.8198, ogled: 1. 8. 2016.
[9] J. W. Helton in S. McCullough, Every free basic convex semi-algebraic set has an
LMI representation, Ann. of Math. (2) 176 (2012), 979–1013.
[10] D. S. Kaliuzhnyi-Verbovetskyi in V. Vinnikov, Foundations of free noncommutative
function theory, Amer. Math. Soc., 2014.
[11] B. Magajna, On C∗-extreme points, Proc. Amer. Math. Soc. 129 (2001), 771–780.
[12] P. B. Morenz, The structure of C∗-convex sets, Canad. J. Math. 46 (1994), 1007–
1026.
[13] Y. Nesterov in A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Pro-
gramming, SIAM, 1994.
[14] V. Paulsen, Completely bounded maps and operator algebras, Cambridge Univ. Press,
2002.
[15] C. Procesi, The invariant theory of n× n matrices, Adv. Math. 19 (1976), 306–381.
[16] L. Vandenberghe in S. Boyd, Semidefinite programming, SIAM Review 38 (1996),
49–95.
[17] D.-V. Voiculescu, Free analysis questions II: The Grassmannian completion and the
series expansions at the origin, J. reine angew. Math. 645 (2010), 155–236.
[18] G. Wittstock, On matrix order and convexity, North-Holland Mathematics Studies
90 (1984), 175–188.
81–99 99