Symmetry and Positive Definitive Matrix
Linear Algebra Lec. 25
Positive Definite Matrices and Minima
Linear Algebra Lec. 27
Similar Matrices and Jordan Form Linear Algebra Lec. 28
Symmetric Matrices
정리된 블로그를 공부하자.
Symmetric Matrices
정리 블로그
중요한것만 정리해놓았다.
Spectral theorem
Properties of Symmetric Matrix
- The eigenvalues are Real
- The eigenvectors are Perpendicular
2번은 사실 직교하는 eigenvectors들을 선택할 수 있다는 뜻이다.
Diagonlalization of symmetric matrix
General case
\[A=S \Lambda S^{-1}\]Symmetric case
\[A=Q \Lambda Q^T\]2번 특성을 통해 Symmetric Matrix의 eigenvectors를 perpendicular하도록 선택하면 위와같이 간단한 식으로 분해할 수 있다. perpendicular할 뿐만 아니라 eigenvectors의 scale은 상관없으므로 unit vector로 잡으면 된다.
결국 orthonormal eigenvectors Q로 잡은 것이 위와 같다.
위 식은 매우 중요하다!
이것이 대칭행렬임을 증명하는 방법은 실제로 transpose해보는 것이다.
Spectral theorem
\[A=Q \Lambda Q^T\]위 식은 eigenvalue와 eigenvector를 보여주며, symmetry를 보여준다.
그래서 수학적으로 spectral하다고 한다.
Spectrum은 행렬의 eigenvalue들의 집합이다.
빛을 순수한 요소로 분해하는 것을 스펙트럼이라고 하는 것에서 아이디어를 얻은 것이다.
이러한 것을 보통 메커니즘적으로 principle axis theorem이라고 한다.
기하학적으로 보면 어떤 물질을 올바른 축에서 바라보면 그것이 diagonal하게 된다는 것이다. 방향이 서로 엮이지 않도록.
Why real eigenvalues?
도대체 왜 실수가 나오는것일까?
\[Ax = \lambda x\]람다와 x는 complex할 수 있다. 심지어 A도.
그러나 A가 symmetric하면 람다는 절대 그렇지 않다는 것을 증명할 것이다. 그러나 일단은 A가 실수라는 것을 다루자.
\[Ax= \lambda x \rightarrow \bar{A} \bar{x} = \bar{\lambda} \bar{x}\]어떤 방정식이 있으면 위와같이 모든 것에 대한 conjugate를 얻을 수 있다.(A는 실수라서 conjugate와 동일하다.)
좌변은 실수 행렬은 eigenvalue lambda와 eigenvector x를 가지고, 그것은 eigenvalue 켤레수 lambda와 eigenvector 켤레수 x를 가진다.
이제 symmetry를 사용해보자.
\[A \bar{x} = \bar{\lambda} \bar{x} \rightarrow \bar{x}^T A^T = \bar{x}^T \bar{\lambda}\]A는 symmetric하므로
\[\bar{x}^T A = \bar{x}^T \bar{\lambda}\]이를 이용해서 서로 같다는 것을 증명할 수 있다.
\[Ax = \lambda x\]\(\bar{x}^T\)를 곱한다.
\[\bar{x}^T A x = \lambda \bar{x}^T x\]적당히 식을 만져보면 왜 같은지 알 수 있을 것이다.
\[\lambda \bar{x}^T x = \bar{\lambda} \bar{x}^T x\]결국 이와같은 식이 생긴다.
\[\lambda = \bar{\lambda}\]conjugate한게 원래의 값과 같다는 것은, 실수라는 것이다.
\[\therefore \lambda \text{ is real!}\]벡터 x가 complex하더라도 \(\bar{x}^T x\) 연산은 conjugate한 element끼리의 내적이므로 실수가된다. 그것도 0이 아니라면 항상 양수가 된다.(직접 계산해보면)
\(x^T x\) 는 length squared다.
만약 A가 실수가 아니라면? 강의 23분부터 보면됨.
Good matrices
Real \(\lambda\)’s
Perpendicular x’s
이 두가지 조건만 있으면 Good matrices다.
만약 복소수 행렬이더라도 conjugate symmetric하면? 좋은 행렬이 되는 것이다.
이는 다음과 같이 표현된다.
\[A = \bar{A}^T\]위와 같은 조건을 가진다면, Good matrices다.
대칭행렬의 그 외의 특징들
블로그 참고
투영행렬!
Every symmetric matrix is a combination of perpendicular projection matrices
이것은 spectral theorem을 생각하는 또 다른 방식이자, 사람들이 좋아하는 방식이다.
모든 symmetric matrix가 그런식으로 쪼개질 수 있다는 것이다.
양수 음수
symmetric matrix의 eigenvalues가 실수라면, 그것은 양수일까 음수일까?
미분방정식에 있어서 instability와 stability를 따지기 위해선 이것은 매우 중요한 문제다.
50차수의 고유값을 알아내는건 참 어렵다. 50차 다항식을 풀어야하기 때문이다. 지금까지는 그러라고 배워왔지만, 그건 많아봐야 2차나 3차에 대한 것이었다. 50차는 무리. 그러나 numerical linear algebra의 발달으로 그것이 간단하도록 가능해졌다.
그러나 실제로 값을 구하지 않고도 양수 음수를 알아낼 수 있다.
매틀랩에게 50개의 pivot을 찾아내라고 하면 쉽게 할것이다. 실수 행렬이라면 50개의 pivot의 몇개는 양수이고 몇개는 음수인지를 알아내서 쉽게 알아낼 수 있다. 만약 30개의 pivot이 양수라면, 30개의 eigenvalue도 양수일 것이다. 놀라운 일이다.
물론 symmetric matrix일 때.
# Signs of pviots = # Signs of \(\lambda\)’s
product of the pivots = product of the eigenvalues = determinant
각각의 고유값에 대해 얘기해주진 않는다.
Positive Definite Matrix
Positive definite symmetric matrix
먼저, Positive Definite Matrix는 Symmetric하다.
이건 최고다.
특성을 정리하면,
- all eigenvalues are positive
- all pivots are positive
- all subdeterminants are postive
Symmetric하면서 모든 eigenvalues가 positive한 것을 말한다.
이는 모든 pivot이 positive하다는 것을 의미한다!
이는 미분방정식에서 정말로 얻고싶은 행렬일 것이다.
eigenvalues의 부호를 알기에 stability를 알 수 있게 된다.
이는 determinant도 positive라는 것이다. 그러나 역은 성립하지 않는다. 음수 행렬에서도 determinant가 positive일 수 있기 때문이다.
그래서 모든 sub-determinant도 positive하다는 특성으로 말할 수 있다. sub-determinant는 왼쪽위부터 사각형을 하나씩 넓혀나가면서 그 determinant를 만드는 것이다.
예를 들면 다음과 같다.
\[\begin{bmatrix} 5 & 2 \\ 2 & 3 \end{bmatrix}\]이와같은 행렬에서, 먼저 5만 있는 1 by 1 행렬의 determinant, 그리고 전체 행렬의 2 by 2 determinant 이 모두가 positive라는 것이다.
Positive Definite Matrix Tests for Minimum Ellipsoids in Rn
첫번째 목표는 행렬이 PDM(Positive Definite Matrix)인지를 검증하는 것이다.(Test) 그리고 그 의미가 무엇일까?
그리고 기하학과 연결하여 타원면(Ellipsoid)이 PD(Positive Definite)와 무슨 관계가 있는지 알아볼 것이다. Hyperbola는 PD와 관계가 없다.
그리고 그 응용으로 최소값을 찾아내는 것은 매우 멋지다.
Definition of Positive Definitive
2 by 2 Example
\[\begin{bmatrix} a & b \\ b & c \end{bmatrix}\]앞으로 모든 행렬은 Symmetric하다고 생각하자.
질문은, 이 행렬이 PD냐는거다.
다음 각각은 PD에 대한 완전한 검증(test)이다.
-
\(\lambda_1 \gt 0, \lambda_2 \gt 0\)
Eigenvalue가 모두 양수인가? -
\(a \gt 0, ac-b^2 \gt 0\)
Sub-determinant가 모두 양수인가? -
pivots \(a > 0, \frac{ac-b^2}{a} >0\)
pivot이 모두 양수인가?(다른 pivot은 determinant over a가 나옴) -
\(x^TAx >0\) *
PD의 정의는 이 4번째 항목이다.
Another Example
\[\begin{bmatrix} 2 & 6 \\ 6 & x \end{bmatrix}\]x에 어떤 숫자를 넣어야 PD가될까?
만약 x=19면 PD인가?
sub-determinant가 모두 양수이므로 OK이다.
만약 x=18이면?
아니다.
하지만 determinant가 0이다.
이러한 것을 positive semi-definite라고 한다.
이 행렬의 eigenvalue는 무엇인가?
이 행렬은 singular matrix이고, 하나의 eigenvalue는 0이다.
또 다른 eigenvalue는 trace로부터 보면 20이라는 것을 알 수 있다.
즉, 0보다 크거나 같은 경우이다.
\[\lambda \ge 0\]그러면 pivot은 무엇인가? 2 밖에 없다. pivot test는 그러면 통과하지 못한다.
\(x^TAx\) 테스트를 해보자.
이것이 이제부터 중요한 것이다.
x는 임의의 벡터이고, 아무 것이나 예를 들어보겠다.
\[x^TAx\] \[\begin{bmatrix} x_1 & x_2 \end{bmatrix} \begin{bmatrix} 2 & 6 \\ 6 & 18 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}\]일단 A는 실수행렬이다. 복소수인 경우는 생각하지 말자. 전개해보면,
\[2x_1^2+12x_1x_2+18x_2^2 > 0\]Quadratic Form이 나온다. 더이상 Linear하지도 않다.
모든 \(x_1, x_2\)에 관하여, 이것이 양수일까? 앞에서 실패했듯, 여기서도 실패할 것이다.
이걸 그래프를 통해 알아보자.
Graphs of \(x^TAx\)
\[f(x,y)=\vec{x}^TAx=a\vec{x}^2 + 2bxy + cy^2\]위의 그래프를 그려보자. 아래의 행렬을 기준으로.
Non-positive definite
\[\begin{bmatrix} 2 & 6 \\ 6 & 7 \end{bmatrix}\]determinant를 보면 pivot 하나는 음수라는 것을 알 수 있다.
\[2x^2+12xy+7y^2=0\]확실히 원점을 지난다는 것을 알 수 있다. y=0의 경우 x가 convex 포물선을 그린다. x=0의 경우 y가 convex 포물선을 그 린다.
그러나 언제나 convex하지는 않다. 항상 양수가 아니며, 어느 부분에선 음수일 것이기 때문에 어떤 방향으로는 내려갈 것이다. 즉, 원점이 최소값이 아니다. 원점은 Saddle point가 된다.
사실 eigenvector 방향으로 바라보면 확실해진다
Positive Definite
\[\begin{bmatrix} 2 & 6 \\ 6 & 20 \end{bmatrix}\]실제로 찾지 않고 eigenvalue의 부호를 말할 수 있는가? 물론 2 by 2라면 간단히 찾을 수 있지만, 그러지말고.
\[\lambda_1 \lambda_2 = det(A)\]det(A)=4로 양수이고,
trace=\(\lambda_1 + \lambda_2\)=22이다.
Eigenvalue가 모두 양수라는 뜻이다.
\[2x_1^2+12x_1x_2+20x_2^2 \ge 0\]원점을 제외하고는 전부 양수다! 그리고 최소값을 원점에서 가진다.
\[2x^2+12xy+20y^2\]Convex한 모양을 지닌다.
이를 체크하기 위해선 먼저 1차 도함수가 0이어야 한다. 그러나 그것만으로는 충분하지 않다. 위의 Non positive definite 예제에서도 원점에서는 1차 도함수가 0이다.
그러면 2차도함수가 중요하다.
미적분에서 1차 도함수가 0이고, 2차 도함수가 양수면 그 지점이 최소값이 된다.
행렬에서는 1차 도함수가 0이고, 그 지점의 2차 도함수 행렬이 Positive Definite해야한다. 이것이 Hessian Matrix이다.
Calculus: MIN ~ \(\frac{d^2u}{dx^2}>0\), \(\frac{du}{dx}=0\)
Linear Algebra: MIN \(f(x_1,x_2,...)\) ~ MATRIX OF 2nd DERIVS IS POSITIVE DEFINITE (and stationary point)
1차 미분값이 0인 곡선의 점을 정류점(stationary point)이라고 한다
위의 식을 제곱으로 묶어서 다시 표현하면,
\[f(x,y)=2x^2+12xy+20y^2=2(x+3y)^2+2y^2\]전부 양수라는 것을 알 수 있다. bowl 모양의 그래프가 그려진다.
그리고 만약 bowl을 z 축에 수직하도록 자르면 무슨 곡선이 나오는가? 바로 타원이다.
\[2x^2+12xy+7y^2=0\]이 식의 경우는 z 축에 수직하도록 자르면 hyperbola가 나온다.
그리고 하나 첨가할 말은,
\[2(x+3y)^2+2y^2\]위의 식에서 2, 3, 2 같은 계수들이 어디서 나오는지에 관한거다. 이들은 사실 elimination 과정에서 나온다. 제곱으로 묶는 것은 Gaussian Elimination의 good old method이다.
\[A= \begin{bmatrix} 2 & 6 \\ 6 & 20 \end{bmatrix}\] \[U= \begin{bmatrix} 2 & 6 \\ 0 & 2 \end{bmatrix}\] \[L= \begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix}\]pivot은 2이다.
row2에서 row1을 뺄때 multiplier는? 3이다. 그래서 3이 나온 것이다.
두번째 pivot은 2이다.
이 숫자들은 우연이 아닌것이다. 제곱을 완성하는 것은 elimination이다.
이것이 검증에 의미하는 바는 무엇인가? multiplier는 제곱 안에 들어갈 것이므로 의미가 없다.
그러나 pivot이 중요하다. 전부다 제곱으로 묶이게 되면 이 제곱들은 전부 양수이지만, pivot이 계수로써 작동한다.
그렇기 때문에 pivot이 검증에 포함되는 것이다.
2 by 2 케이스에서 이 연결점을 발견하였지만, 이는 3 by 3, m by m에서도 작동한다.
Hessian Matrix
2차 도함수 행렬이다.
\[\begin{bmatrix} f_{xx} & \\ & f_{yy} \end{bmatrix}\]여기서 순수 이계도함수들이 모두 양수여야 최소값이 된다.
그러나 이건 충분하지 않다.
\[H= \begin{bmatrix} f_{xx} & f_{xy} \\ f_{yx} & f_{yy} \end{bmatrix}\]이 순수 이계도함수들이 충분히 커서 cross derivative들도 이겨낼 수 있을 정도여야한다! 위와 같은 행렬을 Hessian Matrix라고 한다.
검증할 때는 일차도함수가 0이라는 조건에서, 이 Hessian Matrix가 Positive Definite여야 최소값이 나온다.
(곡선이 smooth하면 이는 symmetric matrix가된다)
두 변수가 있을때 어느 지점에서 최소값이 나오는가? 그게 바로 미적이 존재하는 이유이다.
이제 3 by 3이나 m by m에서도 마찬가지다. m by m matrices에서도 elimination은 마찬가지로 할 수 있기 때문이다.
3 by 3 example
\[\begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{bmatrix}\]이 행렬은 PD인가?
Sub-determinant
det=2, 3, 4
모든 sub-determinant가 양수이므로 PD이다.
Pivots
pivots = 2, 3/2, 4/3
Eigenvalues
아마 모두 양수일 것이다.
Eigenvalues = \(2- \sqrt{2}\), \(2\), \(2+ \sqrt{2}\)
곱이 4이고, 합이 6이다. 딱맞다.
\(x^TAx\)
\[x^TAx = 2x_1^2+2x_2^2+2x_3^2-2x_1x_2-2x_2x_3 > 0\]bowl형태의 convex function이다.
이 경우에 4차원의 축에 직교하도록 slice하면 타원면 ellipsoid가 나온다. 이는 풋볼 공과 비슷하게 생겼다.
\[x^TAx = 2x_1^2+2x_2^2+2x_3^2-2x_1x_2-2x_2x_3 = 1\]가운데에 중심이 있고, 3개의 principal direction을 가진다.
이 경우에는 세개의 eigenvalue가 전부 다르므로, major axis, middle axis, minor axis 이렇게 세개의 eigenvector를 갖게 될것이다. 그 길이는 eigenvalue에 의해서 정해진다.
Principal Axis Theorem
위에서 다루던 A를 분해해보자.
\[Q \Lambda Q^T\]여기서 Q는 eigenvector matrix고, 람다는 eigenvalue matrix이다.
eigenvalue가 axes의 길이를 알려주는 것이다.
이를 principal axis theorem이라고 한다.
그렇기 때문에 이 대각화는 eigenvalue 관련하여 가장 중요한 matrix factorizaion이다.
이는 Symmetric matrix에 대한 대각화이고, 역행렬 대신에 transpose를 할 수 있다.