Дважды стохастическая матрица

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Дважды стохастическая матрица — квадратная матрица A=(a_{ij}) с неотрицательными вещественными элементами, в которой все ее строчные и столбцовые суммы равны 1, то есть

\sum_i a_{ij}=\sum_j a_{ij}=1.

Множество всех дважды стохастических матриц обозначается через \Omega_n.

Свойства[править | править вики-текст]

  • Теорема Биркгофа. Множество \Omega_n всех дважды стохастических матриц образует выпуклый многогранник, вершины которого — матрицы перестановки. Иначе говоря, если A \in \Omega_n, то A = \sum_{j=1}^{s} \theta_{j} P_{j}, где P_{1}, ..., P_{s} — матрицы перестановки, а \theta_{1}, ..., \theta_{s} — неотрицательные числа, \sum_{j=1}^{s} \theta_{j} = 1[1]
  • Любая дважды стохастическая матрица S порядка n является выпуклой линейной комбинацией не более чем n^{2}-2n+2 матриц перестановок[2].
  • Пусть x_{1} \geqslant x_{2} \geqslant ... \geqslant x_{n} и y_{1} \geqslant y_{2} \geqslant ... \geqslant y_{n}, причем x_{1} + ... + x_{k} \leqslant y_{1} + ... + y_{k} при всех k < n и x_{1} + ... + x_{n} = y_{1} + ... + y_{n}. Тогда существует такая дважды стохастическая матрица S, что Sy=x[2].

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

  • Минк Х. Перманенты. — М.: Мир, 1982. — 211 с.
  • Прасолов В. В. Задачи и теоремы линейной алгебры. — М.: Наука, 1996. — 304 с. — ISBN 5-02-014727-3