[行列解析8.7]注記

注と参考文献

定理 8.7.2 は G. Birkhoff により “Tres observaciones sobre el álgebra lineal”, Univ. Nac. Tucumán Rev. Ser. A 5 (1946) 147–150 に現れる。

1916年に D. Kőnig は、非負有理数成分をもつ行列に対して (8.7.2) と同値な定理を発表した（Kőnig (1936) p.239 または Kőnig (1990) p.381 参照）。したがって、(8.7.2) はしばしば「Birkhoff–Kőnigの定理」と呼ばれる。

(8.7.2) の証明の中で非構成的な部分は、積 \( a_{1\sigma(1)} \cdots a_{n\sigma(n)} > 0 \) を満たす特定の置換 \( \sigma \) を同定する点のみである。

このような置換を構成的に求めるアルゴリズムは、Bapat と Raghavan (1997) の pp.64–65 に記されている。
この書籍には、二重確率行列に関する包括的な議論（第2章参照）と、多数の参考文献が収録されている。