Beweise die folgende Ungleichung/Freundschaftsparadoxon

Question

Aufgabe:

Beweise die Ungleichung, das sogenannte Freundschaftsparadoxon. N die Anzahl Freunde, M die Anzahl bekanntschaften unter den Freunden

Text erkannt:

$\frac{1}{N} \sum \limits_{i} k_{i} \leq \frac{1}{2 M} \sum \limits_{i, j} a_{i j} k_{j}$

Tipp: Es gilt

Ausserdem wäre die Cauchy Schwarz Ungleichung nützlich
Problem/Ansatz:

Mir ist bewusst dass ich die linke Seite schonmal durch 2M/N ersetzen kann. Wie ich nun weiterkomme ist mir rätselhaft

Answer 1

Das ist tatsächlich nur eine umgestellte Form der Cauchy-Schwarz-Ungleichung.

Ich schreib das jetzt alles mit Vektoren und Matrizen, sodass das deutlich wird. Setze dazu

$e= \begin{pmatrix} 1 &1 & \ldots & 1\end{pmatrix}^T \in \mathbb R^N$

$k = (k_i) = Ae$, wobei $A= A^T$ die Adjazenzmatrix ist.

Dann haben wir:

$M =\frac 12 e^TAe = \frac 12 \sum_{i=1}^N k_i$ - die Anzahl der Bekanntschaften.

$N = e^Te$ - Anzahl der Freunde.

Zu zeigen ist:

$\frac 1N e^TAe \leq \frac 1{2M}e^T Ak \stackrel{A^T=A}{\Leftrightarrow }2Me^TAe \leq N (Ae)^T(Ae)$

Also zu zeigen ist (Ausdruck für M einsetzen):
$$\boxed{(e^TAe)^2\leq (e^Te)((Ae)^T(Ae))= N |Ae|^2}$$

Das ist aber nichts weiter als die Cauchy-Schwarz-Ungleichung für die Vektoren $e$ und $Ae$.

Damit sind wir fertig.