\documentclass[12pt]{article}
\usepackage{german}
\usepackage{times}
\usepackage{din_a4}
\usepackage{epsf}

\usepackage{amsfonts}
\parindent=0pt
\parskip3mm
\def\qed{\vbox{\hrule
  \hbox{\vrule\hbox to 5pt{\vbox to 8pt{\vfil}\hfil}\vrule}\hrule}}
\def\theorem#1{\par\medbreak\noindent\bf#1\enspace\sl\nobreak}
\def\endtheorem{\par\medskip\rm}
\def\remark#1{\par\medbreak\noindent\bf#1\enspace\rm\nobreak}
\def\endremark{\par\medskip\rm}
\def\proof{\par\medbreak\noindent{\bf Proof.}\enspace}
\def\beweis{\par\medbreak\noindent{\bf Beweis :}\enspace}
\def\ME{\mathop{\rm ME}}
\def\GE{\mathop{\rm GE}}
%\def\endproof{\unskip \nobreak \hskip0pt plus 1fill \qquad \qed \par}
\def\endproof{\nobreak{\parskip0pt\par}\nobreak\rightline{\qed}}
 \newcommand{\N}{\mathbb{N}}
    \newcommand{\Q}{\mathbb{Q}}
    \newcommand{\R}{\mathbb{R}}
    \newcommand{\Z}{\mathbb{Z}}
    \newcommand{\K}{\mathbb{K}}

\begin{document}
 

\hfuzz=3pt
 \def\conv{\mathop{\rm conv}}
\def\lin{\mathop{\rm lin}}
\def\diag{\mathop{\rm diag}}
\def\cone{\mathop{\rm cone}}
\def\L{\hbox{\stk L}}
\def\C{\hbox{\stroke C}}
%\def\K{\hbox{\rm I\kern-3.5pt.K}}
\def\F{\hbox{\Stroke F}}
\def\H{\hbox{\Stroke h}}
\def\lin{\mathop{\rm lin}}
\def\cone{\mathop{\rm cone}}
\def\CONE{\mathop{\rm CONE}}
\def\aff{\mathop{\rm aff}}
\def\rank{\mathop{\rm rank}}
\def\arank{\mathop{\rm arank}}
\def\L{{\rm L}}
\def\Ta{\parindent 20pt\parskip 5pt\par}
\def\Tb{\parskip 0pt\parindent 35pt\hangindent 45pt\par}
\def\Tc{\parskip 0pt\parindent 45pt\hangindent 55pt\par}
\def\Td{\parskip 0pt\parindent 55pt\hangindent 65pt\par}
\def\Te{\parskip 0pt\parindent 65pt\hangindent 75pt\par}
\def\Tf{\parskip 0pt\parindent 75pt\hangindent 85pt\par}
\def\Tg{\parskip 0pt\parindent 85pt\hangindent 95pt\par}
\def\Th{\parskip 0pt\parindent 95pt\hangindent 105pt\par}
\def\Ti{\parskip 0pt\parindent 105pt\hangindent 115pt\par}
\def\Tj{\parskip 0pt\parindent 115pt\hangindent 125pt\par}
\def\Tk{\parskip 0pt\parindent 125pt\hangindent 135pt\par}
\def\Tl{\parskip 0pt\parindent 135pt\hangindent 145pt\par}
\def\Tm{\parskip 0pt\parindent 145pt\hangindent 155pt\par}
\def\P{$\cal P$}
\def\I{$\cal I$}
\def\T{$\cal T$}
\def\CP{co-$\cal P$}
\def\MCP{{\hbox{co-}\cal P}}
\def\MP{{\cal P}}
\def\MI{{\cal I}}
\def\MT{{\cal T}}
\def\NP{${\cal N}\hskip-2pt{\cal P}$}
\def\MNP{{\cal N}\hskip-2pt{\cal P}}
\def\CNP{$\hbox{co-}{\cal N}\hskip-2pt{\cal P}$}
\def\MCNP{\hbox{co-}{\cal N}\hskip-2pt{\cal P}}
\def\NPh{${\cal N}\hskip-2pt{\cal P}$-hard}
\def\NPe{${\cal N}\hskip-2pt{\cal P}$-easy}
\def\NPeq{${\cal N}\hskip-2pt{\cal P}$-equivalent}
\def\NPc{${\cal N}\hskip-2pt{\cal P}$-complete}
\def\relv{\mathbin{|}\allowbreak}
\def\dt{\mathop{\rm dt}}

\def\cpunkt{\raise 1pt\hbox{.}}
\def\hh{\hphantom{-}}
\def\h{\hphantom{0}}
\def\vv{\hbox to 0pt{\vphantom{g}}}
\def\vl{\vrule}
\def\hline{\noalign{\hrule}}
\def\B{$\cal B$}
\def\MB{{\cal B}}
\def\C{$\cal C$}
\def\MC{{\cal C}}
\def\T{$\cal T$}
\def\MT{{\cal T}}
\def\Kr{\mathop{\rm Kr}}


 \def\lft#1{#1\hfil}
\def\rt#1{\hfil#1}

%\vskip-2truecm


%\section{Einf\"uhrung}





\section{Optimierung, Lineare Algebra, \\
Lineare und Ganzzahlige Programmierung :\\
-- Notation --}

Prof. Dr. Martin Gr\"otschel  \hfill 3. Januar 2001

Der nachfolgende Text ist ein Auszug aus dem Skript zur Vorlesung ``Lineare
Optimierung'', welche von mir im Wintersemester 2000/2001 gehalten wurde.
Hier ist die Notation zur Optimierungstheorie zusammengefasst, die von mir
verwendeten Bezeichnungen der Linearen Algebra sind ebenso aufgef"uhrt,
wie Bezeichnungsweisen f"ur lineare und ganzzahlige Programme. 

\setcounter{subsection}{1}

\subsection{Optimierungsprobleme}

Wir wollen zun\"achst ganz informell, ohne auf technische Spitzfindigkeiten
einzugehen, Optimierungsprobleme einf\"uhren. Sehr viele Probleme
lassen sich wie folgt formulieren.

Gegeben seien eine Menge $S$ und eine geordnete Menge $(T,\le)$,
d.~h.~zwischen je zwei Elementen $s,t\in T$ gilt genau eine der folgenden
Beziehungen $s<t$ , $s>t$ oder $s=t$. Ferner sei eine Abbildung
$f:S\rightarrow T$ gegeben. Gesucht ist ein Element  $x^{\ast}\in S$ mit
der Eigenschaft $f(x^{\ast})\ge f(x)$ f\"ur alle $x\in S$
(Maximierungsproblem) oder $f(x^{\ast})\le f(x)$ f\"ur alle $x\in S$
(Minimierungsproblem). Es ist \"ublich hierf\"ur eine der folgenden
Schreibweisen zu benutzen:
$$\begin{array}{ll}
\max_{x\in S}f(x)\quad & \hbox{ oder }\quad\max\{f(x)\mid x\in S\},\\
\min_{x\in S}f(x)\quad & \hbox{ oder }\quad\min\{f(x)\mid x\in S\}.\\
\end{array}
\leqno(1.7)$$
In der Praxis treten als geordnete Mengen $(T,\le)$ meistens die reellen
Zahlen $\R$, die rationalen Zahlen $\Q$ oder die ganzen Zahlen $\Z$ auf,
alle mit der nat\"urlichen Ordnung versehen (die wir deswegen auch gar
nicht erst notieren). Die Aufgabe (1.7) ist viel zu allgemein, um
dar\"uber etwas Interessantes sagen zu k\"onnen. Wenn $S$ durch die
Auflistung aller Elemente gegeben ist, ist das Problem entweder sinnlos
oder trivial (man rechnet ganz einfach $f(x)$ f\"ur alle $x\in S$ aus).
Das hei\ss t,$S$ mu\ss\ irgendwie (explizit oder implizit) strukturiert
sein, so da\ss\ vern\"unftige Aussagen \"uber $S$ m\"oglich sind,
ohne da\ss\ man alle Elemente in $S$ einzeln kennt.
Das gleiche gilt f\"ur die Funktion $f:S\rightarrow T$. Ist sie nur
punktweise durch $x\mapsto f(x)$ gegeben, lohnt sich das Studium von
(1.7) nicht. Erst wenn $f$ durch hinreichend strukturierte ``Formeln''
bzw.~``Eigenschaften'' bestimmt ist, weden tieferliegende mathematische
Einsichten m\"oglich.

Die Optimierungsprobleme, die in der Praxis auftreten, haben fast alle
irgendeine ``vern\"unftige'' Struktur. Das mu\ss\ nicht unbedingt hei\ss en,
da\ss\ die Probleme dadurch auf einfache Weise l\"osbar sind, aber immerhin
ist es meistens m\"oglich, sie in das zur Zeit bekannte und untersuchte
Universum der verschiedenen Typen von
Optimierungsproblemen einzureihen und zu klassifizieren.

Im Laufe des Studiums werden Ihnen noch sehr unterschiedliche
Optimierungsaufgaben begegnen. Viele werden von einem der folgenden Typen
sein.

\remark{(1.8) Ein Kontrollproblem.}
Gegeben sei ein Steuerproze\ss\ (z.~B.~die Bewegungsgleichung eines Autos),
etwa der Form
$$\dot x(t)=f(t,x(t),u(t)),$$
wobei $u$ eine Steuerung ist (Benzinzufuhr). Ferner seien eine
Anfangsbedingung
$$x(0)=x_0,$$
(z.~B.: das Auto steht) sowie eine Endbedingung
$$x(T)=x_1$$
(z.B. das Auto hat eine Geschwindigkeit von 50 km/h) gegeben.
Gesucht ist eine Steuerung
$u$ f"ur den Zeitraum $[0,T]$, so da\ss\ z.~B. $$\int_0^T|u|^2\dt$$
minimal ist (etwa minimaler Benzinverbrauch).
\endremark
\endproof

\remark{(1.9) Ein Approximationsproblem.}
Gegeben sei eine (numerisch schwierig auszuwertende) Funktion $f$,
finde eine Polynom $p$ vom Grad $n$, so da\ss\
$$\Vert f-p\Vert\; \hbox{ oder }\; \Vert f-p\Vert_{\infty}$$
minimal ist.
\endremark
\endproof

\remark{(1.10) Nichtlineares Optimierungsproblem.}
Es seien $f$, $g_i$ $(i=1,\ldots,m)$, $h_j$ $(j=1,\ldots,p)$
differenzierbare  Funktionen von $\R^n\rightarrow
\R$, dann hei\ss t
$$\begin{array}{ll}
\min f(x) & \\
g_i(x)    & \le0\quad i=1,\ldots,m\\
h_i(x)    & =0  \quad j=1,\ldots,p\\
x         & \in\R^n \\
\end{array}$$
ein nichtlineares Optimierungsproblem.
Ist eine der Funktionen nicht differenzierbar, so spricht man von einem
nichtdifferenzierbaren Optimierungsproblem. Im Allgemeinen wird davon
ausgegangen, da"s alle betrachteten Funktionen zumindest stetig sind.

\endremark \endproof

\remark{(1.11) Konvexes Optimierungsproblem.}
Eine Menge $S\subseteq\R^n$ hei\ss t {\bf konvex}, falls gilt: Sind $x,y\in S$
und ist $\lambda\in\R$, $0\le\lambda\le1$, dann gilt $\lambda x+
(1-\lambda)y\in S$. Eine Funktion $f:\R^n\rightarrow\R$ hei\ss t {\bf konvex},
falls f\"ur alle $\lambda\in\R$, $0\le\lambda\le1$ und alle $x,y\in\R^n$
gilt
$$\lambda f(x)+(1-\lambda)f(y)\ge f(\lambda x+(1-\lambda)y).$$
Ist $S\subseteq\R^n$ konvex (z.~B.~kann $S$ wie folgt gegeben sein
$S=\{x\in\R^n\mid g_i(x)\le0,\:i=1,\ldots,m\}$ wobei die $g_i$ konvexe
Funktionen sind), und ist $f:\R^n\rightarrow\R$ eine konvexe Funktion,
dann ist
$$\min_{x\in S}f(x)$$
ein konvexes Minimierungsproblem.
\endremark
\endproof

\remark{(1.12) Lineares Optimierungsproblem (Lineares Programm).}

Gegeben seien $c\in\R^n$, $A\in\R^{(m,n)}$, $b\in\R^m$, dann  hei\ss t

$$\begin{array}{ll}
\max c^Tx & \\
Ax         \le b &\\
x          \in\R^n &\\
\end{array}$$
lineares Optimierungsproblem.
 \endremark
\endproof

\remark{(1.13) Lineares ganzzahliges Optimierungsproblem.}

Gegeben seien $c\in\R^n$, $A\in\R^{(m,n)}$, $b\in\R^m$, dann hei\ss t
$$\begin{array}{ll}

\max c^Tx & \\
Ax         \le b &\\
x          \in\Z^n &\\
\end{array}$$
lineares ganzzahliges (oder kurz: ganzzahliges) Optimierungsproblem.
 \endremark
\endproof

Selbst bei  Optimierungsproblemen wie $(1.8),\ldots,(1.13)$, die nicht
sonderlich allgemein erscheinen m"ogen, kann es sein, da\ss\ (bei spezieller
Wahl der  Zielfunktion $f$ und der Nebenbedingungen) die Aufgabenstellung
(finde ein $x^{\ast}\in S$, so da\ss\ $f(x^{\ast})$ so gro\ss\ (oder klein)
wie m\"oglich ist) keine vern\"unftige Antwort besitzt. Es mag sein, da\ss\
$f$ \"uber $S$ unbeschr\"ankt ist; $f$ kann beschr\"ankt sein \"uber $S$, aber
ein Maximum kann innerhalb $S$ nicht erreicht werden, d.h., das ''max``
m"u"ste eigentlich durch ''sup`` ersetzt werden.  $S$ kann leer sein,
ohne da\ss\ dies a priori klar ist, etc.. Der Leser m\"oge sich Beispiele
mit derartigen Eigenschaften \"uberlegen! Bei der Formulierung von
Problemen dieser Art
mu\ss\ man sich also Gedanken dar\"uber machen, ob die betrachtete
Fragestellung \"uberhaupt eine sinnvolle Antwort erlaubt.

In unserer Vorlesung werden wir uns lediglich mit den
Problemen (1.12)  und (1.13) besch\"aftigen. Das lineare Optimierungsproblem
(1.12) ist sicherlich das derzeit f\"ur die Praxis bedeutendste Problem,
da sich
au\ss erordentlich viele und sehr unterschiedliche reale Probleme
als lineare Programme formulieren lassen. Au\ss erdem liegt eine sehr
ausgefeilte Theorie vor, und mit den modernen Verfahren der linearen
Optimierung k\"onnen derartige Probleme mit Tausenden von Variablen und
Ungleichungen gel\"ost werden. Dagegen ist Problem (1.13),  viel schwieriger.
Die Beschr\"ankung der L\"osungsmenge auf die zul\"assigen ganzzahligen
L\"osungen f\"uhrt direkt zu einem Sprung im Schwierigkeitsgrad des
Problems. Verschiedene spezielle lineare ganzzahlige Programme k\"onnen
in beliebiger Gr\"o\ss enordnung gel\"ost werden. Bei wenig strukturierten
allgemeinen Problemen des Typs (1.13) versagen dagegen die
L\"osungsverfahren manchmal bereits bei weniger als 100 Variablen und
Nebenbedingungen.

\"Uber Kontrolltheorie (Probleme des  Typs (1.8)), Approximationstheorie
(Probleme des Typs (1.9)), Nichtlineare Optimierung (Probleme des Typs (1.10)
und (1.11) werden an der TU Berlin Spezialvorlesungen angeboten.  Es ist
anzumerken, da\ss\ sich sowohl die Theorie als auch die Algorithmen zur
L\"osung von Problemen des Typs (1.8) bis (1.11) ganz erheblich von denen zur
L\"osung von Problemen des Typs (1.12) und (1.13) unterscheiden.

\subsection{Notation}

Wir gehen in der  Vorlesung davon aus, da\ss\ die H\"orer die
Grundvorlesungen Lineare Algebra und Analysis kenen. Wir werden
haupts\"achlich Methoden der linearen Algebra benutzen und setzen eine
gewisse Vertrautheit mit der Vektor- und Matrizenrechnung voraus.

\medskip
\noindent
{\bf Grundmengen}

\medskip
\noindent
Wir benutzen folgende Bezeichnungen:
$$\begin{array}{ll}

\N & =\{1,2,3,\ldots\}\;=\;\hbox{ Menge der {\bf  nat\"urlichen Zahlen,}} \\
\Z & = \hbox{ Menge der {\bf  ganzen Zahlen,}}\\
\Q & = \hbox{ Menge der {\bf  rationalen Zahlen,}} \\
\R & = \hbox{ Menge der {\bf  reellen Zahlen,}}\\
\end{array}$$
und mit $M_+$ bezeichnen wir die Menge der nichtnegativen Zahlen in $M$
f\"ur $M\in\:\{\Z,\Q,\R\}$. Wir betrachten $\Q$ und $\R$ als K\"orper mit
der \"ublichen Addition und Multiplikation und der kanonischen Ordnung
``$\le$''. Desgleichen betrachten wir $\N$ und $\Z$ als mit den \"ublichen
Rechenarten versehen. Wir werden uns fast immer in diesen Zahlenuniversen
bewegen, da diese die f\"ur die Praxis relevanten sind. Manche S\"atze
gelten jedoch nur, wenn wir uns auf $\Q$ oder  $\R$ beschr\"anken. Um
hier eine saubere Trennung zu haben, treffen wir die folgende Konvention.
Wenn wir das Symbol

$$\K$$

benutzen, so hei\ss t dies immer das $\K$ einer der angeordneten K\"orper
$\R$ oder $\Q$ ist. Sollte ein Satz nur f\"ur $\R$ oder nur f\"ur $\Q$
gelten, so treffen wir die jeweils  notwendige Einschr\"ankung.



F\"ur diejenigen, die sich f\"ur m\"oglichst allgemeine S\"atze
interessieren,  sei an dieser  Stelle folgendes vermerkt.  Jeder der
nachfolgend angegebenen S\"atze bleibt ein wahrer Satz, wenn wir als
Grundk\"orper $\K$ einen archimedisch angeordneten K\"orper w\"ahlen.
Ein bekannter Satz besagt, da\ss\ jeder archimedisch angeordnete K\"orper
isomorph zu einem Unterk\"orper von $\R$ ist, der $\Q$ enth\"alt. Unsere
S\"atze bleiben also richtig, wenn wir statt $\K\in\{\Q,\R\}$
irgendeinen archimedisch angeordneten K\"orper $\K$ mit $\Q\subseteq
\K\subseteq\R$ w\"ahlen.

Wir k\"onnen in fast allen  S\"atzen (insbesondere bei denen, die keine
Ganzzahligkeitsbedingungen haben) auch die Voraussetzung ``archimedisch''
fallen lassen, d.~h.~fast alle S\"atze gelten auch f\"ur angeordnete
K\"orper. Vieles was wir im $\K^n$ beweisen, ist auch in beliebigen
metrischen R\"aumen oder R\"aumen mit anderen als euklidischen
Skalarprodukten richtig. Diejenigen, die Spa\ss\ an derartigen
Verallgemeinerungen haben, sind eingeladen, die entsprechenden Beweise
in die allgemeinere Sprache zu \"ubertragen.

In dieser  Vorlesung interessieren wir uns f\"ur so allgemeine Strukturen
nicht. Wir verbleiben in den (f\"ur die Praxis besonders wichtigen)
R\"aumen, die \"uber den reellen oder rationalen Zahlen errichtet werden.
Also, nochmals, wenn immer wir das  Symbol $\K$ im weiteren gebrauchen,
gilt
$$\K\in\{\R,\Q\},$$
und $\K$ ist ein K\"orper mit den \"ublichen Rechenoperationen und
Strukturen. Nat\"urlich ist $\K_+=\{x\in\K\mid x\ge0\}$

Die Teilmengenbeziehung zwischen zwei Mengen $M$ und $N$ bezeichnen wir
wie \"ublich mit $M\subseteq N$. Gilt $M\subseteq N$ und $M\ne N$, so
schreiben wir $M\subset N$. $M\setminus N$ bezeichnet die mengentheoretische
Differenz $\{x\in M\mid x\not\in N\}$.

\medskip
\noindent
{\bf Vektoren und Matrizen}

\medskip
\noindent
Ist $R$ eine beliebige Menge, $n\in\N$, so bezeichnen wir mit
$$R^n$$
die Menge aller {\bf  n-Tupel} oder Vektoren der L\"ange $n$ mit Komponenten
aus $R$. (Aus technischen Gr\"unden ist es gelegentlich n\"utzlich,
Vektoren $x\in R^0$, also Vektoren ohne Komponenten, zu benutzen. Wenn
wir dies tun, werden wir es explizit erw\"ahnen, andernfalls setzen wir
immer $n\ge1$ voraus.) Wir betrachten Vektoren $x=(x_i)_{i=1,\ldots,n}
\:\in R^n$ immer als {\bf  Spaltenvektoren} d.~h.
$$
x=\left( 
\begin{array}{c}
x_1\\\vdots\\ x_n
\end{array} \right),
$$

%$$x=\pmatrix{x_1\\\vdots\\ x_n\\},$$

wollen wir mit Zeilenvektoren rechnen, so schreiben wir $x^T$ (lies:
$x$ {\bf  transponiert}). Die Menge $\K^n$ ist bekanntlich ein $n$-dimensionaler
Vektorraum \"uber $\K$. Mit
$$y^Tx:=\sum^n_{i=1}x_iy_i$$
bezeichnen wir das {\bf  innere Produkt} zweier Vektoren $x,y\in\K^n$.
Wir nennen $x$ und $y$ {\bf  senkrecht (orthogonal)}, falls $x^Ty=0$ gilt.
Der $\K^n$ ist f\"ur uns immer (wenn nichts anderes gesagt wird) mit der
{\bf  euklidischen Norm}
$$\Vert x\Vert:=\sqrt{x^Tx}$$
ausgestattet.

F\"ur Mengen $S,T\subseteq\K^n$ und $\alpha\in\K$ benutzen wir die
folgenden Standardbezeichnungen f\"ur Mengenoperationen
$$\begin{array}{ll}
S+T      & :=\{x+y\in\K^n\mid x\in S, y\in T\},\\
S-T      & :=\{x-y\in\K^n\mid x\in S, y\in T\},\\
\alpha S & :=\{\alpha x\in\K^n\mid x\in S,\}.\\
\end{array}$$

Einige Vektoren aus $\K^n$ werden h\"aufig auftreten, weswegen wir sie mit
besonderen Symbolen bezeichnen. Mit $e_j$ bezeichnen wir den Vektor aus
$\K^n$, dessen $j$-te Komponente 1 und dessen \"ubrige Komponenten 0
sind. Mit 0 bezeichnen wir den Nullvektor, mit {\bf 1} den  Vektor, dessen
Komponenten alle 1 sind. Also

$$
e_j=\left(
\begin{array}{c}
0\\\vdots\\0\ {\bf 1}\\0\\\vdots\\0
\end{array} \right), \quad
0=\left(
\begin{array}{c}
0\\\vdots\\\vdots\\\vdots\\0
\end{array} \right), \quad
{\bf 1} =\left(
\begin{array}{c}
1\\\vdots\\\vdots\\\vdots\\ {\bf 1}
\end{array} \right).
$$




Welche  Dimension die Vektoren $e_j$, $0$, $ {\bf 1} $ haben, ergibt sich jeweils
aus dem Zusammenhang.

\noindent
F\"ur eine Menge $R$ und $m,n\in\N$ bezeichnet
$$R^{(m,n)} \mbox{ oder }   R^{(m\times n)} $$
die Menge der $(m,n)$-{\bf  Matrizen} ($m$ Zeilen, $n$ Spalten) mit
Eintr\"agen aus $R$. (Aus technischen Gr\"unden werden wir gelegentlich
auch $n=0$ oder $m=0$ zulassen, d.~h.~wir werden auch Matrizen mit $m$
Zeilen und ohne Spalten bzw.~$n$  Spalten und ohne Zeilen betrachten.
Dieser  Fall wird jedoch immer explizit erw\"ahnt, somit ist immer
$n\ge1$ und $m\ge1$ vorausgesetzt.) Ist $A\in R^{(m,n)}$, so schreiben wir
$$A=(a_{ij})_{\scriptstyle i=1,\ldots,m\atop\scriptstyle j=1,\ldots,n}$$
und meinen damit, da\ss\ $A$ die folgende Form hat

$$
A=\left( 
\begin{array}{cccc}
a_{11}&a_{12}&\ldots&a_{1n}\\
a_{21}&a_{22}&\ldots&a_{2n}\\
\vdots&\vdots&\ddots&\vdots\\
a_{m1}&a_{m2}&\ldots&a_{mn}
\end{array} \right),
$$

 

Wenn nichts anderes gesagt wird, hat $A$ die  Zeilenindexmenge $M=\{1,\ldots,
m\}$ und die Spaltenindexmenge $N=\{1,\ldots,n\}$. Die $j$-{\bf  te Spalte}
von $A$ ist ein $m$-Vektor, den wir mit $A_{{\cpunkt}j}$ bezeichnen,

$$A_{{\cpunkt}j}=\left( \begin{array}{c} a_{1j}\\\vdots\\ a_{mj}
\end{array} \right).$$

Die $i$-{\bf  te Zeile} von $A$ ist ein Zeilenvektor der L\"ange $n$, den
wir mit $A_{i{\cpunkt}}$ bezeichnen, d.~h.
$$A_{i{\cpunkt}}=(a_{i1},a_{i2},\ldots,a_{in}).$$
Wir werden in dieser Vorlesung sehr h\"aufig Untermatrizen von Matrizen
konstruieren, sie umsortieren und mit ihnen rechnen m\"ussen. Um dies
ohne Zweideutigkeiten durchf\"uhren zu k\"onnen, f\"uhren wir zus\"atzlich
 eine etwas exaktere als die oben eingef\"uhrte Standardbezeichnungsweise
ein.

Wir werden --- wenn immer es aus technischen Gr\"unden notwendig
erscheint --- die Zeilen- und Spaltenindexmengen einer $(m,n)$-Matrix $A$
nicht als Mengen sondern als Vektoren auffassen. Wir sprechen dann vom
$$\vcenter{\halign{\lft{#}\quad&\rt{$#$}&\lft{$#$}\cr
vollen Zeilenindexvektor  & M\;=\; &(1,2,\ldots,m)\cr
vollen Spaltenindexvektor & N\;=\; &(1,2,\ldots,n)\cr
}}$$
von $A$. Ein {\bf  Zeilenindexvektor} von $A$ ist ein Vektor mit h\"ochstens
$m$ Komponenten, der aus $M$ durch Weglassen einiger Komponenten von $M$
und Permutation der \"ubrigen Komponenten entsteht. Analog entsteht ein
{\bf  Spaltenindexvektor} durch Weglassen von Komponenten von $N$ und
Permutation der \"ubrigen Komponenten. Ist also
$$\begin{array}{ll}
I=(i_1,i_2,\ldots,i_p)\quad & \hbox{ ein Zeilenindexvektor von $A$ und } \\
J=(j_1,j_2,\ldots,j_q)\quad & \hbox{ ein Spaltenindexvektor von $A$, } \\
\end{array}$$
so gilt immer $i_s,i_t\in\{1,\ldots,m\}$ und $i_s\ne i_t$ f\"ur
$1\le s<t\le m$, und analog gilt
$j_s,j_t\in\{1,\ldots,n\}$ und $j_s\ne j_t$ f\"ur
$1\le s<t\le n$. Wir setzen


$$
A_{IJ}:=\left( 
\begin{array}{cccc}
 a_{i_1j_1}&a_{i_1j_2}&\ldots&a_{i_1j_q}\\
a_{i_2j_1}&a_{i_2j_2}&\ldots&\\
\vdots&\vdots&\ddots&\vdots\\
a_{i_pj_1}&a_{i_pj_2}&\ldots&a_{i_pj_q}
\end{array} \right)
$$

und nennen $A_{IJ}$ {\bf  Untermatrix} von $A$.

$A_{IJ}$ ist also eine $(p,q)$-Matrix, die aus $A$ dadurch entsteht, da\ss\
man die  Zeilen, die zu Indizes geh\"oren, die nicht in $I$ enthalten
sind, und die Spalten, die zu Indizes geh\"oren, die nicht in $J$ enthalten
sind, streicht und dann die so entstehende Matrix umsortiert.

Ist $I=(i)$ und $J=(j)$, so erhalten wir zwei Darstellungsweisen f\"ur
Zeilen bzw.~Spalten von $A$:
$$\begin{array}{ll}
A_{IN} & = A_{i{\cpunkt}}\;,\\
A_{MJ} & = A_{{\cpunkt}j}\;.\\
\end{array}$$
Aus Gr\"unden der Notationsvereinfachung werden wir auch die folgende (etwas
unsaubere) Schreibweise benutzen. Ist $M$ der volle Zeilenindexvektor
von $A$ und $I$ ein Zeilenindexvektor, so schreiben wir auch
$$I\subseteq M,$$
obwohl $I$ und $M$ keine Mengen sind, und f\"ur
$i\in\{1,\ldots,m\}$ benutzen wir
$$i\in I\quad\hbox{ oder } i\not\in I,$$
um festzustellen, da\ss\ $i$ als Komponente von $I$ auftritt oder nicht.
Analog verfahren wir bez\"uglich der Spaltenindizes.

Gelegentlich spielt die tats\"achliche Anordnung der  Zeilen und Spalten
keine Rolle. Wenn also z.~B.~$I\subseteq\{1,\ldots,n\}$ und
$J\subseteq\{1,\ldots,m\}$ gilt, dann werden wir auch einfach schreiben
$$A_{IJ},$$
obwohl diese Matrix dann nur bis auf Zeilen- und Spaltenpermutationen
definiert ist. Wir werden versuchen, diese
Bezeichnungen immer so zu verwenden, da\ss\ keine Zweideutigkeiten auftreten.
Deshalb treffen wir ab jetzt die Verabredung, da\ss\ wir --- falls wir
Mengen (und nicht Indexvektoren) $I$ und $J$ benutzen -- die Elemente von
$I=\{i_1,\ldots,i_p\}$ und von $J=\{j_1,\ldots,j_q\}$ kanonisch anordnen,
d.~h.~die Indizierung der Elemente von $I$ und $J$ sei so gew\"ahlt,
da\ss\ $i_1<i_2<\ldots<i_p$ und $j_1<j_2<\ldots<j_q$ gilt. Bei dieser
Verabredung ist dann $A_{IJ}$ die Matrix die aus $A$ durch Streichen der
Zeilen $i$, $i\not\in I$, und der Spalten $j$, $j\not\in J$, entsteht.

Ist $I\subseteq\{1,\ldots,m\}$ und $J\subseteq\{1,\ldots,n\}$ oder sind
$I$ und $J$ Zeilen- bzw.~Splaltenindexvektoren, dann schreiben wir auch
$$A_{I{\cpunkt}}\quad\hbox{ statt }\quad A_{IN}$$
$$A_{{\cpunkt}J}\quad\hbox{ statt }\quad A_{MJ}$$
$A_{I{\cpunkt}}$ entsteht also aus $A$ durch Streichen der Zeilen $i$,
$i\not\in I$, $A_{{\cpunkt}J}$ durch  Streichen der Spalten $j$,
$j\not\in J$.

\noindent
Sind $A,B\in\K^{(m,n)}$, $C\in\K^{(n,s)}$, $\alpha\in\K$, so sind
$$\vcenter{\halign{\rt{#}\quad&\lft{$#$}\cr
die {\bf  Summe} & A\,+\,B\;,\cr
das {\bf  Produkt} & \alpha A,\cr
das {\bf  Matrixprodukt} & AC\cr
}}$$
wie in der linearen Algebra \"ublich definiert.

F\"ur einige h\"aufig auftretende Matrizen haben wir spezielle Symbole
reserviert. Mit 0 bezeichnen wir die Nullmatrix (alle Matrixelemente
sind Null), wobei sich die Dimension der Nullmatrix jeweils aus dem
Zusammenhang ergibt. (Das Symbol 0 kann also sowohl eine Zahl, einen
Vektor als auch eine Matrix bezeichnen). Mit $I$ bezeichnen wir die
Einheitsmatrix. Diese Matrix ist quadratisch, die Hauptdiagonalelemente
von $I$ sind Eins, alle \"ubrigen Null. Wollen wir die Dimension von $I$
betonen, so schreiben wir auch $I_n$ und meinen damit die
$(n,n)$-Einheitsmatrix. Diejenige  $(m,n)$-Matrix, bei der alle Elemente
Eins sind, bezeichnen wir mit $E$. Wir schreiben auch $E_{m,n}$ bzw.~$E_n$,
um die Dimension zu spezifizieren ($E_n$ ist eine $(n,n)$-Matrix).
Ist $x$ ein $n$-Vektor, so bezeichnet $\diag(x)$ diejenige
$(n,n)$-Matrix $A=(a_{ij})$ mit $a_{ii}=x_i$ $(i=1,\ldots,n)$ und
$a_{ij}=0$ $(i\ne j)$. Wir halten an dieser Stelle noch einmal folgendes
fest. Wenn wir von einer Matrix $A$ sprechen, ohne anzugeben, welche
Dimension sie hat und aus welchem Bereich sie ist, dann nehmen wir implizit
an, da\ss\ gilt $A\in\K^{(m,n)}$.
Analog gilt immer $x\in\K^n$, wenn sich nicht aus dem Zusammenhang anderes
ergibt.

\medskip
\noindent
{\bf Kombinationen von Vektoren, H\"ullen, Unabh\"angigkeit}

\medskip
\noindent
Ein Vektor $x\in\K^n$ hei\ss t {\bf  Linearkombination} der Vektoren
$x_1,\ldots,
x_k\in\K^n$, falls es einen Vektor $\lambda=(\lambda_1,\ldots,\lambda_k)^T
\in\K^k$ gibt mit
$$x=\sum^k_{i=1}\lambda_ix_i\;.$$
Gilt zus\"atzlich
$$\left.\vcenter{\halign{\lft{$#$}\cr
     \lambda\ge 0\cr
     \lambda^T{\bf 1}  =1\cr
     \lambda \ge0 \hbox{ und } \lambda^T{\bf 1}  =1\cr}}\quad\right\}
   \quad\hbox{so hei\ss t} \quad x \quad
   \left\{\quad\vcenter{\halign{\lft{$#$}\cr
     \hbox{{\bf  konische} }\cr
     \hbox{{\bf  affine}}\cr
     \hbox{{\bf  konvexe}}\cr}}\quad\right\}
     \quad\hbox{{\bf  Kombination} }$$
der Vektoren $x_1,\ldots,x_k$. Diese Kombinationen hei\ss en {\bf  echt},
falls weder $\lambda=0$ noch $\lambda=e_j$ f\"ur ein
$j\in\{1,\ldots,k\}$ gilt.

\noindent
F\"ur eine nichtleere Teilmenge $S\subseteq\K^n$ hei\ss t
 $$\left.\vcenter{\halign{\lft{$#$}\cr
     \lin (S)\cr
     \cone (S)\cr
     \aff (S)\cr
     \conv (S)\cr}}\quad\right\}
   \quad\hbox{die} \quad
   \left\{\quad\vcenter{\halign{\lft{$#$}\cr
     \hbox{{\bf  lineare}}\cr
     \hbox{{\bf  konische}}\cr
     \hbox{{\bf  affine}}\cr
     \hbox{{\bf  konvexe}}\cr}}\quad\right\}
   \quad\hbox{{\bf  H\"ulle} von S, d.~h.}$$

%\ins{lin(S)}\ins{cone(S)}\ins{aff(S)}\ins{conv(S)}


die Menge aller Vektoren, die als lineare (konische, affine oder konvexe)
Kombination von endlich vielen Vektoren aus $S$ dargestellt werden
k\"onnen. Wir setzen au\ss erdem

\vspace*{-4mm}

$$\begin{array}{ll}
\lin (\emptyset ) & := \cone (\emptyset) := \{0\},\\
\aff (\emptyset ) & := \conv (\emptyset) := \emptyset.
\end{array}$$
Ist $A$ eine $(m,n)$-Matrix, so schreiben wir auch
$$\lin(A),\;\cone(A),\;\aff(A),\;\conv(A)$$
und meinen damit die lineare, konische, affine bzw.~konvexe H\"ulle der
Spaltenvektoren $A_{{\cpunkt}1},A_{{\cpunkt}2}, \linebreak 
\ldots,A_{{\cpunkt}n}$ von $A$. Eine Teilmenge $S\subseteq\K^n$ hei\ss t
 $$\left\{\quad\vcenter{\halign{\lft{$#$}\cr
      \hbox{{\bf  linearer Raum}}\cr
      \hbox{{\bf  Kegel}}\cr
      \hbox{{\bf  affiner Raum}}\cr
      \hbox{{\bf  konvexe Menge}}\cr}}\quad\right\}
      \quad\hbox{falls}\quad
   \left\{\quad\vcenter{\halign{\lft{$#$}\cr
   S=\lin (S)\cr
   S=\cone (S)\cr
   S=\aff (S)\cr
   S=\conv (S)\cr}}\quad\right\}.$$

Eine nichtleere endliche Teilmenge $S\subseteq\K^n$ hei\ss t {\bf  linear}
(bzw.~{\bf  affin}) {\bf  unabh\"an\-gig}, falls kein Element von $S$ als
echte Linearkombination (bzw.~Affinkombination) von Elementen von $S$
dargestellt werden kann. Die leere Menge ist affin, jedoch nicht linear
unabh\"angig. Jede Menge $S\subseteq\K^n$, die nicht linear bzw.~affin
unabh\"angig ist, hei\ss t {\bf  linear} bzw.~{\bf  affin abh\"angig}. Aus
der linearen Algebra wissen wir, da\ss\ eine linear (bzw.~affin)
unabh\"angige Teilmenge des $\K^n$ h\"ochstens $n$ (bzw.~$n+1$) Elemente
enth\"alt. F\"ur eine Teilmenge $S\subseteq\K^n$ hei\ss t die Kardinalit\"at
einer gr\"o\ss ten linear (bzw.~affin) unabh\"angigen Teilmenge von $S$
der {\bf  Rang} (bzw.~{\bf  affine Rang}) von $S$. Wir schreiben daf\"ur
rang$(S)$  bzw.~arang$(S)$. Die {\bf  Dimension} einer Teilmenge
$S\subseteq\K^n$, Bezeichnung: $\dim(S)$, ist die Kardinalit\"at
einer gr\"o\ss ten affin unabh\"angigen  Teilmenge von $S$ minus 1,
d.~h.~$\dim(S)=\mbox{ arang}(S)-1$.

Der {\bf  Rang einer Matrix} $A$, bezeichnet mit
rang($A)$, ist der Rang ihrer
Spaltenvektoren. Aus der linearen Algebra wissen wir, da\ss\ rang$(A)$
mit dem Rang der Zeilenvektoren von $A$ \"ubereinstimmt. Gilt f\"ur
eine $(m,n)$-Matrix $A$, rang$(A)=\min\{m,n\}$, so sagen wir, da\ss\
$A$ {\bf  vollen Rang} hat. Eine $(n,n)$-Matrix mit vollem Rang
ist {\bf  regul\"ar}, d.~h.~sie besitzt eine (eindeutig bestimmte)
inverse Matrix (geschrieben $A^{-1}$) mit der Eigenschaft
$AA^{-1}=I$.



\end{document}