Section 2.4 치환과 \(PA=LU\)분해
Subsection 2.4.1 LU분해의 실패와 \(PA=LU\)
보조설명 2.1.3에서 본 행렬
\begin{equation*}
A = \begin{bmatrix}1\amp1\amp0\\0\amp0\amp1\\0\amp1\amp1\end{bmatrix}
\end{equation*}
은 소거하기 위해 행교환이 필요했다. 즉, \(A\)의 \((2,2)\) 성분이 \(0\)이어서 축으로 활용할 수 없었고, 2행과 3행을 교환해 \((2,2)\)성분을 영 아닌 수로 만들었다.
행교환 개념 심화를 위해 치환과 치환행렬을 도입한다. 2행과 3행의 교환은 행렬
\begin{equation}
P=\begin{bmatrix}1\amp0\amp0 \\ 0 \amp 0 \amp 1 \\ 0 \amp 1 \amp 0
\end{bmatrix}\tag{2.4.1}
\end{equation}
으로 표현할 수 있는데, 그 이유는
\begin{equation*}
PA=
\begin{bmatrix}1\amp0\amp0 \\ 0 \amp 0 \amp 1 \\ 0 \amp 1 \amp 0 \end{bmatrix}
\begin{bmatrix}1\amp1\amp0\\0\amp0\amp1\\0\amp1\amp1\end{bmatrix}=
\begin{bmatrix}
1\amp1\amp0
\\
0\amp1\amp1
\\
0\amp0\amp1
\end{bmatrix}
\end{equation*}
으로, \(P\)를 왼쪽에 곱하면 2행과 3행이 교환되기 때문이다. 이 때, \(P\)를 치환행렬이라고 한다.
보조설명 2.4.1. 호환과 치환.
종합하면, \(A\)의 \(PA=LU\)분해는
\begin{equation*}
\begin{bmatrix}1\amp0\amp0 \\ 0 \amp 0 \amp 1 \\ 0 \amp 1 \amp 0 \end{bmatrix}
\begin{bmatrix}1\amp1\amp0\\0\amp0\amp1\\0\amp1\amp1\end{bmatrix}=
\begin{bmatrix}1\amp0\amp0\\0\amp1\amp0\\0\amp0\amp1\end{bmatrix}
\begin{bmatrix}
1\amp1\amp0
\\
0\amp1\amp1
\\
0\amp0\amp1
\end{bmatrix}
\end{equation*}
이다.
Subsection 2.4.2 치환행렬
정의 2.4.2.
항등행렬의 행을 재배열해 얻은 행렬을 치환행렬이라 한다.
관찰 2.4.3. 열 재배열.
치환행렬에서 1을 보면 각 행에 하나씩 있다. 정사각행렬임을 상기하면 각 열에도 하나씩 있음을 알 수 있다. 따라서, 항등행렬의 열을 재배열해도 치환행렬이다.
관찰 2.4.4. 치환행렬 오른쪽에 곱하기.
치환행렬을 오른쪽에 곱하면 열이 재배열된다.
관찰 2.4.5. 치환행렬의 곱은 치환행렬.
치환행렬을 두 개 곱하면, 단위행렬의 열을 두 번 재배열하게 되는데, 그 결과는 다시 단위행렬의 행 재배열로 얻으지므로 치환행렬이다.
치환에 대해서는 절 5.1.3에서 자세히 다룬다.
Subsection 2.4.3 편축
\(PA=LU\)분해는 \(LU\)분해의 실패를 보완하는 것 외에 다른 기능이 있다. 가령, 당신의 컴퓨터는 근사값을 계산하며 유효숫자는 두 개라고 가정해 보자.
\begin{equation*}
\begin{bmatrix}
0.1 \amp 0 \amp 1
\\
-1\amp 0.1 \amp 0
\\
0 \amp -1 \amp 0.1
\end{bmatrix}
\end{equation*}
의 LU분해를 생각해보자.
계산해보면
\begin{equation*}
\begin{bmatrix}
0.1 \amp 0 \amp 1
\\
-1\amp 0.1 \amp 0
\\
0 \amp -1 \amp 0.1
\end{bmatrix}
=
\begin{bmatrix}
1 \amp 0 \amp 0
\\
-10\amp 1 \amp 0
\\
0 \amp -10 \amp 1
\end{bmatrix}
\begin{bmatrix}
0.1 \amp 0 \amp 1
\\
0\amp 0.1 \amp 10
\\
0 \amp 0 \amp 100.1
\end{bmatrix}
\end{equation*}
이다. 당신의 컴퓨터는 유효숫자가 두 자리 뿐이므로
\begin{equation*}
100.1\rightarrow 100
\end{equation*}
으로 저장하여, 원래 행렬을 계산해 보면
\begin{equation*}
\begin{bmatrix}
1 \amp 0 \amp 0
\\
-10\amp 1 \amp 0
\\
0 \amp -10 \amp 1
\end{bmatrix}
\begin{bmatrix}
0.1 \amp 0 \amp 1
\\
0\amp 0.1 \amp 10
\\
0 \amp 0 \amp 100
\end{bmatrix}
=
\begin{bmatrix}
0.1 \amp 0 \amp 1
\\
-1\amp 0.1 \amp 0
\\
0 \amp -1 \amp 0
\end{bmatrix}
\end{equation*}
이 된다. \((3,3)\)성분은
\begin{equation*}
0.1 \rightarrow 0
\end{equation*}
으로 100%의 오차가 발생했다.
이번에는 \(PA\)
\begin{equation*}
\begin{bmatrix}
0 \amp 1 \amp 0
\\
0\amp 0 \amp 1
\\
1 \amp 0 \amp 0
\end{bmatrix}
\begin{bmatrix}
0.1 \amp 0 \amp 1
\\
-1\amp 0.1 \amp 0
\\
0 \amp -1 \amp 0.1
\end{bmatrix}
\end{equation*}
의 LU분해를 생각해보자.
\begin{equation}
\begin{bmatrix}
0 \amp 1 \amp 0
\\
0\amp 0 \amp 1
\\
1 \amp 0 \amp 0
\end{bmatrix}
\begin{bmatrix}
0.1 \amp 0 \amp 1
\\
-1\amp 0.1 \amp 0
\\
0 \amp -1 \amp 0.1
\end{bmatrix}
=
\begin{bmatrix}
-1\amp 0.1 \amp 0
\\
0 \amp -1 \amp 0.1
\\
0.1 \amp 0 \amp 1
\end{bmatrix}
=
\begin{bmatrix}
1\amp 0 \amp 0
\\
0 \amp 1 \amp 0
\\
-0.1 \amp -0.01 \amp 1
\end{bmatrix}
\begin{bmatrix}
-1\amp 0.1 \amp 0
\\
0 \amp -1 \amp 0.1
\\
0 \amp 0 \amp 1.001
\end{bmatrix}\tag{2.4.2}
\end{equation}
이다. 유효숫자 조건에 따라 (3,3)성분을
\begin{equation*}
1.001\rightarrow 1.0
\end{equation*}
으로 저장하는 경우 원래 행렬은
\begin{equation*}
\begin{bmatrix}
1\amp 0 \amp 0
\\
0 \amp 1 \amp 0
\\
-0.1 \amp -0.01 \amp 1
\end{bmatrix}
\begin{bmatrix}
-1\amp 0.1 \amp 0
\\
0 \amp -1 \amp 0.1
\\
0 \amp 0 \amp 1.0
\end{bmatrix}
=
\begin{bmatrix}
-1\amp 0.1 \amp 0
\\
0 \amp -1 \amp 0.1
\\
0.1 \amp 0 \amp 0.99
\end{bmatrix}
\end{equation*}
으로 복원된다. 이때, (3,3)성분은
\begin{equation*}
1\rightarrow 0.99
\end{equation*}
으로 바뀌어 1%의 오차가 발생했다.
근사 계산에서 오차를 줄이기 위한 방법으로 편축을 사용한 \(PA=LU\)분해를 소개한다. 원 행렬
\begin{equation*}
\begin{bmatrix}
0.1 \amp 0 \amp 1
\\
-1\amp 0.1 \amp 0
\\
0 \amp -1 \amp 0.1
\end{bmatrix}
\end{equation*}
의 경우 이대로 소거하면 \(0.1\)이 축이 될 텐데, 1행과 2행을 교환하면
\begin{equation*}
\begin{bmatrix}
-1\amp 0.1 \amp 0
\\
0.1 \amp 0 \amp 1
\\
0 \amp -1 \amp 0.1
\end{bmatrix}
\end{equation*}
이 되어 \(-1\)이 축이 된다.
\begin{equation*}
|-1|>|0.1|
\end{equation*}
이므로 (절댓값이) 더 큰 축을 선택한 셈이다. 같은 원리로 소거의 다음 단계
\begin{equation*}
\begin{bmatrix}
-1\amp 0.1 \amp 0
\\
0 \amp 0.01 \amp 1
\\
0 \amp -1 \amp 0.1
\end{bmatrix}
\end{equation*}
에서 가능한 축의 후보는 \(0.01\)과 \(-1\)인데, 역시
\begin{equation*}
|-1| > |0.01|
\end{equation*}
이므로 큰 축을 택하기 위해 2행과 3행을 교환해
\begin{equation*}
\begin{bmatrix}
-1\amp 0.1 \amp 0
\\
0 \amp -1 \amp 0.1
\\
0 \amp 0.01 \amp 1
\end{bmatrix}
\end{equation*}
를 얻고 여기서부터 다시 소거를 진행한다. 전체 과정을 \(PA=LU\)로 쓰면 (2.4.2)이다.
Subsection 2.4.4 치환행렬의 역행렬
전치 개념을 벡터에서 행렬로 확장하자.
정의 2.4.6.
행렬 \(\begin{bmatrix}\boldsymbol c_1 \amp \cdots \amp \boldsymbol c_n \end{bmatrix}\)의 전치는 \(\begin{bmatrix}\boldsymbol c_1^{\operatorname{T}}\\\boldsymbol c_2^{\operatorname{T}}\\\vdots\\\boldsymbol c_n^{\operatorname{T}}\end{bmatrix}\)으로 정의한다. 반대로, \(\begin{bmatrix}\boldsymbol r_1\\\boldsymbol r_2\\\vdots\\\boldsymbol r_m\end{bmatrix}\)의 전치는 \(\begin{bmatrix}\boldsymbol r_1^{\operatorname{T}}\amp\cdots\amp \boldsymbol r_m^{\operatorname{T}}\end{bmatrix}\)로 정의한다. 행렬 \(A\)의 전치는 \(A^{\operatorname{T}}\)로 나타낸다.
치환행렬
\begin{equation*}
P_{312}
=
\begin{bmatrix}
0\amp0\amp1
\\
1\amp0\amp0
\\
0\amp1\amp0
\end{bmatrix}
\end{equation*}
을 생각하자.
\begin{equation*}
P_{312}
P_{312}^{\operatorname T}
=
\begin{bmatrix}
0\amp0\amp1
\\
1\amp0\amp0
\\
0\amp1\amp0
\end{bmatrix}
\begin{bmatrix}
0\amp1\amp0
\\
0\amp0\amp1
\\
1\amp0\amp0
\end{bmatrix}
=
\begin{bmatrix}
1\amp0\amp0
\\
0\amp1\amp0
\\
0\amp0\amp1
\end{bmatrix}
\end{equation*}
임을 관찰하자.
일반적으로, 치환행렬 \(P\)는 가역이고
\begin{equation}
P^{\operatorname T}= P^{-1}\tag{2.4.3}
\end{equation}
이 성립한다.
(2.4.3)이 성립하는 이유를 알아보자. 행렬 \(A\)의 행벡터를 \(\boldsymbol r_1,\cdots,\boldsymbol r_m\)이라 하면, \(AA^{\operatorname T}\)의 성분은 \(\boldsymbol r_i \bullet \boldsymbol r_j\)꼴이다. \(A=P\)인 경우
\begin{equation*}
\boldsymbol r_i \bullet \boldsymbol r_j=
\begin{cases}
1 \amp \hspace{10pt}\text{$i=j$}
\\
0 \amp \hspace{10pt}\text{$i\not=j$}
\end{cases}
\end{equation*}
이므로 \(PP^{\operatorname T}=I\)를 얻는다. 비슷하게 \(P^{\operatorname T}P=I\)를 얻고, 종합하여 결론에 도달한다.
Subsection 2.4.5 축과 랭크
이 절에서는 \(PA=LU\)분해와 \(A=CR\)분해의 관계를 알아보자.
명제 2.4.7.
\(B\)가 가역행렬이고
\begin{equation*}
A=CR
\end{equation*}
이 CR분해일 때 \(BA\)의 CR분해는
\begin{equation*}
BA = (BC)R
\end{equation*}
이다.
증명.
\(A\)의 열벡터를 \(\boldsymbol c_1,\cdots,\boldsymbol c_n\)이라 하자. \(BA\)의 열벡터는 \(B\boldsymbol c_1,\cdots,B\boldsymbol c_n\)이다. 정리를 증명하기 위해서는 각 \(k=1,2,\cdots,n\)에 대하여
\begin{equation*}
\boldsymbol c_k \in \operatorname{span}(\boldsymbol c_1,\cdots,\boldsymbol c_{k-1}) \Leftrightarrow
B\boldsymbol c_k \in \operatorname{span}(B\boldsymbol c_1,\cdots,B\boldsymbol c_{k-1})
\end{equation*}
를 보이면 충분하다.
만약
\begin{equation*}
\boldsymbol c_k = a_1\boldsymbol c_1+ \cdots +a_{k-1} \boldsymbol c_{k-1}
\end{equation*}
이면 양변에 \(B\)를 곱해
\begin{equation*}
B\boldsymbol c_k = a_1B\boldsymbol c_1+ \cdots +a_{k-1} B\boldsymbol c_{k-1}
\end{equation*}
를 얻는다. 즉, \(B\boldsymbol c_k \in \operatorname{span}(B\boldsymbol c_1,\cdots,B\boldsymbol c_{k-1})\)이다.
반대로
\begin{equation*}
B\boldsymbol c_k = a_1B\boldsymbol c_1+ \cdots +a_{k-1} B\boldsymbol c_{k-1}
\end{equation*}
라면 \(B^{-1}\)를 곱해 \(\boldsymbol c_k \in \operatorname{span}(\boldsymbol c_1,\cdots,\boldsymbol c_{k-1})\)을 얻는다.
정리 2.4.7로부터 축과 랭크의 관계를 유도할 수 있다.
정리 2.4.8.
행렬 \(A\)의 랭크는 축의 개수와 같다.
증명.
먼저, 정리의 주장을 \(A=U\)인 경우, 즉 \(A\)가 이미 소거된 경우를 살펴보자. \(U\)에서 축의 위치가 \(k_1,\cdots,k_r\)열에 있다면, \(U=CR\)분해에서 \(C\)는 축의 위치에 해당하는 \(U\)의 열벡터 로 구성된다. 다시 말해 \(U=[\boldsymbol u_1 \cdots \boldsymbol u_n]\)이면 \(C=[\boldsymbol c_{k_1} \cdots \boldsymbol u_{k_r}]\)이다. 따라서, 축의 개수가 랭크와 같다.
일반적인 \(A\)에 대해 정리의 주장을 확인해보자. \(PA=LU\)분해를 사용하자. \(PA=LU\)의 좌변에 \(L^{-1}\)를 곱해
\begin{equation*}
BA=U
\end{equation*}
로 쓰자. 즉, \(B=L^{-1}P\)이다. 한편, \(A=CR\)에 \(B\)를 곱하면
\begin{equation*}
BA=(BC)R
\end{equation*}
인데, \(BA=U\)이므로 \(U\)의 CR분해
\begin{equation*}
U=(BC)R
\end{equation*}
를 얻는다. 정의로부터 \(\operatorname{rank}(A)\)=(\(C\)의 열 개수)이고, (\(C\)의 행 개수)=(\(BC\)의 열 개수)이므로, 원하는 결론을 위해서는 (\(U\)의 축 개수)=(\(BC\)의 열 개수)를 확인하면 충분하다. 이는 앞에서 살펴본 “이미 소거된 경우”에 해당하므로, 이것으로 증명이 끝난다.
Subsection 2.4.6 \(PA=LU\)분해
명제 2.4.9.
임의의 정사각행렬 \(A\)에 대하여 적당한 치환행렬 \(P\)가 존재하여 \(PA\)는 LU분해를 갖는다. 즉,
\begin{equation*}
PA=LU
\end{equation*}
로 분해된다. 단, 우변은 \(PA\)의 LU분해이다.
증명.
연습문제.
분해 \(PA=LU\)를 변형한
\begin{equation}
PA=LDU\tag{2.4.4}
\end{equation}
도 가능한데, 여기서 \(D\)는 대각행렬로 \(U\)의 모든 축이 1이 되도록 고른 것이다. 가령, 행렬
\begin{equation*}
\begin{bmatrix}
2&4&6
\\
0&0&5
\end{bmatrix}
\end{equation*}
는
\begin{equation*}
\begin{bmatrix}
2&4&6
\\
0&0&5
\end{bmatrix}
=
\begin{bmatrix}
2&0
\\
0&5
\end{bmatrix}
\begin{bmatrix}
1&2&3
\\
0&0&1
\end{bmatrix}
\end{equation*}
으로 쓸 수 있다.
연습문제 2.4.7 연습문제
1.
2.
- 참
- 거짓
\(A\boldsymbol x\)와 \(\boldsymbol y\)을 내적한 값은 \(\boldsymbol x\)와 \(A^{\operatorname{T}} \boldsymbol y\)를 내적한 값과 같다. (단, 모든 내적 및 곱셈은 잘 정의된다고 가정한다.)
3.
- 홀
- 짝
행렬 \(\begin{bmatrix}
0&0&0&1 \\
0&0&1&0 \\
0&1&0&0 \\
1&0&0&0
\end{bmatrix}\) 의 홀짝을 판별하여라.
4.
- 홀
- 짝
행렬 \(\begin{bmatrix}
1&0&0&0 \\
0&0&1&0 \\
0&1&0&0 \\
0&0&0&1
\end{bmatrix}\) 의 홀짝을 판별하여라.
5.
- 홀
- 짝
행렬 \(\begin{bmatrix}
0&0&0&1 \\
1&0&0&0 \\
0&1&0&0 \\
0&0&1&0
\end{bmatrix}\) 의 홀짝을 판별하여라.
6.
- 참
- 거짓
치환행렬은 항상 가역이다.
7.
- 참
- 거짓
치환행렬의 서로 다른 두 행은 반드시 다르다.
8.
- 참
- 거짓
치환행렬의 서로 다른 두 행은 반드시 서로 수직이다.
9.
- 작은 축을 선택했을 때 행렬 분해가 불가능할 수 있다.
- 분해의 가능성과는 관계가 없으며 근사 계산에 관한 것이다.
편축 개념을 사용한 분해에 대한 설명으로 옳은 것을 고르시오.
10.
- 참
- 거짓
치환행렬은 대칭행렬이다.
11.
- 참
- 거짓
가역행렬의 전치는 가역행렬이다.
