이진 행렬 문서 원본 보기

{{위키데이터 속성 추적}}
'''논리 행렬'''(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 의 엔트리(성분)는 다음과 같이 정의된다.
:<math>M_{i,j} =
 \begin{cases}
   1 & (x_i, y_j) \in R \\
   0 & (x_i, y_j) \not\in R
 \end{cases}
 </math>
행렬의 행과 열 번호를 지정하기 위해 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)}
이것에 상응하는 부울 행렬 표현은 다음과 같다.
:<math>\begin{pmatrix}
   1 & 1 & 1 & 1 \\
   0 & 1 & 0 & 1 \\
   0 & 0 & 1 & 0 \\
   0 & 0 & 0 & 1
 \end{pmatrix}
 </math>
이러한 행렬표현은 [[레드헤퍼 행렬]]과 관련있다.

==관련된 예==
* [[순열 행렬]] ( permutation matrix )은 (0, 1)행렬이며, 열과 행 각각은 정확히 하나의 0이 아닌 원소를 가진다.
:[[코스타스 배열]](Costas array) 은 순열 행렬의 특별한 경우이다.
*조합 및 유한 기하학 의 발생 행렬 은 점 (또는 정점)과 기하학의 선, 블록 설계 의 블록 또는 그래프 ([[이산 수학]])의 선 사이의 빈도를 나타내는 행렬을 가진다.
*분산 분석의 설계 행렬 은 일정한 행 합계를 갖는 (0,1) 행렬이다.
* [[그래프 이론]]의 [[인접행렬|인접 행렬]]은 행과 열이 정점을 나타내고 행렬이 그래프의 모서리를 나타내는 행렬이다. 단순하고 방향이 없는 그래프의 [[인접행렬]]은 대각선이 0 인 이진 [[대칭 행렬]]이다.
*단순하고 방향이 잡히지 않은 [[이분 그래프]]에서의 [[인접행렬]]<!-- 인 [[쌍접 행렬]](bi-adjacency matrix) -->은 (0,1)행렬이고, 어떤 (0,1)행렬은 이런 방식으로 발생한다.
* [[제곱 인수가 없는 정수]] m 과  [[매끄러운 수]] n 의 리스트에서 소수 인자는 m × π ( n ) (0,1)행렬로 표현 될 수있다. 여기서 π는 [[소수 계량 함수|소수 세기 함수]]이고 , <math>a_{ij}</math>는 1이면 j 번째 소수가 i 번째 숫자를 나눌 경우에만. 이 표현은 [[이차 체|2차 체]] 분해 알고리즘에 유용하다.
*단 두 색상의 픽셀 을 포함하는 비트 맵 이미지는 0이 한 색상의 픽셀을 나타내고 1이 다른 색상의 픽셀을 나타내는 (0,1) 매트릭스로 표현 될 수 있다.
*이진 행렬을 사용하여 Go<ref>{{웹 인용 |url=http://senseis.xmp.net/?BinMatrix |제목=보관된 사본 |확인날짜=2017-08-08 |보존url=https://web.archive.org/web/20170812021831/http://senseis.xmp.net/?BinMatrix |보존날짜=2017-08-12 |url-status=dead }}</ref> 게임에서 게임 규칙을 확인한다

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

부울 도메인이 [[반환 (수학)|반 환]](semiring)으로 간주되는 경우, 즉 [[행렬]] 연산의 덧셈은 [[논리합|논리 합]] 에대한 덧셈으로, 곱셈은  [[논리곱|논리 곱]]에 대한 곱셈으로 상응한다면, 두개의 주어진 [[이진관계의 구성]]을 나타내는 행렬 표현에서 이러한 관계의 행렬 표현의 [[행렬 곱셈|행렬 곱]]과 같다. 이 연산은 [[시간복잡도|예상 시간]] <math>O ( n^2 )</math>에서 계산될 수 있다.<ref>{{저널 인용| author=Patrick E. O'Neil, Elizabeth J. O'Neil| title=A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure| journal=Information and Control| year=1973| volume=22| issue=2 |pages=132–138| url=http://www.sciencedirect.com/science/article/pii/S0019995873902283/pdf?md5=37b2d0aafda0b0639e48370c73d5e82a&pid=1-s2.0-S0019995873902283-main.pdf| doi=10.1016/s0019-9958(73)90228-3}} &mdash; The algorithm relies on addition being [[idempotent]], cf. p.134 (bottom).</ref>

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

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

== 같이 보기 ==
* [[이항 관계]]
* [[레드헤퍼 행렬]]
* [[논리 연산]]
* [[단위 행렬]]

== 각주 ==
{{각주}}
* [https://web.archive.org/web/20170810171701/http://www.ndsl.kr/ndsl/search/detail/article/articleSearchResultDetail.do?cn=NPAP08647106 이진 행렬을 적용한 DSM 설계 원리에 대한 고찰]
{{전거 통제}}
[[분류:행렬]]
[[분류:논리학]]