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

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

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

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

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

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

Равнозначно определению, матрица 0-1 сбалансирована если и только если он не содержит подматрицы, которая является матрица инцидентности любой нечетный цикл (а график цикла нечетного порядка).^[2]

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

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

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

${ displaystyle 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 & 0 & 1 & 1 end {bmatrix}}}$

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

Связь с другими матричными классами

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

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

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

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

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

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

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

SC = |{т | [а_sj = 1, а_ij = 0 для s < я < т, а_tj = 1], j = 1, ..., п}|

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

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

Рекомендации