Zuordnungsmatrix

Eine Zuordnungsmatrix ist eine Matrix, die eine Zuordnung zwischen zwei endlichen Mengen A und B oder zwischen Basen von Vektorräumen repräsentiert. In der einfachsten Form handelt es sich um eine binäre Matrix M mit den Abmessungen |A|×|B|, wobei M_{ij} = 1 gilt, wenn dem Element i aus A das Element j aus B zugeordnet ist, und M_{ij} = 0 sonst.

Ist die Zuordnung eine Funktion, besitzt jede Zeile höchstens eine und gegebenenfalls genau eine 1; bei einer totalen Zuordnung ist die Zeilensumme gleich 1. Die Spaltensummen geben an, wie viele Elemente aus A dem jeweiligen Element in B zugeordnet sind. Bei einer bijektiven Zuordnung entspricht M einer Permutationsmatrix, d. h. genau eine 1 pro Zeile und pro Spalte.

Bezug zu Graphen und linearen Abbildungen: Die Zuordnungsmatrix ist die Adjazenzmatrix eines bipartiten Graphen mit Knotenmengen A und B. In der linearen Algebra kann eine Abbildung zwischen Vektorräumen durch eine Matrix dargestellt werden, wobei Spalten die Bilder der Basisvektoren darstellen. Allgemein können Zuordnungsmatrizen auch gewichtete Einträge enthalten, wodurch M zu einer linearen Abbildung mit Real- oder Komplexwerten wird statt einer reinen 0/1-Variante.

Operationen und Anwendungen: Die Zusammensetzung von Zuordnungen entspricht Matrixmultiplikation (eine Zuordnung A→B gefolgt von B→C ergibt eine Zuordnung A→C). Anwendungen finden sich im Operations Research (Zuweisungsproblem), in der Informatik zur Repräsentation von Zuordnungen und in der Graphentheorie zur Beschreibung bipartiter Strukturen.

---