Diskrete Mathematik/Gemischte Satzabfrage/19/Aufgabe/Lösung

Es sei $M$ eine endliche Menge mit $m$ Elementen und $N$ eine endliche Menge mit $n$ Elementen. Es sei $m > n$ . Dann gibt es keine injektive Abbildung
$M ⟶ N .$
Es sei $M$ eine komplexe $d \times d$ -Matrix mit dem charakteristischen Polynom
$χ_{M} (T) = {(T - λ_{1})}^{d_{1}} \dots {(T - λ_{k})}^{d_{k}} .$

Dann gibt es für jeden Vektor $v \in ℂ^{d}$ und jedes $j = 1, \dots, d$ (von $j$ abhängige) Polynome $Q_{1}, \dots, Q_{k} \in ℂ [T]$ mit $grad (Q_{i}) \leq d_{i} - 1$ derart, dass

${(M^{n} v)}_{j} = \sum_{i = 1}^{k} λ_{i}^{n - d_{i} + 1} Q_{i} (n)$

für alle $n \geq d$ gilt.
Bei $λ_{i} \neq 0$ für alle $i$ ist

${(M^{n} v)}_{j} = \sum_{i = 1}^{k} λ_{i}^{n} P_{i} (n)$
mit Polynomen $P_{i}$ , die die gleiche Gradbedingung erfüllen.
Zu einem Graphen $G = (V, E)$ ist die Waldmenge $𝒲 (G)$ (mit der vollen Knotenmenge) ein Matroid auf $E$ . Der Rang dieses Matroids ist die Anzahl der Kanten in einem aufspannenden Wald.