Математика · объяснение и практика

Сбалансированная матрица: как разложить назначения на перестановки

Доказываем разложение целочисленной матрицы с одинаковыми суммами строк и столбцов, затем получаем смесь перестановок для дважды стохастической матрицы.

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

Главная мысль

Неотрицательная целочисленная квадратная матрица с общей суммой l в каждой строке и каждом столбце является суммой l матриц перестановок. Если неотрицательная матрица имеет суммы всех строк и столбцов один, она является конечной выпуклой смесью матриц перестановок. Условия по обоим направлениям существенны.

Каждый слой использует строку и столбец ровно по разу

Матрица перестановки имеет ровно одну единицу в каждой строке и каждом столбце, остальные клетки нулевые. Она описывает одно взаимно однозначное назначение. Сумма l таких матриц описывает l слоёв назначений, где повторение одной пары в разных слоях разрешено. Это не требование, чтобы исходная клетка была только нулём или единицей.

Для целочисленной матрицы число l тоже целое и неотрицательное. При l=0 все клетки нулевые, и достаточно пустой суммы. Если l>0, нужно найти полное назначение только по положительным клеткам, чтобы вычитание единиц не создало отрицательные значения.

Наличие положительной клетки в каждой строке само по себе такого назначения не гарантирует. Однако равные суммы столбцов обеспечивают дополнительные групповые ограничения. Именно они позволяют применить критерий Холла к множествам положительных позиций строк.

Почему положительный носитель содержит перестановку

Возьмём k строк. Суммарный вес их клеток равен kl. Один столбец содержит всего l, значит, весь этот вес не может разместиться меньше чем в k столбцах. Объединение положительных позиций любых k строк имеет размер хотя бы k. По теореме Холла можно выбрать по одной положительной клетке в каждой строке без повторения столбца.

Выбранные клетки образуют матрицу перестановки P. Из целочисленной матрицы вычитаем P: выбранные положительные целые уменьшаются не ниже нуля, суммы всех строк и столбцов становятся l−1. Повторяем рассуждение до нуля. Получено ровно l слоёв, каждый из которых является допустимым назначением.

Доказательство использует общую сумму, а не одинаковость самих строк. Выделенные перестановки могут различаться. Восстановленная сумма должна совпасть с каждой клеткой исходной матрицы, а не только с её общим количеством единиц.

Пример

Разложите целочисленную матрицу со строками (1;1;0), (0;1;1), (1;0;1) на слои.

Каждая строка и каждый столбец имеют сумму два. Первый слой — единичная матрица: пары 1→1,2→2,3→3. Остаток имеет единицы в позициях 1→2,2→3,3→1 и является второй перестановкой. Клетки восстанавливаются точно. После деления исходной матрицы на два получаем смесь этих перестановок с весами 1/2 и 1/2.

Для действительных весов вычитается общий минимум

Теперь суммы строк и столбцов равны единице, а клетки могут быть дробными. Тот же аргумент с k строками даёт полную перестановку положительных клеток. Пусть α — наименьшая из выбранных клеток. Вычтем αP; все клетки останутся неотрицательными, суммы станут 1−α, а хотя бы одна положительная клетка обратится в ноль.

Если α=1, исходная матрица уже равна P. Иначе делим остаток на 1−α, получая снова дважды стохастическую матрицу. Новых положительных позиций не возникает, поэтому число положительных клеток строго уменьшается на каждом продолжающемся шаге. Процесс конечен. Раскрывая последовательные выражения, получаем неотрицательные веса перестановок с суммой один.

Это существование выпуклой смеси, а не утверждение её единственности. Матрица задаёт усреднённые доли назначений, но сама не сообщает, какой конкретный слой или случайный выбор был реализован. Отдельная нормировка каждой строки без проверки столбцов не обеспечивает такого представления.

От чтения к действию

А теперь — вы

Дважды стохастическая матрица имеет строки (0,2;0,5;0,3), (0,5;0,5;0), (0,3;0;0,7). Выбрана диагональная перестановка. Какой наибольший α можно вычесть сразу?

Частые вопросы

Каждая строка с суммой один уже гарантирует смесь перестановок?

Нет. Например, две одинаковые строки (3/4;1/4) имеют суммы столбцов 3/2 и 1/2; смесь перестановок обязана иметь обе суммы один.

Зачем брать минимум именно выбранных клеток?

Общий вычитаемый вес не может превышать ни одной клетки перестановки. Минимум сохраняет неотрицательность и обнуляет хотя бы одну выбранную позицию.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться