이진 행렬

논리 행렬(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 의 엔트리(성분)는 다음과 같이 정의된다.

 

행렬의 행과 열 번호를 지정하기 위해 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)}

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

 

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

관련된 예편집

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

속성편집

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

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

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

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

같이 보기편집

참고편집

  1. “보관된 사본”. 2017년 8월 12일에 원본 문서에서 보존된 문서. 2017년 8월 8일에 확인함. 
  2. Patrick E. O'Neil, Elizabeth J. O'Neil (1973). “A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure” (PDF). 《Information and Control》 22 (2): 132–138. doi:10.1016/s0019-9958(73)90228-3.  — The algorithm relies on addition being idempotent, cf. p.134 (bottom).