Category Archives: 배우기

김영길/ 선형대수학/ Directional preference of covariance matrix for random process

Simulation Solutions

  • H H^{\dagger} = K = E \Lambda E^{\dagger}
    • \Rightarrow I = H^{-1} E \Lambda E^{\dagger} H^{-1 \dagger}
    • U^{\dagger} \triangleq H^{-1}E \Lambda^{1 \over 2} 는 unitary
    • \Rightarrow H = E \Lambda^{1 \over 2} U
  • Simulation Solutions
    • z_{0}(u) = E \Lambda^{1 \over 2} U w(u)
  • orthogonal matrix U 는 항상 diagonal 위에는 모두 0 이 나오는 E \Lambda^{1 over 2}U 를 선택할 수 있다.
    • E \Lambda^{1 \over 2}U 는 causal operator가 된다.

Example 4.1

  • Eigenvector들을 이용한 Covariance matrix의  Causal Factorization
  • random vector y(u) 에 대하여
    • Covariance matrix K_{y} = \left[ \begin{array}{rrr} 1 & -{1 \over 2} & -{1 \over 2} \\ -{1 \over 2} & 1 & -{1 \over 2} \\ -{1 \over 2} & - {1 \over 2} & 1 \end{array} \right]
    • HH^{\dagger} = K_{y} 가 되는 matrix H 를 찾으면
    • y(u) y(u) = Hw(u) 를 통해 simulate 될 수 있다.
  • H 를 구하는 방법
    • (K_{y} - \lambda I)e = 0
    • det(K_{y} - \lambda I) = 0
    • det \left[ \begin{array}{rrr} 1 - \lambda & -{1 \over 2} & -{1 \over 2} \\ -{1 \over 2} & 1 - \lambda & -{1 \over 2} \\ -{1 \over 2} & - {1 \over 2} & 1 - \lambda \end{array} \right] = -{\lambda \over 4} (2 \lambda - 3)^{2} = 0
    • K_{y}e_{1} = 0 \Rightarrow e_{1}^{t} = {1 \over \sqrt{3}}(1, 1, 1)
    • (K_{y} - {3 \over 2} I)e_{2} = 0 \Rightarrow e_{2}^{t} = {1 \over \sqrt{2}}(1, -1, 0)
    • (K_{y} - {3 \over 2} I)e_{3} = 0 \Rightarrow e_{3}^{t} = \sqrt{{2 \over 3}}({1 \over 2}, {1 \over 2}, -1)
    • E \Lambda^{1 \over 2} = \left[ \begin{array}{rrr} 0 & {\sqrt{3} \over 2} & {1 \over 2} \\ 0 & -{\sqrt{3} \over 2} & {1 \over 2} \\ 0 & 0 & -1 \end{array} \right]
    • y(u) = \left[ \begin{array}{rrr} {\sqrt{3} \over 2} & {1 \over 2} \\ -{\sqrt{3} \over 2} & {1 \over 2} \\ 0 & -1 \end{array} \right] w(u)
    • By choosing U = \left[ \begin{array}{rrr} 0 & 0 & 1 \\ {\sqrt{3} \over 2} & -{1 \over 2} & 0 \\ {1 \over 2} & {\sqrt{3} \over 2} & 0 \end{array} \right]
    • E \Lambda^{1 \over 2} U = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ -{1 \over 2} & {\sqrt{3} \over 2} & 0 \\ -{1 \over 2} & -{\sqrt{3} \over 2} & 0 \end{array} \right]
    • z(u) = \left[ \begin{array}{rrr} 1 & 0 \\ -{1 \over 2} & {\sqrt{3} \over 2} \\ -{1 \over 2} & -{\sqrt{3} \over 2} \end{array} \right] w(u)

Brute Force Factorization

  • K = HH^{\dagger}
    • \left[ \begin{array}{rrr} 1 & -{1 \over 2} & -{1 \over 2} \\ -{1 \over 2} & 1 & -{1 \over 2} \\ -{1 \over 2} & - {1 \over 2} & 1 \end{array} \right] = \left[ \begin{array}{rrr} h_{11} & 0 & 0 \\ h_{21} & h_{22} & 0 \\ h_{31} & h_{32} & h_{33} \end{array} \right] \left[ \begin{array}{rrr} h_{11}^{*} & h_{21}^{*} & h_{31}^{*} \\ 0 & h_{22}^{*} & h_{32}^{*} \\ 0 & 0 & h_{33}^{*} \end{array} \right]
    • 1 = |h_{11}|^{2} \Leftarrow h_{11} = i
    • -{1 \over 2} = h_{21} h_{11}^{*} = -h_{21}i \Leftrightarrow h_{21} = - {i \over 2}
    • -{1 \over 2} = h_{31} h_{11}^{*} = -h_{31}i \Leftrightarrow h_{31} = - {i \over 2}
    • 1 = |h_{21}|^{2} + |h_{22}|^{2} = {1 \over 4} + |h_{22}|^{2} \Leftarrow h_{22} = - {\sqrt{3} \over 2}
    • H = \left[ \begin{array}{rrr} i & 0 \\ -{i \over 2} & -{\sqrt{3} \over 2} \\ -{i \over 2} & {\sqrt{3} \over 2} \end{array} \right]
  • K = E \Lambda E^{\dagger}
    • = \left[ \begin{array}{rrrr} \lambda_{1} e_{1} & \lambda_{2} e_{2} & ... & \lambda_{n} e_{n} \end{array} \right] \left[ \begin{array}{rrrr} e_{1}^{\dagger} \\ e_{2}^{\dagger} \\ ... \\ e_{n}^{\dagger} \end{array} \right]  = \sum_{i=1}^{n} \lambda_{i} e_{i} e_{i}^{\dagger}
    • K 의 eigenvalue들은 K 의 spectrum이라 부른다.
  • x = \sum_{j = 1}^{n} a_{j} e_{j}
    • y = Kx = (\sum_{i = 1}^{n} \lambda_{i} e_{i} e_{i}^{\dagger})(\sum_{j = 1}^{n} a_{j} e_{j})
    • e_{i} 의 orthonormaliity를 이용해서
    • y = \sum_{i = 1}^{n} \lambda_{i} a_{i} e_{i}

Random Vectors의 Eigen-Representation

  • simulation problem
    • z(u) = E \Lambda^{1 \over 2} w(u) + m_{z}
    • z(u) = m_{z} + \sum_{j=1}^{n} x_{j}(u) e_{j} = m_{z} + \sum_{j = 1}^{n} \sqrt{\lambda_{j}} w_{j}(u) e_{j}
  • uncorrelated coefficients와 함께 알려진 벡터들의 random 선형 결합 z(u) 의 representation를 Karhuenen-Loeve expansion의 finite-dimensional analog라고 한다.

Average Length Measures for Random Vectors

  • \mathbb{E} \{|z(u)|^{2}\} = \mathbb{E} \{ z^{\dagger}(u) z(u) \} = \sum_{t=1}^{n} R_{z}(t, t) = TR(R_{z})
  • \mathbb{E} \{ |z(u)|^{2} \} = \sum_{i = 1}^{n} \lambda_{i}

Directional Preference

  • 길이가 |b| = 1 인 벡터에 대하여
    • (z_{0}(u), b) b \triangleq b^{\dagger} z_{0}(u) b 의 mean-squared length는 다음과 같다.
    • \mathbb{E} \{ |(z_{0}(u), b) b|^{2} \} = \mathbb{E} \{ |(b^{\dagger} z_{0}(u))|^{2} \} |b|^{2}
      • = \mathbb{E} \{ b^{\dagger} z_{0}(u) z_{0}^{\dagger}(u) b \} = b^{\dagger} K_{z}b
    • z(u) 가 mean-zero real random vector라고 가정하면
      • K_{z} = \left[ \begin{array}{rr} 4 & 2 \\ 2 & 7 \end{array} \right] 
      • \lambda_{1} = 3, e_{1} = {1 \over \sqrt{5}} \left[ \begin{array}{rr} 2 \\ -1 \end{array} \right]
      • \lambda_{2} = 8, e_{2} = {1 \over \sqrt{5}} \left[ \begin{array}{rr} 1 \\ 2 \end{array} \right]
    • z(u) 의 rms length 는
      • \sqrt{\mathbb{E} \{ |z(u)|^{2} \}} = \sqrt{11} \approx 3.32
    • z(u) 의 directional preference 계산은 b K_{z} 의 eigen-vector들을 선택해서 한다.
    • b = e_{1}, \beta_{1} = 1, \beta_{2} = 0
      • \sqrt{\mathbb{E} \{ [e_{1}^{t} z(u)]^{2} \}} = \sqrt{e_{1}^{t} K_{z} e_{1}} = \sqrt{\lambda_{1}} \approx 1.73
    • b = e_{2}, \beta_{1} = 0, \beta_{2} = 1
      • \sqrt{\mathbb{E} \{ [e_{2}^{t} z(u)]^{2} \}} = \sqrt{e_{2}^{t} K_{z} e_{2}} = \sqrt{\lambda_{2}} \approx 2.83
    • b 의 rms projection의 maximum과 minimum이 eigen-vector의 방향을 가리킨다.
    • b K_{z} 의 eigen-vector들로 쓰면 다음과 같다.
      • b = \sum_{i = 1}^{n} \beta_{i} e_{i}
      • \beta_{i} = e_{i}^{\dagger} b
    • b 는 unit vector
    • E 의 eigenvector column들은 orthonormal set
      • 1 = |b|^{2} = |\sum_{i=1}^{n} \beta_{i} e_{i}|^{2} = \sum_{i=1}^{n} \sum_{j = 1}^{n} \beta_{i}^{*} \beta_{j} e_{i}^{\dagger} e_{j} = \sum_{i=1}^{n} |\beta_{i}|^{2}
    • \mathbb{E} \{ |(z_{0}(u), b) b|^{2} \} = b^{\dagger} K_{z} b = \sum_{i=0}^{n} \sum_{j=0}^{n} \beta_{i}^{*} \beta_{j} e_{i}^{\dagger} K_{z} e_{j}
      • = \sum_{i=1}^{n} |\beta_{i}|^{2} \lambda_{i}
    • |\beta_{i}|^{2} 에 대해
      • \min_{i} \lambda_{i} \leq \sum_{i=1}^{n} |\beta_{i}|^{2} \lambda_{i} \leq \max_{i} \lambda_{i}
    • 이런 이유로 projection variance는 K_{z} 의 eigenvalue의 largest와 smallest 사이에 존재한다.

김영길/ 선형대수학/ factorization of covariance matrix for random process

Covariance matrix

  • 어떤 랜덤 vector의 covariance matrix K_{z} 는 다음과 같다.
    • K_{z} = E\{[z(u) - m_{z}] [z(u) - m_{z}]^{\dagger}\}
      • m_{z} 는 평균벡터
      • \dagger 는 conjugate transpose로 켤레전치행렬이 된다. (복소수의 부호를 바꾸고 전치시킨 행렬)
    • = E\{z(u)z^{\dagger}(u) - m_{z}z^{\dagger}(u) - z(u)m_{z}^{\dagger} + m_{z}m_{z}^{\dagger} \}
    • = E\{z(u)z^{\dagger}(u)\} - m_{z}E\{z^{\dagger}(u)\} - E\{z(u)\}m_{z}^{\dagger} + m_{z}m_{z}^{\dagger}
    • = R_{z} - m_{z} m_{z}^{\dagger}

Pseudo-correlation, Pseudo-covariance matrix

  • Pseudo-correlation
    • \tilde{T}_{z} = E \{z(u)z^{t}(u)\}
  • Pseudo-covariance
    • \tilde{K}_{z} = E \{ [z(u) - m_{z}][z(u) - m_{z}]^{t} \}
  • 임의의 벡터 a \in C^{n} 에 대하여
    • a^{\dagger}K_{z}a \geq 0
    • 이러한 성질에 때문에 Covariance matrix K_{z} 는 non-negative definite라고 한다. 이는 correlation matrix R_{z} 도 마찬가지다.
      • (non-negative definite은 positive semi definite(양의 준정부호)이라고도 한다)

Theorem

  • Correlation function은 non-negative definite이다.
  • 증명)
    • w(u) \triangleq \sum_{j=1}^{n} a_{j} z(u, t_{j})
    • \mathbb{E}\{|w(u)|^{2}\} = \mathbb{E} \{ | \sum_{j=1}^{n} a_{j} z(u, t_{j}) |^{2} \}
    • = \sum_{j=1}^{n} \sum_{k=1}^{n} a_{j} \mathbb{E}\{ z(u, t_{j}) z^{*} (u, t_{k})\} a_{k}^{*}
    • = \sum_{j=1}^{n} \sum_{k=1}^{n} a_{j} R_{z}(t_{j}, t_{k}) a_{k}^{*} \geq 0

Linear transformation or random vectors

  • y(u) = \left[ \begin{array}{rrrr} y(u, 1) \\ y(u, 2) \\ ... \\ y(u, n) \end{array} \right]
    • y(u) 는 랜덤 벡터
  • = \left[ \begin{array}{rrrr} h_{11} & h_{12} & ... & h_{1n} \\ h_{21} & h_{22} & ... & h_{2n} \\ ... \\ h_{m1} & h_{m2} & ... & h_{mn} \end{array} \right] \left[ \begin{array}{rrrr} z(u, 1) \\ z(u, 2) \\ ... \\ z(u, n) \end{array} \right] =Hz(u)
    • z(u) 는 랜덤 벡터
    • H 는 선형변환 (행렬)
  • E \{ y(u, t) \} = E \{ \sum_{\tau = 1}^{n} h_{t \tau} z(u, \tau) \}
    • = \sum_{\tau =1}^{n} h_{t \tau} E\{z(u, \tau) \} = \sum_{\tau =1}^{n} h_{t \tau} m_{z}(\tau)
  • E\{y(u, t_{1}) y^{*}(u, t_{2})\}
    • = E \{ [ \sum_{\tau_{1} = 1}^{n} h_{t_{1} \tau_{1}} z(u, \tau_{1}) ] [ \sum_{\tau_{2} = 1}^{n} h_{t_{2} \tau_{2}}^{*} z^{*}(u, \tau_{2}) ] \}
    • = \sum_{\tau_{1} = 1}^{n} \sum_{\tau_{2} = 1}^{n} h_{t_{1} \tau_{1}} h_{t_{2} \tau_{2}}^{*} E[ z(u, \tau_{1}) z^{*}(u, \tau_{2}) ]
  • E\{ y(u, t_{1}) y^{*}(u, t_{2}) \}
    • = \sum_{\tau_{1} = 1}^{n} \sum_{\tau_{2} = 1}^{n} h_{t_{1} \tau_{1}} h_{t_{2} \tau_{2}}^{*} R_{z} (\tau_{1}, \tau_{2})
  • Thus,
    • m_{y} = E\{y(u)\} = E \{Hz(u)\} = HE\{z(u)\} = Hm_{z}
    • R_{y} = E\{y(u) y^{\dagger}(u) \} = E\{Hz(u)(Hz(u))^{\dagger}\}
      • = E\{Hz(u) z^{\dagger}(u) H^{\dagger}\} = HE\{z(u) z^{\dagger}(u)\}H^{\dagger}
      • = HR_{z} H^{\dagger}
    • \tilde{R}_{y} = E \{ Hz(u) z^{t}(u) H^{t} \}
      • HE\{z(u) z^{t}(u)\}H^{t} = H \tilde{R}_{z} H^{t}
  • Centered output vector
    • y_{0}(u) = y(u) - m_{y} = Hz(u) - Hm_{z}
    • = H[z(u) - m_{z}] = Hz_{0}(u)
  • Covariance matrix
    • K_{y} = HK_{z}H^{\dagger}
  • Pseudo-covariance matrix
    • \tilde{K}_{y} = H \tilde{K}_{z} H^{t}

Simulation problem

  • Real white random vector w(u)
    • m_{w} = 0, K_{w} = \sigma^{2} I
  • Complex white random vector w_{c}(u)
    • m_{w_{c}} = 0, K_{w_{c}} = 2 \sigma^{2} I, \tilde{K}_{w_{c}} = 0
  • Simulation block diagram (다이어그램 이미지 생략)
    • z(u) = Hw(u) + c
    • m_{z} = \mathbb{E} \{ Hw(u) + c\} = \mathbb{E} \{ Hw(u) \} + \mathbb{E} \{ c \}
      • = H \mathbb{E} \{ w(u) \} + c = c
    • z_{0}(u) = z(u) - m_{z}
    • z_{0}(u) = Hw(u)
    • K_{z} = R_{z_{0}} = HH^{\dagger}

Covariance Matrix Structure and Factorization

  • Ke = \lambda e, (e \neq 0)
    • \lambda 는 eigenvalue, e 는 eigenvector
  • Hermitian matrix K 의 Eigenvalue \lambda 는 항상 real이 된다.
    • (e^{\dagger} Ke)^{\dagger} = e^{\dagger}Ke = \lambda |e|^{2}
    • e^{\dagger} Ke 는 자기자신의 conjugate와 같다. conjugate 했는데 자기 자신이 된다는 것은 real이라는 뜻
  • non-negative definite matrix K 의 eigenvalue \lambda 는 항상 non-negative하다.
    • 만일 K 가 positive definite 하면 \lambda 는 반드시 positive하다.
  • Hermitian matrix K 의 distinct한 eigenvalue들은 orthogonal하다.
    • \lambda_{1} \neq \lambda_{2}
    • \lambda_{1} e_{1}^{\dagger} e_{2} = (Ke_{1})^{\dagger} e_{2} = e_{1}^{\dagger} K^{\dagger} e_{2}
      • = e_{1}^{\dagger}K e_{2} = \lambda_{2} e_{1}^{\dagger} e_{2}
    • \lambda_{1} \neq \lambda_{2} 이므로 e_{1}^{\dagger} e_{2} = 0
  • 같은 eigenvalue를 갖는 eigenvector들의 집합은 linear space의 subspace가 된다.
    • K(e_{1} + e_{2}) = Ke_{1} + Ke_{2} = \lambda(e_{1} + e_{2})
    • K(a e_{1}) = aKe_{1} = \lambda_{1} (ae_{1})
  • Hermitian matrix들은 항상 대각화 가능하다.

Unitary matrix

  • E^{\dagger}E = I = E E^{\dagger} E 를 unitary matrix라 한다.
    • K = E \Lambda E^{\dagger}
    • diagonal matrix \Lambda 에 루트를 씌우면
      • \Lambda^{1 \over 2} = \left[ \begin{array}{rrr} \lambda_{1}^{1 \over 2} &  & 0 \\ & ... &  \\ 0 &  & \lambda_{n}^{1 \over 2} \end{array} \right]
    • K = E\Lambda^{1 \over 2} \Lambda^{1 \over 2} E^{\dagger} = (E \Lambda^{1 \over 2})(E \Lambda^{1 \over 2})^{\dagger}
  • K 의 다른 factorization도 가능하다.
    • K = (E \Lambda^{1 \over 2} U)(E \Lambda^{1 \over 2} U)^{\dagger}
    • U 는 unitary matrix
  • Simulation Solution
    • z_{0}(u) = E \Lambda^{1 \over 2} U w(u)

 

김영길/ 선형대수학/ orthogonal complement, LU decomposition, least square, correlation matrix

Def

  • inner product space V 의 nonempty subset S 에 대하여, S 의 orthogonal complement(직교 여공간)는 다음과 같이 정의한다.
    • S \bot = \{ x \in V | \langle x, y \rangle = 0, \forall y \in S \}
    • S \bot V 의 벡터 중에 S 의 모든 벡터들과 orthogonal한 것을 모아 놓은 집합
  • Ex 9)
    • V = R^{3}, S = \{ (0, 0, 1) \} 일 때
      • S \bot = xy plane 

Thm 6.7

  • W \subseteq V 일 때
    • dim(V) = dim(W) + dim(W \bot)
  • Ex 11)
    • V = R^{3} 에서
      • W = span(\{(1, 0, 0), (0, 1, 0)\}) = \{(a, b, 0) | a, b \in R\} 이면
      • dim(W) = 2
      • W \bot = \{ (0, 0, c) | c \in R \}
      • dim(W \bot) = 1
  • Ex 12)
    • (Null space of A )\bot = row space of A
      • A 의 널공간은 A 의 모든 row와 수직인 것을 모아 놓은 것이 된다. 
    • (Null space of A^{t} )\bot = column space of A
      • 이것을 Left Null Space라고도 한다.

LU decomposition

  • n \times n 정사각행렬 A 에 대하여
    • 만일 row exchange를 하지 않고 A \to U 를 만들 수 있으면 
    • A = LU
      • L 는 lower triangular matrix
      • U 는 upper triangular matrix
  • (예시 생략)

Least square solution (최소제곱해)

  • overdetermined problems의 least square solution
    • Ax = b 의 꼴에서 x 를 구할 수 없을 때
      • \left[ \begin{array}{rrrr} 1 & 2 \\ 3 & 4 \\ 2 & 0 \\ 4 & 2 \end{array} \right] \left[ \begin{array}{rr} x_{1} \\ x_{2} \end{array} \right] = \left[ \begin{array}{rrrr} 2 \\ 1 \\ 0 \\ 3 \end{array} \right]
      • 위와 같은 경우 해가 없다. (Inconsistent system)
    • 이럴 때는 b 에 최대한 가깝게 x 를 조정한다.
      • \hat{x} = \arg \min_{x} \| Ax - b \|^{2}
    • 이때 b 와 가장 가까워지는 \hat{x} 는 (error vector – b 와의 간격이 error값이 된다) A 의 모든 벡터와 수직인 값이 된다. (거꾸로 말하면 A 의 모든 벡터와 수직이 되는 값을 찾으면 된다.)
      • (b - A \hat{x}) \bot a_{j} (\forall j)

Orthogonality principle

  • 앞서 살펴본 경우의 A 와 수직인 벡터를 찾는 방법
  • a_{j}^{T} (b - A \hat{x}) = 0 (j = 1, 2, ... , n)
    • \left[ \begin{array}{rrrr} - & a_{1}^{T} & - \\ - & a_{2}^{T} & - \\ & ... & \\ - & a_{n}^{T} & - \end{array} \right] \left[ \begin{array}{rrr} | \\ b - A \hat{x} \\ | \end{array} \right] = \left[ \begin{array}{rrrr} 0 \\ 0 \\ ... \\ 0 \end{array} \right]
    • A^{T}(b - A \hat{x}) = 0
    • A^{T} A \hat{x} = A^{T} b
  • A 가 full rank일 때
    • \hat{x} = (A^{T}A)^{-1}A^{T}b
    • A 의 Moore Penrose pseudo-inverse는 (A^{T}A)^{-1}A^{T} 가 된다.
  • A 의 column space로 향하는 B 의 Projection
    • p = A \hat{x} = A(A^{T}A)^{-1}A^{T}b = Pb
  • Projection matrix
    • P = A(A^{T}A)^{-1}A^{T}
    • P^{2} = P
      • P 는 Projection 되었기 때문에 제곱해도 변하지 않는다. 

Ex. Measurements

  • 다음과 같이 점이 주어졌을 때
    • (x_{1}, y_{1}) = (-1, 1)
    • (x_{2}, y_{2}) = (1, 1)
    • (x_{3}, y_{3}) = (2, 3)
  • y = C + Dx 가 되는 line을 찾으려고 한다. (error를 최소화하는 직선을 찾는 문제. 제곱은 결국 거리기 때문에 거리를 최소화한다는 의미에서 최소제곱을 찾는 문제이다)
    • \left[ \begin{array}{rrr} 1 & -1 \\ 1 & 1 \\ 1 & 2 \end{array} \right] \left[ \begin{array}{rr} C \\ D \end{array} \right] = \left[ \begin{array}{rrr} 1 \\ 1 \\ 3 \end{array} \right]
    • A^{T}A = \left[ \begin{array}{rrr} 1 & 1 & 1 \\ -1 & 1 & 2 \end{array} \right] \left[ \begin{array}{rrr} 1 & -1 \\ 1 & 1 \\ 1 & 2 \end{array} \right] = \left[ \begin{array}{rr} 3 & 2 \\ 2 & 6 \end{array} \right]
    • A^{T}b = \left[ \begin{array}{rrr} 1 & 1 & 1 \\ -1 & 1 & 2 \end{array} \right] \left[ \begin{array}{rrr} 1 \\ 1 \\ 3 \end{array} \right] = \left[ \begin{array}{rr} 5 \\ 6 \end{array} \right]
    • A^{T} A \hat{x} = A^{T} b
    • \left[ \begin{array}{rr} 3 & 2 \\ 2 & 6 \end{array} \right] \left[ \begin{array}{rr} C \\ D \end{array} \right] = \left[ \begin{array}{rr} 5 \\ 6 \end{array} \right]
    • C = {9 \over 7}, D = {4 \over 7}
    • \therefore y = {9 \over 7} + {4 \over 7}x

Unitary matrix

  • Unitary matrix란 Rows도 orthonormal이고 Columns도 orthonormal한 matrix를 말한다.
    • AA^{\dagger} = A^{\dagger}A = I
    • det(A) = 1

Matrix in random processes

  • Random vectors의 Second-Moment Descriptions
    • Random vector z = \left[ \begin{array}{rrrr} z(u, 1) \\ z(u, 2) \\ ... \\ z(u, n) \end{array} \right]
  • Mean vector M_{z}
    • M_{z} = \left[ \begin{array}{rrrr} m_{z}(1) \\ m_{z}(2) \\ ... \\ m_{z}(n) \end{array} \right] = \left[ \begin{array}{rrrr} E\{z(u, 1)\} \\ E\{z(u, 2)\} \\ ... \\ E\{z(u, n)\} \end{array} \right] = E\{z(u)\}
  • Correlation matrix R_{z}
    • R_{z} = \left[ \begin{array}{rrrr} R_{z}(1, 1) & R_{z}(1, 2) & ... & R_{z}(1, n) \\ R_{z}(2, 1) & R_{z}(2, 2) & ... & R_{z}(2, n) \\ ... \\ R_{z}(n, 1) & R_{z}(n, 2) & ... & R_{z}(n, n) \end{array} \right]
    • = \left[ \begin{array}{rrrr} E\{z(u,1) z^{*}(u, 1)\} & E\{z(u,1) z^{*}(u, 2)\} & ... & E\{z(u,1) z^{*}(u, n)\} \\ E\{z(u,2) z^{*}(u, 1)\} & E\{z(u,2) z^{*}(u, 2)\} & ... & E\{z(u,2) z^{*}(u, n)\} \\ ... \\ E\{z(u,n) z^{*}(u, 1)\} & E\{z(u,n) z^{*}(u, 2)\} & ... & E\{z(u,n) z^{*}(u, n)\} \end{array} \right]
    • = E \{ \left[ \begin{array}{rrrr} z(u, 1) \\ z(u, 2) \\ ... \\ z(u, n) \end{array} \right] \left[ \begin{array}{rrrr} z^{*}(u, 1) & z^{*}(u, 2) & ... & z^{*}(u, n) \end{array} \right] \}
    • = E\{z(u)z^{\dagger}(u)\}

김영길/ 선형대수학/ inner product space, Gram Schmidt process

Inner product space

(지난 강의 설명 생략)

  • x = (1 + i, 4), y = (2 - 3i, 4 + 5i), x, y \in C^{2} 일 때, x, y 의 inner product는 다음과 같다.
    • \langle x, y \rangle = (1+i)(2+3i) + 4(4-5i) = 15 - 15i
    • (뒤에 곱해주는 벡터는 복소수 앞의 부호가 반전 됨을 주의(켤레). 벡터가 R 에 속할 때는 복소수가 없기 때문에 그냥 곱해줬던 것)
  • Ex 3)
    • V = C([0, 1])
      • ([0, 1] 사이의 연속 함수들의 집합일 때)
      • \langle f, g \rangle = \int_{0}^{1} f(t) g(t) dt

Def. Conjugate transpose

  • A \in M_{m \times n}(F) 일 때  A 의 Conjugate transpose는 A* 라 한다.
  • Conjugate transpose는 책마다 adjoint 라고도 하고 Hermitian이라고도 한다. (다 동일한 개념) 각각 기호는 다음과 같다.
    • A* = A^{H} = A^{\dagger}
  • Conjugate transpose는 대각선 위치에 있는 원소들은 켤레 복소수로 만들고, 그 밖의 원소들은 켤레 복소수로 만들면서 위치를 tranpose 해준다.
    • \left[ \begin{array}{rr} 1 & 1 - 2i \\ 2 - i & 1 + i \end{array} \right] = \left[ \begin{array}{rr} 1 & 2 + i \\ 1 + 2i & 1 - i \end{array} \right]

Def. Norm of x

  • inner product 가 있는 vector space를 inner product space라 한다.
  • Norm은 inner product가 있으면 자동적으로 파생된다.
  • 벡터 x 의 norm은 다음과 같이 정의된다.
    • \|x\| = \sqrt{ \langle x, x \rangle }
      • (자기 자신을 내적한 후에 루트를 씌운 것)
  • Ex 6)
    • x = (a_{1}, a_{2}, ... , a_{n}) \in F^{n} 일 때
      • \|x\| = \sqrt{|a_{1}|^{2} + |a_{2}|^{2} + ... + |a_{n}|^{2}}

Thm 6.2

  • \| c \cdot x \| = |c| \cdot \|x\|
  • \|x\| = 0 인 경우는 x = 0 인 경우 밖에 없다.
    • \|x\| \geq 0

inequality

  • Cauchy-Schwartz inequality
    • | \langle x, y \rangle | \leq \|x\| \cdot \|y\|
    • (두 벡터의 내적의 절대값이 각각의 norm의 곱보다 작다)
  • Triangular inequality (삼각 부등식)
    • \| x + y \| \leq \|x\| + \|y\|
    • (두 변의 길이의 합은 나머지 한 변의 길이 보다 항상 크다)

Def. orthogonal, orthonormal, nomalization

  • x, y 의 내적이 0이면 orthogonal이라고 한다. (일반적으로 두 벡터가 수직이다라고 표현하는 개념)
    • \langle x, y \rangle = 0
  • 벡터들의 집합 S 에 대해, 집합 내 벡터들 간의 내적이 orthogonal 할 때, 집합 S 는 orthogonal 하다고 한다.
  • 벡터 x 의 norm이 1일 때 x 를 unit vector라고 한다.
    • \|x\| = 1
  • 벡터들의 집합 S 에 대해 집합이 orthogonal하고 집합 내 모든 벡터가 unit vector일 때 orthonormal이라고 한다.
    • S = \{ v_{1}, v_{2}, ... , v_{n} \}
    • \langle v_{i}, v_{j} \rangle = \delta_{ij} = \begin{cases} 1 & i = j \\ 0 & i \neq j \end{cases} 
      • (자기 자신과의 내적한 것이 1이고 (=norm), 다른 벡터와 내적은 0)
    • 이때 \delta_{ij} 를 Kronecker delta function이라 한다.
  • 벡터 x 의 normalization이란 방향은 같지만 크기가 1 인 벡터를 의미한다.
    • y = {x \over \|x\|}
    • \|y\| = 1
  • (계산 예제 생략 – 교재 참조)

6.2 Gram-Schmit orthonormalization

  • F^{3} 에서 표준기저 \{ (1, 0, 0), (0, 1, 0), (0, 0, 1) \} 는 orthonormal basis가 된다.
  • \{ ({1 \over \sqrt{5}}, {2 \over \sqrt{5}}), ({2 \over \sqrt{5}}, -{1 \over \sqrt{5}}) \} R^{2} 에서 orthonormal basis가 된다.
  • Ex 3)
    • S = \{ u_{1}, u_{2}, u_{3} \} 가 orthonormal set이고
      • S = \{ {1 \over \sqrt{2}}(1, 1, 0), {1 \over \sqrt{3}}(1, -1, 1), {1 \over \sqrt{6}}(-1, 1, 2) \}
    • y = (2, 1, 3) = span(S) 일때
    • y 를 기저의 선형 결합으로 표현하고자 한다면
      • y = a_{1}u_{1} + a_{2} u_{2} + a_{3} u_{3}
    • 이때의 계수는 어떻게 구할 수 있는가
      • a_{1}, a_{2}, a_{3} = ?
    • projection을 구하면 된다.
      • y = a_{1}u_{1} + a_{2} u_{2} + a_{3} u_{3}
      • y \cdot u_{1} = (a_{1} u_{1} + a_{2} u_{2} + a_{3} u_{3}) \cdot u_{1}
        • 양변에 u_{1} 을 대입하면 u_{1} 끼리 곱하면 1 이 되므로 a_{1} 만 남고 orthonormal이므로 u_{1}, u_{2}, u_{3} 의 내적은 모두 0이 된다. 고로 a_{1} = \langle y, u_{1} \rangle 만 남게 된다.
      • a_{1} = \langle y, u_{1} \rangle = (2, 1, 3) \cdot {1 \over \sqrt{2}} (1, 1, 0) = {1 \over \sqrt{2}}(2 + 1) = {3 \over \sqrt{2}}
      • 같은 식으로 a_{2}, a_{3} 에 대해서도 계산해 주면 된다.

Gram-Schmidt Process

  • inner product space의 선형독립인 부분집합 \{ w_{1}, w_{2} \} 에서 orthonormal하고 span(\{ w_{1}, w_{2} \}) = span(\{ u_{1}, u_{2} \}) 인 부분집합 \{ u_{1}, u_{2} \} 를 찾는 절차 
    1. u_{1} 을 normalize한다
      • u_{1} = {w_{1} \over \|w_{1}\|}
    2. w_{2} 에서 u_{1} 과 평행한 성분을 제거해서 u_{1} 와 수직인 성분만 남겨서 u_{1} 과 orthogonal한 v_{2} 를 구한다.
      • v_{2} = w_{2} - \langle w_{2}, u_{1} \rangle u_{1}
        • \langle w_{2}, u_{1} \rangle u_{1} 을 하면 w_{2} 에서 u_{1} 과 평행한 성분이 나온다.
        • 그 것을 w_{2} 에서 빼주면 결국 w_{2} 에서 u_{1} 과 의 수직인 성분만 남는다.
    3. v_{2} u_{1} 과 수직이지만 길이가 1 이 아니기 때문에 normalize해서 u_{2} 를 만든다.
      • u_{2} = {v_{2} \over \|v_{2}\|}
      • (이런 과정이 성립할 수 있는 이유는 애초에 w_{1}, w_{2} 이 선형독립이었기 때문)
  • 위와 같은 것을 \{ w_{1}, w_{2}, w_{3} \} 에서 찾는 방법 (벡터가 2개일 때와 개념은 동일하다) 
    1. u_{1} = {w_{1} \over \|w_{1}\|}
    2. v_{2} = w_{2} - \langle w_{2}, u_{1} \rangle u_{1}
    3. u_{2} = {v_{2} \over \|v_{2}\|}
    4. v_{3} = w_{3} - \langle w_{3}, u_{1} \rangle u_{1} - \langle w_{3}, u_{2} \rangle u_{2}
    5. u_{3} = {v_{3} \over \|v_{3}\|}
  • 절차
    1. 먼저 벡터 하나를 normalize 해서 orthonormal한 벡터를 만들고,
    2. normalize된 벡터를 이용해서 다음 벡터에서 처음 벡터와 평행한 성분을 제거하고
      • normalize된 벡터와 현재 벡터 사이의 내적에 다시 normalize된 벡터를 곱해서 뺀다
    3. 제거한 벡터를 normalize해서 다음 orthonormal 벡터를 만들고
    4. 모든 벡터에 대해 orthonormal 벡터를 찾을 때까지 2-3 반복
  • (Gram-Schmdit Process 예제 생략 – 교재 참조)

김영길/ 선형대수학/ Eigen decomposition, Cayley-Hamilton theorem, inner product space

(대각화 가능 판별 예제 생략 – 교재 참조)

(행렬의 n승을 구하는 예제 생략 – eigenvalue, eigenvector를 이용해서 대각화하면 계산 된다)

System of differential equations

  • 주어진 연립 미분 방정식이 다음과 같을 때, 해를 구하는 방법
    • x'_{1}(t) = 3x_{1}(t) + x_{2}(t) + x_{3}(t)
    • x'_{2}(t) = 2x_{1}(t) + 4x_{2}(t) + 2x_{3}(t)
    • x'_{3}(t) = -x_{1}(t) - x_{2}(t) + x_{3}(t)
    • x = \left[ \begin{array}{rrr} x_{1}(t) \\ x_{2}(t) \\ x_{3}(t) \end{array} \right]
    • x' = \left[ \begin{array}{rrr} 3 & 1 & 1 \\ 2 & 4 & 2 \\ -1 & -1 & 1 \end{array} \right] x = Ax
    • A = QDQ^{-1}
      • AQ = QD 에서 파생 D 는 Diagonal matrix
    • x' = QDQ^{-1}x
    • Q^{-1}x' = DQ^{-1}x
    • y' = Dy
      • Q^{-1}x = y 로 치환
    • Q = \left[ \begin{array}{rrr} -1 & 0 & -1 \\ 0 & -1 & -2 \\ 1 & 1 & 1 \end{array} \right]
    • D = \left[ \begin{array}{rrr} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 4 \end{array} \right]
    • \left[ \begin{array}{rrr} y'_{1}(t) \\ y'_{2}(t) \\ y'_{3}(t) \end{array} \right] = \left[ \begin{array}{rrr} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 4 \end{array} \right] \left[ \begin{array}{rrr} y_{1}(t) \\ y_{2}(t) \\ y_{3}(t) \end{array} \right] = \left[ \begin{array}{rrr} 2y_{1}(t) \\ 2y_{2}(t) \\ 4y_{3}(t) \end{array} \right]
  • 각 함수는 독립적 (system is decoupled)
    • y_{1}(t) = c_{1} e^{2t}
    • y_{2}(t) = c_{2} e^{2t}
    • y_{3}(t) = c_{3} e^{4t}
    • x = Qy 했던 것을 되돌려준다.
    • \left[ \begin{array}{rrr} x_{1}(t) \\ x_{2}(t) \\ x_{3}(t) \end{array} \right] = \left[ \begin{array}{rrr} -1 & 0 & -1 \\ 0 & -1 & -2 \\ 1 & 1 & 1 \end{array} \right] \left[ \begin{array}{rrr} c_{1}e^{2t} \\ c_{2}e^{2t} \\ c_{3}e^{4t} \end{array} \right]
  • eigenvalue, eigenvector를 이용해서 system을 decoupling 시킨 후에 decoupling된 1차 미분 방정식을 풀고 다시 coupling된 상태로 만들어주면 된다. 이렇게 연립 미분 방정식을 풀 수 있다.

Thm 5.23 Cayley-Hamilton theorem

  • 선형변환 T : V \to V 에 대하여
    • f(t) T 의 특성 방정식이고
    • = det([T]_{\beta} - tI) 일 때
    • f(T) = T_{0}
  • Ex 7)
    • T : R^{2} \to R^{2}
      • (a, b) \mapsto (a + 2b, -2a +b)
    • \beta = \{ (1, 0), (0, 1) \}
    • T(1, 0) = (1, -2)
    • T(0, 1) = (-2, 1)
    • A = [T]_{\beta} = \left[ \begin{array}{rr} 1 & 2 \\ -2 & 1 \end{array} \right]
    • T 의 특성 방정식은
      • f(t) = det([T]_{\beta} - tI) = det \left[ \begin{array}{rr} 1 - t & 2 \\ -2 & 1 - t \end{array} \right] = t^{2} - 2t + 5
    • Cayley-Hamilton 정리에 의해
      • A^{2} - 2A + 5I = 0
  • A = \left[ \begin{array}{rr} a & b \\ c & d \end{array} \right] 에 대해
    • A 의 특성 방정식은
      • det(A - tI) = \left[ \begin{array}{rr} a - t & b \\ c & d - t \end{array} \right]
      • t^{2} - (a + d)t + ad - bc
      • A^{2} - (a + d)A + (ad - bc)I = 0

Inner product space

Inner product and norm

  • Ex 1)
    • x = (a_{1}, a_{2}, ... , a_{n}) \in F^{n}
    • y = (b_{1}, b_{2}, ... , b_{n}) \in F^{n}
    • <x, y> = \sum_{i=1}^{n} a_{i} \bar{b}_{i}
    • z = (c_{1}, c_{2}, ... , c_{n}) \in F^{n}
    • <x + z, y> = \sum_{i=1}^{n}(a_{i} + c_{i})\bar{b}_{i} = \sum_{i=1}^{n} a_{i} \bar{b}_{i} + \sum_{i=1}^{n} c_{i} \bar{b}_{i}
    • = <x, y> + <z, y>

김영길/ 선형대수학/ Eigen decomposition

Corollary

  • n 개의 차원을 가진 선형변환 T : V \to V 에 대하여
    • 만일 T n 개의 distinct eigenvalue를 갖고 있다면, T 는 대각화가능하다.
    • eigenvector를 볼 필요도 없다.
  • Ex 1)
    • A = \left[ \begin{array}{rr} 1 & 1 \\ 1 & 1 \end{array} \right]
    • det(A - tI) = det \left[ \begin{array}{rr} 1 - t & 1 \\ 1 & 1 - t \end{array} \right] = t(t-2)
    • t(t-2) A 의 특성다항식이므로 eigenvalue는 0, 1 이 된다. 
    • A 2 \times 2 행렬이었기 때문에, A 는 대각화 가능하다.

Thm 5.5의 역은 성립하지 않는다.

  • T 가 대각화 가능하다 \nRightarrow n 개의 distinct eigenvalues
  • Ex)
    • A = \left[ \begin{array}{rr} 1 & 0 \\ 0 & 1 \end{array} \right]
    • 이때 A 의 eigenvalue는 1개 뿐이다.
      • Ax = \lambda x
    • 하지만 A 는 항상 대각화가능하다.

Split

  • Split이란 주어진 다항식을 1차 다항식으로 쪼개는 것을 말한다.
  • t^{2} -1 = (t+1)(t-1) 이 되므로 t^{2} - 1 R 에서 split 가능하다.
  • (t^{2}+1)(t-2) R 에서 split 가능하지 않지만 C 에서는 split 가능하다.
    • (t - i)(t+i)(t-2)
  • n 개의 distinct eigenvalue가 있으면 대각화 가능하고 f(t) R 에서 split 가능하다.
    • 하지만 일반적으로 역은 성립하지 않는다.
  • 결국 특성다항식에 중근이 생길 때는 대각화 가능 한지 판단이 어렵다. 즉 중근이 있을 때 대각화가능한지 판별하려면 eigenvector를 모두 구해보는 방법 밖에 없다.

(Ex 2. 생략 – 행렬이 대각화 가능한지 판별하는 문제 – 교재로 대체)

  • 중근이 되는 eigenvalue의 경우에 몇 개의 eigenvector를 구할 수 있는가?
    • Algebraic multiplicity(대수적 중복도) 만큼의 eigenvector만 나오면 대각화 가능

Def

  • 선형변환 T : V \to V 에 대하여
    • \lambda T 의 eigenvalue일 때
    • Eigenspace는 \lambda 에 상응한다.
      • E_{\lambda} = \{ x \in V | T(x) = \lambda x \} = N(T - \lambda I)
      • E_{\lambda} 는 Eigenspace를 의미한다
      • Eigenspace는 T(x) = \lambda x 가 되는 x 를 모아 놓은 집합
      • T - \lambda I 의 널공간이 Eigenspace가 된다.
      • Eigenvector는 결국 Eigenspace의 기저이다.

Thm 5.7

  • 선형변환 T : V \to V 에 대하여
    • \lambda 가 대수적 중복도 m 을 갖는 선형변환 T 의 eigenvalue일 때
      • 1 \leq \dim(E_{\lambda}) \leq m
      • Eigenspace의 차원(=Eigenvector의 개수)은 1 m 사이에 존재한다.
      • 이때 dim(E_{\lambda}) \lambda 의 geometric multiplicity(기하적 중복도)라고 한다
      • geometric multiplicity가 algebraic multiplicity와 같으면 행렬은 대각화 가능하다. geometric multiplicity가 algebraic multiplicity보다 작으면 대각화 불가능

(algebraic multiplicity와 geometric multiplicity를 이용해서 행렬의 대각화 가능 판별 여부 구하는 예제 생략 – 교재 참조)

T 의 대각화가능 조건

  • f(t) F 에서 split 가능해야 하고
  • 모든 \lambda 에 대해 nullity(T - \lambda I) 가 algebraic multiplicity이고 geometric multiplicity 일 때 
  • T 는 대각화 가능하다.

(예제 생략 – 교재 참조)

김영길/ 선형대수학/ diagonalizability, eigenvector

Thm 5.3

  • A \in M_{n \times n} 일 때
    • A 의 특성 다항식은 최고차항의 계수가 (-1)^{n} n 차 다항식이다.
    • A 는 최대 n 개의 서로 다른 eigenvalue를 갖는다.
      • (n 차이기 때문. 아예 없을 수도 있다.)

Thm 5.4

  • V 가 선형변환 T 의 eigenvector이고 \lambda 가 eigenvalue일 때
    • v \neq 0 이고 v \in N(T - \lambda I) 이다.
      • (N(T) 는 널공간)
  • 증명)
    • T(v) = \lambda v = \lambda Iv (v \neq 0)
    • \Leftrightarrow (T - \lambda I)v = 0 (v \neq 0)
    • \Leftrightarrow v \in N (T - \lambda I) (v \neq 0)
  • (eigenvalue를 이용해서 eigenvector를 구하는 예제 생략)
  • Ax = \lambda x 이므로 (A - \lambda I)x = 0 을 이용하여 eigenvector를 구한다.
  • \beta 가 eigenvector의 a basis consisting이라 할 때 \beta Q 의 컬럼으로 쓰면 
    • QD = AQ \Leftrightarrow D = Q^{-1}AQ
    • Ex)
      • Q = \left[ \begin{array}{rr} 1 & 1 \\ 2 & -2 \end{array} \right]
      • D = Q^{-1}AQ = \left[ \begin{array}{rr} 3 & 0 \\ 0 & -1 \end{array} \right] = \left[ \begin{array}{rr} \lambda_{1} & 0 \\ 0 & \lambda_{2} \end{array} \right]

Decoupling by eigen-decomposition

  • D = Q^{-1}AQ = \left[ \begin{array}{rr} 3 & 0 \\ 0 & -1 \end{array} \right] = \left[ \begin{array}{rr} \lambda_{1} & 0 \\ 0 & \lambda_{2} \end{array} \right]
  • \left[ \begin{array}{rr} 3 & 0 \\ 0 & -1 \end{array} \right] \left[ \begin{array}{rr} y_{1} \\ y_{2} \end{array} \right] = \left[ \begin{array}{rr} 3y_{1} \\ -y_{2} \end{array} \right]
  • 1st 컴포넌트의 output은 오로지 1st 컴포넌트의 input에 의해 결정된다.
    • (eigenvalue와 eigenvector를 이용하면 임의의 시스템을 decoupling 할 수 있다는 것)
  • (선형변환에서 eigenvalue가 주어졌을 때, eigenvector 구하는 예제 생략)

Diagonalizability

  • Thm 5.1에서 T 가 diagonalizable (T : V \to V
    • \Leftrightarrow T 의 eigenvector의 ordered basis consisting가 존재한다. 
    • (T 가 대각화 가능하다는 것은 decoupling 가능하다는 것이 된다)
  • Question)
    • eigenvector들을 찾았는데 이것이 basis가 되는가? 즉, dim(V) 개를 찾았는가? 찾은 eigenvector들은 선형독립인가?

Thm 5.5

  • 선형변환 T : V \to V 에 대하여
    • \lambda_{1}, \lambda_{2}, ... , \lambda_{k} T 의 distinct eigenvalue일 때
    • v_{1}, v_{2}, ... , v_{k} T 의 eigenvector이면, \{ v_{1}, v_{2}, ... , v_{k} \} 는 선형독립이다.
      • \lambda_{i} v_{i} 와 correspond (i = 1, 2, ... , k )
  • 증명)
    • k = 1 을 가정하고
    • v_{1} v \neq 0 이고 eigenvector일 때 \{ v_{1} \} 는 선형독립
    • Thm 5.5가 k - 1 개의 distinct eigenvalue에 대해 성립한다고 가정
      • a_{1} v_{1} + a_{2} v_{2} + ... + a_{k} v_{k} = 0 이라고 가정
    • T - \lambda_{k} I 를 양변에 적용
      • a_{1}(T - \lambda_{k} I) v_{1} + a_{2} (T - \lambda_{k} I) v_{2} + ... + a_{k} (T - \lambda_{k} I) v_{k} = 0
      • a_{1}(\lambda_{1} - \lambda_{k}) v_{1} + a_{2} (\lambda_{2} - \lambda_{k}) v_{2} + ... + a_{k} (\lambda_{k} - \lambda_{k}) v_{k} = 0
    • Induction hypothesis에 의해
      • a_{1}(\lambda_{1} - \lambda_{k}) = a_{2} (\lambda_{2} - \lambda_{k}) = ... = a_{k-1} (\lambda_{k-1} - \lambda_{k}) = 0
      • \lambda_{1}, \lambda_{2}, ... , \lambda_{k} 가 distinct이므로
      • a_{1} = a_{2} = ... = a_{k-1} = 0
      • 따라서 a_{k} v_{k} = 0 , v_{k} 는 nonzero vector, a_{k} = 0
      • 그러므로 독립이다.
  • (n 차원 선형변환 T 에서 n 개의 eigenvalue가 존재하고 서로 다르면 그때의 eigenvector끼리는 선형독립이 보장되고 선형변환 T 는 대각화 가능. T 의 eigenvalue가 n 개가 안되면 복잡하다고 함)

 

김영길/ 선형대수학/ diagonalization, eigenvector, characteristic polynomial

Diagonal

  • 행렬 D = [T]_{\beta} 가 Diagonal 하면
    • T(v_{j}) = \lambda_{j} v_{j}
  • 역으로 순서기저 \beta = \{ v_{1}, v_{2}, ... , v_{n} \} T(v_{j}) = \lambda_{j}v_{j} 를 만족시키면
    • [T]_{\beta} = \left[ \begin{array}{rrrr} \lambda_{1} & & & \\ & \lambda_{2} & & \\ & & ... & \\ & & & \lambda_{n} \end{array} \right]

EigenVector, EigenValue

  • 선형변환 T : V \to V 에 대하여 
    • 영이 아닌 벡터 v \in V T(v) = \lambda v 를 만족할 때 
      • \lambda 를 eigenvalue라고 하고 v 를 eigenvector라 한다.
  • 행렬에서는 Av = \lambda v 일 때, v A 의 eigenvector라 한다. (eigenvector of L_{A} )

Thm 5.1

  • 선형변환 T : V \to V 에대하여
    • T 의 eigenvector들로 이루어진 순서기저 \beta 를 만들 수 있으면 T 는 대각화가능이라고 한다.
    • (eigenvector로 V 를 span하고 선형독립)
  • T 가 대각화가능이고, 대각행렬 D D = [T]_{\beta} 일 때 
    • D_{jj} 는 eigenvalue가 된다.
  • (예제1 생략  – 교재 참조)
  • (예제2 생략 – 교재 참조 – 90도 회전하는 선형변환에서는 eigenvector와 eigenvalue가 없다)

Thm 5.2

  • A \in M_{n \times n}(F) 일 때
    • \lambda 가 A의 eigenvalue이면 
      • det(A - \lambda I) = 0
  • 증명)
    • \lambda A 의 eigenvalue이므로
      • \Leftrightarrow Av = \lambda v
      • \Leftrightarrow (A - \lambda I)v = 0
      • \Leftrightarrow (A - \lambda I) 는 not invertible
      • \Leftrightarrow det(A - \lambda I) = 0
  • 정의)
    • A \in M_{n \times n}(F) 일 때
      • f(t) = det(A - t I) 는 A의 characteristic polynomial(특성 다항식)이라 한다.
    • Ex)
      • A = \left[ \begin{array}{rr} 1 & 1 \\ 4 & 1 \end{array} \right]
      • det(A - tI) = det \left[ \begin{array}{rr} 1 - t & 1 \\ 4 & 1 - t \end{array} \right] = t^{2} - 2t - 3
      • = (t-3)(t+1)
      • eigenvalue는 3, -1
      • (eigenvalue는 위와 같이 계산할 수 있기 때문에 구하기 쉽다)

Similar matrices는 항상 같은 특성 다항식을 갖는다 (B = Q^{-1}AQ )

  • 증명)
    • Av = \lambda v
      • v = Qu
      • AQu = \lambda Q u
      • Q^{-1}AQu = \lambda u
      • Bu = \lambda u
    • similar matrices의 경우에 eigenvalue는 같지만, eigenvector는 같지 않다.

정의

  • 선형변환 T : V \to V 에 대하여, \beta 가 순서기저일 때
    • A 의 특성 다항식 T 는 
      • [T]_{\beta} = det(A - tI)
    • 순서기저 \beta 가 무엇이든간에 characteristic polynomial은 변하지 않는다.
  • 선형변환 T 의 eigenvalue \lambda 는 행렬 [T]_{\beta} \lambda 와 같다.
    • (\beta 가 무엇이든 \lambda 는 동일하다)
  • 선형변환 T 의 특성 다항식은 det(T - tI) 라고 쓰기도 한다.
  • (예제 생략 – 교재 참조)

김영길/ 선형대수학/ determinant, Cramer’s rule, diagonalization, eigenvalue

Type 2 operation

  • 행렬 B 가 행렬 A 의 어떤 행에 non-zero인 k 를 곱해준 행렬이라고 할 때
    • det(B) = k \cdot det(A)
    • (Type 2 연산을 한 경우 곱해준 상수만큼 det가 변한다)
  • det(kA) = k^{n} det(A)
    • (행렬에 상수를 곱해준 결과의 determinant는 행렬의 det에 k^{n} 을 곱한 것과 같다. row가 n 개 이기 때문)

Determinant of upper triangular matrix

  • A = \left[ \begin{array}{rrr} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \end{array} \right] 일 때
    • det(A) = 24 이것은 대각 원소들의 곱이면서 pivot들의 곱과 같다.
  • (계산하는 예제 생략 – upper triangular matrix로 변환하면서 type1 연산을 1회 해줬기 때문에 최종 det값에 -를 곱해주는 것에 주의)
  • (cofactor보다 row operation이 determinant를 구하는게 훨씬 쉽다)

4.3 Properties of determinant

  • E = \left[ \begin{array}{rrr} 1 & 0 & 3 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array} \right] 인 경우
    • 단위 행렬의 row exchange matrix이므로 det(E) = -1
    • (Type 1 연산을 하면 det에 -1 이 곱해진다.)
  • E = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{array} \right] 인 경우
    • 단위 행렬에 한 행에 2 를 곱해준 matrix이므로 det(E) = 2
    • (Type 2 연산을 하면 det에 k 가 곱해진다.)
  • E = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right] 인 경우
    • 단위 행렬의 한 행을 곱해서 다른 행에 더해준 matrix이므로 det(E) = 1
    • (Type 3 연산은 det에 변화가 없다.)

Thm 4.7 det(AB) = det(A) det(B)

  • 행렬 A: n \times n 일 때
    • rank(A) = n 이면 (full rank일 때)
    • \Leftrightarrow A : invertible
    • \Leftrightarrow A 는 elementary matrix들의 곱이 된다.
      • (elementary matrixs는 단위행렬에 elementary row operation을 1회 적용해 준 행렬)
    • \Leftrightarrow A 는 nonsingular
      • (nonsingular란 정칙행렬 또는 가역행렬. A 가 정칙행렬이면 AA^{-1} = A^{-1}A = I 가 성립한다.)
    • \Leftrightarrow det(A) \neq 0
    • det(A) det(A^{-1}) = det(I) = 1
    • det(A) = det(A^{t})

Thm 4.9 Cramer’s rule

  • Ax = b 일 때
    • det(A) \neq 0 이면
    • x_{k} = {det(M_{k}) \over det(A)}
    • M_{k} A k -th column을 B 로 치환한 행렬
  • Ex 1) 
    • \left[ \begin{array}{rrr} 1 & 2 & 3 \\ 1 & 0 & 1 \\ 1 & 1 & -1 \end{array} \right] \left[ \begin{array}{rrr} x_{1} \\ x_{2} \\ x_{3} \end{array} \right] = \left[ \begin{array}{rrr} 2 \\ 3 \\ 1 \end{array} \right]
    • x_{1} = {det(M_{1}) \over det(A)} = {\left| \begin{array}{rrr} 2 & 2 & 3 \\ 3 & 0 & 1 \\ 1 & 1 & -1 \end{array} \right| \over det(A)}
    • x_{2} = {det(M_{2}) \over det(A)} = {\left| \begin{array}{rrr} 1 & 2 & 3 \\ 1 & 3 & 1 \\ 1 & 1 & -1 \end{array} \right| \over det(A)}
    • x_{3} = {det(M_{3}) \over det(A)} = {\left| \begin{array}{rrr} 1 & 2 & 2 \\ 1 & 0 & 3 \\ 1 & 1 & 1 \end{array} \right| \over det(A)}
    • (Cramer’s rule은 제약조건도 많고, determinant를 구하는 것도 번거롭고 나눗셈도 해줘야 하기 때문에 유용하지는 않음)

A: 3 \times 3 matrix

  • |det(A)| 의 의미는 평행 6면체의 부피가 된다.
    • a_{1} = (1, -2, 1)
    • a_{2} = (1, 0, -1)
    • a_{3} = (1, 1, 1)
    • \left| det \left[ \begin{array}{rrr} 1 & -2 & 1 \\ 1 & 0 & -1 \\ 1 & 1 & 1 \end{array} \right] \right| = 6

Diagonalization (대각화)

  • Question 1
    • 선형변환 T 가 있을 때 [T]_{\beta} 를 대각행렬로 만드는 순서기저 \beta 를 찾을 수 있는가?
    • (대각행렬이란 정사각행렬에서 주대각선을 제외한 나머지 원소가 모두 0인 행렬)
  • Question 2
    • 그러한 기저를 찾을 수 있다면 어떻게 찾을 수 있는가?
  • (위 조건의 순서기저를 찾을 수 있다면, 그 순서기저를 eigen-basis라 한다)

\beta = \{ v_{1}, v_{2}, ... , v_{n} \}

  • [T]_{\beta} = \left[ \begin{array}{rrrr} \lambda_{1} & & &  \\ & \lambda_{2} & &  \\ & & ... & \\ & & & \lambda_{n} \end{array} \right]
  • T(v_{j}) = 0 v_{1} + 0 v_{2} + ... + \lambda_{j} v_{j} + ... + 0 v_{n} = \lambda_{j} v_{j}
    • (T(v_{j}) = \lambda_{j} v_{j} 가 된다는 것은 input을 넣어도 방향이 바뀌지 않는다는 것.)
    • (이때의 v_{j} 가 eigen-vector가 되고, 이때의 \lambda_{j} 가 eigen-value가 된다. 그리고 이 eigen-vector들을 모은 \beta 는 eigen-basis가 된다.)

5.1 Eigenvalues and Eigenvector

  • T : V \to V 일 때,
    • [T]_{\beta} 가 대각행렬이 되게 하는 순서기저 \beta 가 존재하면 T 가 대각화가 가능하다고 한다.
    • (T(v_{j}) = \lambda_{j} v_{j} 가 되는 non-zero vector v_{j} n 개 만큼 존재해야 한다.)

김영길/ 선형대수학/ system of linear equations, determinant

Thm 3.9

  • K Ax = b (b \neq 0) 의 해 집합일 때
    • K_{H} Ax = 0 의 해 집합이라고 정의
    • K = \{s\} + K_{H} = \{ s + k : k \in K_{H} \}
    • s Ax = b 의 해 중 하나
    • (non-homogeneous 방정식을 푸는 방법은 homogeneous 방정식을 먼저 풀고, non-homogeneous의 particular solution을 더해줌으로써 구한다)
  • Ex 3)
    • \left[ \begin{array}{rrr} 1 & 2 & 1 \\ 1 & -1 & -1 \end{array} \right] \left[ \begin{array}{rrr} x_{1} \\ x_{2} \\ x_{3} \end{array} \right] = \left[ \begin{array}{rr} 7 \\ -4 \end{array} \right] 일 때
    • rank(A) = 2 (반드시 solution이 존재한다)
      • \left[ \begin{array}{rrr} 1 & 2 & 1 \\ 0 & -3 & -2 \end{array} \right] \left[ \begin{array}{rrr} x_{1} \\ x_{2} \\ x_{3} \end{array} \right] = \left[ \begin{array}{rr} 7 \\ -11 \end{array} \right] 
    • homogeneous solution은
      • \left[ \begin{array}{rrr} x_{1} \\ x_{2} \\ x_{3} \end{array} \right] = c \left[ \begin{array}{rrr} {1 \over 3} \\ -{2 \over 3} \\ 1 \end{array} \right]
    • particular solution을 구하기 위해 free variable에 0을 대입한다.
      • x_{3} = 0
      • x_{2} = {11 \over 3}, x_{1} = -{1 \over 3}
    • 결과 (homogeneous에 non-homogeneous 해를 1개 더해준 값)
      • \left[ \begin{array}{rrr} x_{1} \\ x_{2} \\ x_{3} \end{array} \right] = c \left[ \begin{array}{rrr} {1 \over 3} \\ -{2 \over 3} \\ 1 \end{array} \right] + \left[ \begin{array}{rrr} -{1 \over 3} \\ {11 \over 3} \\ 0 \end{array} \right]
    • (homogeneous의 해가 원점을 지나는 직선이라고 할 때, non-homogeneous의 해는 원점을 지나지 않는 직선이라고 할 수 있다)

4.1 Determinants of order 2

  • 행렬 A = \left[ \begin{array}{rr} a & b \\ c & d \end{array} \right] (a, b, c, d \in F) 일 때
    • det(A) = |A| = ad - bc
      • (행렬의 경우 절댓값 기호를 씌우면 det를 의미하고, 집합에 절댓값 기호를 씌우면 집합의 원소의 개수를 의미한다.)
    • det(A + B) \neq det(A) + det(B)
  • 따라서 det : M_{2 \times 2}(R) \to R 는 nonlinear transform이 된다.
    • det(A) \neq 0 \Leftrightarrow A: invertible

Orientation

  • \beta = \{ u, v \} R^{2} 의 순서기저라고 할 때, \beta 의 Orientation은 다음과 같다.
    • O \left[ \begin{array}{rr} u \\ v \end{array} \right] = {det \left[ \begin{array}{rr} u \\ v \end{array} \right] \over \left| det \left[ \begin{array}{rr} u \\ v \end{array} \right] \right|} = \pm 1
    • (orientation은 결국 자기 자신의 절댓값으로 나눈 것이기 때문에 +1 또는 -1 이 나올 수 밖에 없다. 기저이기 때문에 분모는 0 이 아님)
  • Ex)
    • e_{1} = [1 0], e_{2} = [0 1] 일 때
      • det \left[ \begin{array}{rr} e_{1} \\ e_{2} \end{array} \right] = 1
      • O \left[ \begin{array}{rr} e_{1} \\ e_{2} \end{array} \right] = 1
      • O \left[ \begin{array}{rr} e_{1} \\ -e_{2} \end{array} \right] = -1
  • orientation 의미는 결국 right-hand system을 만족하느냐를 따지는 것. orientation이 +1 이면 반시계방향으로 회전하고, -1 이면 시계방향으로 회전한다.
  • 임의의 두 벡터 \{ u, v \} \in R^{2} 는 평행사변형을 만든다.
    • 이때 u, v 를 row로 구성된 행렬의 det의 절댓값은 위 평행사변형의 넓이가 된다.
    • 만일 u, v 가 dependent하면 area는 0 이 된다. (두 벡터의 방향이 같으므로 넓이가 만들어지지 않는다)

Area function (면적 함수)

  • A \left[ \begin{array}{rr} u \\ v \end{array} \right] 는 벡터 u, v 로 만들어 내는 면적이 된다.
    • A \left[ \begin{array}{rr} u \\ v \end{array} \right] = det \left[ \begin{array}{rr} u \\ v \end{array} \right] 또는 A \left[ \begin{array}{rr} u \\ v \end{array} \right] = -det \left[ \begin{array}{rr} u \\ v \end{array} \right]
    • \therefore A \left[ \begin{array}{rr} u \\ v \end{array} \right] = \left| det \left[ \begin{array}{rr} u \\ v \end{array} \right] \right|
    • A \left[ \begin{array}{rr} u \\ v \end{array} \right] = O \left[ \begin{array}{rr} u \\ v \end{array} \right] \cdot det \left[ \begin{array}{rr} u \\ v \end{array} \right]
  • Ex)
    • u = (-1, 5), v = (4, -2) 일 때
      • \left| \left[ \begin{array}{rr} -1 & 5 \\ 4 & -2 \end{array} \right] \right| = 2 - 9 = -7
      • 벡터 u 에서 벡터 v 는 시계방향으로 180도 이하 각도가 되기 때문에 orientation은 -1 이 된다.

Determinants of order n

  • A = \left[ \begin{array}{rrr} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{array} \right] \in M_{3 \times 3}(R)  일 때
    • Submatrix \tilde{A}_{11} \left[ \begin{array}{rr} 5 & 6 \\ 8 & 9 \end{array} \right], \tilde{A}_{13} \left[ \begin{array}{rr} 4 & 5 \\ 7 & 8 \end{array} \right]  
    • Submatrix란 행렬의 원소 A_{ij} 에 대해 i 행과 j 열을 제외한 나머지 원소들의 행렬이 된다.
  • Def. det(A) = \sum_{j=1}^{n} (-1)^{1 + j} A_{1j} det(\tilde{A}_{1j})  
    • 만일 A = A_{11}, det(A) = A_{11}  
    • (위 식의 정의는 그 자체가 recursive이다. 재귀이기 때문에 탈출문이 필요한데, 맨 마지막에 1 \times 1 이 될 때 자기 자신을 return 함으로써 식을 종료한다) 

Cofactor

  • 특별히 C_{ij} = (-1)^{i+j} det(\tilde{A}_{ij}) A_{ij} 의 cofactor라 한다.
  • 행렬 A 의 1행을 따라 cofactor을 expansion하면 다음과 같다.
    • det(A) = A_{11} C_{11} + A_{12} + C_{12} + ... + A_{1n} C_{1n}
    • (n \times n 행렬의 det는 cofactor expansion을 통해 구할 수 있다.)
  • Ex)
    • A = \left[ \begin{array}{rrr} 1 & 3 & -3 \\ -3 & -5 & 2 \\ -4 & 4 & -6 \end{array} \right] 일 때
    • det(A) = 1 (30-8) - 3(18+8) - 3(-12-20)

Corollary

  • A \in M_{n \times n}(F) 에 대하여
    1. A 의 행 (또는 열)이 모두 0이면 det(A) = 0
    2. A 의 2개의 행 (또는 열)이 같다면 det(A) = 0 (full rank가 아니므로)

Thm 4.5

  • 행렬 B 가 행렬 A 의 행을 변환해서 만든 것이라면 (type 1)
    • det(B) = -det(A)

Thm 4.6

  • 행렬의 한 행에 scalar곱을 해서 다른 행에 더해도 (type 3 operation) det는 변하지 않는다.
    • (행렬을 사다리꼴로 만들면 그 행렬의 det는 pivot들의 곱이 된다. cofactor expansion 보다 간편하다)