Сбалансированная матрица

В математике сбалансированная матрица 0–1 — это матрица (матрица, в которой каждый элемент равен нулю или единице), которая не содержит квадратной подматрицы нечетного порядка, у которой все суммы строк и суммы всех столбцов равны 2.

Сбалансированные матрицы изучаются в рамках линейного программирования . Важность сбалансированных матриц обусловлена ​​тем фактом, что решение задачи линейного программирования является целочисленным, если ее матрица коэффициентов сбалансирована, а ее правая часть или ее целевой вектор представляет собой вектор, равный единице. В частности, если искать интегральное решение линейной программы такого типа, нет необходимости явно решать целочисленную линейную программу , а достаточно найти оптимальное вершинное решение самой линейной программы .

Например, следующая матрица является сбалансированной матрицей:

${\begin{bmatrix}1&1&1&1\\1&1&0&0\\1&0&1&0\\1&0&0&1\\\end{bmatrix}}$

Характеризация запрещенными подматрицами

Эквивалентно определению, матрица 0-1 сбалансирована тогда и только тогда, когда она не содержит подматрицу, которая является матрицей инцидентности любого нечетного цикла ( граф цикла нечетного порядка).

Следовательно, единственной несбалансированной матрицей три на три 0-1 является (с точностью до перестановки строк и столбцов) следующая матрица инцидентности графа цикла третьего порядка:

$C_{3}={\begin{bmatrix}1&0&1\\1&1&0\\0&1&1\\\end{bmatrix}}$

Следующая матрица представляет собой матрицу инцидентности графа циклов пятого порядка:

$C_{5}={\begin{bmatrix}1&0&0&0&1\\1&1&0&0&0\\0&1&1&0&0\\0&0&1&1&0\\0&0&0&1&1\\\end{bmatrix}}$

Из приведенной выше характеристики следует, что любая матрица, содержащая $C_{3}$ или $C_{5}$ (или матрица инцидентности любого другого нечетного цикла) как подматрица не сбалансирована.

Подключение к другим классам матриц

Каждая сбалансированная матрица является идеальной матрицей .

Более ограничивающим, чем понятие сбалансированных матриц, является понятие полностью сбалансированных матриц . Матрица 0–1 называется полностью сбалансированной, если она не содержит квадратной подматрицы, не имеющей повторяющихся столбцов, а все суммы строк и суммы всех столбцов равны 2. Эквивалентно, матрица полностью сбалансирована тогда и только тогда, когда она не содержит подматрицы. это матрица инцидентности любого цикла (независимо от того, нечетного или четного порядка). Из этой характеристики сразу следует, что любая полностью сбалансированная матрица является сбалансированной.

матрица 0-1 Более того, любая полностью унимодулярная также сбалансирована. Следующая матрица является сбалансированной, поскольку она не содержит подматриц, являющихся матрицей инцидентности нечетного цикла:

${\begin{bmatrix}1&1&1&1\\1&1&0&0\\1&0&1&0\\1&0&0&1\\\end{bmatrix}}$

Поскольку эта матрица не является полностью унимодулярной (ее определитель равен -2), полностью унимодулярные матрицы 0–1 являются собственным подмножеством сбалансированных матриц.

Например, сбалансированные матрицы возникают как матрица коэффициентов в особых случаях задачи разделения множества .

Альтернативный метод идентификации некоторых сбалансированных матриц заключается в подсчете подпоследовательностей, где счетчик подпоследовательностей SC любой строки s матрицы A равен

СК = |{ т | [ a _{sj знак} равно 1, a _ij знак равно 0 для s < i < t , a _{tj знак} равно 1], j знак равно 1, ..., n }|

Если матрица A 0-1 имеет SC( s ) ≤ 1 для всех строк s = 1, ..., m , то A имеет уникальную подпоследовательность и полностью унимодулярна. и поэтому также сбалансирован. Обратите внимание, что это условие является достаточным, но не необходимым для того, чтобы А было сбалансированным. Другими словами, матрицы 0–1 с SC( s ) ≤ 1 для всех строк s = 1,..., m являются собственным подмножеством множества сбалансированных матриц.

В более общем смысле матрица, в которой каждый элемент равен 0, 1 или -1, называется сбалансированной, если в каждой подматрице с двумя ненулевыми элементами в строке и столбце сумма элементов кратна 4.