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.