연습문제 풀이 (Problem 1.2.11 ~ 1.8.23)

Problem 1.2.11

$0$이 아닌 대각 항들을 갖는 $d\times d$ 삼각 행렬  $L$에 대해 가역 행렬 $\Delta$ 와 순 삼각행렬 $A$가 존재하여 $L=\left(\Delta + A\right)$로 표현이 가능하다. 이떄 행렬에 대한 역변환과 행렬 곱셉 및 덧셈만 이용하여 $L$의 역행렬을 계산하라.

Hint. $d\times d$ 크기의 순 삼각행렬은 항상 멱영이며, $A^d=0$임을 주목하라.

앞의 정리 $\left(I+A \right )^{-1}=\displaystyle\sum_{d=0}^\infty A^d$가 유도되는 과정을 활용하자.

우변에 $\left(I+A \right )$를 곱했을 때, $I$만 남고 나머지는 뒤의 $A$항에 의해 삭제가 되는 원리를 활용한 방법인데(등비수열의 합 유도) 이를 활용할 것이다.

일단 $I$가 나와야 하므로 $\Delta^{-1}$은 필수로 있어야 하고, 이가 $A$랑 곱해지면 $\Delta^{-1}A$가 된다.

이를 $\Delta$항과 어떤 항이 곱해져서 소거시켜야 하므로 $-\Delta^{-2}A$가 있어야 하고, 이가 $A$랑 곱해지면 $-\Delta^{-2}A^2$가 된다.

동일하게 $\Delta^{-3}A^2$가 있어야하고, 이가 $A$랑 곱해지면 $\Delta^{-3}A^3$이고...

이 일련의 과정을 반복하면 나오는 식은

$\Delta^{-1}-\Delta^{-2}A+\Delta^{-3}A^2-\cdots=\Delta^{-1}\left( I-\Delta^{-1} A+\Delta^{-2}A^2\cdots\right )$이 된다.

이가 성립하는 이유는 $\displaystyle\lim_{d\,\rightarrow\,\infty}A^d=0$임을 기억하라.

---

Problem 1.2.12

$I$와 $P$가 $k\times k$ 행렬일 때, $\left(I+P \right )^{-1}=I-\left(I+P \right )^{-1}P$가 성립함을 보여라.

보이기만 하면 되므로, $\left(I+P \right )$과 $I-\left(I+P \right )^{-1}P$을 곱해서 $I$가 됨을 보이자.

$\begin{aligned}
\left(I+P \right )\left\{ I-\left(I+P \right )^{-1}P\right \}&=\left(I+P \right )-P\\
&=I
\end{aligned}$

이에 따라 성립한다.

---

Problem 1.2.14

두 벡터의 외적에 대한 프로베니우스 노움은 유클리드 노움의 곱과 동일함을 보이시오.

$A\otimes B=C$라 하고, $C=\left[c_{ij} \right ]_{i\leq n,~j\leq d}$로 하자.

이 때, 외적의 정의에 의해 $c_{ij}=a_i\times b_j$이다.

따라서

\begin{aligned} 
\lVert C\rVert_F&=\displaystyle\sqrt{\sum_{i=1}^n\sum_{j=1}^d c_{ij}{}^2}\\
&=\displaystyle\sqrt{\sum_{i=1}^n\sum_{j=1}^d \left(a_ib_j \right )^2}\\
&=\displaystyle\sqrt{\sum_{i=1}^n\left(a_i\sum_{j=1}^d b_j{}^2\right )}\\
&=\displaystyle\sqrt{\left( \sum_{i=1}^n a_i{}^2\right )\left( \sum_{j=1}^d b_j{}^2\right )}\\
&=\lVert A\rVert\cdot\lVert B\rVert
\end{aligned}이고, 이에 따라 준식이 성립한다.

---

Problem 1.2.15

프로베니우스 노움이 $\epsilon$인 $n \times n$ 행렬의 역의 프로베니우스 노움은 $\frac{\sqrt{n}}{\epsilon}$ 이상임을 보이시오.

Lemma 1.2.7에 의해 $\lVert AA^{-1}\rVert_F\leq\lVert A\rVert_F\lVert A^{-1}\rVert_F$이 성립한다.

이때 $\lVert I\rVert_F=\sqrt{n}$이 성립하고, 문제의 조건에 의해 $\lVert A\rVert_F=\epsilon$을 이용하면

$\sqrt{n}\leq \epsilon\lVert A^{-1}\rVert_F$이고, $\epsilon>0$이므로 양변에 나누어도 부등호가 안바뀜을 이용하여 나누면 $\lVert A^{-1}\rVert_F\geq\frac{\sqrt{n}}{\epsilon}$

따라서 준 부등식이 성립한다.

---

1.3 챕터의 연습문제는 쉽고 딱히 적을 내용도 없어서 생략.

---

Problem 1.5.1

테일러 급수는 복소수 함수에서도 유효하다.(증명 없이 넘어가자)

테일러 급수를 사용하여 오일러 항등식 $e^{i\theta}=\cos\left(\theta \right )+i\sin \left(\theta \right )$가 성립함을 보이시오.

$e^x$를 테일러 전개하자.

$\exp\left(x \right )=\displaystyle\sum_{n\in \mathbb{N}^+}\frac{x^n}{n!}$이고, $x=i\theta$를 대입하면 $\exp\left(i\theta \right )=\displaystyle\sum_{n\in \mathbb{N}^+}\frac{\left(i\theta \right )^n}{n!}$

허수의 정의에 의해 $i^{4n+2}=\mathit{}-1\in\mathbb{R}$, $i^{4n}=1\in\mathbb{R}$이므로 위의 식에서 $n$이 홀수일 때와 짝수일 떄를 분리해서 전개하면

\begin{aligned} 
\exp\left(i\theta \right )&=\displaystyle\sum_{n\in \mathbb{N}^+}\frac{\left(i\theta \right )^n}{n!}\\
&=\sum_{n\in \mathbb{N}^+}\frac{\left(i\theta \right )^{2n}}{\left(2n \right )!}+\sum_{n\in \mathbb{N}^+}\frac{\left(i\theta \right )^{2n+1}}{\left(2n+1 \right )!}\\
&=\sum_{n\in \mathbb{N}^+}\frac{\left(-1 \right )^n\theta^{\,2n}}{\left(2n \right )!}+i\sum_{n\in \mathbb{N}^+}\frac{\left(-1 \right )^n\theta ^{\,2n+1}}{\left(2n+1 \right )!}\\
&=\cos \left(\theta \right )+i\sin\left(\theta \right )
\end{aligned}이고, 이에 따라 준식이 성립한다.

 

---

Problem 1.8.1

길이가 $a$로 동일한 두 벡터 $\bar{x}$와 $\bar{y}$에 대해

(1) $\bar{x}-\bar{y}\mathit{}$와 $\bar{x}+\bar{y}\mathit{}$가 직교함을 보이시오.

(2) $\bar{x}-3\bar{y}\mathit{}$와 $\bar{x}+3\bar{y}\mathit{}$의 점곱이 음수임을 보이시오.

(1) 직교하기 위해서는 두 벡터의 내적값이 $0$이어야 한다.

Dot proudct를 하면 $\lVert\bar{x}\rVert^2-\lVert\bar{y}\rVert^2$이 되고, 길이가 $a$이므로 $0$이다.

(2) 동일하게 내적을 수행하자.

$\lVert\bar{x}\rVert^2-9\lVert\bar{y}\rVert^2$이 성립하고, 길이가 $a$이므로 계산값은 $-8a^2<0\mathit{}$이다.

---

Problem 1.8.2

각각 크기가 $10\times 2$, $2\times 10$, $10\times 10$인 $3$개의 행렬 $A$, $B$, $C$가 있다고 하자.

(1) 행렬 곱 $ABC\mathit{}$를 계산할 때, $(AB)C\mathit{}$를 계산하는 것과 $A(BC)\mathit{}$를 계산하는 것 중 어느쪽이 효율적인가?

(2) 행렬 곱 $CAB\mathit{}$를 계산할 때, $(CA)B\mathit{}$를 계산하는 것과 $C(AB)\mathit{}$를 계산하는 것 중 어느쪽이 효율적인가?

(1)

$(AB)$를 계산하는데 $10\times2\times10$번의 연산이, 이후 $10\times 10$ 행렬과 $10\times 10$ 행렬을 곱하는데 $10\times 10\times10$의 연산이 필요하다.

반대로 후자부터 계산하면 $2\times10\times10$번의 연산과 $10\times2\times10$의 연산이 걸리므로 후자가 이득이다.

(2) (1)과 동일한 방식으로 계산한다.

---

Problem 1.8.3

행렬 $A$가 $A=\mathit{}-A^T$를 만족할 경우 행렬의 모든 대각 항이 $0$임을 보이시오.

$A=\mathit{}-A^T$이므로 $a_{ii}=\mathit{}-a_{ii}$가 성립해야한다.

따라서 모든 대각항이 $0$이다.

---

Problem 1.8.4

$A=\mathit{}-A^T$를 만족하는 행렬 $A$와 임의의 열벡터 $\bar{x}$에 대해 $\bar{x}^T A\bar{x}=0$가 성립함을 보이시오.

일단 준식은 $1\times 1$ 행렬로 값을 의미하는 바임을 기억하자.

$A=\mathit{}-A^T$임으로 우리가 보이고자 하는 식에 대입하자.

$\begin{aligned} 
\bar{x}^T A\bar{x}&=\mathit{}-\bar{x}^TA^T\bar{x}\\
&=\mathit{}-\left(\bar{x}^TA\bar{x} \right )^T\\
\end{aligned}$이고, 1.8.3에 의해 $\bar{x}^T A\bar{x}$의 대각 항이 $0$이다.

이 때 $\bar{x}^T A\bar{x}$은 값이기 때문에, 대각항이 곧 값이 되고, 따라서 준식이 성립한다.

---

Problem 1.8.5

$n\times d$인 행렬 $D$에 대해 $A=DD^T$인 $n\times n$행렬 $A$가 있다고 가정하자. 임의의 $n$차원 column-vector $\bar{x}$에 대해 $\bar{x}^TA\bar{x}\geq0$임을 보이시오.

$A=DD^T$임을 이용하기 위해 준 식에 대입하자.

\begin{aligned} 
\bar{x}^TA\bar{x}&=\bar{x}^TDD^T\bar{x}\\
&=\left(D^T\bar{x} \right )^T\left(D^T\bar{x} \right )\\
&=\left(D^T\bar{x} \right )\cdot \left(D^T\bar{x} \right )\\
&\geq0
\end{aligned}

---

Problem 1.8.6

$A$의 $i$번째 열과 $B$의 $i$번째 행을 서로 역의 관계인 값들로 배율조정 하면 행렬 곱 $AB$는 변화되지 않은 상태로 유지됨을 보이시오.

$A$의 $i$번째 열을 바꾸는 Elementary matrix를 $E_1$, $B$의 $i$번째 행을 바꾸는 Elementary matrix를 $E_2$라 하자.

그러면 배율조정한 후 곱한 식은 $AE_1E_2B$가 되고, 행렬의 곱에서는 결합법칙이 성립하므로 $E_1E_2$에 대해 주목하자

$E_1$과 $E_2$ 모두 단위행렬 $I$에서 배율조정을 한 것으로 봐도 된다.

이 때, 단위행렬 $I$의 $i$번째 행을 건들든, $i$번째 열을 건들든 둘 다 $\left(i,~i\right)$ 원소를 바꾸는 것은 동일하다.

즉, 단위행렬에 한해서는 행에 대해 배율조정을 하든 열에 대해 배율조정을 하든 결과는 같다.

따라서 $E_1$과 $E_2$는 $i$번째 행(혹은 $i$번째 열)에 대해 서로 역의 배율조정을 한 것이고, 이는 다시 원행렬 $I$로 돌아오기 때문에 $E_1E_2=I$가 되고, 문제의 설명이 성립한다.

---

Problem 1.8.7

모든 행렬 곱 $AB$는 $A\,'\Delta B\,'$ 형태로 표현될 수 있음을 보이시오. 여기에서 $A\,'$는 각 열에 있는 항들의 제곱합이 $1$인 행렬이고 $B'$는 각 행에 있는 항들의 제곱합이 $1$인 행렬이다. 그리고 $\Delta$는 대각선상에 음이 아닌 항들을 갖는 적절하게 선택된 대각행렬이다.

$A$는 열에 있는 항들에 대해 조절하고, $B$는 행에 있는 항들에 대해 조절하고, $AB$와 $A\,'\Delta B\,'$가 같다라는 것을 보여야 하므로 기본 행렬과 밀접한 관계가 있음을 알 수 있다.

열에 있는 항들에 대한 조정은 기본행렬을 뒤에 곱하고, 행은 반대로 앞에 곱하는 것에서부터 착안한다.

$A\, '$은 각 열에 있는 항들의 제곱합이 $1$이여야 한다는게 핵심이다. 이해를 돕기 위해 $A=\begin{bmatrix} \bar{a_1}&\bar{a_2}&\cdots&\bar{a_n}\end{bmatrix}$라 하자.

column-vector $\bar{a_i}$의 항들의 제곱합을 $K^2$라 하고, $\bar{b_i}=\frac{1}{K}\bar{a_i}$라 하자. $\bar{b_i}$의 모든 항들의 제곱은 $\displaystyle\frac{1}{K^2}\sum a_{ki}\mathit{}^2=1$이다.

즉, 각 열벡터에 있는 항들의 제곱합을 이용하여 배율조정을 하면, 문제에서 요구한 $A\,'$을 만들어낼 수 있다.

보다 정확하게, $K_i:=\sqrt{\displaystyle\sum a_{ki}\mathit{}^2}$로 정의하고, $E_1=\begin{bmatrix}
K_1&\cdots&0\\
\vdots&\ddots&\vdots\\
0&\cdots&K_n
\end{bmatrix}$라 하면 $AE_1=A\,'$이 된다.

$B$도 동일한 방법으로 배율 조정을 하여 $E_2B=B\,'$이 되는 기본행렬 $E_2$를 찾아낼 수 있다.

기본행렬의 곱은 대각행렬이고, $E_1$과 $E_2$ 모두 대각 항이 양수이므로 $E_1\times E_2$도 동일하게 음이 아닌 항들을 갖는 대각행렬이다.

---

Problem 1.8.8

한 가지 유형의 기본 행 연산을 최대 $d$번 사용하여 순열 행렬을 단위행렬로 변환하는 방법을 설명하시오. 이 사실을 사용하여 $d\times d$ 행렬 $A$를 최대 $d$개의 기본 행렬 연산자의 곱으로 표현하시오.

순열행렬의 특징으로는 ① 각 행 $i$에 $1$의 값을 가지는 것이 단 하나, 그 이외는 0 ② 열도 동일이다.

최대 $d$번 활용하여 다시 단위행렬을 만들기 위해서 선택정렬 기법을 활용하자.

선택정렬은 다음과 같은 과정으로 이루어지는 정렬을 의미한다.

1. 현재 원소 $i$번째를 기준으로 $i$번째에서 $N$번째까지의 원소 중 최솟값을 찾는다.(Find)

2. $i$번째 원소와 그 원소의 값을 바꾼다.(Swap)

한 원소에 대해 찾는 과정이 최대 $N$, 이러한 원소가 총 $N$개 있으므로 시간복잡도는 $\mathcal{O}\left(N^2\right)$이다. 이 때, 2번 과정은 최대 $N$번 이루어지므로 교환 횟수는 $N$번임을 알 수 있다.

이와 비슷하게, 최솟값이 아니라 $1$이 들어가있는 행을 찾아서 두 행을 바꿔준다는 식으로 진행하자.

즉, $i$번째 행에 대해 $a_{ki}=1$인 $k$를 찾아서 바꾸는 식으로 진행하면 된다. $k\geq i$인 것은 자명하므로 아무리 많아봤자 $d$번을 초과할 수 없다는 것도 쉽게 알 수 있다.

---

Problem 1.8.9

어떤 순열 행렬 $E$을 이용하여 $A$의 모든 열들의 순서를 바꾼 행렬을 $A\,'$라 하자. 이 때, $A^{-1}$을 알고 있다고 가정할 때, 역행렬을 새로 구하지 않고 $A\,'^{-1}$을 구하는 방법을 제시하라.

식으로 표기하면 $AE$=$A\,'$이다.

이때 $E$가 단위행렬로부터 파생된 순열행렬이고, 순열행렬의 역함수는 이전의 숫자를 되찾아간다는 느낌으로 진행한다.

즉슨 2 → 3 → 1 →4 라는 순열행렬이 있으면, 이의 역함수는 3 → 1 → 2 → 4가 된다.

이는 1이라는 숫자가 3번째에 있으므로 3을, 2라는 숫자가 1번째에 있으므로 1을... 이를 반복한다.

순열행렬은 반드시 역함수를 가지므로 양변에 역함수를 취하면 $E^{-1}A^{-1}=A\,'^{-1}$이 된다.

우리는 어떻게 바뀌었는지에 대한 순서를 알고 있으므로 이에 대한 역도 알수 있고, 역함수 행렬의 열을 역순으로 바꿔주기만 하면 $A\,^{-1}$의 역행렬을 구해줄 수 있다.

p.s.) 순열행렬 $E$에 대해 $E^T=E^{-1}$이 성립함을 이용하여 바로 전치행렬로 접근해도 괜찮다.

---

Problem 1.8.10

$n\times d$ 행렬 $D$를 $D\approx UV^T$로 근사 인수분해했다고 가정하자. 여기에서 $U$는 $n\times k $행렬이고 $V$는 $d\times k$ 행렬이다. $UV^T=U\,'V\,'^T$를 만족하는 $D$의 대안적 인수분해 $U\,'V\,'^T$는 무수히 많이 존재함을 보이시오.

핵심은 $U\,'$과 $V\,'$의 다른 꼴을 찾아내라는 것이 아니라, 그냥 무수히 많이 존재함을 보이는 문제라는 것이다. 

따라서 우리는 $U$의 전체 항에 $0$이 아닌 실수 $c$를 나눠주고, $V$에 해당 실수 $c$를 곱해준 행렬들을 각각 $U\,'$, $V\,'$로 하면 무한개로 만들어 낼 수 있다.

---

Problem 1.8.12

순열 행렬의 누승들 중에 항상 단위행렬이 나타나는 이유를 설명하시오. 

Hint. 순열 개수의 유한성 측면에서 생각해보시오.

$\forall\,i\in\mathbb{N}\,:\,A^i\neq I$라 하자.

이 말은 즉슨 $A^i\times A\neq I\times A$가 성립한다는 것인데, 순열행렬의 특성 상 싸이클을 한번 돌고 나면 다시 처음의 순열행렬로 돌아오게 된다.

무슨 말이냐면 4 → 2 → 1 → 3 이렇게 4개의 사이클이 있으면 4번 이후로는 다시 4 → 2 → 1 → 3로 돌아오게 된다라는 것이다.

따라서 부정이 모순이고, 원 명제가 성립한다. (이때 $A^i$가 역행렬을 가지므로 $A^i C=I$를 만족하는 행렬 $C$가 유일하다라는 것은 전제로 깔려있다.)

---

Problem 1.8.13

행렬 다항식 $\displaystyle\sum_{i=0}^t a_iA\,i$를 생각해보자. 이 다항식에 대한 단순 계산에는 $\mathcal{O}\left(t^2 \right )$ 회의 행렬 곱셈이 필요하다. 다항식을 재배열함으로써 곱셈 횟수를 $\mathcal{O}\left(t \right )$로 줄이는 방법을 설명하시오.

일단 왜 $\mathcal{O}\left(t^2\right)$번이 드는지 알아보자.

$0$에서 $t$까지 반복을 돌려야하므로 여기에서 $\mathcal{O}\left(t\right)$가 드는건 확인을 헀고, 이제 $i=k$일 때 마다 $A^k$를 계산해야하므로 $\mathcal{O}\left(t\right)$의 반복을 계산해야한다.

따라서 $\mathcal{O}\left(t^2 \right )$인데, 일단 $0$에서 $t$까지 $\mathcal{O}\left(t \right )$가 필요한 것은 바꿀 수가 없다. 따라서, $A^k$를 반복하는 것을 $\mathcal{O}\left(1 \right )$만에 계산하는 방법을 제시하면 된다.

다항식을 내림차순이 아닌 오름차순으로 정렬하자. 

그 이후, $A^2$은 직전의 $A$항에 $A$를 곱하고, $A^3$은 직전의 $A^2$에 $A$를 곱하고.. 하는 식으로 하면 행렬 곱셈의 횟수는 $1$번으로 총 $\mathcal{O}\left(t \right )$의 계산으로 바뀌게 된다.