이진 행렬

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

논리 행렬(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. http://senseis.xmp.net/?BinMatrix
  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).