Преобразования бистохастической матрицы

[fractalon]

Бистохастической матрицей называется матрица размера $n \times n$ такая, что $a_{i j} \ge 0$, $\forall 1 \le i \le n: \sum \limits_{j=1}^{n} {a_{i j}} = 1$ и $\forall 1 \le j \le n: \sum \limits_{i=1}^{n} {a_{i j}} = 1$. Самым простым примером является матрица вида $a_{i i} = 1$ и $a_{i j} = 0$ ($i \not = j$).
Для любого набора индексов $i_1 \not = i_2, j_1 \not = j_2$ и $\varepsilon > 0$ после преобразований вида
$a_{i_1 j_1} = a_{i_1 j_1} - \varepsilon$
$a_{i_1 j_2} = a_{i_1 j_2} + \varepsilon$
$a_{i_2 j_1} = a_{i_2 j_1} + \varepsilon$
$a_{i_2 j_2} = a_{i_2 j_2} - \varepsilon$
матрица остаётся бистохастической если никакие элементы не вылезают за границы $(0;1)$. Здесь мы выбираем декартов прямоугольник и как бы сдвигаем величину $\varepsilon$ в одну сторону по этому прямоугольнику.

Вопрос: можно ли с помощью указанных выше преобразований получить из единичной любую бистохастическую матрицу?

[arseniiv]

Проблема только в том, чтобы показать, можно ли череду преобразований, промежуточные результаты которой выходят за рамки $a_{ij}\geqslant0$, преобразовать в череду, промежуточные результаты которой хорошие. Так-то можно любую матрицу преобразовать в матрицу с нулями везде кроме одной строки и столбца (элементами которых будут единицы и $2-n$ на пересечении), так что «некрасивое» преобразование из единичной матрицы в любую другую бистохастическую есть.

Элементарные преобразования коммутируют, также преобразование на $\varepsilon_1+\varepsilon_2$ можно разделить на отдельные преобразования на $\varepsilon_1$ и $\varepsilon_2$. От этого, наверно, и стоит плясать: когда преобразование делает отрицательные элементы, расщепить его на два, первое из которых доводит те элементы до нулей, а второе надо сделать позже. Всегда ли это возможно — простой идеи пока не увидел.

[odelschwank]

Найдем среди элементов первых строки и столбца (кроме $a_{11}$) минимальный отличный от нуля. Пусть это $a_{1k}$.

Тогда существует $j \ne 1$, такое что $a_{j1} \geqslant a_{1k}$. При этом $1 - a_{jk} = \sum\limits_{l \ne k}a_{lk} \geqslant a_{1k}$, поэтому можно применить ваше преобразование с индексами $1 \ne j, 1 \ne k$ и $\varepsilon = a_{1k}$, тем самым получив матрицу, в которой $a_{1k} = 0$.

Процесс можно продолжать, пока в 1-й строке и столбце не будут одни нули. После этого переходим ко 2-й строке и столбцу и т.д.