Machine-Learning-basics/Linear Algebra, Matrix Calculus.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 왜 선형대수를 알아야 하는가?\n",
    "\n",
    "Deep learning을 이해하기 위해서 반드시 선형대수 + 행렬미분 + 확률의 탄탄한 기초가 필요하다.\n",
    "\n",
    "예) Transformer의 attention matrix:\n",
    "\n",
    "$$\\mathrm{Att}_{\\leftrightarrow}(Q, K, V) = D^{-1}AV, ~A = \\exp(QK^T/\\sqrt{d}), ~D = \\mathrm{diag}(A1_L)$$\n",
    "\n",
    "이렇게 핵심 아이디어가 행렬에 관한 식으로 표현되는 경우가 많다.\n",
    "\n",
    "#### 목표: 선형대수와 행렬미분의 기초를 배우고 간단한 머신러닝 알고리즘(PCA)을 유도해보고자 한다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 기본 표기법 (Basic Notation)\n",
    "\n",
    "- $A\\in \\mathbb{R}^{m\\times n}$는 $m$개의 행과 $n$개의 열을 가진 행렬을 의미한다.\n",
    "- $x \\in \\mathbb{R}^n$는 $n$개의 원소를 가진 벡터를 의미한다. $n$차원 벡터는 $n$개의 행과 1개의 열을 가진 행렬로 생각할 수도 있다. 이것을 열벡터(column vector)로 부르기도 한다. 만약, 명시적으로 행벡터(row vector)를 표현하고자 한다면, $x^T$($T$는 transpose를 의미)로 쓴다.\n",
    "- 벡터 $x$의 $i$번째 원소는 $x_i$로 표시한다.\n",
    "\\begin{align*}\n",
    "x = \\begin{bmatrix}\n",
    "    x_1\\\\\n",
    "    x_2\\\\\n",
    "    \\vdots\\\\\n",
    "    x_n\n",
    "\\end{bmatrix}\n",
    "\\end{align*}\n",
    "- $a_{ij}$(또는 $A_{ij}, A_{i,j}$)는 행렬 $A$의 $i$번째 행, $j$번째 열에 있는 원소를 표시한다.\n",
    "\\begin{align*}\n",
    "A = \\begin{bmatrix}\n",
    "    a_{11} & a_{12} & \\cdots & a_{1n}\\\\\n",
    "    a_{21} & a_{22} & \\cdots & a_{2n}\\\\\n",
    "    \\vdots & \\vdots & \\ddots & \\vdots\\\\\n",
    "    a_{m1} & a_{m2} & \\cdots & a_{mn}\n",
    "\\end{bmatrix}\n",
    "\\end{align*}\n",
    "- $A$의 $j$번째 열을 $a_j$ 혹은 $A_{:,j}$로 표시한다.\n",
    "\\begin{align*}\n",
    "A = \\begin{bmatrix}\n",
    "    \\vert & \\vert & & \\vert\\\\\n",
    "    a_1 & a_2 & \\cdots & a_n\\\\\n",
    "    \\vert & \\vert & & \\vert\n",
    "\\end{bmatrix}\n",
    "\\end{align*}\n",
    "- $A$의 $i$번째 행을 $a_i^T$ 혹은 $A_{i,:}$로 표시한다.\n",
    "\\begin{align*}\n",
    "A = \\begin{bmatrix}\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_1^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_2^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     & \\vdots &\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_m^T & \\rule[.5ex]{1.7ex}{0.5pt}\n",
    "\\end{bmatrix}\n",
    "\\end{align*}\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python에서의 벡터, 행렬 표현방법"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10.5, 5.2, 3.25, 7.0]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[10.5, 5.2, 3.25, 7.0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "x = np.array([10.5, 5.2, 3.25])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3,)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.25"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i = 2\n",
    "x[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[10.5 ],\n",
       "       [ 5.2 ],\n",
       "       [ 3.25]])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.expand_dims(x, axis=1)#.shape # 차원 추가해서 2-d arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[10, 20, 30],\n",
       "       [40, 50, 60]])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = np.array([\n",
    "    [10,20,30],\n",
    "    [40,50,60]\n",
    "])\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 3)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "30"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i = 0\n",
    "j = 2\n",
    "A[i, j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([20, 50])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# column vector\n",
    "j = 1\n",
    "A[:, j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([40, 50, 60])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# row vector\n",
    "i = 1\n",
    "A[i, :]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 행렬의 곱셉 (Matrix Multiplication)\n",
    "\n",
    "두 개의 행렬 $A\\in \\mathbb{R}^{m\\times n}$, $B\\in \\mathbb{R}^{n\\times p}$의 곱 $C = AB \\in \\mathbb{R}^{m\\times p}$는 다음과 같이 정의된다.\n",
    "\n",
    "$$C_{ij} = \\sum_{k=1}^n A_{ik}B_{kj}$$\n",
    "\n",
    "행렬의 곱셈을 이해하는 몇 가지 방식들\n",
    "- 벡터 $\\times$ 벡터\n",
    "- 행렬 $\\times$ 벡터\n",
    "- 행렬 $\\times$ 행렬"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 벡터 $\\times$ 벡터 (Vector-Vector Products)\n",
    "\n",
    "두 개의 벡터 $x, y\\in \\mathbb{R}^n$이 주어졌을 때 내적(inner product 또는 dot product) $x^Ty$는 다음과 같이 정의된다.\n",
    "\n",
    "\\begin{align*}\n",
    "x^Ty \\in \\mathbb{R} = [\\mbox{ }x_1\\mbox{ }x_2\\mbox{ }\\cdots \\mbox{ }x_n\\mbox{ }] \\begin{bmatrix}\n",
    "    y_1\\\\\n",
    "    y_2\\\\\n",
    "    \\vdots\\\\\n",
    "    y_n\n",
    "\\end{bmatrix}\n",
    "= \\sum_{i=1}^n x_i y_i\n",
    "\\end{align*}\n",
    "\n",
    "$$x^Ty = y^Tx$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "x = np.array([1, 2, 3])\n",
    "y = np.array([4, 5, 6])\n",
    "x.dot(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y.dot(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "두 개의 벡터 $x\\in \\mathbb{R}^m, y\\in \\mathbb{R}^n$이 주어졌을 때 외적(outer product) $xy^T\\in \\mathbb{R}^{m\\times n}$는 다음과 같이 정의된다.\n",
    "\n",
    "\\begin{align*}\n",
    "xy^T \\in \\mathbb{R}^{m\\times n} = \\begin{bmatrix}\n",
    "    x_1\\\\\n",
    "    x_2\\\\\n",
    "    \\vdots\\\\\n",
    "    x_m\n",
    "\\end{bmatrix}\n",
    "[\\mbox{ }y_1\\mbox{ }y_2\\mbox{ }\\cdots \\mbox{ }y_n\\mbox{ }]\n",
    "= \\begin{bmatrix}\n",
    "    x_1y_1 & x_1y_2 & \\cdots & x_1y_n\\\\\n",
    "    x_2y_1 & x_2y_2 & \\cdots & x_2y_n\\\\\n",
    "    \\vdots & \\vdots & \\ddots & \\vdots\\\\\n",
    "    x_my_1 & x_my_2 & \\cdots & x_my_n\n",
    "\\end{bmatrix}\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = np.array([1, 2, 3])\n",
    "y = np.array([4, 5, 6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((3, 1, 1), (1, 3))"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = np.expand_dims(x, axis=1) # 2d-arr (행렬)로\n",
    "y = np.expand_dims(y, axis=0)\n",
    "x.shape, y.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[[ 4,  5,  6]],\n",
       "\n",
       "       [[ 8, 10, 12]],\n",
       "\n",
       "       [[12, 15, 18]]])"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.matmul(x,y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "외적이 유용한 경우. 아래 행렬 $A$는 모든 열들이 동일한 벡터 $x$를 가지고 있다. 외적을 이용하면 간편하게 $x\\mathbf{1}^T$로 나타낼 수 있다 ($\\mathbf{1}\\in \\mathbb{R}^n$는 모든 원소가 1인 $n$차원 벡터).\n",
    "\n",
    "\\begin{align*}\n",
    "A = \\begin{bmatrix}\n",
    "    \\vert & \\vert & & \\vert\\\\\n",
    "    x & x & \\cdots & x\\\\\n",
    "    \\vert & \\vert & & \\vert\n",
    "\\end{bmatrix}\n",
    "= \\begin{bmatrix}\n",
    "    x_1 & x_1 & \\cdots & x_1\\\\\n",
    "    x_2 & x_2 & \\cdots & x_2\\\\\n",
    "    \\vdots & \\vdots & \\ddots & \\vdots\\\\\n",
    "    x_m & x_m & \\cdots & x_m\n",
    "\\end{bmatrix}\n",
    "= \\begin{bmatrix}\n",
    "    x_1\\\\\n",
    "    x_2\\\\\n",
    "    \\vdots\\\\\n",
    "    x_m\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "    1 & 1 & \\cdots & 1\n",
    "\\end{bmatrix}\n",
    "= x\\mathbf{1}^T\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "# column vector\n",
    "x = np.expand_dims(np.array([1, 2, 3]), axis=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1., 1., 1., 1.]])"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ones = np.ones([1,4])\n",
    "ones"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1., 1., 1., 1.],\n",
       "       [2., 2., 2., 2.],\n",
       "       [3., 3., 3., 3.]])"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = np.matmul(x, ones)\n",
    "A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 행렬 $\\times$ 벡터 (Matrix-Vector Products)\n",
    "\n",
    "행렬 $A\\in \\mathbb{R}^{m\\times n}$와 벡터 $x\\in \\mathbb{R}^n$의 곱은 벡터 $y = Ax \\in \\mathbb{R}^m$이다. 이 곱을 몇 가지 측면에서 바라볼 수 있다.\n",
    "\n",
    "#### 열벡터를 오른쪽에 곱하고($Ax$), $A$가 행의 형태로 표현되었을 때\n",
    "\n",
    "\\begin{align*}\n",
    "y = Ax = \n",
    "\\begin{bmatrix}\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_1^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_2^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     & \\vdots &\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_m^T & \\rule[.5ex]{1.7ex}{0.5pt}\n",
    "\\end{bmatrix} x\n",
    "= \\begin{bmatrix}\n",
    "a_1^Tx\\\\\n",
    "a_2^Tx\\\\\n",
    "\\vdots\\\\\n",
    "a_m^Tx\n",
    "\\end{bmatrix}\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1, 2, 3],\n",
       "       [4, 5, 6]])"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = np.array([\n",
    "    [1,2,3],\n",
    "    [4,5,6]\n",
    "])\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1.],\n",
       "       [1.],\n",
       "       [1.]])"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ones = np.ones([3,1])\n",
    "ones"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 6.],\n",
       "       [15.]])"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.matmul(A, ones)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 열벡터를 오른쪽에 곱하고($Ax$), $A$가 열의 형태로 표현되었을 때\n",
    "\n",
    "\\begin{align*}\n",
    "y = Ax = \n",
    "\\begin{bmatrix}\n",
    "    \\vert & \\vert & & \\vert\\\\\n",
    "    a_1 & a_2 & \\cdots & a_n\\\\\n",
    "    \\vert & \\vert & & \\vert\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "x_1\\\\\n",
    "x_2\\\\\n",
    "\\vdots\\\\\n",
    "x_n\n",
    "\\end{bmatrix}\n",
    "= \\begin{bmatrix}\n",
    "\\vert\\\\\n",
    "a_1\\\\\n",
    "\\vert\n",
    "\\end{bmatrix} x_1 +\n",
    "\\begin{bmatrix}\n",
    "\\vert\\\\\n",
    "a_2\\\\\n",
    "\\vert\n",
    "\\end{bmatrix} x_2 + \\cdots +\n",
    "\\begin{bmatrix}\n",
    "\\vert\\\\\n",
    "a_n\\\\\n",
    "\\vert\n",
    "\\end{bmatrix} x_n\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[4],\n",
       "       [5]])"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = np.array([\n",
    "    [1,0,1],\n",
    "    [0,1,1]\n",
    "])\n",
    "x = np.array([\n",
    "    [1],\n",
    "    [2],\n",
    "    [3]\n",
    "])\n",
    "np.matmul(A, x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a_0: [1 0] \tx_0: [1] \ta_0*x_0: [1 0]\n",
      "a_1: [0 1] \tx_1: [2] \ta_1*x_1: [0 2]\n",
      "a_2: [1 1] \tx_2: [3] \ta_2*x_2: [3 3]\n"
     ]
    }
   ],
   "source": [
    "for i in range(A.shape[1]):\n",
    "    print('a_'+str(i)+':', A[:,i], '\\tx_'+str(i)+':', x[i], '\\ta_'+str(i)+'*x_'+str(i)+':', A[:,i]*x[i])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 행벡터를 왼쪽에 곱하고($x^TA$), $A$가 열의 형태로 표현되었을 때\n",
    "\n",
    "$A\\in \\mathbb{R}^{m\\times n}$, $x\\in \\mathbb{R}^m$, $y\\in \\mathbb{R}^n$일 때, $y^T = x^TA$\n",
    "\n",
    "\\begin{align*}\n",
    "y^T = x^TA = x^T\n",
    "\\begin{bmatrix}\n",
    "    \\vert & \\vert & & \\vert\\\\\n",
    "    a_1 & a_2 & \\cdots & a_n\\\\\n",
    "    \\vert & \\vert & & \\vert\n",
    "\\end{bmatrix}\n",
    "= \\begin{bmatrix}\n",
    "x^Ta_1 & x^Ta_2 & \\cdots & x^Ta_n\n",
    "\\end{bmatrix}\n",
    "\\end{align*}\n",
    "\n",
    "#### 행벡터를 왼쪽에 곱하고($x^TA$), $A$가 행의 형태로 표현되었을 때\n",
    "\n",
    "\\begin{align*}\n",
    "y^T =& x^TA\\\\\n",
    "    =& \\begin{bmatrix}\n",
    "    x_1 & x_2 & \\cdots & x_m\n",
    "    \\end{bmatrix}\n",
    "    \\begin{bmatrix}\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_1^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_2^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     & \\vdots &\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_m^T & \\rule[.5ex]{1.7ex}{0.5pt}\n",
    "    \\end{bmatrix}\\\\\n",
    "    =& x_1 \\begin{bmatrix}\n",
    "        \\rule[.5ex]{1.7ex}{0.5pt} & a_1^T & \\rule[.5ex]{1.7ex}{0.5pt}\n",
    "    \\end{bmatrix} + x_2 \\begin{bmatrix}\n",
    "        \\rule[.5ex]{1.7ex}{0.5pt} & a_2^T & \\rule[.5ex]{1.7ex}{0.5pt}\n",
    "    \\end{bmatrix} + \\cdots + x_n \\begin{bmatrix}\n",
    "        \\rule[.5ex]{1.7ex}{0.5pt} & a_n^T & \\rule[.5ex]{1.7ex}{0.5pt}\n",
    "    \\end{bmatrix}\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 행렬 $\\times$ 행렬 (Matrix-Matrix Products)\n",
    "\n",
    "행렬 $\\times$ 행렬 연산도 몇 가지 관점으로 접근할 수 있다.\n",
    "\n",
    "#### 일련의 벡터 $\\times$ 벡터 연산으로 표현하는 경우\n",
    "\n",
    "$A$와 $B$가 행 또는 열로 표현되었는가에 따라 두 가지 경우로 나눌 수 있다.\n",
    "\n",
    "- $A$가 행으로 $B$가 열로 표현되었을 때\n",
    "\\begin{align*}\n",
    "C = AB = \\begin{bmatrix}\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_1^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_2^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     & \\vdots &\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_m^T & \\rule[.5ex]{1.7ex}{0.5pt}\n",
    "    \\end{bmatrix}\n",
    "    \\begin{bmatrix}\n",
    "    \\vert & \\vert & & \\vert\\\\\n",
    "    b_1 & b_2 & \\cdots & b_p\\\\\n",
    "    \\vert & \\vert & & \\vert\n",
    "    \\end{bmatrix}\n",
    "= \\begin{bmatrix}\n",
    "    a_1^Tb_1 & a_1^Tb_2 & \\cdots & a_1^Tb_p\\\\\n",
    "    a_2^Tb_1 & a_2^Tb_2 & \\cdots & a_2^Tb_p\\\\\n",
    "    \\vdots & \\vdots & \\ddots & \\vdots\\\\\n",
    "    a_m^Tb_1 & a_m^Tb_2 & \\cdots & a_m^Tb_p\\\\\n",
    "\\end{bmatrix}\n",
    "\\end{align*}\n",
    "\n",
    "$A\\in \\mathbb{R}^{m\\times n}$, $B\\in \\mathbb{R}^{n\\times p}$, $a_i \\in \\mathbb{R}^n$, $b_j \\in \\mathbb{R}^n$이기 때문에 내적값들이 자연스럽게 정의된다.\n",
    "\n",
    "- $A$가 열로 $B$가 행으로 표현되었을 때\n",
    "\n",
    "위보다는 까다롭지만 가끔씩 유용하다.\n",
    "\n",
    "\\begin{align*}\n",
    "C = AB = \n",
    "    \\begin{bmatrix}\n",
    "    \\vert & \\vert & & \\vert\\\\\n",
    "    a_1 & a_2 & \\cdots & a_n\\\\\n",
    "    \\vert & \\vert & & \\vert\n",
    "    \\end{bmatrix}\n",
    "    \\begin{bmatrix}\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & b_1^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & b_2^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     & \\vdots &\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & b_n^T & \\rule[.5ex]{1.7ex}{0.5pt}\n",
    "    \\end{bmatrix}\n",
    "= \\sum_{i=1}^n a_i b_i^T\n",
    "\\end{align*}\n",
    "\n",
    "$AB$는 모든 $i$에 대해서 $a_i\\in \\mathbb{R}^m$와 $b_i\\in \\mathbb{R}^p$의 외적의 합이다. $a_i b_i^T$의 차원은 $m\\times p$이다 ($C$의 차원과 동일).\n",
    "\n",
    "#### 일련의 행렬 $\\times$ 벡터 연산으로 표현하는 경우\n",
    "\n",
    "- $B$가 열로 표현되었을 때\n",
    "\n",
    "$C=AB$일 때 $C$의 열들을 $A$와 $B$의 열들의 곱으로 나타낼 수 있다.\n",
    "\n",
    "\\begin{align*}\n",
    "C = AB =\n",
    "    A \\begin{bmatrix}\n",
    "    \\vert & \\vert & & \\vert\\\\\n",
    "    b_1 & b_2 & \\cdots & b_p\\\\\n",
    "    \\vert & \\vert & & \\vert\n",
    "    \\end{bmatrix}\n",
    "= \\begin{bmatrix}\n",
    "    \\vert & \\vert & & \\vert\\\\\n",
    "    Ab_1 & Ab_2 & \\cdots & Ab_p\\\\\n",
    "    \\vert & \\vert & & \\vert\n",
    "    \\end{bmatrix}\n",
    "\\end{align*}\n",
    "\n",
    "각각의 $c_i = Ab_i$는 앞에서 살펴본 행렬 $\\times$ 벡터의 두 가지 관점으로 해석할 수 있다.\n",
    "\n",
    "- $A$가 행으로 표현되었을 때\n",
    "\n",
    "\\begin{align*}\n",
    "C = AB =\n",
    "    \\begin{bmatrix}\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_1^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_2^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     & \\vdots &\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_m^T & \\rule[.5ex]{1.7ex}{0.5pt}\n",
    "    \\end{bmatrix} B\n",
    "= \\begin{bmatrix}\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_1^TB & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_2^TB & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     & \\vdots &\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_m^TB & \\rule[.5ex]{1.7ex}{0.5pt}\n",
    "    \\end{bmatrix}\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 중요 연산과 성질들 (Operations and Properties)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 정방(Square), 삼각(triangular), 대각(diagonal), 단위(identity) 행렬들\n",
    "\n",
    "정방행렬(square matrix): 행과 열의 개수가 동일\n",
    "\n",
    "\\begin{bmatrix}\n",
    "  4 & 9 & 2 \\\\\n",
    "  3 & 5 & 7 \\\\\n",
    "  8 & 1 & 6\n",
    "\\end{bmatrix}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "상삼각행렬(upper triangular matrix): 정방행렬이며 주대각선 아래 원소들이 모두 0\n",
    "\n",
    "\\begin{bmatrix}\n",
    "  4 & 9 & 2 \\\\\n",
    "  0 & 5 & 7 \\\\\n",
    "  0 & 0 & 6\n",
    "\\end{bmatrix}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "하삼각행렬(lower triangular matrix): 정방행렬이며 주대각선 위 원소들이 모두 0\n",
    "\n",
    "\\begin{bmatrix}\n",
    "  4 & 0 & 0 \\\\\n",
    "  3 & 5 & 0 \\\\\n",
    "  8 & 1 & 6\n",
    "\\end{bmatrix}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "대각행렬(diagonal matrix): 정방행렬이며 주대각선 제외 모든 원소가 0\n",
    "\n",
    "\\begin{bmatrix}\n",
    "  4 & 0 & 0 \\\\\n",
    "  0 & 5 & 0 \\\\\n",
    "  0 & 0 & 6\n",
    "\\end{bmatrix}\n",
    "\n",
    "NumPy's `diag` 함수를 사용해서 대각행렬을 생성할 수 있다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[4, 0, 0],\n",
       "       [0, 5, 0],\n",
       "       [0, 0, 6]])"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.diag([4, 5, 6])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`diag` 함수에 행렬을 전달하면 주대각선 값들을 얻을 수 있다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 5, 9])"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D = np.array([\n",
    "        [1, 2, 3],\n",
    "        [4, 5, 6],\n",
    "        [7, 8, 9],\n",
    "    ])\n",
    "np.diag(D)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "단위행렬(identity matrix): 대각행렬이며 주대각선 원소들이 모두 1. $I$로 표시한다.\n",
    "\n",
    "\\begin{bmatrix}\n",
    "  1 & 0 & 0 \\\\\n",
    "  0 & 1 & 0 \\\\\n",
    "  0 & 0 & 1\n",
    "\\end{bmatrix}\n",
    "\n",
    "Numpy의 `eye` 함수를 사용하면 원하는 크기의 단위행렬을 생성할 수 있다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1., 0., 0.],\n",
       "       [0., 1., 0.],\n",
       "       [0., 0., 1.]])"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.eye(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 전치 (Transpose)\n",
    "\n",
    "행렬을 전치하는 것은 그 행렬을 뒤집는 것으로 생각할 수 있다. 행렬 $A\\in \\mathbb{R}^{m\\times n}$이 주어졌을 때 그것의 전치행렬은 $A^T \\in \\mathbb{R}^{n\\times m}$으로 표시하고 각 원소는 다음과 같이 주어진다.\n",
    "\n",
    "$$\\left( A^T \\right)_{ij} = A_{ji}$$\n",
    "\n",
    "다음의 성질들이 성립한다.\n",
    "\n",
    "- $(A^T)^T = A$\n",
    "- $\\left(AB\\right)^T = B^TA^T$\n",
    "- $(A + B)^T = A^T + B^T$\n",
    "\n",
    "$ A^T =\n",
    "\\begin{bmatrix}\n",
    "  1 & 2 & 3 \\\\\n",
    "  4 & 5 & 6\n",
    "\\end{bmatrix}^T =\n",
    "\\begin{bmatrix}\n",
    "  1 & 4 \\\\\n",
    "  2 & 5 \\\\\n",
    "  3 & 6\n",
    "\\end{bmatrix}$\n",
    "\n",
    "Numpy의 `T` 속성(attribute)을 사용해서 전치행렬을 구할 수 있다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = np.array([\n",
    "    [1,2,3],\n",
    "    [4,5,6]\n",
    "])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1, 4],\n",
       "       [2, 5],\n",
       "       [3, 6]])"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1, 2, 3],\n",
       "       [4, 5, 6]])"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.T.T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "B = np.array([[1,2], [4, 5], [6, 7]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[27, 60],\n",
       "       [33, 75]])"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.matmul(A, B).T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[27, 60],\n",
       "       [33, 75]])"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.matmul(B.T, A.T)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "B = np.array([[1,2,3], [4, 5, 6]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 2,  8],\n",
       "       [ 4, 10],\n",
       "       [ 6, 12]])"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(A + B).T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 2,  8],\n",
       "       [ 4, 10],\n",
       "       [ 6, 12]])"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.T + B.T"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  대칭행렬 (Symmetic Matrices)\n",
    "\n",
    "정방행렬 $A$가 $A^T$와 동일할 때 대칭행렬이라고 부른다. $A = -A^T$일 때는 반대칭(anti-symmetric)행렬이라고 부른다.\n",
    "\n",
    "$AA^T$는 항상 대칭행렬이다.\n",
    "\n",
    "$A + A^T$는 대칭, $A - A^T$는 반대칭이다.\n",
    "\n",
    "$$A = \\frac{1}{2}(A+A^T)+\\frac{1}{2}(A-A^T)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[14, 32],\n",
       "       [32, 77]])"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.matmul(A, A.T)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[17, 22, 27],\n",
       "       [22, 29, 36],\n",
       "       [27, 36, 45]])"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.matmul(A.T, A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 대각합 (Trace)\n",
    "\n",
    "정방행렬 $A\\in \\mathbb{R}^{n\\times n}$의 대각합은 $\\mathrm{tr}(A)$로 표시(또는 $\\mathrm{tr}A$)하고 그 값은 $\\sum_{i=1}^n A_{ii}$이다. 대각합은 다음과 같은 성질을 가진다.\n",
    "\n",
    "- For $A\\in \\mathbb{R}^{n\\times n}$, $\\mathrm{tr}A = \\mathrm{tr}A^T$\n",
    "- For $A,B\\in \\mathbb{R}^{n\\times n}$, $\\mathrm{tr}(A+B) = \\mathrm{tr}A + \\mathrm{tr}B$\n",
    "- For $A\\in \\mathbb{R}^{n\\times n}, t\\in\\mathbb{R}$, $\\mathrm{tr}(tA) = t\\,\\mathrm{tr}A$\n",
    "- For $A, B$ such that $AB$ is square, $\\mathrm{tr}AB = \\mathrm{tr}BA$\n",
    "- For $A, B, C$ such that $ABC$ is square, $\\mathrm{tr}ABC = \\mathrm{tr}BCA = \\mathrm{tr}CAB$, and so on for the product of more matrices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "123"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = np.array([\n",
    "        [100, 200, 300],\n",
    "        [ 10,  20,  30],\n",
    "        [  1,   2,   3],\n",
    "    ])\n",
    "np.trace(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Norms\n",
    "\n",
    "벡터의 norm은 벡터의 길이로 이해할 수 있다. $l_2$ norm (Euclidean norm)은 다음과 같이 정의된다.\n",
    "\n",
    "$$\\left \\Vert x \\right \\|_2 = \\sqrt{\\sum_{i=1}^n{x_i}^2}$$\n",
    "\n",
    "$\\left \\Vert x \\right \\|_2^2 = x^Tx$임을 기억하라."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5.0"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy.linalg as LA\n",
    "LA.norm(np.array([3, 4]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$l_p$ norm\n",
    "\n",
    "$$\\left \\Vert x \\right \\|_p = \\left(\\sum_{i=1}^n|{x_i}|^p\\right)^{1/p}$$\n",
    "\n",
    "Frobenius norm (행렬에 대해서)\n",
    "\n",
    "$$\\left \\Vert A \\right \\|_F = \\sqrt{\\sum_{i=1}^m\\sum_{j=1}^n A_{ij}^2} = \\sqrt{\\mathrm{tr}(A^TA)}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = np.array([\n",
    "        [100, 200, 300],\n",
    "        [ 10,  20,  30],\n",
    "        [  1,   2,   3],\n",
    "    ])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "376.0505285197722"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LA.norm(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "376.0505285197722"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.trace(A.T.dot(A))**0.5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 선형독립과 Rank (Linear Independence and Rank)\n",
    "\n",
    "벡터들의 집합 $\\{x_1,x_2,\\ldots,x_n\\}\\subset \\mathbb{R}^m$에 속해 있는 어떤 벡터도 나머지 벡터들의 선형조합으로 나타낼 수 없을 때 이 집합을 선형독립(linear independent)이라고 부른다. 역으로 어떠한 벡터가 나머지 벡터들의 선형조합으로 나타내질 수 있을 때 이 집합을 (선형)종속(dependent)이라고 부른다.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = np.array([\n",
    "        [1, 4, 2],\n",
    "        [2, 1, -3],\n",
    "        [3, 5, -1],\n",
    "    ])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "위 행렬 $A$의 열들의 집합은 종속이다. 왜냐하면"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ True,  True,  True])"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A[:, 2] == -2*A[:, 0] + A[:, 1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Column rank: 행렬 $A\\in \\mathbb{R}^{m\\times n}$의 열들의 부분집합 중에서 가장 큰 선형독립인 집합의 크기\n",
    "\n",
    "Row rank: 행렬 $A\\in \\mathbb{R}^{m\\times n}$의 행들의 부분집합 중에서 가장 큰 선형독립인 집합의 크기\n",
    "\n",
    "모든 행렬의 column rank와 row rank는 동일하다. 따라서 단순히 $\\mathrm{rank}(A)$로 표시한다. 다음의 성질들이 성립한다.\n",
    "\n",
    "- For $A\\in \\mathbb{R}^{m\\times n}$, $\\mathrm{rank}(A) \\leq \\min(m, n)$. If $\\mathrm{rank}(A) = \\min(m, n)$, then $A$ is said to be ***full rank***.\n",
    "- For $A\\in \\mathbb{R}^{m\\times n}$, $\\mathrm{rank}(A) = \\mathrm{rank}(A^T)$.\n",
    "- For $A\\in \\mathbb{R}^{m\\times n}, B\\in \\mathbb{R}^{n\\times p}$, $\\mathrm{rank}(A+B) \\leq \\min(\\mathrm{rank}(A), \\mathrm{rank}(B))$.\n",
    "- For $A, B\\in \\mathbb{R}^{m\\times n}$, $\\mathrm{rank}(A+B) \\leq \\mathrm{rank}(A) + \\mathrm{rank}(B)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LA.matrix_rank(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 역행렬 (The Inverse)\n",
    "\n",
    "정방행렬 $A\\in \\mathbb{R}^{n\\times n}$의 역행렬 $A^{-1}$은 다음을 만족하는 정방행렬($\\in \\mathbb{R}^{n\\times n}$)이다.\n",
    "\n",
    "$$A^{-1}A = I = AA^{-1}$$\n",
    "\n",
    "$A$의 역행렬이 존재할 때, $A$를 ***invertible*** 또는 ***non-singular***하다고 말한다.\n",
    "\n",
    "- $A$의 역행렬이 존재하기 위해선 $A$는 full rank여야 한다.\n",
    "- $(A^{-1})^{-1} = A$\n",
    "- $(AB)^{-1} = B^{-1}A^{-1}$\n",
    "- $(A^{-1})^T = (A^T)^{-1}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[-2. ,  1. ],\n",
       "       [ 1.5, -0.5]])"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = np.array([\n",
    "        [1, 2],\n",
    "        [3, 4],\n",
    "    ])\n",
    "LA.inv(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1., 2.],\n",
       "       [3., 4.]])"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LA.inv(LA.inv(A))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 직교 행렬 (Orthogonal Matrices)\n",
    "\n",
    "$x^Ty=0$가 성립하는 두 벡터 $x, y \\in \\mathbb{R}^n$를 직교(orthogonal)라고 부른다. $\\|x\\|_2 = 1$인 벡터 $x\\in \\mathbb{R}^n$를 정규화(normalized)된 벡터라고 부른다.\n",
    "\n",
    "모든 열들이 서로 직교이고 정규화된 정방행렬 $U\\in \\mathbb{R}^{n\\times n}$를 직교행렬이라고 부른다. 따라서 다음이 성립한다.\n",
    "\n",
    "- $U^TU = I$\n",
    "- $UU^T = I$ 이건 밑에서 증명\n",
    "- $U^{-1} = U^T$\n",
    "- $\\|Ux\\|_2 = \\|x\\|_2$ for any $x\\in \\mathbb{R}^{n}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 치역(Range), 영공간(Nullspace)\n",
    "\n",
    "#### 벡터의 집합($\\{x_1,x_2,\\ldots,x_n\\}$)에 대한 생성(span)\n",
    "\n",
    "$$\\mathrm{span}(\\{x_1,x_2,\\ldots,x_n\\}) = \\left\\{ v : v = \\sum_{i=1}^n\\alpha_i x_i, \\alpha_i \\in \\mathbb{R} \\right\\}$$\n",
    "\n",
    "#### 행렬의 치역 (range)\n",
    "행렬 $A\\in \\mathbb{R}^{m\\times n}$의 치역 $\\mathcal{R}(A)$는 A의 모든 열들에 대한 생성(span)이다.\n",
    "$$\\mathcal{R}(A) = \\{ v\\in \\mathbb{R}^m : v = Ax, x\\in \\mathbb{R}^n\\}$$\n",
    "\n",
    "#### 영공간 (nullspace)\n",
    "행렬 $A\\in \\mathbb{R}^{m\\times n}$의 영공간(nullspace) $\\mathcal{N}(A)$는 $A$와 곱해졌을 때 0이 되는 모든 벡터들의 집합이다.\n",
    "$$\\mathcal{N}(A) = \\{x\\in \\mathbb{R}^n : Ax = 0\\}$$\n",
    "\n",
    "중요한 성질:\n",
    "$$\\{w : w = u + v, u\\in \\mathcal{R}(A^T), v \\in \\mathcal{N}(A)\\} = \\mathbb{R}^n ~\\mathrm{and}~ \\mathcal{R}(A^T) \\cap \\mathcal{N}(A) = \\{0\\}$$\n",
    "\n",
    "$\\mathcal{R}(A^T)$와 $\\mathcal{N}(A)$를 직교여공간(orthogonal complements)라고 부르고 $\\mathcal{R}(A^T) = \\mathcal{N}(A)^\\perp$라고 표시한다.\n",
    "\n",
    "#### 투영 (projection)\n",
    "\n",
    "$\\mathcal{R}(A)$위로 벡터 $y\\in \\mathbb{R}^m$의 투영(projection)은\n",
    "\n",
    "$$\\mathrm{Proj}(y;A) = \\mathop{\\mathrm{argmin}}_{v\\in \\mathcal{R}(A)} \\| v - y \\|_2 = A(A^TA)^{-1}A^Ty$$\n",
    "\n",
    "\n",
    "$U^TU = I$인 정방행렬 $U$는 $UU^T = I$임을 보이기\n",
    "- $U$의 치역은 전체공간이므로 임의의 $y$에 대해 $\\mathrm{Proj}(y;U) = y$이어야 한다.\n",
    "- 모든 $y$에 대해 $U(U^TU)^{-1}U^{T}y = y$이어야 하므로 $U(U^TU)^{-1}U^T= I$이다.\n",
    "- 따라서 $UU^T = I$이다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 행렬식 (Determinant)\n",
    "\n",
    "정방행렬 $A\\in \\mathbb{R}^{n\\times n}$의 행렬식(determinant) $|A|$ (또는 $\\det A$)는 다음과 같이 계산할 수 있다.\n",
    "\n",
    "$|A| = A_{1,1}\\times|A^{(1,1)}| - A_{1,2}\\times|A^{(1,2)}| + A_{1,3}\\times|A^{(1,3)}| - A_{1,4}\\times|A^{(1,4)}| + \\cdots ± A_{1,n}\\times|A^{(1,n)}|$\n",
    "\n",
    "where $A^{(i,j)}$ is the matrix $A$ without row $i$ and column $j$.\n",
    "\n",
    "$A = \\begin{bmatrix}\n",
    "  1 & 2 & 3 \\\\\n",
    "  4 & 5 & 6 \\\\\n",
    "  7 & 8 & 0\n",
    "\\end{bmatrix}$\n",
    "\n",
    "위의 식을 사용하면 아래와 같이 전개된다.\n",
    "\n",
    "\\begin{align*}\n",
    "|A| = 1 \\times \\left | \\begin{bmatrix} 5 & 6 \\\\ 8 & 0 \\end{bmatrix} \\right |\n",
    "     - 2 \\times \\left | \\begin{bmatrix} 4 & 6 \\\\ 7 & 0 \\end{bmatrix} \\right |\n",
    "     + 3 \\times \\left | \\begin{bmatrix} 4 & 5 \\\\ 7 & 8 \\end{bmatrix} \\right |\n",
    "\\end{align*}\n",
    "\n",
    "이제 위의 $2 \\times 2$ 행렬들의 행렬식을 계산하면 된다.\n",
    "\n",
    "$\\left | \\begin{bmatrix} 5 & 6 \\\\ 8 & 0 \\end{bmatrix} \\right | = 5 \\times 0 - 6 \\times 8 = -48$\n",
    "\n",
    "$\\left | \\begin{bmatrix} 4 & 6 \\\\ 7 & 0 \\end{bmatrix} \\right | = 4 \\times 0 - 6 \\times 7 = -42$\n",
    "\n",
    "$\\left | \\begin{bmatrix} 4 & 5 \\\\ 7 & 8 \\end{bmatrix} \\right | = 4 \\times 8 - 5 \\times 7 = -3$\n",
    "\n",
    "최종결과는 다음과 같다.\n",
    "\n",
    "$|A| = 1 \\times (-48) - 2 \\times (-42) + 3 \\times (-3) = 27$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`numpy.linalg` 모듈의 `det` 함수를 사용하여 행렬식을 쉽게 구할 수 있다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "27.0"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = np.array([\n",
    "        [1, 2, 3],\n",
    "        [4, 5, 6],\n",
    "        [7, 8, 0]\n",
    "    ])\n",
    "LA.det(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 행렬식의 기하학적 해석\n",
    "\n",
    "행렬\n",
    "\\begin{align*}\n",
    "\\begin{bmatrix}\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_1^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_2^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     & \\vdots &\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_n^T & \\rule[.5ex]{1.7ex}{0.5pt}\n",
    "\\end{bmatrix}\n",
    "\\end{align*}\n",
    "이 주어졌을 때, 행 벡터들의 선형조합(단 조합에 쓰이는 계수들은 0에서 1사이)이 나타내는 $\\mathbb{R}^n$ 공간 상의 모든 점들의 집합 $S$를 생각해보자. 엄밀하게 나타내자면\n",
    "$$S = \\{v\\in \\mathbb{R}^n : v=\\sum_{i=1}^n \\alpha_i a_i ~\\mathrm{where}~ 0\\leq \\alpha_i \\leq 1, i=1,\\ldots,n\\}$$\n",
    "\n",
    "**중요한 사실은 행렬식의 절대값이 이 $S$의 부피(volume)과 일치한다는 것이다!**\n",
    "\n",
    "예를 들어, 행렬\n",
    "\n",
    "$$A = \\begin{bmatrix}\n",
    "  1 & 3 \\\\\n",
    "  3 & 2\n",
    "\\end{bmatrix}$$\n",
    "의 행벡터들은\n",
    "$$a_1 = \\begin{bmatrix}\n",
    "  1\\\\\n",
    "  3\n",
    "\\end{bmatrix}\n",
    "a_2 = \\begin{bmatrix}\n",
    "  3\\\\\n",
    "  2\n",
    "\\end{bmatrix}$$\n",
    "이다. $S$에 속한 점들을 2차원평면에 나타내면 다음과 같다.\n",
    "\n",
    "<div>\n",
    "<img src=\"images/fig_det.png\" width=\"300\"/>\n",
    "</div>\n",
    "\n",
    "평행사변형 $S$의 넓이는 7인데 이 값은 $A$의 행렬식 $|A|=-7$의 절대값과 일치함을 알 수 있다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "행렬식의 중요한 성질들\n",
    "\n",
    "- $|I|=1$\n",
    "- $A$의 하나의 행에 $t\\in \\mathbb{R}$를 곱하면 행렬식은 $t|A|$\n",
    "$$\\begin{align*}\n",
    "\\left|~\\begin{bmatrix}\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & ta_1^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_2^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     & \\vdots &\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_n^T & \\rule[.5ex]{1.7ex}{0.5pt}\n",
    "\\end{bmatrix}~\\right| = t|A|\n",
    "\\end{align*}\n",
    "$$\n",
    "- $A$의 두 행들을 교환하면 행렬식은 $-|A|$\n",
    "$$\\begin{align*}\n",
    "\\left|~\\begin{bmatrix}\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_2^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_1^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     & \\vdots &\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & a_n^T & \\rule[.5ex]{1.7ex}{0.5pt}\n",
    "\\end{bmatrix}~\\right| = -|A|\n",
    "\\end{align*}\n",
    "$$\n",
    "- For $A\\in \\mathbb{R}^{n\\times n}$, $|A| = |A^T|$.\n",
    "- For $A, B\\in \\mathbb{R}^{n\\times n}$, $|AB| = |A| |B|$.\n",
    "- For $A\\in \\mathbb{R}^{n\\times n}$, $|A|=0$, if and only if A is singular (non-invertible). $A$가 singular이면 행들이 linearly dependent할 것인데, 이 경우 $S$의 형태는 부피가 0인 납작한 판의 형태가 될 것이다.\n",
    "- For $A\\in \\mathbb{R}^{n\\times n}$ and $A$ non-singular, $|A^{-1}| = 1/|A|$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 이차형식 (Quadratic Forms)\n",
    "\n",
    "정방행렬 $A\\in \\mathbb{R}^{n\\times n}$와 벡터 $x\\in \\mathbb{R}^n$가 주어졌을 때, scalar값 $x^TAx$를 이차형식(quadratic form)이라고 부른다. 다음과 같이 표현할 수 있다.\n",
    "\n",
    "$$x^TAx = \\sum_{i=1}^n x_i(Ax)_i = \\sum_{i=1}^n x_i \\left(\\sum_{j=1}^n A_{ij}x_j\\right) = \\sum_{i=1}^n\\sum_{j=1}^n A_{ij}x_ix_j$$\n",
    "\n",
    "다음이 성립함을 알 수 있다.\n",
    "\n",
    "$$x^TAx = (x^TAx)^T = x^TA^Tx = x^T\\left(\\frac{1}{2}A + \\frac{1}{2}A^T\\right)x$$\n",
    "\n",
    "따라서 이차형식에 나타나는 행렬을 대칭행렬로 가정하는 경우가 많다.\n",
    "\n",
    "- 대칭행렬 $A\\in \\mathbb{S}^n$이 0이 아닌 모든 벡터 $x\\in \\mathbb{R}^n$에 대해서 $x^TAx \\gt 0$을 만족할 때, 양의 정부호(positive definite)라고 부르고 $A\\succ 0$(또는 단순히 $A \\gt 0$)로 표시한다. 모든 양의 정부호 행렬들의 집합을 $\\mathbb{S}_{++}^n$으로 표시한다.\n",
    "- 대칭행렬 $A\\in \\mathbb{S}^n$이 0이 아닌 모든 벡터 $x\\in \\mathbb{R}^n$에 대해서 $x^TAx \\ge 0$을 만족할 때, 양의 준정부호(positive sesmi-definite)라고 부르고 $A\\succeq 0$(또는 단순히 $A \\ge 0$)로 표시한다. 모든 양의 준정부호 행렬들의 집합을 $\\mathbb{S}_{+}^n$으로 표시한다.\n",
    "- 대칭행렬 $A\\in \\mathbb{S}^n$이 0이 아닌 모든 벡터 $x\\in \\mathbb{R}^n$에 대해서 $x^TAx \\lt 0$을 만족할 때, 음의 정부호(negative definite)라고 부르고 $A\\prec 0$(또는 단순히 $A \\lt 0$)로 표시한다.\n",
    "- 대칭행렬 $A\\in \\mathbb{S}^n$이 0이 아닌 모든 벡터 $x\\in \\mathbb{R}^n$에 대해서 $x^TAx \\leq 0$을 만족할 때, 음의 준정부호(negative sesmi-definite)라고 부르고 $A\\preceq 0$(또는 단순히 $A \\leq 0$)로 표시한다.\n",
    "- 대칭행렬 $A\\in \\mathbb{S}^n$가 양의 준정부호 또는 음의 준정부호도 아닌 경우, 부정부호(indefinite)라고 부른다. 이것은 $x_1^TAx_1 > 0, x_2^TAx_2 < 0$을 만족하는 $x_1, x_2\\in \\mathbb{R}^n$이 존재한다는 것을 의미한다.\n",
    "\n",
    "Positive definite 그리고 negative definite 행렬은 full rank이며 따라서 invertible이다.\n",
    "\n",
    "#### Gram matrix\n",
    "임의의 행렬 $A\\in \\mathbb{R}^{m\\times n}$이 주어졌을 때 행렬 $G = A^TA$를 Gram matrix라고 부르고 항상 positive semi-definite이다. 만약 $m\\ge n$이고 $A$가 full rank이면, $G$는 positive definite이다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 고유값 (Eigenvalues), 고유벡터 (Eigenvectors)\n",
    "\n",
    "정방행렬 $A\\in \\mathbb{R}^{n\\times n}$이 주어졌을 때,\n",
    "$$Ax = \\lambda x, x\\neq 0$$\n",
    "을 만족하는 $\\lambda \\in \\mathbb{C}$를 $A$의 고유값(eigenvalue) 그리고 $x\\in \\mathbb{C}^n$을 연관된 고유벡터(eigenvector)라고 부른다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`numpy.linalg` 모듈의 `eig` 함수를 사용하여 고유값과 고유벡터를 구할 수 있다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1, 2, 3],\n",
       "       [4, 5, 6],\n",
       "       [7, 8, 0]])"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([12.12289378, -0.38838384, -5.73450994]),\n",
       " array([[-0.29982463, -0.74706733, -0.27625411],\n",
       "        [-0.70747178,  0.65820192, -0.38842554],\n",
       "        [-0.63999131, -0.09306254,  0.87909571]]))"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eigenvalues, eigenvectors = LA.eig(A)\n",
    "eigenvalues, eigenvectors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-0.29982463, -0.70747178, -0.63999131])"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eigenvectors[:, 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-3.63474211, -8.57660525, -7.75854663])"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.matmul(A, eigenvectors[:, 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-3.63474211, -8.57660525, -7.75854663])"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eigenvalues[0] * eigenvectors[:, 0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 고유값, 고유벡터의 성질들\n",
    "\n",
    "- $\\mathrm{tr}A = \\sum_{i=1}^n \\lambda_i$\n",
    "- $|A| = \\prod_{i=1}^n \\lambda_i$\n",
    "- $\\mathrm{rank}(A)$는 0이 아닌 $A$의 고유값의 개수와 같다.\n",
    "- $A$가 non-singular일 때, $1/\\lambda_i$는 $A^{-1}$의 고유값이다(고유벡터 $x_i$와 연관된). 즉, $A^{-1}x_i = (1/\\lambda_i)x_i$이다.\n",
    "- 대각행렬 $D = \\mathrm{diag}(d_1,\\ldots,d_n)$의 고유값들은 $d_1,\\ldots,d_n$이다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = np.array([\n",
    "        [1, 2, 3],\n",
    "        [4, 5, 9],\n",
    "        [7, 8, 15]\n",
    "    ])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([ 2.12819293e+01, -2.81929326e-01,  9.68995205e-16]),\n",
       " array([[ 0.17485683,  0.85386809, -0.57735027],\n",
       "        [ 0.50887555,  0.18337571, -0.57735027],\n",
       "        [ 0.84289427, -0.48711666,  0.57735027]]))"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eigenvalues, eigenvectors = LA.eig(A)\n",
    "eigenvalues, eigenvectors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LA.matrix_rank(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "모든 고유값과 고유벡터들을 다음과 같이 하나의 식으로 나타낼 수 있다.\n",
    "\n",
    "$$AX = X\\Lambda$$\n",
    "\n",
    "$$X\\in \\mathbb{R}^{n\\times n} = \n",
    "\\begin{bmatrix}\n",
    "    \\vert & \\vert & & \\vert\\\\\n",
    "    x_1 & x_2 & \\cdots & x_n\\\\\n",
    "    \\vert & \\vert & & \\vert\n",
    "\\end{bmatrix},~\n",
    "\\Lambda = \\mathrm{diag}(\\lambda_1,\\ldots,\\lambda_n)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 고유값, 고유벡터와 대칭행렬\n",
    "\n",
    "대칭행렬 $A\\in \\mathbb{S}^n$가 가지는 놀라운 성질들\n",
    "- $A$의 모든 고유값들은 실수값(real)이다.\n",
    "- $A$의 고유벡터들은 orthonomal(orthogonal, normalized)이다.\n",
    "\n",
    "따라서 임의의 대칭행렬 $A$를 $A=U\\Lambda U^T$($U$는 위의 $X$처럼 $A$의 고유벡터들로 이뤄진 행렬)로 나타낼 수 있다.\n",
    "\n",
    "$A\\in \\mathbb{S}^n = U\\Lambda U^T$라고 하자. 그러면\n",
    "$$x^TAx = x^T U\\Lambda U^T x = y^T\\Lambda y = \\sum_{i=1}^n \\lambda_i y_i^2$$\n",
    "where $y=U^Tx$\n",
    "\n",
    "$y_i^2$가 양수이므로 위 식의 부호는 $\\lambda_i$ 값들에 의해서 결정된다. 만약 모든 $\\lambda_i > 0$이면, $A$는 positive definite이고 모든 $\\lambda_i \\ge 0$이면, $A$는 positive seimi-definite이다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 행렬미분 (Matrix Calculus)\n",
    "\n",
    "### The Gradient\n",
    "\n",
    "행렬 $A\\in \\mathbb{R}^{m\\times n}$를 입력으로 받아서 실수값을 돌려주는 함수 $f : \\mathbb{R}^{m\\times n} \\to \\mathbb{R}$이 있다고 하자. $f$의 gradient는 다음과 같이 정의된다.\n",
    "\n",
    "$$\n",
    "\\nabla_Af(A)\\in \\mathbb{R}^{m\\times n} = \\begin{bmatrix}\n",
    "    \\frac{\\partial f(A)}{\\partial A_{11}} & \\frac{\\partial f(A)}{\\partial A_{12}} & \\cdots & \\frac{\\partial f(A)}{\\partial A_{1n}}\\\\\n",
    "    \\frac{\\partial f(A)}{\\partial A_{21}} & \\frac{\\partial f(A)}{\\partial A_{22}} & \\cdots & \\frac{\\partial f(A)}{\\partial A_{2n}}\\\\\n",
    "    \\vdots & \\vdots & \\ddots & \\vdots\\\\\n",
    "    \\frac{\\partial f(A)}{\\partial A_{m1}} & \\frac{\\partial f(A)}{\\partial A_{m2}} & \\cdots & \\frac{\\partial f(A)}{\\partial A_{mn}}\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "$$(\\nabla_Af(A))_{ij} = \\frac{\\partial f(A)}{\\partial A_{ij}}$$\n",
    "\n",
    "특별히 $A$가 벡터 $x\\in \\mathbb{R}^n$인 경우는,\n",
    "$$\n",
    "\\nabla_x f(x) = \n",
    "\\begin{bmatrix}\n",
    "\\frac{\\partial f(x)}{\\partial x_1}\\\\\n",
    "\\frac{\\partial f(x)}{\\partial x_2}\\\\\n",
    "\\vdots\\\\\n",
    "\\frac{\\partial f(x)}{\\partial x_n}\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "### The Hessian\n",
    "\n",
    "$$\n",
    "\\nabla_x^2 f(x)\\in \\mathbb{R}^{n\\times n} = \\begin{bmatrix}\n",
    "    \\frac{\\partial^2 f(x)}{\\partial x_1^2} & \\frac{\\partial^2 f(x)}{\\partial x_1x_2} & \\cdots & \\frac{\\partial^2 f(x)}{\\partial x_1x_n}\\\\\n",
    "    \\frac{\\partial^2 f(x)}{\\partial x_2x_1} & \\frac{\\partial^2 f(x)}{\\partial x_2^2} & \\cdots & \\frac{\\partial^2 f(x)}{\\partial x_2x_n}\\\\\n",
    "    \\vdots & \\vdots & \\ddots & \\vdots\\\\\n",
    "    \\frac{\\partial^2 f(x)}{\\partial x_nx_1} & \\frac{\\partial^2 f(x)}{\\partial x_nx_2} & \\cdots & \\frac{\\partial^2 f(x)}{\\partial x_n^2}\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "$$(\\nabla_x^2 f(x))_{ij} = \\frac{\\partial^2 f(x)}{\\partial x_i \\partial x_j}$$\n",
    "\n",
    "\n",
    "중요한 공식들\n",
    "\n",
    "$x, b\\in \\mathbb{R}^n$, $A\\in \\mathbb{S}^n$일 때 다음이 성립한다.\n",
    "- $\\nabla_x b^Tx = b$\n",
    "- $\\nabla_x x^TAx = 2Ax$\n",
    "- $\\nabla_x^2 x^TAx = 2A$\n",
    "- $\\nabla_A \\log |A| = A^{-1}$ ($A\\in\\mathbb{S}_{++}^n$인 경우)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 적용예제들\n",
    "\n",
    "### 최소제곱법 (Least Squares)\n",
    "\n",
    "행렬 $A\\in \\mathbb{R}^{m\\times n}$($A$는 full rank로 가정)와 벡터 $b\\in \\mathbb{R}^n$가 주어졌고 $b\\notin \\mathcal{R}(A)$인 경우, $Ax = b$를 만족하는 벡터 $x\\in \\mathbb{R}^n$을 찾을 수 없다. 대신 $Ax$가 $b$와 최대한 가까워지는 $x$, 즉\n",
    "\n",
    "$$\\| Ax - b\\|_2^2$$\n",
    "을 최소화시키는 $x$를 찾는 문제를 고려할 수 있다. $\\|x\\|_2^2 = x^Tx$이므로\n",
    "\n",
    "\\begin{align*}\n",
    "\\| Ax - b\\|_2^2 &= (Ax - b)^T(Ax - b)\\\\\n",
    "&= x^TA^TAx - 2b^TAx + b^Tb\n",
    "\\end{align*}\n",
    "\n",
    "\\begin{align*}\n",
    "\\nabla_x (x^TA^TAx - 2b^TAx + b^Tb) &= \\nabla_x x^TA^TAx - \\nabla_x 2b^TAx + \\nabla_x b^Tb\\\\\n",
    "&= 2A^TAx - 2A^Tb\n",
    "\\end{align*}\n",
    "\n",
    "0으로 놓고 $x$에 관해 풀면\n",
    "$$x = (A^TA)^{-1}A^Tb$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 고유값과 최적화문제 (Eigenvalues as Optimization)\n",
    "\n",
    "다음 형태의 최적화문제를 행렬미분을 사용해 풀면 고유값이 최적해가 되는 것을 보일 수 있다.\n",
    "\n",
    "$$\\max_{x\\in \\mathbb{R}^n} x^TAx \\mathrm{~~~~subject~to~} \\|x\\|_2^2=1$$\n",
    "\n",
    "제약조건이 있는 최소화문제는 Lagrangian을 사용해서 해결\n",
    "\n",
    "$$\\mathcal{L}(x, \\lambda) = x^TAx - \\lambda x^Tx$$\n",
    "\n",
    "다음을 만족해야 함.\n",
    "\n",
    "$$\\nabla_x \\mathcal{L}(x, \\lambda) = \\nabla_x ( x^TAx - \\lambda x^Tx) = 2A^Tx - 2\\lambda x = 0$$\n",
    "\n",
    "따라서 최적해 $x$는 $Ax = \\lambda x$를 만족해야 하므로 $A$의 고유벡터만이 최적해가 될 수 있다. 고유벡터 $u_i$는\n",
    "\n",
    "$$u_i^TAu_i = \\sum_{j=1}^n \\lambda_j y_j^2 = \\lambda_i$$\n",
    "을 만족하므로($y=U^Tu_i$), 최적해는 가장 큰 고유값에 해당하는 고유벡터이다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Autoencoder와 Principal Components Analysis (PCA)\n",
    "\n",
    "Autoencoder란?\n",
    "\n",
    "\n",
    "<div>\n",
    "<img src=\"images/autoencoder.png\" width=\"400\"/>\n",
    "</div>\n",
    "\n",
    "Autoencoder의 응용예제\n",
    "- Dimensionality Reduction\n",
    "- Image Compression\n",
    "- Image Denoising\n",
    "- Feature Extraction\n",
    "- Image generation\n",
    "- Sequence to sequence prediction\n",
    "- Recommendation system\n",
    "\n",
    "PCA를 가장 간단한 형태의 autoencoder로 생각할 수 있다. 이 관점으로 PCA를 유도할텐데, 이제까지 우리가 배운 것만으로 가능하다!\n",
    "\n",
    "$m$개의 점들 $\\{x_1,\\ldots,x_m\\}$, $x_i\\in \\mathbb{R}^n$이 주어졌다고 하자. 각각의 점들을 $l$차원의 공간으로 투영시키는 함수 $f(x) = c\\in \\mathbb{R}^l$와 이것을 다시 $n$차원의 공간으로 회복하는 함수 $g(c)$를 생각해보자. $f$를 인코딩 함수, $g$를 디코딩 함수라고 부르며\n",
    "\n",
    "$$x \\approx g(f(x))$$\n",
    "가 되기를 원한다.\n",
    "\n",
    "#### 디코딩 함수\n",
    "\n",
    "함수 $g$는 간단한 선형함수로 정의하기로 한다.\n",
    "\n",
    "$$g(c) = Dc, ~~D\\in \\mathbb{R}^{n\\times l}$$\n",
    "\n",
    "여기서 $D$는 열들이 정규화되어 있고 서로 직교하는 경우로 한정한다.\n",
    "\n",
    "#### 인코딩 함수\n",
    "\n",
    "디코딩 함수가 위와 같이 주어졌을 때, 어떤 함수가 최적의 인코딩 함수일까?\n",
    "\n",
    "$$f(x)^* = \\mathop{\\mathrm{argmin}}_{f(x)} \\int \\| x - g(f(x))\\|_2^2 dx$$\n",
    "\n",
    "변분법(calculus of variations)의 방법(Euler-Lagrange 방정식)으로 풀 수 있다. 방정식\n",
    "\n",
    "$$\\nabla_f \\| x - g(f(x))\\|_2^2 = 0$$\n",
    "을 $f$에 관해 풀면 된다. $f(x)=c$로 두고 두면\n",
    "\n",
    "\\begin{align*}\n",
    "\\| x - g(c)\\|_2^2 &= (x-g(c))^T(x-g(c))\\\\\n",
    "&= x^Tx - x^Tg(c) - g(c)^Tx + g(c)^Tg(c)\\\\\n",
    "&= x^Tx - 2x^Tg(c) + g(c)^Tg(c)\\\\\n",
    "&= x^Tx - 2x^TDc + c^TD^TDc\\\\\n",
    "&= x^Tx - 2x^TDc + c^TI_lc\\\\\n",
    "&= x^Tx - 2x^TDc + c^Tc\\\\\n",
    "\\end{align*}\n",
    "\n",
    "$$\\nabla_c (x^Tx - 2x^TDc + c^Tc) = 0$$\n",
    "\n",
    "$$-2D^Tx + 2c = 0$$\n",
    "\n",
    "$$c = D^Tx$$\n",
    "\n",
    "따라서 최적의 인코더 함수는\n",
    "$$f(x) = D^Tx$$\n",
    "\n",
    "#### 최적의 $D$ 찾기\n",
    "\n",
    "입력값 $x$와 출력값 $g(f(x))$ 사이의 거리가 최소화되는 $D$를 찾는다.\n",
    "\n",
    "\\begin{align*}\n",
    "X = \\begin{bmatrix}\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & x_1^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     & \\vdots &\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & x_m^T & \\rule[.5ex]{1.7ex}{0.5pt}\n",
    "\\end{bmatrix},~~\n",
    "R = \\begin{bmatrix}\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & g(f(x_1))^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     & \\vdots &\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & g(f(x_m))^T & \\rule[.5ex]{1.7ex}{0.5pt}\n",
    "\\end{bmatrix}\n",
    "\\end{align*}\n",
    "\n",
    "에러행렬 $E$를 다음과 정의할 수 있다.\n",
    "\n",
    "$$E = X - R$$\n",
    "\n",
    "우리가 찾는 최적의 $D$는 다음과 같다.\n",
    "\n",
    "$$D^* = \\mathop{\\mathrm{argmin}}_{D} \\|E\\|_F^2~~~\\mathrm{subject~to~} D^TD=I_l$$\n",
    "\n",
    "$R$을 다시 정리해보자.\n",
    "\n",
    "\\begin{align*}\n",
    "R &= \\begin{bmatrix}\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & g(f(x_1))^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     & \\vdots &\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & g(f(x_m))^T & \\rule[.5ex]{1.7ex}{0.5pt}\n",
    "\\end{bmatrix}\\\\\n",
    "&= \\begin{bmatrix}\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & \\left(DD^Tx_1 \\right)^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     & \\vdots &\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & \\left(DD^Tx_m \\right)^T & \\rule[.5ex]{1.7ex}{0.5pt}\n",
    "\\end{bmatrix}\\\\\n",
    "&= \\begin{bmatrix}\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & x_1^TDD^T & \\rule[.5ex]{1.7ex}{0.5pt}\\\\\n",
    "     & \\vdots &\\\\\n",
    "     \\rule[.5ex]{1.7ex}{0.5pt} & x_m^TDD^T & \\rule[.5ex]{1.7ex}{0.5pt}\n",
    "\\end{bmatrix}\\\\\n",
    "&= XDD^T\n",
    "\\end{align*}\n",
    "\n",
    "\\begin{align*}\n",
    "\\mathop{\\mathrm{argmin}}_{D} \\|E\\|_F^2 &= \\mathop{\\mathrm{argmin}}_{D} \\| X - XDD^T\\|_F^2\\\\\n",
    "&= \\mathop{\\mathrm{argmin}}_{D} \\mathrm{tr}\\left( \\left(X - XDD^T\\right)^T\\left(X - XDD^T\\right) \\right)\\\\\n",
    "&= \\mathop{\\mathrm{argmin}}_{D} \\mathrm{tr} \\left( X^TX - X^TXDD^T - DD^TX^TX + DD^TX^TXDD^T \\right)\\\\\n",
    "&= \\mathop{\\mathrm{argmin}}_{D} \\mathrm{tr} \\left( X^TX \\right) - \\mathrm{tr} \\left( X^TXDD^T \\right) - \\mathrm{tr} \\left( DD^TX^TX \\right) + \\mathrm{tr} \\left( DD^TX^TXDD^T \\right)\\\\\n",
    "&= \\mathop{\\mathrm{argmin}}_{D} - \\mathrm{tr} \\left( X^TXDD^T \\right) - \\mathrm{tr} \\left( DD^TX^TX \\right) + \\mathrm{tr} \\left( DD^TX^TXDD^T \\right)\\\\\n",
    "&= \\mathop{\\mathrm{argmin}}_{D} - 2\\mathrm{tr} \\left( X^TXDD^T \\right) + \\mathrm{tr} \\left( DD^TX^TXDD^T \\right)\\\\\n",
    "&= \\mathop{\\mathrm{argmin}}_{D} - 2\\mathrm{tr} \\left( X^TXDD^T \\right) + \\mathrm{tr} \\left( X^TXDD^TDD^T \\right)\\\\\n",
    "&= \\mathop{\\mathrm{argmin}}_{D} - 2\\mathrm{tr} \\left( X^TXDD^T \\right) + \\mathrm{tr} \\left( X^TXDD^T \\right)\\\\\n",
    "&= \\mathop{\\mathrm{argmin}}_{D} - \\mathrm{tr} \\left( X^TXDD^T \\right)\\\\\n",
    "&= \\mathop{\\mathrm{argmin}}_{D} - \\mathrm{tr} \\left( D^TX^TXD \\right)\\\\\n",
    "&= \\mathop{\\mathrm{argmax}}_{D} \\mathrm{tr} \\left( D^TX^TXD\\right)\\\\\n",
    "&= \\mathop{\\mathrm{argmax}}_{d_1,\\ldots,d_l} \\sum_{i=1}^l d_i^TX^TXd_i\n",
    "\\end{align*}\n",
    "\n",
    "\n",
    "$d_i^Td_i = 1$이므로 벡터들 $d_1,\\ldots,d_l$이 $X^TX$의 가장 큰 $l$개의 고유값에 해당하는 고유벡터들일 때 $\\sum_{i=1}^l d_i^TX^TXd_i$이 최대화된다."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}