2.3 Konkrete Fragen, die wir im Laufe der Vorlesungen LA1/2 werden beantworten können

Um den vorherigen Abschnitt nicht vollständig im Vagen zu lassen, nenne ich hier einige Fragen/Problemstellungen, die wir mit den im Laufe der Vorlesung entwickelten Methoden beantworten oder mindestens besser verstehen können.

Zum Teil handelt es sich um »Anwendungen« von Methoden der linearen Algebra auf mathematische Probleme, wo diese nicht offensichtlich sind. Zum Teil handelt es sich um Anwendungen, die außerhalb der Universität wichtig sind. Viele (mindestens ebenso interessante) Anwendungen innerhalb der Mathematik müssen leider außen vor bleiben, weil mehr Mathematik benötigt wird, als uns im Moment zur Verfügung steht, um über diese Probleme überhaupt zu sprechen.

(Für viele der folgenden Fragen/Probleme gibt es mehrere verschiedene Lösungsansätze. Man muss nicht immer Lineare Algebra benutzen – aber oft ist es möglich und nützlich.)

Wenn Ihnen die Formelsprache zu kompliziert ist, dann überspringen Sie die Frage erstmal. Es wird nicht lange dauern, bis Ihnen das keine Probleme mehr bereitet, und dann können Sie noch einmal hierher zurückkommen.

Frage 2.1

Die Fibonacci-Folge (siehe auch Wikipedia (Englisch)) ist die Folge natürlicher Zahlen, die gegeben ist durch

\[ F_0=0, \quad F_1=1,\quad F_{n} = F_{n-1} + F_{n-2}\ \text{für alle}\ n\ge 2. \]

Die ersten Terme der Folge lauten also $0, 1, 1, 2, 3, 5, 8, 13, 21$.

Wir werden später die folgenden Fragen leicht mit Linearer Algebra beantworten können:

Wie kann man möglichst schnell eine einzelne Fibonacci-Zahl $F_n$ für großes $n$ berechnen (zum Beispiel $F_{10\, 000\, 000\, 000}$), ohne alle Fibonacci-Zahlen dazwischen berechnen zu müssen? Siehe Beispiel 5.60.
Was ist eine geschlossene Formel für die $n$-te Fibonacci-Zahl $F_n$, in der die kleineren Fibonacci-Zahlen nicht auftreten? Siehe Ergänzung 6.60, Beispiel 10.19.

Die dabei verwendeten Methoden sind oft auch nützlich, um andere Folgen, die in ähnlicher Weise (durch eine »lineare Rekursionsgleichung«) definiert sind, zu analysieren. (Zum Teil lassen sich diese Fragen natürlich auch auf anderem Wege beantworten. Versuchen Sie es ruhig einmal!)

Frage 2.2

Der folgende Satz ist wichtig für das Verfahren des Quadratischen Siebes, das ist eines der besten bekannten Verfahren, um sehr große ganze Zahlen in ihre Primfaktoren zu zerlegen. Die Frage, ob/wie man das »schnell« machen kann, ist von hoher Bedeutung für Verschlüsselungsverfahren (beziehungsweise die Frage, ob man sie knacken kann), die an allen möglichen Stellen eingesetzt werden (Online-Banking, …), zum Beispiel das RSA-Verfahren .

Satz 2.3

Gegeben seien eine natürliche Zahl $n\ge 1$ und $n$ verschiedene Primzahlen $p_1$, …, $p_n$. Wenn $a_1$, …, $a_{n+1}$ natürliche Zahlen ${\gt}1$ sind, in deren Primfaktorzerlegungen nur die Primzahlen $p_1$, …, $p_n$ vorkommen, dann gibt es eine Möglichkeit, einige der Zahlen $a_i$ so auszuwählen, dass ihr Produkt eine Quadratzahl ist.

Beispiel 2.4

Wir betrachten die Primzahlen $2$, $3$ und $7$ und die vier Zahlen $7$, $12$, $18$, $21$. Dann ist $7 \cdot 12 \cdot 21 = 4\cdot 9\cdot 49 = (42)^2$ eine Quadratzahl.

Wir kommen in Ergänzung 6.63 auf diese Frage zurück.

Frage 2.5

Wann kann man ein Rechteck wie in der Abbildung lückenlos durch Quadrate überdecken?

$\begin{tikzpicture} [scale=0.7] \draw [thick] (1, 0) -- (9, 0) --(9, 5) -- (1, 5) -- (1,0); \draw [thick] (1, 0) -- (6, 0) --(6, 5) -- (1, 5) -- (1,0); \draw [thick] (6, 0) -- (9, 0) -- (9, 3) -- (6, 3) -- (6, 0); \draw [thick] (6, 3) -- (6, 5) -- (8, 5) -- (8, 3) -- (6, 3); \draw [thick] (8, 5) -- (9, 5) -- (9, 4) -- (8, 4); \end{tikzpicture}$

Es gilt der folgende Satz:

Satz 2.6

Sei $R$ ein Rechteck mit Seitenlängen $a, b\in \mathbb R_{{\gt}0}$. Dabei sei $a\in \mathbb Q$ und $b\in \mathbb R\setminus \mathbb Q$. Dann lässt sich $R$ nicht vollständig durch (endlich viele) Quadrate überdecken, die sich nicht überlappen.

Wir werden das in Kapitel 7 beweisen können, siehe Ergänzung 7.65.

Die nächste »Frage« ist ziemlich lang, aber ein gutes (und inzwischen ziemlich prominentes) Beispiel für eine Anwendung von Methoden der Linearen Algebra, mit denen (fast) jede∗r täglich in Kontakt ist.

Frage 2.7 Googles Page-rank-Algorithmus

Wir wollen das Problem betrachten, eine gute Internet-Suchmaschine zu bauen. Wir stellen uns vor, dass bereits eine Datenbank aller Webseiten, die eine Benutzer∗in finden können soll, existiert. Die Frage, die wir betrachten wollen, ist, wie die Suchmaschine entscheidet, in welcher Reihenfolge die Treffer zu einem Suchbegriff angezeigt werden. Dass Google ziemlich schnell alle damaligen Mitbewerber fast vollständig vom Markt verdrängen konnte, lag wesentlich mit daran, dass bei Google viel verlässlicher die relevanten Treffer weit oben in der Liste der Suchergebnisse angezeigt wurden. Der Ansatz, den wir hier beschreiben, ist die Basis des Google-Algorithmus. (Genauer des Page-rank-Algorithmus, der die Grundlage für die Google-Suche in den ersten Jahren nach der Gründung war. Sicher wurden nicht alle Feinheiten verraten, und inzwischen wurde der Algorithmus weiterentwickelt und/oder durch andere Methoden ersetzt. Das Prinzip, das wir hier kennenlernen, ist aber natürlich nach wie vor von Bedeutung; die Frage, wie man »Wichtigkeit/Relevanz« in einem »Netzwerk« messen kann, stellt sich ja an vielen Stellen.)

Wir stellen uns vor, dass wir die Webseiten in unserer Datenbank durchnummerieren. Für jede Webseite wollen wir eine Zahl berechnen, die misst, wie »wichtig« diese Seite ist. Für die erste Seite in unserer Datenbank bezeichnen wir die zu findende Zahl mit $x_1$, für die zweite mit $x_2$ usw., also für die $i$-te Seite mit $x_i$. Je höher der Wert $x_i$ ist, desto höher würde die Seite in der Liste der Suchergebnisse angezeigt, wenn sie bei den Treffern dabei ist. (Wenn Sie die Formelsprache hier oder in den nächsten Absätzen stört, dann springen Sie erstmal zu Beispiel 2.8.)

Dabei messen die Zahlen $x_i$ die »Relevanz« einer Seite unabhängig von dem jeweiligen Suchbegriff. Wenn dann eine Suche ausgeführt wird, werden die entsprechenden Webseiten als »Treffer« aus der Datenbank ausgewählt und dann in der Reihenfolge ihrer Relevanz angezeigt.

Die erste wesentliche Überlegung ist, die Relevanz einer Webseite nicht durch eine komplizierte Analyse ihres Inhalts zu messen, sondern mit einer Methode, die sich leicht mit den erhobenen Daten umsetzen lässt. Im ersten Schritt stellen wir fest, dass eine Seite umso relevanter sein dürfte, je mehr andere Seiten auf sie verlinken. Wir könnten also einfach die Anzahl dieser Links für jeden Suchtreffer zählen und die Treffer dementsprechend anordnen. Wenn wir mit $L_i$ die Menge aller Webseiten bezeichnen, die auf die $i$-te Seite verlinken, so könnten wir diesen Ansatz schreiben als

\[ x_i = \# L_i,\quad \text{die Anzahl der Elemente in}\ L_i. \]

Wir wollen dabei nicht berücksichtigen, wenn eine Seite auf sich selbst verlinkt; es soll also $i$ kein Element von $L_i$ sein.

Es ist aber vernünftig, das Verfahren noch etwas zu verfeinern. Es sollte eine Rolle spielen, ob ein Link auf die betrachtete Seite von einer »wichtigen« oder »unwichtigen« Seite kommt. Wir sollten in der vorherigen Formel nicht für jedes Element $j$ von $L_i$ (wir schreiben dann $j\in L_i$) eine $1$ zählen, sondern den Einfluss entsprechend gewichten – und zwar gerade mit der Zahl $x_j$, die die Relevanz der Seite $j$ angibt. Ein besserer Ansatz wäre also

\[ x_i = \sum _{j\in L_i} x_j, \]

das heißt $x_i$ ist die Summe aller Werte $x_j$, wo die $j$-te Seite einen Link auf die $i$-te Seite hat. Wir benutzen hier das Summensymbol $\sum $ ( der große griechische Buchstabe Sigma, siehe Beispiel 3.43) als Abkürzung für die Summe aller derjenigen $x_j$ mit $j\in L_i$. Das macht einen komplizierten Eindruck. Denn wir können $x_i$ nicht mehr direkt berechnen, weil wir für die Berechnung der $x_j$ ja möglicherweise $x_i$ schon kennen müssten (wenn $i\in L_j$ ist). Trotzdem ist es nicht so schlimm, wie es aussieht: Wir können die Gesamtheit dieser Gleichungen (für alle $i$) als ein sehr großes lineares Gleichungssystem in den Unbestimmten $x_i$ auffassen.

Diese Änderung eröffnet noch die folgende Interpretationsmöglichkeit für die Zahlen $x_i$. Es ist klar, dass das obige Gleichungssystem (wenn es überhaupt eine Lösung hat, für die nicht alle $x_i$ gleich Null sind) keine eindeutige Lösung haben kann; denn wenn wir eine Lösung haben, erhalten wir eine neue Lösung, indem wir jedes $x_i$ mit derselben Zahl multiplizieren. Für die resultierende Sortierung nach Relevanz tut das aber nichts zu Sache (jedenfalls, wenn wir nur mit positiven Zahlen multiplizieren). Wenn wir optimistisch sind, könnten wir versuchen, die Zahlen $x_i$ so zu suchen, dass sie alle zwischen $0$ und $1$ liegen und dass die Summe aller $x_i$ gleich $1$ ist. Damit stellt man sicher, dass die Skala nicht ausufert und man die Werte möglichst konkret festnagelt. So kann man zum Beispiel besser Vergleiche zwischen solchen Berechnungen für verschiedene »Netzwerke« anstellen.

Mit dieser Konvention kann man die Zahl $x_i$ auch als Wahrscheinlichkeit interpretieren. Dazu stellen wir uns eine Internet-Surfer∗in vor, die auf jeder Seite zufällig irgendeinen der Links auf andere Seiten aufruft. Dann ist $x_i$ die Wahrscheinlichkeit, dass sie sich gerade auf der $i$-ten Seite aufhält. Zum Beispiel würde $x_2 = 0,013 = 1,3\% $ bedeuten, dass die Wahrscheinlichkeit, sich dabei gerade auf der zweiten Seite zu befinden, $1,3\% $ ist.

Eine weitere Verbesserung des Verfahrens ist die folgende. Mit der obigen Formel könnte selbst eine relativ unwichtige Seite die Bewertung vieler anderer Seiten dadurch beeinflussen, dass sie sehr viele Links auf andere Seiten einbaut. Es ist daher vernünftig, ein Stimmgewicht einzuführen, das bewirkt, dass eine Seite ihre Relevanz sozusagen auf alle Seiten aufteilt, auf die sie verlinkt. Wir ersetzen daher die Gleichung oben durch

\[ x_i = \sum _{j\in L_i}\frac{1}{n_j}x_j, \]

wobei $n_j$ die Anzahl der ausgehenden Links von Seite $j$ ist. (Weil $j\in L_i$ für alle $j$, die einen Beitrag zu der Summe liefern, verlinkt Seite $j$ mindestens auf Seite $i$, also ist $n_j {\gt} 0$ und wir können durch diese Zahl teilen.)

Beispiel 2.8

Betrachten wir als Beispiel das in der Abbildung dargestellte Mini-Internet; Links sind dort als Pfeile dargestellt.

$\begin{tikzpicture} [>=Stealth] \graph[simple necklace layout, nodes={circle,minimum size=.7cm,draw}, node sep=1cm]{ 1,2,6,4,5,3; 1->[xshift=1pt,yshift=2pt]3 -> 2, 3 ->[xshift=-1pt,yshift=-2pt]1 -> 2; 3 -> 5 -> 6 ->[xshift=-1pt,yshift=-2pt] 4 -> 3; 5 ->[xshift=-1pt,yshift=2pt] 4 ->[xshift=1pt,yshift=2pt] 6; 5 -> 2; 6 -> 1; 2 -> 4; }; \end{tikzpicture}$

Die Daten, die wir brauchen, um das gesuchte Gleichungssystem aufzustellen, sind in der folgenden Tabelle gesammelt:

Seite	Verlinkt von	Anzahl ausgehende Links
1	3, 6	2
2	1, 3, 5	1
3	1, 4	3
4	2, 5, 6	2
5	3	3
6	4, 5	2

Aus diesen Daten stellen wir nach dem obigen Rezept das folgende lineare Gleichungssystem auf. Zum Beispiel erhalten wir folgendermaßen dir erste Gleichung: Auf die erste Seite verlinken die Seiten $3$ und $6$, also sind nur die Koeffizienten von $x_3$ und $x_6$ auf der rechten Seite der Gleichung $\ne 0$. Für den Koeffizienten von $x_3$ erhalten wir $\frac13$, weil die dritte Seite $3$ ausgehende Links hat. Die sechste Seite hat $2$ ausgehende Links, also ist der Koeffizient von $x_6$ gleich $\frac12$.

$x_1$	=				$\frac{1}{3} x_3$					$+$	$\frac{1}{2} x_6$
$x_2$	=	$\frac{1}{2} x_1$		$+$	$\frac{1}{3} x_3$			$+$	$\frac{1}{3} x_5$
$x_3$	=	$\frac{1}{2} x_1$				$+$	$\frac{1}{2} x_4$
$x_4$	=		$x_2$					$+$	$\frac{1}{3} x_5$	$+$	$\frac{1}{2} x_6$
$x_5$	=				$\frac{1}{3} x_3$
$x_6$	=						$\frac{1}{2} x_4$	$+$	$\frac{1}{3} x_5$

An dieser Stelle können wir schon eine Besonderheit feststellen, die bei der weiteren Betrachtung eine große Rolle spielen wird. Wenn man auf der rechten Seite alle Koeffizienten einer Spalte aufsummiert, dann ist die Summe immer gleich $1$. Überzeugen Sie sich, dass das in der Tat eine direkte Konsequenz davon ist, wie wir das Gleichungssystem aufbauen. (Es gibt allerdings die Möglichkeit, dass als »Sonderfall« Spalten auftreten, in denen alle Koeffizienten $=0$ sind. Wann wäre das der Fall?)

Eine Lösung dieses Gleichungssystems ist gegeben durch $(32, 36, 45, 58, 15, 34)$. Jedenfalls lässt sich leicht nachprüfen, dass diese Zahlen wirklich alle $6$ Gleichungen erfüllen. Es ist auch nicht »schwierig«, diese Lösung (zum Beispiel durch Einsetzen und/oder Elimination von Variablen) zu finden. Allerdings macht es sich bei einem Gleichungssystem dieser Größe bezahlt, einen systematischen Ansatz zu wählen, wie wir ihn demnächst kennenlernen werden (den Gauß-Algorithmus, Abschnitt 5.2).

Wir hatten auch gesagt, dass wir als Summe der $x_i$ gerne $1$ erhalten möchten. Das ist natürlich mit der obigen Lösung nicht erfüllt. Wir können die Lösung aber skalieren: Wenn wir alle $x_i$ mit derselben Zahl multiplizieren, oder durch dieselbe Zahl teilen, entsteht aus einer Lösung des Gleichungssystems eine neue Lösung. In diesem Fall teilen wir alle Einträge durch die Gesamtsumme $220$. Wir erhalten die Lösung $(\frac{32}{220}, \frac{36}{220}, \frac{45}{220}, \frac{58}{220}, \frac{15}{220}, \frac{34}{220})$, wobei wir ausnahmsweise nicht gekürzt haben, weil es so ein bisschen übersichtlicher erscheint. Für diese Lösung ist die Summe aller $x_i$ gleich $\frac{220}{220}=1$. Außerdem liegen alle $x_i$ zwischen $0$ und $1$. Man kann auch zeigen: Dies ist die einzige Lösung, so dass sich die Einträge zu $1$ summieren. Das ist die Lösung des Page-rank-Problems in diesem Fall. Die wichtigste Seite ist Seite 4, mit Abstand am unwichtigsten (aus Sicht des Algorithmus) ist Seite 5.

Auch im allgemeinen Fall handelt es sich hier nach wie vor um ein lineares Gleichungssystem (das wir über den rationalen oder über den reellen Zahlen betrachten können). Dies ist noch nicht ganz das endgültige Gleichungssystem des Page-rank-Algorithmus, aber wir verschieben die Diskussion der weiteren Verbesserungen auf Ergänzung 5.61, wo wir die zur Verfügung stehende Sprache schon etwas erweitert haben.

Wir wollen es hier dabei belassen, zwei Fragen zu formulieren:

Gibt es eine Lösung für dieses Gleichungssystem, d.h. gibt es Zahlen $x_i$, die die Gleichungen erfüllen? Ist die Lösung (bis auf Skalieren) eindeutig bestimmt? (Denn wenn es mehrere Lösungen, also mehrere mögliche Rankings der Suchergebnisse gibt, ständen wir vor dem neuen Problem, wie wir uns zwischen diesen entscheiden könnten.)
Wenn es eine eindeutige Lösung gibt, wie kann man sie (angesichts der in der Praxis riesigen Zahl an Gleichungen und Variablen) berechnen?

Wir werden in den Ergänzungen 5.61, 7.67 und 10.24 auf diese Fragen zurückkommen und sehen, dass Frage (1) nach Durchführung der angekündigten Verbesserungen eine positive Antwort hat (Korollar 7.70), und es für Teil (2) Methoden gibt, die die spezielle Form dieses Gleichungssystems ausnutzen, siehe Ergänzung 10.24.

Frage 2.9

Wie kann man große Datenmengen analysieren, effizient abspeichern und komprimieren? Diese Frage ist recht allgemein gehalten. Wir werden an mehreren Stellen darauf zurückkommen; teilweise erst in der Linearen Algebra 2.

Konkrete Anwendungen sind

die (verlustfreie oder verlustbehaftete) Kompression von Bilddaten: Wie speichern Sie eine Bilddatei möglichst effizient ab, ohne Information zu verlieren – statt den Farbwert jedes einzelnen Bildpunktes abzuspeichern, möchte man ausnutzen, dass in typischen Bildern benachbarte Bildpunkte oft ähnliche Farbwerte haben. Was hat man für Möglichkeiten, den benötigten Speicherplatz noch deutlich stärker zu reduzieren, wenn man (kleine) Qualitätseinbußen in Kauf nimmt? Siehe Ergänzung 5.63.
Wie kann man die Qualität einer Datensammlung (beispielsweise wieder einer Bilddatei) verbessern, indem man Fehler (»noise«) sozusagen ausbügelt?

Wir werden nach und nach mit den Begrifflichkeiten, die zum jeweiligen Zeitpunkt zur Verfügung stehen, weitere Fragen entdecken/sehen, die wir dann erst später beantworten können. Zum Beispiel:

Es gibt keine Divisionsalgebra, die die reellen Zahlen als Teilkörper enthält und über $\mathbb R$ die Vektorraumdimension $3$ hat. Siehe Ergänzungen 4.9, 6.65 für die Erläuterung der Frage und 10.20 für die Lösung.

Mit dieser Frage hat sich R. Hamilton um 1840 beschäftigt, es handelte sich damals um ein aktuelles Forschungsproblem, das ihn 1843 zur »(Er-)findung« der Quaternionen führte. Diese spielen auch in der heutigen Mathematik (und Physik, und zum Beispiel auch in der Computergeometrie) eine Rolle. Es handelt sich dabei um einen Zahlbereich, der die reellen und die komplexen Zahlen enthält, aber auch noch zusätzliche Elemente. Es gelten dort die üblichen Rechenregeln bis auf das Kommutativgesetz der Multiplikation. Siehe Ergänzungen 4.11, 5.64, 9.44.

Every morning, on my coming down to breakfast, you used to ask me: “Well, Papa, can you multiply triplets?” Whereto I was always obliged to reply, with a sad shake of the head: “No, I can only add and subtract them.”

R. Hamilton in einem Brief an seinen Sohn aus dem Jahr 1865,
in dem er auch von seiner Erfindung der Quaternionen berichtet.

Als zwei weitere Beispiele für Gebiete, aus denen die Lineare Algebra nicht wegzudenken ist, seien hier genannt:

die Kodierungstheorie, die sich damit befasst, wie man Informationen so über einen Kommunikationskanal (wie eine Funkverbindung oder ein »Internetkabel«) übertragen kann, dass sich Übertragungsfehler durch den Empfänger feststellen und bestenfalls automatisch korrigieren lassen. Dies ist eine sehr anwendungsnahe Theorie mit großen Überschneidungen mit der Informatik und den Ingenieurwissenschaften. Siehe Kapitel 12,
die Graphentheorie, in der Konfigurationen von Punkten (»Knoten«), die durch Strecken (»Kanten«) miteinander verbunden sind, untersucht werden. Beispiele für gerichtete Graphen, in denen jede Kante mit einer Richtung versehen ist, sind die Darstellungen eines Netzwerks im Abschnitt über den Page-rank-Algorithmus (Frage 2.7). Es ist vielleicht ein bisschen überraschend, dass man Methoden der Linearen Algebra (wie zum Beispiel die Theorie der Eigenwerte, deren Anfänge wir zum Ende der Linearen Algebra 1 hin kennenlernen werden und die uns dann auch noch im kommenden Semester beschäftigen wird) auf das Studium von solchen Graphen anwenden kann, sie erweisen sich aber oft als sehr nützlich. Siehe Kapitel 13.
Die lineare Algebra ist auch eng mit der analytischen Geometrie verwoben. Siehe Kapitel 11 für einige Bemerkungen dazu. In der Folgevorlesung Lineare Algebra 2 werden wir dieses Thema noch weiter vertiefen können.
Der Begriff der Symmetrie spielt in vielen Bereichen der Mathematik eine Rolle und Symmetrien werden meist mithilfe des Begriffs der Gruppe beschrieben und untersucht, den wir in Kapitel 8 kennenlernen werden.

Weitere Beispiele finden Sie in den Büchern [ LM ] , [ Ba ] , in der Einleitung von [ Fi ] (und den dort gegebenen Literaturverweisen), [ Ma ] (Anwendungen von linearer Algebra auf mathematische Probleme), [ RS ] . Siehe auch Anhang D.

\(x_1\)	=				\(\frac{1}{3} x_3\)					\(+\)	\(\frac{1}{2} x_6\)
\(x_2\)	=	\(\frac{1}{2} x_1\)		\(+\)	\(\frac{1}{3} x_3\)			\(+\)	\(\frac{1}{3} x_5\)
\(x_3\)	=	\(\frac{1}{2} x_1\)				\(+\)	\(\frac{1}{2} x_4\)
\(x_4\)	=		\(x_2\)					\(+\)	\(\frac{1}{3} x_5\)	\(+\)	\(\frac{1}{2} x_6\)
\(x_5\)	=				\(\frac{1}{3} x_3\)
\(x_6\)	=						\(\frac{1}{2} x_4\)	\(+\)	\(\frac{1}{3} x_5\)