Über kombinatorische Eigenschaften von Matrizen. (Q577964)

Die Elemente einer quadratischen Matrix \(n\)-ten Grades \(\|a_{ij}\|\) seien ganze nichtnegative Zahlen. Verf. betrachtet Systeme von Zeilen und Kolonnen, welche die \(i\)-te Zeile bzw. die \(j\)-te Kolonne mit einer Multiplizität \(\lambda_i\) bzw. \(\mu_j\) enthalten, für welche \((\lambda_i+\mu_j)\geqq a_{ij}\) (\(i, j = 1\), 2,\dots, \(n\)) ist. Es wird der folgende Satz bewiesen: \[ \text{Min}\sum\limits_{k=1}^{n}(\lambda_k+\mu_k)= \text{Max}\sum\limits_{i=1}^{n}a_{i\nu_i}, \] wenn \[ \lambda_i+\mu_j\geqq a_{ij} \] gilt (wo \(\nu_1\), \(\nu_2\),\dots, \(\nu_n\) sämtliche Permutationen von 1, 2,\dots, \(n\) durchlaufen). (Verallgemeinerung eines Satzes von \textit{D. König}, s. das folgende Referat.) Es wird auch ein duales Gegenstück dieses Satzes bewiesen.