Permutation Matrix

Permutation Matrix의 정의

Permutation matrix란, Identity matrix로부터 일련의 row exchange operation들을 통해 얻어질 수 있는 행렬을 의미한다.

Permutation Matrix의 개수

n by n 행렬은 n!개의 permutation matrix를 가진다. 각 행의 원소 중 1의 갯수는 1개이고 그에 해당해는 열의 인덱스가 행마다 다름을 고려해보면 n!이 나온다는 것을 쉽게 알 수 있다.

Permutation Matrix의 성질

 

1. Row Exchange가 한 번만 일어난 Permutation matrix에 대해서 $P^T=P$이다. 즉 i번째 행과 j번째 행을 바꾸는 것은, i번 째 열과 j번째 열을 바꾸는 것과 동일하다.

또한 $P^{-1}=P$ 이고, $P^2$ = $I$ 이다.

 

2. 모든 Permutation Matrix에 대해 $P^TP=I$ 이다. (Orthogonal Matrix)

$(P^TP){ij} = \Sigma_k P{ik}P^T_{ki}=\Sigma_k P_{ik}P_{jk}$ 를 생각해보면, $i=j$ 일 때만 1이되고 나머지의 경우는 0이 된다.

 

3. linear combination of permutation matrix

 Permutation Matrix들의 linear combination으로 얻어지는 행렬의 Column Sum과 Row Sum은 일정하다. 예를 들어 아래는 2 by 2 행렬의 예시이다.

Column 기준으로 생각해볼 때, Coefficient가 각 열에 모두 곱해진다.