# Satz von der eingeschränkten Invertierbarkeit

Der Satz von der eingeschränkten Invertierbarkeit (englisch restricted invertibility theorem), auch Satz von Bourgain-Tzafriri, ist ein mathematischer Satz aus der Funktionalanalysis. Das Theorem beschäftigt sich mit der Frage der Invertierbarkeit eines linearen Operators (respektive einer quadratischen Matrix) auf einem endlichdimensionalen $l_{p}^{n}$-Raum. Das Theorem hat bedeutende Anwendungen in der lokalen Theorie der Banach-Räume.
Der Satz wurde von Jean Bourgain und Lior Tzafriri bewiesen.

## Eingeschränkte Invertierbarkeit

Notation:
* $l_{p}^{n}:=(\mathbb {R} ^{n},\|\cdot \|_{p}).$
* $l_{p}:=l_{p}^{\infty }$ ist der Folgenraum der $p$-summierbaren Folgen.
* $\|L\|$ ist die Operatornorm.
* $|S|$ ist die Kardinalität von $S$.

### Aussage

Sei $L:l_{2}^{n}\to l_{2}^{n}$ ein linearer Operator, so dass für jeden Einheitsvektor $\{e_{1},\dots ,e_{n}\}$ gilt
    $\|Le_{j}\|=1,\quad \forall j\in \{1,\dots ,n\}$.
Dann existieren universelle Konstanten $c,d>0$ und eine Index-Untermenge $S\subseteq \{1,\dots ,n\}$, welche mindestens
    $|S|\geq {\frac {cn}{\|L\|^{2}}}$
Indizes hat, so dass für die Norm der Restriktion gilt
    $\left\|\sum \limits _{i\in S}a_{i}Le_{i}\right\|^{2}\geq d\sum \limits _{i\in S}|a_{i}|^{2}$
wobei $\{a_{i}\}_{i\in S}$ beliebige Skalare sind.

## Erläuterungen an einem Beispiel

Sei $L$ eine reelle $n\times n$-Matrix und $L_{S}$ bezeichnet die Restriktion von $L$ auf die Spalten mit Indizes in $S$
    $L_{S}:=\sum \limits _{i\in S}Le_{i}.$
Es gilt nun für jeden Vektor $a\in \mathbb {R} ^{|S|}$, dass
    $\left\|L_{S}a\right\|\geq d\|a\|.$
Betrachtet man nun den kleinsten Singulärwert (oder allgemeiner die Schatten-Norm)
    $\sigma _{\operatorname {min} }(L_{S})=\min \limits _{\|x\|=1}\|L_{S}x\|$
dann gilt
    $\sigma _{\operatorname {min} }(L_{S})\geq d>0$
und daraus folgt, dass $L_{S}$ invertierbar ist. Weiter besitzt $L_{S}$ mindestens $cn/\|L\|^{2}$ Spalten. Außerdem folgt aus der Konditionsnummer
    $\kappa (L_{S})={\frac {\sigma _{\operatorname {max} }(L_{S})}{\sigma _{\operatorname {min} }(L_{S})}},$
dass die Operatornorm der Inversen nach oben beschränkt ist
    $\|L_{S}^{-1}\|={\frac {\kappa (L_{S})}{\|L_{S}\|}}={\frac {\sigma _{\operatorname {max} }(L_{S})}{\|L_{S}\|\sigma _{\operatorname {min} }(L_{S})}}\leq {\frac {\sigma _{\operatorname {max} }(L_{S})}{d^{2}}}=:K.$

## Verallgemeinerungen

Es existieren diverse Verallgemeinerungen und verwandte Aussagen (u. a. von Spielman-Srivastava, Vershynin und Naor-Youssef). Zum Beispiel kann die Restriktion der Einheitsvektoren $\|Le_{j}\|=1$ entfernt werden. Es existiert auch eine Version für unendlichdimensionale Räume.

### Bourgain-Tzafriri-Vermutung

Eine Verallgemeinerung ist die Bourgain-Tzafriri-Vermutung (BT-Vermutung), welche äquivalent zum Kadison-Singer-Problem (KS-Problem) ist. Das KS-Problem wurde 2013 positiv gelöst und somit auch die BT-Vermutung.

#### Formulierung

Sei $L:l_{2}^{n}\to l_{2}^{n}$ ein linearer Operator, so dass für jeden Einheitsvektor $\{e_{1},\dots ,e_{n}\}$ gilt
    $\|Le_{j}\|=1,\quad \forall j\in \{1,\dots ,n\}$.
Dann existiert eine universelle Konstante $c>0$, so das für jede positive Zahl $b>0$ mit
    $\|L\|\leq b$
ein $m=m(b)\in \mathbb {N}$ und eine Partition $\{I_{j}\}_{j=1}^{m}$ von $\{1,\dots ,n\}$ existieren, so dass
    $\left\|\sum \limits _{i\in I_{j}}a_{i}Le_{i}\right\|^{2}\geq c\sum \limits _{i\in I_{j}}|a_{i}|^{2},\qquad 1\leq j\leq m$
wobei $\{a_{i}\}_{i\in I_{j}}$ beliebige Skalare sind.