행렬

■ Echelon form of a matrix

https://en.wikipedia.org/wiki/Row_echelon_form

https://www.khanacademy.org/math/linear-algebra/vectors_and_spaces/matrices_elimination/v/matrices-reduced-row-echelon-form-1

http://www.math.odu.edu/~bogacki/cgi-bin/lat.cgi?c=rref   : submit a (augmented) matrix, and it returns reduced row echelon form matrix and the row operations (Gaussian Elimination) needed to get there.

     to    

Echelon form  from an augmented matrix :

- [ 0 0 ... 0  b ] 같은 row (즉, 0 = b 같은 식.  b: non-zero)가 없으니 이 linear system 은 해가 있다 (consistent).  즉, coefficient matrix의 열들의 linear combination으로 [-7, -1, -4] 벡터를 만들 수 있다.  

- 1, -1 위치가 pivot position.  따라서 첫번째, 세번째 변수 x1, x3가 basic variable, x2, x4가 free variable.  Free variable 이 있기에 이 linear system은 해가 다수 있다.

- 만약 x2 = x4 = 0 으로 하면 x3= -2,  x1=3.  따라서 x = [3, 0, -2, 0] 이 위 linear system의 솔루션 중 하나.

■ 행렬 곱하기

Interpretation 1.

The (i,j)th entry of imatrix product AB (A∈R^mxn , B∈R^nxp) is the inner product of the i'th row of A and the j'th column of B.

Interpretation 2.

View matrix-matrix product as a set of matrix-vector products.

즉, AB의 각 column은 A와 해당 B의 column과의 matrix-vector multiplication (linear combination)

Interpretation 3.
View matrix-matrix product as a sum of (outer) products m×1 matrix of A's column and 1×p matrix of B's row.

col₁(A)row₁(B) : 행렬 A의 첫번째 column과 행렬 B의 첫번째 row간의 matrix multiplication. col_i(A)가 m × 1 matrix, row_i(B) ( i=0,… n ) 가 1 × p matrix이므로 col₁(A)row₁(B)의 크기는 m × p.  AB는 이들의 matrix 합이므로 크기 역시 m × p. 

■ Properties of Matrix Operations

A, B, C가 m × n matrix, c, d가 scalar 이면 아래 matrix addition, scalar multiplication이 참

a)  A + B = B + A                 (Commutativity)

b)  A + (B + C) = (A + B) + C      (Associativity of addition)

c)  c(dA) = (cd)A               (Associativity of multiplication)

d)  1A = A                       (Multiplicative identity)

e)  c(A + B) = cA + cB           (Distributivity)

f)  (c + d)A = cA + dA            (Distributivity)

0가 m × n zero matrix 이면 다음이 참

g)  A + 0 = A

h)  A + (-A) = 0

i)  If cA = 0 then c = 0 or A = 0

 

A, B와 C가 서로 행렬 곱하기, 더하기가 가능한 행렬이고, I_m 이 m × m identity matrix 이면 다음이 참.

A(BC) = (AB)C          : associative law

A(B + C) = AB + AC    : left distributive law

(B + C)A = BA + CA    : right distributive law

r(AB) = (rA)B = A(rB)   for any scalar r

I_mA = A = AI_{n               : identity matrix multiplication}

-  AB, BA 가 가능해도 일반적으로 AB ≠ BA  (matrix multiplication is not commutative)

-  AB = AC 라도 B = C 인것은 아니다.  (∴ Cancellation does not hold for matrix multiplication)

-  AB = 0 일때 A = 0 또는 B = 0 인 것은 아니다

* Note that the properties stated above also holds when the m x n matrices are indeed vectors whether they are column vector (m x 1 matrix) or row vector (1 x n) assuming the given additions and multiplications are applicable to given matrices/vectors of correct sizes.  So, the following operation is possible,

Letting,

 

x = c₁v₁ + c₂v₂ + …  + c_nv_n    ( x, v's are column vectors of m x 1 size, and c's are scalars )

 

and if Ax matrix-vector multiplication is possible as when A is p x m matrix,

 

Ax = A( c₁v₁ + c₂v₂ + … + c_nv_n ) = A(c₁v₁) + A(c₂v₂) + … + A(c_nv_n)

 

     = c₁(Av₁) + c₂(Av₂) + … + c_n(Av_n)

 

■ matrix transpose

■ matrix inverse

A  n x n square matrix A is invertible if there is a n x n square matrix C such that

CA = I  and AC = I  ( I : Identity matrix )

We call C is an inverse of A and denote it by A^-1 

So,  A^-1A  = I   and   AA^-1 = I

A square matrix is either invertible or non-invertible.  A square matrix that is not invertible is called a singular matrix, and the invertible is called a nonsingular matrix. If a matrix is invertible, then its inverse is unique.

 

* How do we know a square matrix A is invertible?

1) 앞에서 square matrix A가 invertible 하면 Ax = b로 표현된 linear system에서 b가 무슨 값이든지 unique한 solution x가 존재하고 그 값이 A^-1b 라고 했다. 우린 A^-1 을 모르니 이를 통해 x를 구하진 못하고, 다른 방식으로 Ax=b equation에서 unique한 solution vector x가 있음을 보이면 matrix가 invertible함.

2) A의 determinant가 0이 아님을 보이는 것으로 A의 invertibility 보임 (if det(A) ≠ 0, then A is invertible)

* If a matrix is invertible what is its inverse?

1) AA^-1 = I 을 이용해 구하려는 A^-1이 A와 같은 크기의 square matrix이어야 하니 이를 A와 같은 크기의 x로 놓고 linear system을 푼다. 일반적으로는 Gauss-Jordan Elimination 방법으로 Inverse를 구함 (refer web & books)

2) 

으로 inverse를 구할 수 있음.   ( 참조 )

3) and there are other methods...

Invertible Matrix Theorem - A가 n × n square matrix 이라면 다음은 모두 같은 말

a. A가 invertible


b. The matrix A has n pivot positions   


c. A is row-equivalent( reduced echelon form ) to the Identity matrix I_n

d. 어떤 벡터 b∈Rⁿ 에 대해서도 Ax = b 방정식의 unique solution x∈Rⁿ가 있음

e. Ax = 0 방정식의 solution은 x=0.  즉, 하나의 solution이 있는데 그것이 trivial 한 것임. (만약 Ax = 0 방정식이 non-trivial solution x를
   
    가지려면 A 가 non-invertible(singular) 해야 됨.  이 말은 det(A) = 0 ).  따라서,..

f. A의 column 들이 linearly independent (A의 row들 역시 linearly independent)

g. A 의 column/row 들이 Rⁿ 을 span 


h. The columns/rows of A form a basis of Rⁿ

i. rank A = n  (즉, n x n matrix A는 full rank.  즉, A의 column들이 span 하는 벡터 공간 Rⁿ 의 dimension이 n)  


j. null space (kernel) of A is { 0 }


k. det(A) ≠ 0

l. The linear transformation T(x) = Ax is one-to-one

m. The linear transformation T(x) = Ax is onto

n. A^T is invertible

위 정리들을 연상할 때 A의 inverse 가 있다면 역시 n x n square이며 n 개의 pivot이 있다는 것에서 출발해, 그러면 row-reduction을 계속해 나가면 결국 reduced echelon form에 도달하고 (모든 행렬은 unique한 reduced echelon form을 갖는다), 그러면 n x n Inverse의 reduced echelon form은 Identity matrix I_n 이고, 모든 x_i = b_i 가 된다.    또, 만약 b가 0 이면 모든 x_i=0 이 되며 (즉 x = 0, trivial sol.)  A의 column들이 independent 하다는 말이며...  

■ Square n x n matrix A가 non-invertible 이면 위의 invertible matrix theorem의 내용들이 모두 False.  즉,

  - The matrix A has less than n pivot positions

  - A의 column 들이 linearly dependent

  - det(A) = 0

  - Ax = b 방정식에서 솔루션이 없던가 또는 무수하게 많음 (augmented matrix의 echelon form을 보고 판단할 수 있음. 

    즉 row중에 [0  0  .... b]  같은 것이 있으면 솔루션이 없고,  [0  0  .... b]  같은 것이 없는데 free variable이 있으면 솔루션이 무수히 많음)

  - rank(A) < n 

--- 등

* Ax = 0 방정식이 trivial solution만 있으면, A의 column들은 linearly independent.  따라서 A가 square matrix 이고, A가 invertible 또는 det(A) ≠ 0 을 보이면 A의 column들이 linearly independent ( ∵  A가 invertible 하면 Ax = 0 방정식의 유일한 해 x = A^-1*0  이 있는데 물론 이 때 x = 0 이 된다.  즉 trivial solution만 있기에 A 의 column들은 linearly independent ) 

* A의 column이 linearly dependent하면 A의 null space (Ax=0 homogeneous eq.의 solution) 가 non-trivial.

* n×n square matrix A가 invertible 일 때 대표적인 속성으로;

- A is row-equivalent to the n-by-n identity matrix I_n.   (  ∵  n x n square matrix A 가 n개의 pivot을 가지고 있으니 row reduction을 계속 해 나가면 당연히 identity matrix 형태가 될 것이다)

- A has full rank; that is, rank A = n.

- The columns of A are linearly independent.

* Matrix Inverse 관련 추가 정리/Properties

 

■ Markov Chain 맛보기

가수 Andy를 좋아하는 사람들 중 30%는 한 달 후 가수 Bang으로 갈아타고 70%는 그대로 Andy 팬으로 남는다. 가수 Bing의 팬 중 20%는 한 달 후 Andy로 갈아타고 80%는 그대로 Bang팬으로 남는다.  이 수치는 Andy팬이 몇 명인지, Bing팬이 몇 명인가와 관계없이 일정하다.  이를 그래프로 나타내면,

  

노드 A는 Andy 팬을 나타내고, B는 Bang팬을 나타냄.  A, B를 state. 시간 흐름에 따라 state A, B가 변할 것임. 처음엔 Andy팬이 6백명, Bang팬이 4백명 이었는데, 18개월 뒤에는 어떻게 변할까 등을 알고 싶을 때 이처럼 모델을 만들면 많은 것을 알 수 있음.  프로세스(일단 '시간'이라 함)가 진행됨에 따라 팬들은 A, B 두 state를 왔다 갔다 할 것임.  팬이 한 state에서 다른 state로 옮겨갈 확률이 과거에 자신이 어떤 state를 오고 갔었는지와 관계없고 현재 state만에 좌우될 때 이를 Markov Chain이라 함.  위의 0.7, 0.3과 같이 state 이동 확률을 state transition probability.    

처음에 Andy팬 수가 600, Bang팬 수가 400명이니,

한 달 뒤 Andy팬 수는,     600·0.7  + 400·0.2   

한 달 뒤 Bang팬 수는,     600·0.3  + 400·0.8  

matrix식으로 표현하면,

시작할 때 팬 분포를 x₀, 한달 뒤를 x₁, 두달 뒤를 x₂라 하면 

x₀, x₁, x_k 같이 Markov chain의 state를 나타내는 벡터를 state vector.  x_k = P·x_k-1 에서 state x_k는 state transition matrix P와 바로 전 state x_k-1에 의해 결정됨을 보임 (또는, 바로 뒤의 state를 알고 싶으면 P와 현재 state로 가능).  

State Transition Matrix P의 column index는 현재, row index는 다음 상태를 나타냄. 즉, (2, 1) index 위치의 P_BA 값 0.3은 B → A로가 아니고, A에서 B state로 바뀔 확률을 나타냄. 

P의 각 column 합은 1로서 이를 probability vector라 함.  Markov chain의 transition matrix는 probability vector인 column들로 되어 있고, 이런 square matrix를 stochastic matrix라고도 함.

시간이 계속 흘러 k=100, 즉, 100달 후에 state vector는 어떻게 되었을까?  계속 변화가 있을 것인가?  아니면 어떤 상태에 도달하면 더 이상 변화가 (거의) 없을 것인가?  어떤 state vector x에 이르러 더 이상 프로세스가 진행되어도 변화가 없는 상황을,x = Px 라 나타낼 수 있고, 이 때 state vector x를 steady state vector라 함.  Markov chain은 unique한 steady state vector를 갖고 있음.  위 예 Markov chain의 steady state vector는