치환행렬

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 치환 행렬과 순열의 대응
4. 성질
- 4.1. 행렬 곱셈과의 관계
5. 선형대수적 성질
6. 군론적 성질
7. 예
- 7.1. 행의 재배열
- 7.2. 열의 재배열
8. 응용
참조

1. 개요

치환행렬은 m개의 문자에 대한 치환을 표현하는 정사각 행렬이다. 순열과 치환 행렬 사이에는 두 가지 일대일 대응이 존재하며, 행 기반 대응은 순열 π를 행렬 R_π로, 열 기반 대응은 순열 π를 행렬 C_π로 대응시킨다. 치환행렬은 직교 행렬이며, 역행렬은 전치행렬과 같다. 치환행렬의 곱셈은 순열의 합성과 관련되며, 행렬에 치환행렬을 곱하면 행 또는 열이 치환된다. 치환행렬은 군론적 성질을 가지며, 다양한 분야에 응용된다.

더 읽어볼만한 페이지

성긴 행렬 - 영행렬
영행렬은 환 $R$ 위의 모든 성분이 0인 $m \times n$ 행렬로서, 행렬 공간의 덧셈 항등원 역할을 하고, 임의의 행렬에 곱하면 영행렬이 되며, 선형 변환에서는 모든 벡터를 영벡터로 보내는 변환을 나타낸다.
성긴 행렬 - 대각 행렬
대각 행렬은 주대각 성분 외 모든 성분이 0인 정사각 행렬로, 대칭 행렬이자 고윳값은 대각 성분이며 대각화 가능하고, 스칼라 행렬은 주대각 성분이 같은 대각 행렬이다.
순열 - 레비치비타 기호
레비치비타 기호는 n차원 공간에서 정의되는 완전 반대칭 텐서로, 순열의 부호에 따라 +1, -1, 0의 값을 가지며 벡터곱, 행렬식 계산 등 다양한 분야에서 활용된다.
순열 - 완전순열
완전순열은 집합의 순열 중 모든 원소가 원래 위치에 있지 않은 순열, 즉 고정점이 없는 순열을 의미하며, 크기가 n인 집합의 완전순열의 수는 준계승 !n으로 나타내고, 점화식 또는 포함-배제 원리로 계산하며, 몽모르 수라고도 불린다.

치환행렬
정의
정의	각 행과 열에 정확히 하나의 1을 가지고 나머지는 0인 정사각 행렬이다.
특징
성질	크기 의 치환 행렬은 개의 원소를 갖는 집합의 치환을 나타낸다. 임의의 행렬 에 치환 행렬 를 곱하면 () 의 행들이 치환된다. 마찬가지로, 행렬 에 치환 행렬 를 오른쪽에 곱하면 () 의 열들이 치환된다.
응용
활용	가중 그래프 매칭 문제 등에 활용될 수 있다.
추가 정보
다른 이름	순열 행렬 치환 행렬
관련 용어
관련 용어	이중 확률 행렬

2. 정의

m개의 원소를 가지는 집합 {1, ..., m}에 대한 순열 π는 이 집합에서 자기 자신으로 가는 전단사 함수로 정의할 수 있다.

: $\pi\colon \lbrace 1, \ldots, m \rbrace \to \lbrace 1, \ldots, m \rbrace$

이 순열은 다음과 같은 2행 표기법으로 나타낼 수 있다.

: $\begin{bmatrix} 1 & 2 & \cdots & m \\ \pi(1) & \pi(2) & \cdots & \pi(m) \end{bmatrix}$

주어진 순열 π에 대응하는 치환행렬 P_π는 m × m 정사각행렬이다. j번째 원소만 1이고 나머지는 모두 0인 표준 기저 벡터를 '''e'''_j (행벡터로 간주)라고 할 때, P_π는 다음과 같이 정의된다.^[7]

: $P_\pi = \begin{bmatrix} \mathbf e_{\pi(1)} \\ \mathbf e_{\pi(2)} \\ \vdots \\ \mathbf e_{\pi(m)} \end{bmatrix}$

이는 행렬 P_π의 각 행 i가 단위 행렬의 π(i)번째 행과 같다는 의미이다. 즉, P_π = (p_ij)라고 할 때, j = π(i) 이면 p_ij = 1이고, 그렇지 않으면 p_ij = 0이다. 치환행렬 P_π는 다른 행렬 A에 곱해져(P_πA), A의 행 순서를 바꾸는 데 사용된다.

3. 치환 행렬과 순열의 대응

순열과 치환 행렬 사이에는 두 가지 자연스러운 일대일 대응이 있다. 하나는 행렬의 행을 기준으로, 다른 하나는 열을 기준으로 정의된다. 예를 들어, 다음과 같은 순열 π가 주어졌다고 하자:

: $\pi\colon\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}$

이 순열에 대응하는 두 종류의 치환 행렬 $R_\pi$ 와 $C_\pi$ , 그리고 역순열 $\pi^{-1}$ 의 관계는 다음과 같다:

: $\begin{matrix}\pi\colon\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}& \longleftrightarrow &R_\pi\colon\begin{pmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{pmatrix}\\[5pt]\Big\updownarrow && \Big\updownarrow\\[5pt]C_\pi\colon\begin{pmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&1&0\end{pmatrix}& \longleftrightarrow &\pi^{-1}\colon\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}\end{matrix}$
행 기반 대응은 순열 π를 행렬 $R_\pi$ (위 그림의 오른쪽 위)에 대응시킨다. $R_\pi$ 의 $i$ 번째 행은 $\pi(i)$ 번째 열에만 1을 가지고 나머지 성분은 0이다. 위 예시에서 $\pi(1)=3$ 이므로, $R_\pi$ 의 첫 번째 행은 세 번째 열에 1이 있다. 일반적으로 $R_\pi=(r_{ij})$ 는 $j=\pi(i)$ 일 때 $r_{ij}=1$ 이고, 그 외에는 $r_{ij}=0$ 이다.
열 기반 대응은 순열 π를 행렬 $C_\pi$ (위 그림의 왼쪽 아래)에 대응시킨다. $C_\pi$ 의 $j$ 번째 열은 $\pi(j)$ 번째 행에만 1을 가지고 나머지 성분은 0이다. 위 예시에서 $\pi(1)=3$ 이므로, $C_\pi$ 의 첫 번째 열은 세 번째 행에 1이 있다. 일반적으로 $C_\pi=(c_{ij})$ 는 $i=\pi(j)$ 일 때 $c_{ij}=1$ 이고, 그 외에는 $c_{ij}=0$ 이다.

두 대응 방식은 단지 행과 열의 역할을 바꾼 것이므로, 행렬 $C_\pi$ 는 $R_\pi$ 의 전치 행렬이다. 즉, $C_\pi = R_\pi^\mathsf{T}$ 이다. 치환 행렬은 직교 행렬이므로 역행렬은 전치 행렬과 같고, 따라서 $C_\pi=R_\pi^\mathsf{T}=R_\pi^{-1}$ 가 성립한다. 위 그림에서 다른 관계를 살펴보면 $R_{\pi^{-1}}=C_\pi=R_\pi^{-1}$ 이고 $C_{\pi^{-1}}=R_\pi$ 임을 알 수 있다.^[3]

치환 행렬 $R_\pi$ 또는 $C_\pi$ 를 다른 행렬 $M$ 의 앞이나 뒤에 곱하면, $M$ 의 행이나 열이 순열 $\pi$ 또는 $\pi^{-1}$ 에 따라 재배열된다.

벡터 $(v_1,\ldots,v_n)$ 의 원소들을 순열 $\pi$ 에 따라 재배열한다는 것은, $i$ 번째 원소 $v_i$ 를 결과 벡터의 $\pi(i)$ 번째 위치로 옮기는 것을 의미한다. 이렇게 하면 결과 벡터는 $\big(v_{\pi^{-1}(1)},v_{\pi^{-1}(2)},\ldots,v_{\pi^{-1}(n)}\big)$ 가 된다. 즉, 원소를 $\pi$ 에 따라 재배열하려면 인덱스를 $\pi^{-1}$ 에 따라 재배열해야 한다.^[1]

이제 $n \times n$ 행렬 $M=(m_{ij})$ 앞에 $C_\pi$ 를 곱하는 경우( $C_\pi M$ )를 생각해보자. 행렬 곱셈의 정의에 따라, 결과 행렬의 $(i,j)$ 성분은 $\sum_{k=1}^n c_{ik}m_{kj}$ 이다. $c_{ik}$ 는 $i=\pi(k)$ 일 때만 1이고 나머지는 0이므로, 합에서 유일하게 남는 항은 $k=\pi^{-1}(i)$ 일 때의 $m_{\pi^{-1}(i),j}$ 이다. 이는 행 인덱스가 $\pi^{-1}$ 에 따라 치환되었음을 의미하며, 결과적으로 행렬 $M$ 의 행들이 순열 $\pi$ 에 따라 재배열된 것과 같다.^[1]

비슷하게, 행렬 $M$ 뒤에 $R_\pi$ 를 곱하면( $M R_\pi$ ), $M$ 의 열들이 순열 $\pi$ 에 따라 재배열된다.

반대로, $M$ 앞에 $R_\pi$ 를 곱하거나( $R_\pi M$ ) 뒤에 $C_\pi$ 를 곱하면( $M C_\pi$ ), 각각 행 또는 열이 $\pi^{-1}$ 에 따라 재배열된다.

4. 성질

치환 행렬은 몇 가지 중요한 대수적 성질을 가진다.

모든 순열 행렬 $P_\pi$ 는 직교 행렬이다. 이는 치환 행렬과 그 전치 행렬 $P_\pi^\mathsf{T}$ 의 곱이 항등 행렬 $I$ 가 됨을 의미한다.^[1] 구체적으로, 곱 $P_\pi P_\pi^\mathsf{T}$ 의 $(i, j)$ 번째 성분은 $\sum_{k=1}^n (P_\pi)_{ik} (P_\pi^\mathsf{T})_{kj} = \sum_{k=1}^n (P_\pi)_{ik} (P_\pi)_{jk}$ 이다. 만약 $i \neq j$ 이면, $i$ 행과 $j$ 행은 서로 다른 위치에 1을 가지므로 모든 $k$ 에 대해 $(P_\pi)_{ik}$ 와 $(P_\pi)_{jk}$ 중 적어도 하나는 0이 되어 합은 0이다. 만약 $i = j$ 이면, $i$ 행에는 정확히 하나의 $k$ 에 대해 $(P_\pi)_{ik}=1$ 이고 나머지는 0이므로, 합은 $1^2 = 1$ 이 된다. 따라서 $P_\pi P_\pi^\mathsf{T} = I$ 이며, 마찬가지로 $P_\pi^\mathsf{T} P_\pi = I$ 도 성립한다.

직교 행렬의 정의에 따라, 치환 행렬의 역행렬은 그 전치 행렬과 같다.

: $P_\pi^{-1} = P_\pi^\mathsf{T}$

또한, 순열 $\pi$ 의 역순열 $\pi^{-1}$ 에 대응하는 치환 행렬은 원래 치환 행렬의 역행렬과 같다.

: $P_\pi^{-1} = P_{\pi^{-1}}$

결론적으로 다음 세 표현은 모두 동일하다.

: $P_\pi^{-1} = P_{\pi^{-1}} = P_\pi^\mathsf{T}$

두 순열 $\pi$ 와 $\sigma$ 에 대응하는 치환 행렬 $P_\pi$ 와 $P_\sigma$ 의 곱셈은 순열의 합성과 직접적으로 연관된다. 열 벡터에 작용하는 표준적인 정의를 따를 때 (즉, $P_\pi$ 가 벡터 $\mathbf{v}$ 에 작용하여 $i$ 번째 성분을 $\pi(i)$ 번째 위치로 보내는 것이 아니라, $\pi^{-1}(i)$ 번째 성분을 $i$ 번째 위치로 가져오는 방식으로 정의될 때, 즉 $(P_\pi)_{ij} = \delta_{i, \pi(j)}$ ), 두 치환 행렬의 곱은 다음과 같이 두 순열의 합성에 해당하는 치환 행렬이 된다. (순열 합성은 오른쪽부터 적용: $(\sigma \circ \pi)(k) = \sigma(\pi(k))$ )

: $P_{\sigma} P_{\pi} = P_{\sigma \circ \pi}$

이 성질은 치환 행렬이 대칭군 $S_n$ 의 행렬 표현을 제공함을 보여준다. 행 벡터에 작용하도록 정의하거나 다른 합성 순서를 사용하면 곱셈 규칙이 달라질 수 있다.

치환 행렬을 다른 행렬이나 벡터에 곱하면 행이나 열, 또는 벡터 성분의 순서를 바꾸는 효과가 있다. 이에 대한 자세한 내용은 #행렬 곱셈과의 관계 섹션에서 다룬다.

4. 1. 행렬 곱셈과의 관계

치환행렬

P

는 임의의 행렬

A

에 대해 왼쪽 곱셈

P \cdot A

를 통해

A

의 행(row) 순서를 바꾸거나, 오른쪽 곱셈

A \cdot P

를 통해

A

의 열(column) 순서를 재배열하는 역할을 한다.

예를 들어,

3 \times 3

단위 행렬

I

는 다음과 같다.

I = \begin{bmatrix}1 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 1 \end{bmatrix}

이 단위 행렬의 1행과 3행을 서로 바꾸면 다음과 같은 치환행렬

P

를 얻을 수 있다.

P = \begin{bmatrix}0 & 0 & 1 \\0 & 1 & 0 \\1 & 0 & 0\end{bmatrix}

임의의

3 \times 3

행렬

A

를 다음과 같이 정의하자.

A = \begin{bmatrix}a & b & c \\d & e & f \\g & h & i\end{bmatrix}

이때,

P

를

A

의 왼쪽에 곱하면

A

의 1행과 3행이 서로 바뀐다.

P A = \begin{bmatrix}0 & 0 & 1 \\0 & 1 & 0 \\1 & 0 & 0\end{bmatrix}\begin{bmatrix}a & b & c \\d & e & f \\g & h & i\end{bmatrix} =\begin{bmatrix}g & h & i \\d & e & f \\a & b & c\end{bmatrix}

반면,

P

를

A

의 오른쪽에 곱하면

A

의 1열과 3열이 서로 바뀐다.

A P = \begin{bmatrix}a & b & c \\d & e & f \\g & h & i\end{bmatrix}\begin{bmatrix}0 & 0 & 1 \\0 & 1 & 0 \\1 & 0 & 0\end{bmatrix} =\begin{bmatrix}c & b & a \\f & e & d \\i & h & g\end{bmatrix}

일반적으로,

n

개의 원소에 대한 순열

\pi

에 대응하는 치환 행렬

P_\pi

는

i

행

j

열 성분이

(P_\pi)_{ij} = \delta_{i, \pi(j)}

(크로네커 델타)로 정의된다. 즉, 각 열

j

에는

\pi(j)

행에만 1이 있고 나머지는 0이다. 다르게 표현하면,

P_\pi

의

i

번째 행은 표준 기저 벡터

\mathbf{e}_{\pi^{-1}(i)}^\top

와 같다.

벡터

(v_1, \ldots, v_n)

의 성분을 순열

\pi

에 따라 치환한다는 것은, 입력 벡터의

i

번째 성분

v_i

를 출력 벡터의

\pi(i)

번째 위치로 옮기는 것을 의미한다. 결과적으로 출력 벡터는

(v_{\pi^{-1}(1)}, v_{\pi^{-1}(2)}, \ldots, v_{\pi^{-1}(n)})

이 된다. 즉, 성분을

\pi

에 따라 치환하기 위해서는 인덱스를

\pi^{-1}

에 따라 치환해야 한다.^[1] (성분을

\pi

에 따라 치환하는 것을 '알리바이 변환', 인덱스를

\pi

에 따라 치환하는 것을 '에일리어스 변환'이라고도 한다.^[4])

치환 행렬과 행렬 곱셈의 관계는 다음과 같다.

행렬 $M=(m_{i,j})$ 에 치환 행렬 $P_\pi$ 를 '''왼쪽'''에 곱하면 ( $P_\pi M$ ), $M$ 의 '''행'''이 $\pi$ 에 따라 치환된다. 곱 $P_\pi M$ 의 $(i,j)$ 번째 성분은 다음과 같이 계산된다.

\sum_{k=1}^n (P_\pi)_{ik} m_{k,j} = \sum_{k=1}^n \delta_{i, \pi(k)} m_{k,j} = m_{\pi^{-1}(i), j}

이는 결과 행렬의

i

번째 행이 원래 행렬

M

의

\pi^{-1}(i)

번째 행임을 의미한다. 즉, 행 인덱스가

\pi^{-1}

에 따라 치환되었으므로, 행 자체는

\pi

에 따라 치환된 것이다.^[1]

행렬 $M$ 에 치환 행렬 $P_\pi$ 를 '''오른쪽'''에 곱하면 ( $M P_\pi$ ), $M$ 의 '''열'''이 $\pi^{-1}$ 에 따라 치환된다. 곱 $M P_\pi$ 의 $(i,j)$ 번째 성분은 다음과 같이 계산된다.

\sum_{k=1}^n m_{ik} (P_\pi)_{kj} = \sum_{k=1}^n m_{ik} \delta_{k, \pi(j)} = m_{i, \pi(j)}

이는 결과 행렬의

j

번째 열이 원래 행렬

M

의

\pi(j)

번째 열임을 의미한다. 즉, 열 인덱스가

\pi

에 따라 치환되었으므로, 열 자체는

\pi^{-1}

에 따라 치환된 것이다.

만약 행렬

M

의 행을

\pi^{-1}

에 따라 치환하고 싶다면

P_\pi^{-1} M = P_\pi^\top M

을 계산하고, 열을

\pi

에 따라 치환하고 싶다면

M P_\pi^{-1} = M P_\pi^\top

을 계산하면 된다.
치환 행렬의 곱셈 관련 성질두 순열

\pi, \sigma

에 대응하는 치환 행렬

P_\pi, P_\sigma

의 곱은 순열의 합성에 대응하는 치환 행렬과 같다. (여기서 합성은

\pi

를 먼저 적용하고

\sigma

를 나중에 적용하는 순서

\sigma \circ \pi

를 의미한다.)

P_{\sigma} P_{\pi} = P_{\sigma \circ \pi}

치환 행렬은 직교 행렬이다. 즉, 전치 행렬이 역행렬과 같다.

P_{\pi} P_{\pi}^{\top} = I

따라서 역행렬은 다음과 같이 주어진다.

P_{\pi}^{-1} = P_{\pi^{-1}} = P_{\pi}^{\top}

치환 행렬

P_\pi

를 열 벡터

\mathbf{g}

에 왼쪽에 곱하면 벡터의 성분이

\pi^{-1}

에 따라 재배열된다 (즉, 결과 벡터의

i

번째 성분은 원래 벡터의

\pi^{-1}(i)

번째 성분이 된다). 이는 벡터의 항목을

\pi

에 따라 치환하는 것과 같다.

P_\pi \mathbf{g} = \begin{bmatrix} \mathbf{e}_{\pi^{-1}(1)}^\top \\ \mathbf{e}_{\pi^{-1}(2)}^\top \\ \vdots \\ \mathbf{e}_{\pi^{-1}(n)}^\top \end{bmatrix} \begin{bmatrix} g_1 \\ g_2 \\ \vdots \\ g_n \end{bmatrix} = \begin{bmatrix} g_{\pi^{-1}(1)} \\ g_{\pi^{-1}(2)} \\ \vdots \\ g_{\pi^{-1}(n)} \end{bmatrix}

행 벡터

\mathbf{h}

에 치환 행렬

P_\pi

를 오른쪽에 곱하면 벡터의 성분이

\pi

에 따라 재배열된다 (즉, 결과 벡터의

j

번째 성분은 원래 벡터의

\pi(j)

번째 성분이 된다). 이는 벡터의 항목을

\pi^{-1}

에 따라 치환하는 것과 같다.

\mathbf{h} P_\pi = \begin{bmatrix} h_1 & h_2 & \ldots & h_n \end{bmatrix} \begin{bmatrix} \mathbf{e}_{\pi^{-1}(1)}^\top \\ \mathbf{e}_{\pi^{-1}(2)}^\top \\ \vdots \\ \mathbf{e}_{\pi^{-1}(n)}^\top \end{bmatrix}^\top = \begin{bmatrix} h_1 & h_2 & \ldots & h_n \end{bmatrix} \begin{bmatrix} \mathbf{e}_{\pi(1)} & \mathbf{e}_{\pi(2)} & \ldots & \mathbf{e}_{\pi(n)} \end{bmatrix} = \begin{bmatrix} h_{\pi(1)} & h_{\pi(2)} & \ldots & h_{\pi(n)} \end{bmatrix}

(참고: 원본 소스의 행 벡터 곱셈 결과

h_{\pi^{-1}(j)}

는 열 벡터 정의

(P_\pi)_{ij} = \delta_{i, \pi(j)}

와 일관성을 맞추려면

h_{\pi(j)}

가 되어야 할 것으로 보이나, 여기서는 원본 소스의 수식을 따름. 만약

(P_\pi)_{ij} = \delta_{\pi(i), j}

정의를 사용하면 행 벡터 곱셈 결과가

h_{\pi^{-1}(j)}

가 됨)

5. 선형대수적 성질

치환 행렬은 순열과 밀접하게 연관되어 있으며, 순열의 성질로부터 다양한 선형대수적 특성을 도출할 수 있다.

''m''개의 문자에 대한 두 순열 ''π'', ''σ''에 대응하는 치환 행렬을 각각 ''P''_''π'', ''P''_''σ''라고 할 때, 이 두 행렬의 곱은 순열의 합성에 대응하는 치환 행렬과 같다. 즉, 열 벡터에 작용하는 경우 다음과 같은 관계가 성립한다.

: ''P''_''σ''''P''_''π'' = ''P''_{''σ''∘''π''}

치환 행렬은 직교 행렬이다. 즉, 전치행렬이 역행렬과 같다. 이는 역순열에 대응하는 치환 행렬과도 같다.

: ''P''_''π''^-1 = ''P''_''π''^-1 = ''P''_''π''^T

따라서 다음이 성립한다.

: ''P''_''π''''P''_''π''^T = ''I''

여기서 ''I''는 단위 행렬이다.

치환 행렬 ''P''의 대각합(trace)은 대응하는 순열의 고정점 개수와 같다.^[1] 만약 정수 ''k''가 순열의 고정점이라면, 표준 기저 벡터 '''e'''_''k''는 ''P''의 고유벡터이다.^[1]

치환 행렬 ''P''의 복소수 고유값은 대응하는 순열의 순환 분해와 관련이 있다. 순열을 서로소 순환들의 곱 ''κ''_''P'' = ''c''₁''c''₂⋯''c''_''t'' 로 나타냈다고 하자. 각 순환 ''c''_''i''의 길이를 ''ℓ''_''i''라고 할 때, ''x''^{''ℓ''_''i''} = 1의 복소수 해의 집합, 즉 ''ℓ''_''i''번째 단위근들의 집합을 ''L''_''i''라고 하자. 모든 ''L''_''i''들의 중복집합 합집합이 바로 ''P''의 고유값들의 중복집합이다.^[6] 특정 고유값 ''v''의 중복도는 ''v''를 원소로 가지는 집합 ''L''_''i''의 개수와 같다.^[6] 모든 치환 행렬은 정규 행렬이므로 대각화 가능하며, 따라서 고유값의 대수적 중복도와 기하학적 중복도는 항상 같다.^[1]

군론에 따르면 모든 순열은 전치(transposition)들의 곱으로 표현될 수 있다. 이는 모든 치환 행렬이 행을 교환하는 기본 행렬들의 곱으로 분해될 수 있음을 의미한다. 각 행 교환 기본 행렬의 행렬식은 -1이므로, 치환 행렬 ''P''의 행렬식은 대응하는 순열의 부호(sign)와 같다.

6. 군론적 성질

n개의 원소에 대한 치환은 총 $n!$ 개 존재한다. 각 치환 $\pi$ 에 대응하는 치환행렬 $P_{\pi}$ (또는 $C_{\pi}$ , $R_{\pi}$ )을 정의할 수 있으며, 이 대응은 일대일 대응이다. 따라서 치환 행렬도 $n!$ 개 존재한다.

$n \times n$ 크기의 치환 행렬 전체의 집합은 행렬 곱셈 연산에 대해 군을 이룬다. 이 군을 $\mathcal{P}_n$ 으로 표기하며, 군의 항등원은 항등 치환에 대응하는 항등 행렬 $I$ 이다. 이 군의 위수는 $n!$ 이다.

군 $\mathcal{P}_n$ 은 실수를 성분으로 가지는 $n \times n$ 가역행렬 전체의 군인 일반 선형군 $GL_n(\mathbb{R})$ 의 부분군이다. 더 나아가, 임의의 체 $F$ 에 대해서도, 군 $\mathcal{P}_n$ 은 $F$ 를 성분으로 가지는 일반 선형군 $GL_n(F)$ 의 부분군이다. 이는 치환 행렬의 정의와 곱셈이 0과 1만 사용하며, 체의 기본 연산( $0+0=0,$ $0+1=1,$ $0 \times 0=0,$ $0 \times 1=0,$ $1 \times 1=1$ )만으로 정의되기 때문이다.

$\{1, 2, \dots, n\}$ 위의 대칭군을 $S_n$ 이라고 하자.

치환 $\pi$ 를 열 벡터에 작용하는 치환 행렬 $C_{\pi}$ 에 대응시키는 사상 $C\colon S_n\to GL_n(\mathbb{R})$ 는 충실한 표현이다. 여기서 $S_n$ 의 연산은 통상적인 치환의 합성(오른쪽에서 왼쪽으로 적용, $\circ$ )이다.
치환 $\pi$ 를 행 벡터에 작용하는 치환 행렬 $R_{\pi}$ 에 대응시키는 사상 $R\colon S_n\to GL_n(\mathbb{R})$ 도 충실한 표현이다. 이 경우 $S_n$ 의 연산은 반대 순서(왼쪽에서 오른쪽으로 적용, $;$ )로 볼 수 있는 반대군에 대한 표현이다.

두 치환

\pi, \sigma

에 대응하는 (열 벡터 기준) 치환 행렬

P_{\pi}, P_{\sigma}

의 곱은 두 치환의 합성

\sigma\circ\pi

에 대응하는 치환 행렬과 같다:

:

P_{\sigma} P_{\pi} = P_{\sigma\circ\pi}

(행 벡터 기준 치환 행렬을 사용하면 곱 규칙은

P_{\sigma} P_{\pi} = P_{\pi\circ\sigma}

가 된다.)

치환 행렬

P_{\pi}

는 직교 행렬이다. 즉, 전치 행렬이 역행렬과 같다:

:

P_{\pi}P_{\pi}^{\top} = I

따라서

P_{\pi}

의 역행렬은 역치환

\pi^{-1}

에 대응하는 치환 행렬 또는 원래 치환 행렬의 전치 행렬과 같다:

:

P_{\pi}^{-1} = P_{\pi^{-1}} = P_{\pi}^{\top}

군론에서 임의의 순열은 전환(두 원소의 위치를 바꾸는 치환)들의 곱으로 나타낼 수 있다는 사실로부터, 임의의 치환 행렬은 두 행을 교환하는 기본 행렬들의 곱으로 표현할 수 있다. 각 행 교환 기본 행렬의 행렬식은

-1

이므로, 치환 행렬

P_{\pi}

의 행렬식은 대응하는 치환

\pi

의 부호와 같다:

:

\det(P_\pi) = \operatorname{sgn}(\pi)

7. 예

치환행렬은 단위 행렬의 행이나 열의 순서를 바꾸어 얻을 수 있는 행렬이다. 예를 들어, 3x3 단위 행렬 $I$ 의 행이나 열을 재배열하여 치환행렬 $P$ 를 만들 수 있다.

$I = \begin{bmatrix}1 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 1 \end{bmatrix}$

이 치환행렬 $P$ 를 임의의 행렬 $A$ 에 곱하면 $A$ 의 행 또는 열이 재배열된다. $P$ 를 $A$ 의 왼쪽에 곱하면( $PA$ ) $A$ 의 행이 재배열되고, 오른쪽에 곱하면( $AP$ ) $A$ 의 열이 재배열된다. 이는 단위 행렬에서 $P$ 를 만들 때 적용된 행 또는 열의 재배열 방식과 동일하게 이루어진다.

7. 1. 행의 재배열

3 \times 3

단위 행렬

I

는 다음과 같다.

I = \begin{bmatrix}1 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 1 \end{bmatrix}

이 단위 행렬

I

의 1행과 3행을 서로 바꾸면 다음과 같은 행렬

I^a

를 얻을 수 있다. 이는 치환행렬의 한 예이다.

I^{a} = \begin{bmatrix}0 & 0 & 1 \\0 & 1 & 0 \\1 & 0 & 0\end{bmatrix}

임의의

3 \times 3

행렬

A

를 다음과 같이 정의하자.

A =\begin{bmatrix}a & b & c \\d & e & f \\g & h & i\end{bmatrix}

행렬

A

의 왼쪽에 행렬

I^a

를 곱하면 다음과 같은 결과를 얻는다.

I^a A = \begin{bmatrix}0 & 0 & 1 \\0 & 1 & 0 \\1 & 0 & 0\end{bmatrix}\begin{bmatrix}a & b & c \\d & e & f \\g & h & i\end{bmatrix} =\begin{bmatrix}g & h & i \\d & e & f \\a & b & c\end{bmatrix}

이 결과는 원래 행렬

A

의 1행과 3행이 서로 바뀐 것과 같다. 즉, 단위 행렬의 특정 행들을 재배열하여 만든 치환행렬을 어떤 행렬의 왼쪽에 곱하면, 그 행렬의 해당 행들이 동일하게 재배열된다.

7. 2. 열의 재배열

3 \times 3

단위 행렬

I

는 다음과 같다.

I = \begin{bmatrix}1 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 1 \end{bmatrix}

이 단위 행렬의 1열과 3열을 서로 바꾸면 다음과 같은 행렬

I^a

를 얻을 수 있다.

I^{a} = \begin{bmatrix}0 & 0 & 1 \\0 & 1 & 0 \\1 & 0 & 0\end{bmatrix}

임의의

3 \times 3

행렬

A

를 다음과 같이 정의하자.

A =\begin{bmatrix}a & b & c \\d & e & f \\g & h & i\end{bmatrix}

행렬

A

에

I^a

를 오른쪽에서 곱하면 다음과 같은 결과를 얻는다.

A I^a =\begin{bmatrix}a & b & c \\d & e & f \\g & h & i\end{bmatrix}\begin{bmatrix}0 & 0 & 1 \\0 & 1 & 0 \\1 & 0 & 0\end{bmatrix} =\begin{bmatrix}c & b & a \\f & e & d \\i & h & g\end{bmatrix}

결과 행렬은 원래 행렬

A

의 1열과 3열이 서로 바뀐 것과 같다. 즉, 특정 열이 재배열된 단위 행렬을 오른쪽에 곱하면 원래 행렬의 해당 열들이 동일하게 재배열된다.

8. 응용

코스타스 배열: 항목 간의 변위 벡터가 모두 고유한 치환 행렬이다.
n-퀸 문제: 각 대각선과 역대각선에 최대 하나의 항목만 있는 치환 행렬이다.

참조

_[1] 서적 Algebra Prentice Hall 1991
_[2] 논문 A dynamical systems approach to weighted graph matching https://www.scienced[...] 2022-08-21
_[3] 문서
_[4] 서적 The Symmetries of Things A K Peters/CRC Press 2008
_[5] 간행물 2006
_[6] 간행물 2013
_[7] 간행물 2006
_[8] 간행물 2006

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com