Determinant of Square Matrix and Eigenvalue Problem

인공지능 알고리즘을 알아내는 핵심 Process

- 주어진 input과 output에서 어떠한 matrix를 찾아내는가!!

 

SVM

- Eigenvalue, Eigenvector!!

 

Determinant of a square matrix

- The elements aij of the matrix A can be used to compute a number called the determinant of A .

- denoted det(A) or |A|

 

For a starting point, our approach is to define det(A) in terms of determinants of smaller matrices.

- The smallest square matrix one can find is of order 1x1. Let A = (a) then we define det(A) = a.!

 

General Solving Process

- We calculate det(A) using the I-th row of A.(하나의 행 or 열을 선택한다)

- ... 이하 생략// 수식으로 보는 것보다 example로 보자..

 

Example of Determinant of 2x2 matrix

-Take A =  (a b)

                 (c  d)

- Calculating det(A) using first row:

det(A) = (−1)^(1+1) a det( d ) + (−1)^(1+2) b det( c ) = ad − bc

 

Example of Determinant of 3x3 matrix

 

      (a b c)

 det(d e f) = aei + bfg + cdh - bdi - afh - ceg

      (g h i)

 

Trick : a      b        c        a       b 

              ↘    ↘↙   ↘↙      ↙

           d       e      f       d        e

              ↙      ↙↘  ↙↘  ↘ 

           g       h        i       g      h

 

another Trick : c  a  b  c  a 

                        f   d  e  f  d 

                        i   g  h  i   g 

 

Example of Determinant of 4x4 matrix

There is no such secret formula for the determinants of 4x4 or larger square matrices! 

 

It is easy to compute the determinant of an upper triangular matrix

- det(u11 u12 u13 u14 u15

          0   u22 u23 u24 u25

          0    0   u33 u34 u35

          0     0     0   u44 u45

          0     0     0     0   u55)

 

- det(u11 u12 u13 u14 u15

          0   u22 u23 u24 u25

          0     0   u33 u34 u35

          0     0     0   u44 u45

          0     0     0     0   u55)

 

-위의 두가지 방식으로 행 or 열을 선택해서 determinant를 계산하면 easy..!

- det(u11 u12 u13 u14 u15

          0   u22 u23 u24 u25

          0    0   u33 u34 u35     =  u11 u22 u33 u44 u55

          0     0     0   u44 u45

          0     0     0     0   u55)

 

- The determinant of an upper (or lower) triangular matrix is the product of all the diagonal elements of the matrix

 

 

If we perform a legitimate row operation on A to obtain B, there is a simple relation between det(A) and det(B)

 

- Ri <--> Rj (once)

A ------------> B        (-1)det(A) = det(B)

 

- Ri ----> aRi + bRj (once)

A ------------> B        (a)det(A) = det(B)

 

- Example

 

A = (0 2 3 4 5                 |                 All the row operations used are:→

      -1 2 1 1 2                 |                  R2 ↔ R1

      -1 1 2 2 3                 |                  R4 ↔ R3

       0 0 1 1 2                 |                  R4 → R4 - R1

       1 1 1 1 1)                |                  R5 → R5 + R1

                                      |                  R4 → 2R4 + R2

          ↓                          |                  R5 → 2R5 -3R2

                                      |                  R4 → R4 - 5R3

U = (-1 2 1 1 2               |                  R5 → R5 + 5R3

         0 2 3 4 5               |                  R5 → R5 + 3R4

         0 0 1 1 2               | 

         0 0 0 1 -3              |

         0 0 0 0 -8)             |

 

To find the determinant of A:

(-1)(-1)(1)(1)(2)(2)(1)(1)(1)det(A) = det(U) = (-1)(2)(1)(1)(-8)

 

The Big Picture

- If all diagonal elements of U are not zero, then AX=B has a unique solution, A is invertible and det(A) is not zero.

- If U has a zero diagonal element, then det(A)=0, A does not have an inverse and AX=B has either no solution or infinitely many solutions.

 

- If det(A) is not zero then AX=0 has a unique solution given by X=0

- If det(A) is zero then AX=0 has infinitely many solutions.

- If AX=0 has a unique solution X=0 then det(A) is not zero.

- If AX=0 has infinitely many solutions then det(A)=0.

 

We will now look at two related problems: matrix eigen-problem and the diagonalisation of a square matrix

 

These two problems have many applications:

 

Vibration in complicated spring-mass systems

Finding principal strains and stresses

Finding principal axes

Modeling population growth

Queue theory in Financial Engineering

Machine Learning Algorithm (Deep Learning)

 

Eigen value Problem

* The homogeneous system AX=O has infinitely many solution if and only of det(A)=0.

- The matrix eigen-problem may be stated as follows:

Given an N x N matrix A, can we find N x 1 matrix X such that AX =  λX, where λ is a real or complex number?

----> Mapping이라고 생각하자, A라는 복잡계의 Matrix를 간단한 vector X를 가지고 상수곱으로만 표현을 할 수 있는가?

- eigen(독어) : 1, 유일한, 특이한, 어떤 현상을 1같이 단순하게 표현할 수 있는..

-  λ : eigen value

- X : eigen vector

 

Obviously X = 0 satisfies AX = λX for any λ ! But we are more interested in finding X ≠ 0!!

 

AX = λX = λ I(Identity) X

(λ I(Identity) <--- NxN identity matrix)

----> AX - λIX = 0

----> (A - λI)X = 0 : Regard this as a homogeneous system of linear algebraic equations

 

For more than just the trivial solution X=0, it is required that

: "det(A-λI) = 0"

---> X=0이외의 다른 Vector를 찾을 수 있다! --> Eigen Vector!

 

We can find non-trivial X such that AX = λX only for λ which satisfies det(A − λI) = 0

To solve the eigen-matrix problem, we find λ first from:

det(A − λI) = 0 ----> characteristic (polynomial) equation of A

 

What is lambda?

Values of λ satisfying the characteristic equation are called eigenvalues of A

 

If A is an NxN matrix, the characteristic equation is a polynomial equation of order N.

The matrix A can then have up to N distinct eigenvalues!

 

If λ is known then we may solve the homogeneous system (A−λI) X = 0

to find non-trivial X for the eigen-problem.

 

We refer to all the solutions X of the above homogeneous system as eigenvectors of A corresponding to the eigenvalue λ 

 

Eigenvalue를 먼저 구해야 Eigenvector를 구할 수 있다!