Solving Equations

선형방정식의 해를 체계적으로 분석하는 방법과 이를 바탕으로 한 vector space, eigenvalue, Newton's method, inverse function과 implicit function의 핵심 개념을 정리합니다.

2.1 Row Reduction

1) Linear System

선형방정식계는 matrix equation으로 표현할 수 있다.

$$A\mathbf{x}=\mathbf{b}.$$

여기서

• $A$: coefficient matrix
• $\mathbf{x}$: vector of unknowns
• $\mathbf{b}$: vector of constants

2) Augmented Matrix

선형방정식계는 augmented matrix로 나타낼 수 있다.

$$[A\mid\mathbf{b}].$$

Meaning: 방정식의 coefficient와 constant를 하나의 matrix로 묶어 계산한다.

3) Row Operations

해를 바꾸지 않는 기본 row operation은 세 가지이다.

1. 한 row에 nonzero scalar를 곱한다.
2. 한 row의 scalar multiple을 다른 row에 더한다.
3. 두 row를 교환한다.

Row operation을 적용해도

$$A\mathbf{x}=\mathbf{b}$$

의 solution set은 변하지 않는다.

4) Echelon Form

책에서 사용하는 Echelon Form은 다음 조건을 만족한다.

1. 각 nonzero row의 첫 nonzero entry는 $1$이다.
2. 아래 row의 pivotal $1$은 위 row의 pivotal $1$보다 오른쪽에 있다.
3. pivotal $1$이 있는 column의 다른 entry는 모두 $0$이다.
4. zero row는 모두 아래에 위치한다.

Meaning: 방정식의 해 구조를 바로 읽을 수 있도록 matrix를 정리한 형태이다.

5) Row Reduction

모든 matrix는 row operations를 통해 echelon form으로 변환할 수 있다.

이 과정을 Row Reduction 또는 Gaussian Elimination이라고 한다.

책에서 중요한 점은 주어진 matrix의 echelon form이 unique하다는 것이다.

---

2.2 Solving Linear Equations

1) Solution Classification

$$[A\mid\mathbf{b}]$$

를 echelon form

$$[\widetilde A\mid\widetilde{\mathbf b}]$$

으로 row reduce한다.

해는 세 가지 경우로 나뉜다.

2) No Solution

$\widetilde{\mathbf b}$ column에 pivotal $1$이 있으면

$$A\mathbf{x}=\mathbf{b}$$

는 solution을 가지지 않는다.

Meaning: 서로 모순되는 equation이 존재한다.

3) Unique Solution

$\widetilde{\mathbf b}$에 pivotal $1$이 없고 $\widetilde A$의 모든 column에 pivotal $1$이 있으면 unique solution을 가진다.

4) Infinitely Many Solutions

$\widetilde{\mathbf b}$에 pivotal $1$이 없고 $\widetilde A$에 nonpivotal column이 있으면 infinitely many solutions을 가진다.

5) Pivotal Variable

Pivotal Variable: echelon form에서 pivotal $1$을 포함하는 column에 대응하는 variable.

6) Nonpivotal Variable

Nonpivotal Variable: pivotal $1$이 없는 column에 대응하는 variable.

Nonpivotal variables의 값을 자유롭게 선택하면 pivotal variables의 값이 결정된다.

Meaning: nonpivotal variable은 free variable이고 pivotal variable은 그것에 의존한다.

7) Invertibility Criterion

Square matrix $A$에 대해

$$A\text{ is invertible} \iff A\text{ row reduces to }I.$$

따라서

$$A\mathbf{x}=\mathbf{b}$$

가 모든 $\mathbf b$에 대해 unique solution을 가지는 것과 $A$가 invertible인 것은 같은 조건이다.

---

2.3 Matrix Inverses and Elementary Matrices

1) Solving with an Inverse

$A$가 invertible이면

$$A\mathbf{x}=\mathbf{b}$$

의 unique solution은

$$\mathbf{x}=A^{-1}\mathbf{b}$$

이다.

2) Computing an Inverse

$A$의 inverse는 augmented matrix

$$[A\mid I]$$

를 row reduce하여 계산할 수 있다.

만약

$$[A\mid I] \longrightarrow [I\mid B]$$

이면

$$B=A^{-1}.$$

반대로 $A$ 부분이 $I$로 row reduce되지 않으면 $A^{-1}$은 존재하지 않는다.

3) Elementary Matrix

Elementary Matrix: identity matrix에 하나의 row operation을 적용하여 얻은 matrix.

Matrix $A$에 elementary matrix $E$를 왼쪽에서 곱하는 것은 $A$에 해당 row operation을 적용하는 것과 같다.

$$EA.$$

Elementary matrix는 항상 invertible하며 그 inverse도 elementary matrix이다.

---

2.4 Linear Combinations, Span, and Linear Independence

1) Linear Combination

vectors

$$\mathbf v_1,\ldots,\mathbf v_k$$

의 Linear Combination은

$$a_1\mathbf v_1+\cdots+a_k\mathbf v_k$$

형태의 vector이다.

2) Linear Independence

vectors $\mathbf v_1,\ldots,\mathbf v_k$가 linearly independent라는 것은

$$a_1\mathbf v_1+\cdots+a_k\mathbf v_k=\mathbf 0$$

의 유일한 solution이

$$a_1=\cdots=a_k=0$$

이라는 뜻이다.

Meaning: 어떤 vector도 나머지 vector들의 linear combination으로 만들어지지 않는다.

Linear independence는 solution의 uniqueness와 연결된다.

3) Span

Span: 주어진 vectors의 모든 linear combinations의 집합.

$$\operatorname{Span} (\mathbf v_1,\ldots,\mathbf v_k) = \left\{ \sum_{i=1}^{k}a_i\mathbf v_i \right\}.$$

Meaning: 주어진 vectors를 이용해 만들 수 있는 모든 vector의 집합이다.

Span은 solution의 existence와 연결된다.

4) Matrix Criterion

$$A= [\mathbf v_1\ \cdots\ \mathbf v_k]$$

라고 하자.

$\mathbf v_1,\ldots,\mathbf v_k$가 linearly independent인 것은 row-reduced $A$의 모든 column에 pivotal $1$이 있는 것과 동치이다.

또한 $\mathbf v_1,\ldots,\mathbf v_k$가 $\mathbb R^n$을 span하는 것은 row-reduced $A$의 모든 row에 pivotal $1$이 있는 것과 동치이다.

5) Basis

Basis: vector space $V$를 span하면서 linearly independent인 ordered set of vectors.

$$\{\mathbf v_1,\ldots,\mathbf v_k\}.$$

Meaning: 공간의 모든 vector를 중복 없이 표현하기 위한 기본 좌표축이다.

basis를 이용하면 모든 $\mathbf v\in V$를 unique하게

$$\mathbf v = a_1\mathbf v_1+\cdots+a_k\mathbf v_k$$

로 표현할 수 있다.

6) Dimension

Dimension: vector space의 basis에 포함된 vector의 개수.

$$\dim V.$$

모든 basis는 동일한 수의 vectors를 가진다.

특히

$$\dim\mathbb R^n=n.$$

7) Orthonormal Basis

Orthonormal Basis: basis vectors가 서로 orthogonal하고 모두 unit length인 basis.

$$\mathbf v_i\cdot\mathbf v_j=0 \qquad (i\neq j)$$ $$|\mathbf v_i|=1.$$

orthonormal basis에서는

$$\mathbf x = \sum_{i=1}^{n} (\mathbf x\cdot\mathbf v_i)\mathbf v_i.$$

8) Orthogonal Matrix

Orthogonal Matrix: columns가 orthonormal basis를 이루는 square matrix.

$$A^TA=AA^T=I.$$

따라서

$$A^{-1}=A^T.$$

Orthogonal matrix는 dot product와 length를 보존한다.

---

2.5 Kernels, Images, and the Dimension Formula

1) Kernel

Linear transformation

$$T:\mathbb R^n\to\mathbb R^m$$

의 Kernel은

$$\ker T = \{ \mathbf x\in\mathbb R^n \mid T(\mathbf x)=\mathbf 0 \}.$$

Meaning: transformation에 의해 zero로 mapping되는 모든 vectors의 집합이다.

2) Image

Image:

$$\operatorname{img}T = \{ T(\mathbf x) \mid \mathbf x\in\mathbb R^n \}.$$

Meaning: transformation이 실제로 만들어 낼 수 있는 모든 output의 집합이다.

Kernel과 image는 각각 domain과 codomain의 vector subspace이다.

3) Kernel and Uniqueness

$$\ker T=\{\mathbf 0\}$$

이면

$$T(\mathbf x)=\mathbf b$$

는 모든 $\mathbf b$에 대해 solution을 최대 하나만 가진다.

즉,

$$\ker T=\{\mathbf 0\} \iff T\text{ is one-to-one}.$$

4) Image and Existence

$$\operatorname{img}T=\mathbb R^m$$

이면 모든 $\mathbf b\in\mathbb R^m$에 대해

$$T(\mathbf x)=\mathbf b$$

의 solution이 존재한다.

즉,

$$\operatorname{img}T=\mathbb R^m \iff T\text{ is onto}.$$

5) Basis for the Image

Matrix $A$의 original pivotal columns은

$$\operatorname{img}A$$

의 basis를 이룬다.

주의할 점은 row-reduced matrix의 columns가 아니라 original matrix의 pivotal columns를 사용한다는 것이다.

6) Dimension Formula

Linear transformation

$$T:\mathbb R^n\to\mathbb R^m$$

에 대해

$$\boxed{ \dim(\ker T) + \dim(\operatorname{img}T) = n }$$

이다.

Meaning: domain의 dimension은 kernel과 image 사이에 나누어진다.

7) Rank

Rank: image의 dimension.

$$\operatorname{rank}T = \dim(\operatorname{img}T).$$

따라서 dimension formula는

$$\dim(\ker T)+\operatorname{rank}T=n$$

으로 쓸 수 있다.

8) Existence from Uniqueness

특히

$$T:\mathbb R^n\to\mathbb R^n$$

인 경우

$$\ker T=\{\mathbf 0\}$$

이면

$$\operatorname{img}T=\mathbb R^n.$$

따라서 square linear system에서는

$$\text{one-to-one} \iff \text{onto} \iff \text{invertible}.$$

---

2.6 Abstract Vector Spaces

1) Vector Space

Vector Space: vectors를 더하고 scalar를 곱할 수 있으며 이러한 operations가 vector space axioms를 만족하는 집합.

대표적인 예:

$$\mathbb R^n$$ $$\operatorname{Mat}(m,n)$$ $$P_k$$

그리고 function spaces도 vector space가 될 수 있다.

Meaning: vector는 반드시 숫자의 column일 필요가 없다.

2) Linear Transformation

Vector spaces $V,W$ 사이의 mapping

$$T:V\to W$$

가 linear transformation이라는 것은

$$T(av+bw) = aT(v)+bT(w)$$

를 만족한다는 뜻이다.

3) Matrix with Respect to Bases

$V$의 basis를

$$\{v_1,\ldots,v_n\}$$

$W$의 basis를

$$\{w_1,\ldots,w_m\}$$

이라고 하자.

각

$$T(v_k)$$

를 $W$의 basis로 표현한 coefficients가 matrix $[T]$의 $k$번째 column이 된다.

Meaning: abstract linear transformation도 basis를 선택하면 matrix로 표현할 수 있다.

4) Change of Basis Matrix

두 bases

$$\{v\}, \qquad \{v'\}$$

사이의 change of basis matrix를

$$P_{v'\to v}$$

라고 하면

$$[\mathbf x]_v = P_{v'\to v} [\mathbf x]_{v'}$$

이다.

Meaning: 같은 vector를 다른 coordinate system으로 변환한다.

5) Change of Basis Formula

Linear transformation $T$의 matrix representation은 basis에 따라 달라진다.

$$[T]_{v',w'} = P_{w'\to w}^{-1} [T]_{v,w} P_{v'\to v}.$$

특히 domain과 codomain이 같은 vector space이고 같은 basis를 바꾸는 경우

$$A' = P^{-1}AP.$$

이 형태는 eigenbasis에서 매우 중요하다.

---

2.7 Eigenvectors and Eigenvalues

1) Eigenvector and Eigenvalue

Linear transformation

$$T:V\to V$$

에 대해 nonzero vector $v$가

$$Tv=\lambda v$$

를 만족하면 $v$를 Eigenvector, $\lambda$를 Eigenvalue라고 한다.

Meaning: transformation을 적용해도 방향은 변하지 않고 크기만 $\lambda$배 되는 vector이다.

2) Eigenspace

Eigenvalue $\lambda$에 대응하는 eigenspace는

$$E_\lambda = \{ v\mid Tv=\lambda v \}.$$

Eigenvalue의 multiplicity는 책에서 이 eigenspace의 dimension으로 정의한다.

3) Eigenbasis

Eigenbasis: 모든 basis vector가 eigenvector인 basis.

Eigenbasis를 사용하면 linear transformation이 매우 단순해진다.

4) Diagonalization

$P$의 columns가 $A$의 eigenbasis이고 corresponding eigenvalues가

$$\lambda_1,\ldots,\lambda_n$$

이면

$$P^{-1}AP = \begin{bmatrix} \lambda_1&0&\cdots&0\\ 0&\lambda_2&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&\lambda_n \end{bmatrix}.$$

따라서

$$A = PDP^{-1}.$$

Meaning: 적절한 basis를 선택하면 transformation이 각 coordinate를 단순히 scaling하는 형태가 된다.

5) Powers of a Matrix

Diagonalization이 가능하면

$$A^k = PD^kP^{-1}.$$

그리고

$$D^k = \begin{bmatrix} \lambda_1^k&0&\cdots&0\\ 0&\lambda_2^k&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&\lambda_n^k \end{bmatrix}.$$

Meaning: matrix의 높은 power를 계산하는 문제가 scalar powers 계산으로 분리된다.

6) Independent Eigenvectors

서로 다른 eigenvalues에 대응하는 eigenvectors는 linearly independent이다.

따라서 $n$-dimensional vector space에서는 서로 다른 eigenvalue가 최대 $n$개 존재한다.

7) Important Limitation

모든 matrix가 eigenbasis를 가지는 것은 아니다.

Meaning: 모든 square matrix가 diagonalizable한 것은 아니다.

---

2.8 Newton's Method

1) Nonlinear Equation

Nonlinear system

$$f(x)=0$$

을 직접 풀기 어려울 때 현재 guess 근처에서 $f$를 linearize한다.

$$f(x) \approx f(a)+Df(a)(x-a).$$

2) Newton's Method

현재 approximation을 $a_n$이라고 하면

$$f(a_n)+Df(a_n)(a_{n+1}-a_n)=0.$$

따라서

$$\boxed{ a_{n+1} = a_n - [Df(a_n)]^{-1}f(a_n) }$$

이다.

Meaning: nonlinear equation을 매 iteration마다 linear equation으로 바꾸어 푼다.

3) Practical Computation

실제 계산에서는

$$[Df(a_n)]^{-1}$$

을 직접 계산하기보다

$$Df(a_n)h_n = -f(a_n)$$

을 row reduction으로 풀고

$$a_{n+1}=a_n+h_n$$

으로 계산한다.

4) Lipschitz Condition

Newton's method의 convergence를 보장하려면 derivative가 너무 빠르게 변하지 않아야 한다.

$$|Df(x)-Df(y)| \leq M|x-y|.$$

여기서 $M$은 Lipschitz ratio이다.

5) Kantorovich's Theorem

Kantorovich's theorem은 적절한 initial guess와 Lipschitz condition 아래에서 Newton sequence가 실제 root로 convergence한다는 것을 보장한다.

책의 sufficient condition 중 핵심 형태는

$$|f(a_0)| \, |Df(a_0)^{-1}|^2 M \leq \frac12.$$

Meaning: initial residual, inverse derivative의 크기, derivative의 변화율이 충분히 작으면 Newton's method의 convergence를 보장할 수 있다.

---

2.9 Superconvergence

1) Newton's Method Convergence

Kantorovich condition에서

$$|f(a_0)| \, |Df(a_0)^{-1}|^2 M < \frac12$$

처럼 strict inequality가 성립하면 Newton's method는 훨씬 빠르게 convergence할 수 있다.

책에서는 이를 Superconvergence라고 부른다.

2) Main Idea

successive increment를

$$x_i=|a_{i+1}-a_i|$$

라고 하면 superconvergence에서는 이 값이 iteration마다 매우 빠르게 감소한다.

Meaning: Newton's method가 root에 충분히 가까워지면 정확한 digits의 수가 매우 빠르게 증가한다.

---

2.10 Inverse and Implicit Function Theorems

1) Local Inverse

Function

$$f:\mathbb R^n\to\mathbb R^n$$

이 global하게 invertible하지 않더라도 특정 point 주변에서는 inverse를 가질 수 있다.

이를 locally invertible이라고 한다.

2) Inverse Function Theorem

$f$가 continuously differentiable이고

$$Df(x_0)$$

가 invertible이면 $f$는 $x_0$ 근처에서 locally invertible하다.

즉, $y_0=f(x_0)$ 근처에 inverse function

$$g=f^{-1}$$

가 존재한다.

Meaning: derivative가 invertible이면 nonlinear function도 충분히 작은 영역에서는 invertible linear transformation처럼 행동한다.

3) Derivative of the Inverse

$$Dg(y) = [Df(g(y))]^{-1}.$$

특히

$$D(f^{-1})(f(x)) = [Df(x)]^{-1}.$$

4) Local vs Global Invertibility

$$Df(x)$$

가 모든 point에서 invertible이라고 해서 $f$가 global하게 invertible한 것은 아니다.

Inverse function theorem은 local theorem이다.

5) Implicit Function

Equation

$$F(x,y)=0$$

이 어떤 variables를 다른 variables의 function으로 결정할 때 이를 implicit function이라고 한다.

예를 들어 locally

$$x=g(y)$$

의 형태로 나타낼 수 있다.

6) Implicit Function Theorem

$$F:\mathbb R^n\to\mathbb R^{n-k}$$

이고

$$F(c)=0$$

이라고 하자.

만약

$$DF(c)$$

가 onto라면 적절한 $n-k$개의 pivotal variables를 나머지 $k$개의 nonpivotal variables의 function으로 locally 표현할 수 있다.

즉,

$$x=g(y).$$

Meaning: nonlinear equation에서도 linear equation의 pivotal / nonpivotal variable 구조가 local하게 유지된다.

7) Derivative of an Implicit Function

variables를

$$F(x,y)=0$$

로 나누고

$$D_xF$$

가 invertible이면

$$\boxed{ Dg = -(D_xF)^{-1}D_yF }$$

이다.

---

Essential Study Checklist

반드시 이해해야 할 내용:

• Linear system

$$A\mathbf{x}=\mathbf{b}$$

• Augmented Matrix

$$[A\mid\mathbf b]$$

• Row Operations
• Echelon Form
• Pivotal / Nonpivotal Variables
• Unique / None / Infinite Solutions
• Matrix Inverse

$$[A\mid I] \to [I\mid A^{-1}]$$

• Linear Combination
• Linear Independence
• Span
• Basis
• Dimension
• Orthonormal Basis
• Orthogonal Matrix

$$A^{-1}=A^T$$

• Kernel

$$\ker T$$

• Image

$$\operatorname{img}T$$

• Rank
• Dimension Formula

$$\boxed{ \dim(\ker T) + \dim(\operatorname{img}T) = \dim(\text{domain}) }$$

• Change of Basis

$$A' = P^{-1}AP$$

• Eigenvector / Eigenvalue

$$Av=\lambda v$$

• Eigenbasis
• Diagonalization

$$A=PDP^{-1}$$

• Newton's Method

$$\boxed{ a_{n+1} = a_n-[Df(a_n)]^{-1}f(a_n) }$$

• Lipschitz Condition
• Kantorovich's Theorem의 의미
• Superconvergence의 의미
• Inverse Function Theorem

$$Df(x_0)\text{ invertible} \Rightarrow f\text{ locally invertible}$$

• Implicit Function Theorem
• Implicit Function Derivative

$$Dg = -(D_xF)^{-1}D_yF$$