이진 행렬

논리 행렬(Logical matrix), 이진 행렬(Binary matrix), 관계 행렬(Relation matrix), 부울 행렬(Boolean matrix) 또는 (0,1) 행렬은 부울 도메인(Boolean Domain) B = {0, 1}의 항목이있는 행렬이다. 이러한 행렬은 한 쌍의 유한 집합 사이의 이진 관계(이항관계)를 나타 내기 위해 사용될 수 있다.

이항 관계의 행렬표현

R 이 유한 인덱스 집합 X 와 Y 사이의 이항 관계 ( R ⊆ X × Y )라면, R 은 행과 열 인덱스가 각각 X 와 Y 의 원소를 색인하는 논리 행렬 M으로 나타낼 수있다. M 의 엔트리(성분)는 다음과 같이 정의된다.

$M_{i,j}={\begin{cases}1&(x_{i},y_{j})\in R\\0&(x_{i},y_{j})\not \in R\end{cases}}$

행렬의 행과 열 번호를 지정하기 위해 X 와 Y 세트는 양의 정수로 인덱싱(indexing)된다. i는 1에서 X 의 카디널리티 (크기)이고, j는 1에서 Y 의 카디널리티이다. 이러한 내용은 인덱스 집합과 관련된다.

예

집합 {1, 2, 3, 4} 에 대한 이진 관계 R 은 a 가 b를 균등하게 나누고 나머지가없는 경우에만 aRb가 유지되도록 정의된다. 예를 들어 2 R 4는 2가 4를 나누기 때문에 나머지는 남기지 않지만 3 R 4는 나뉘지 않는다. 왜냐하면 3이 4를 나눌 때 1의 나머지가 있기 때문이다. 다음 세트는 관계 R 이 갖는 쌍의 집합이다.

{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}

이것에 상응하는 부울 행렬 표현은 다음과 같다.

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

이러한 행렬표현은 레드헤퍼 행렬과 관련있다.

관련된 예

• 순열 행렬 ( permutation matrix )은 (0, 1)행렬이며, 열과 행 각각은 정확히 하나의 0이 아닌 원소를 가진다.

코스타스 배열(Costas array) 은 순열 행렬의 특별한 경우이다.

• 조합 및 유한 기하학 의 발생 행렬 은 점 (또는 정점)과 기하학의 선, 블록 설계 의 블록 또는 그래프 (이산 수학)의 선 사이의 빈도를 나타내는 행렬을 가진다.
• 분산 분석의 설계 행렬 은 일정한 행 합계를 갖는 (0,1) 행렬이다.
• 그래프 이론의 인접 행렬은 행과 열이 정점을 나타내고 행렬이 그래프의 모서리를 나타내는 행렬이다. 단순하고 방향이 없는 그래프의 인접행렬은 대각선이 0 인 이진 대칭 행렬이다.
• 단순하고 방향이 잡히지 않은 이분 그래프에서의 인접행렬은 (0,1)행렬이고, 어떤 (0,1)행렬은 이런 방식으로 발생한다.
• 제곱 인수가 없는 정수 m 과 매끄러운 수 n 의 리스트에서 소수 인자는 m × π ( n ) (0,1)행렬로 표현 될 수있다. 여기서 π는 소수 세기 함수이고 , $a_{ij}$는 1이면 j 번째 소수가 i 번째 숫자를 나눌 경우에만. 이 표현은 2차 체 분해 알고리즘에 유용하다.
• 단 두 색상의 픽셀 을 포함하는 비트 맵 이미지는 0이 한 색상의 픽셀을 나타내고 1이 다른 색상의 픽셀을 나타내는 (0,1) 매트릭스로 표현 될 수 있다.
• 이진 행렬을 사용하여 Go 게임에서 게임 규칙을 확인한다

속성

유한 집합에 대한 등식 관계 의 행렬 표현은 단위 행렬 즉, 대각선의 항목이 모두 1이고 다른 항목은 모두 0 인 항등행렬이다.

부울 도메인이 반 환(semiring)으로 간주되는 경우, 즉 행렬 연산의 덧셈은 논리 합 에대한 덧셈으로, 곱셈은 논리 곱에 대한 곱셈으로 상응한다면, 두개의 주어진 이진관계의 구성을 나타내는 행렬 표현에서 이러한 관계의 행렬 표현의 행렬 곱과 같다. 이 연산은 예상 시간 $O(n^{2})$에서 계산될 수 있다.

2 진 행렬에 대한 연산 은 모듈러 연산 $mod\;\;2$ 로 정의된다. 즉, 요소는 갈로아 체(Galois field) GF (2) = ℤ 2 의 요소로 처리된다. 이들은 다양한 표현으로 나타나며 더 많은 제한된 특수 형식을 가지고 있다. 예를 들어 XOR-충족 가능성 문제에 적용된다.

구별되는 m -by- n 이진 행렬의 수는 $2^{mn}$ 과 같으며, 따라서 유한하다.

같이 보기

• 이항 관계
• 레드헤퍼 행렬
• 논리 연산
• 단위 행렬

각주

• 이진 행렬을 적용한 DSM 설계 원리에 대한 고찰