균형행렬

수학에서 균형 행렬은 0-1 행렬(모든 항목이 0이거나 1인 행렬)이며 모든 행 합계와 모든 열 합계가 2인 홀수 순서의 제곱 하위 행렬을 포함하지 않는다.

균형 행렬은 선형 프로그래밍에서 연구된다.균형 행렬의 중요성은 선형 프로그래밍 문제의 해법이 그 계수의 행렬이 균형을 이루고 있고 그 오른쪽이나 목표 벡터가 올원 벡터인 경우에 필수적이라는 사실에서 비롯된다.^[1][2]특히 이런 종류의 선형 프로그램에 대한 일체형 솔루션을 탐색할 경우 정수 선형 프로그램을 명시적으로 풀 필요가 없지만, 선형 프로그램 자체의 최적 꼭지점 솔루션을 찾기에 충분하다.

예를 들어, 다음 행렬은 균형 행렬이다.

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

금지된 하위 계수에 의한 특성화

0-1 행렬은 홀수 사이클의 발생 행렬(홀수 순서의 사이클 그래프)인 하위 행렬을 포함하지 않는 경우에만 정의와 동등하게 균형을 이룬다.^[2]

따라서 균형이 맞지 않는 3 X 3 0-1 행렬은 (행과 열의 순열까지) 순서 3의 주기 그래프의 다음과 같은 발생 행렬뿐이다.

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

다음 행렬은 순서 5의 사이클 그래프의 발생 행렬이다.

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

위의 특성화란 서브매트릭스로서 $C{\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$ ${\$ 또는$$ C ${\displaystyle {5\mathrm{}}_{}}$ ${\$또는 다른 홀수 사이클의 발생 행렬)을 포함하는 어떤 행렬도 균형을 이루지 못한다는 것을 의미한다.

다른 매트릭스 클래스에 연결

모든 균형잡힌 행렬은 완벽한 행렬이다.

균형잡힌 행렬의 개념보다 더 제한적인 것은 완전히 균형잡힌 행렬의 개념이다.0-1 행렬은 반복된 열이 없고 모든 행 합계가 2인 정사각형 하위 행렬을 포함하지 않으면 완전 균형이라고 불린다.동등하게, 행렬은 어떤 사이클의 발생 행렬인 하위 행렬을 포함하지 않는 경우에만(이상하거나 짝수 순서에 관계없이) 완전히 균형을 이룬다.이 특성화는 즉시 어떤 완전 균형잡힌 행렬이 균형을 이루고 있음을 암시한다.^[3]

게다가, 0-1 행렬은 완전히 단변형인 것 또한 균형이 잡힌다.다음 행렬은 홀수 주기의 발생 행렬인 하위 행렬을 포함하지 않으므로 균형 행렬이다.

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

이 행렬은 완전히 일변량(결정인자는 -2)이 아니기 때문에 0-1 완전히 일변량 행렬은 균형 행렬의 적절한 하위 집합이다.^[2]

예를 들어, 균형 행렬은 설정된 분할 문제의 특별한 경우 계수 행렬로 발생한다.^[4]

일부 균형 행렬을 식별하는 다른 방법은 매트릭스 A의 모든 행의 부분 카운트 SC를 통해 확인할 수 있다.

SC = {t [a_sj = 1, a_ij = 0 for s < i > t, a_tj = 1, j = 1, n}

0-1 매트릭스 A가 모든 행 s = 1, ..., m에 대해 SC has 1을 갖는 경우, A는 고유한 부속성을 가지며, 따라서^[4] 완전히 비형상적이므로 균형을 이루기도 한다.이 조건은 충분하지만 A가 균형을 잡으려면 필요하지 않다는 점에 유의한다.즉, 모든 행 s = 1, ..., m에 대해 SC가 1인 0-1 행렬은 균형 행렬 집합의 적절한 하위 집합이다.

보다 일반적인 개념으로, 모든 항목이 0, 1 또는 -1인 행렬은 행과 열당 두 개의 0이 아닌 항목이 있는 모든 하위 계층에서 항목 합계가 4의 배수인 경우 균형이라고 한다.^[5]

참조