{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " $$\\frac{\\partial \\mathbf{b}^T \\mathbf{A} \\mathbf{b} }{\\partial \\mathbf{b}} = (\\mathbf{A} + \\mathbf{A}^T) \\mathbf{b}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Proof:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "\\mathbf{b}^T \\mathbf{A} \\mathbf{b}\n",
    "&= \\begin{bmatrix}\n",
    "b_1 & \\cdots & b_n \n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "a_{11} & \\cdots & a_{1n} \\\\ \n",
    "\\vdots & \\ddots  & \\vdots \\\\ \n",
    "a_{n1} & \\cdots  &  a_{nn}\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix} b_1 \\\\ \\vdots \\\\ b_n \\end{bmatrix}  \\\\\n",
    "&= \\begin{bmatrix} \\sum_i^n b_ia_{i1} & \\cdots & \\sum_i^n b_ia_{ij} &\\cdots & \\sum_i^n b_ia_{in} \\end{bmatrix}\n",
    "\\begin{bmatrix} b_1 \\\\ \\vdots \\\\ b_n \\end{bmatrix} \\\\\n",
    "&= \\sum_i^n \\sum_j^n b_i a_{ij} b_j\n",
    " \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "\\frac{\\partial \\mathbf{b}^T \\mathbf{A} \\mathbf{b}}{\\partial \\mathbf{b}} \n",
    "& = \\begin{bmatrix}\n",
    " \\frac{\\partial \\sum_i^n \\sum_j^n b_i a_{ij} b_j}{\\partial b_1} \\\\\n",
    " \\vdots \\\\\n",
    " \\frac{\\partial \\sum_i^n \\sum_j^n b_i a_{ij} b_j}{\\partial b_n} \\\\\n",
    "\\end{bmatrix} \\\\\n",
    "&= \\begin{bmatrix}\n",
    " \\sum_j^n a_{1j} b_j + \\sum_i^n b_i a_{i1}  \\\\\n",
    " \\vdots \\\\\n",
    " \\sum_j^n a_{nj} b_j + \\sum_i^n b_i a_{in}  \\\\\n",
    "\\end{bmatrix} \\\\\n",
    "&= \\begin{bmatrix}\n",
    " \\sum_i^n (a_{1i} + a_{i1}) b_i  \\\\\n",
    " \\vdots \\\\\n",
    " \\sum_i^n (a_{ni} + a_{in}) b_i  \\\\\n",
    "\\end{bmatrix} \\\\\n",
    "&= \\begin{bmatrix}\n",
    " a_{11} + a_{11}  & \\cdots & a_{1i} + a_{i1} & \\cdots & a_{1n} + a_{n1} \\\\\n",
    " \\vdots & \\ddots & \\vdots & \\ddots & \\vdots \\\\\n",
    " a_{n1} + a_{1n}  & \\cdots & a_{ni} + a_{in} & \\cdots & a_{nn} + a_{nn} \\\\\n",
    "\\end{bmatrix} \n",
    "\\begin{bmatrix} b_1 \\\\ \\vdots \\\\ b_n \\end{bmatrix} \\\\\n",
    "&= (\\mathbf{A} + \\mathbf{A}^T) \\mathbf{b}\n",
    " \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ \\frac{\\partial \\text{tr}(\\mathbf{B} \\mathbf{A}) }{\\partial \\mathbf{A}}= \\mathbf{B}^T $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Proof:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "let $\\mathbf{B}$ be a $m \\times n$ matrix, and $\\mathbf{A}$ be a $n \\times m$ matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "\\mathbf{B} \\mathbf{A}\n",
    "&= \n",
    "\\underset{m \\times n}{\\begin{bmatrix}\n",
    " b_{11} & \\cdots & b_{1n} \\\\ \n",
    " \\vdots & \\ddots & \\vdots \\\\ \n",
    " b_{m1} & \\cdots & b_{mn} \\\n",
    "\\end{bmatrix}}\n",
    "\\underset{n \\times m}{\\begin{bmatrix}\n",
    " a_{11} & \\cdots & a_{1m} \\\\ \n",
    " \\vdots & \\ddots & \\vdots \\\\ \n",
    " a_{n1} & \\cdots & a_{nm} \\\n",
    "\\end{bmatrix}}\n",
    "= \\underset{m \\times m}{\\begin{bmatrix}\n",
    " \\sum_i^n b_{1i} a_{i1} & \\cdots & \\sum_i^n b_{1i}a_{im} \\\\ \n",
    " \\vdots & \\ddots & \\vdots \\\\ \n",
    " \\sum_i^n b_{mi}a_{i1} & \\cdots & \\sum_i^n b_{mi} a_{im} \\\n",
    "\\end{bmatrix}}\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "\\text{tr}(\\mathbf{B} \\mathbf{A}) = \\sum_j^m \\sum_i^n b_{ji} a_{ij}\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "\\frac{\\partial \\text{tr}(\\mathbf{B} \\mathbf{A}) }{\\partial \\mathbf{A}}\n",
    "&=\\underset{n \\times m}{\\begin{bmatrix}\n",
    " \\frac{\\partial \\sum_j^m \\sum_i^n b_{ji} a_{ij}}{\\partial a_{11}} & \\cdots  & \\frac{\\partial \\sum_j^m \\sum_i^n b_{ji} a_{ij}}{\\partial a_{1m}} \\\\ \n",
    " \\vdots & \\ddots & \\vdots \\\\ \n",
    " \\frac{\\partial \\sum_j^m \\sum_i^n b_{ji} a_{ij}}{\\partial a_{n1}} & \\cdots &  \\frac{\\partial \\sum_j^m \\sum_i^n b_{ji} a_{ij}}{\\partial a_{nm}} \n",
    "\\end{bmatrix}} \\\\\n",
    "&= \\underset{n \\times m}{\\begin{bmatrix} \n",
    " b_{11} & \\cdots & b_{m1} \\\\\n",
    " \\vdots & \\ddots & \\vdots \\\\ \n",
    " b_{1n} & \\cdots & b_{mn} \\\\\n",
    "\\end{bmatrix}} \\\\\n",
    "&= \\mathbf{B}^T\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\frac{\\partial \\log \\left| \\mathbf{A} \\right|}{\\partial \\mathbf{A}} = \\mathbf{A}^{-T} \\triangleq (\\mathbf{A}^{-1})^T$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Proof for 2-D matrix:\n",
    "\n",
    "\\begin{align*}\n",
    "A &= \\begin{bmatrix}\n",
    "a & b \\\\ \n",
    "c & d \\\\\n",
    "\\end{bmatrix} \\\\\n",
    "|A| &= ad - bc \\\\\n",
    "A^{-1} &= \\begin{bmatrix}\n",
    "d & -b \\\\ \n",
    "-c & a \\\\\n",
    "\\end{bmatrix} \\\\\n",
    "\\frac{\\partial \\ln|A|}{\\partial A} &= \\frac{1}{|A|} \\begin{bmatrix}\n",
    "\\frac{\\partial |A|}{a} & \\frac{\\partial |A|}{b} \\\\ \n",
    "\\frac{\\partial |A|}{c} & \\frac{\\partial |A|}{d}\n",
    "\\end{bmatrix} \\\\\n",
    "&= \\frac{1}{|A|} \\begin{bmatrix}\n",
    "d & -c \\\\ \n",
    "-b & a\n",
    "\\end{bmatrix} \\\\\n",
    "&= (A^{-1})^T\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\text{tr} (\\mathbf{A} \\mathbf{B} \\mathbf{C}) = \\text{tr} (\\mathbf{C} \\mathbf{A} \\mathbf{B}) = \\text{tr} (\\mathbf{B} \\mathbf{C} \\mathbf{A})$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Proof:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, calculate the element of a general three-matrix multiplication"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "\\underset{m \\times q}{\\mathbf{ABC}}\n",
    "&= \n",
    "\\underset{m \\times n}{\\begin{bmatrix}\n",
    " a_{11} & \\cdots & a_{1n} \\\\ \n",
    " \\vdots & \\ddots & \\vdots \\\\ \n",
    " a_{m1} & \\cdots & a_{mn} \\\n",
    "\\end{bmatrix}}\n",
    "\\underset{n \\times p}{\\begin{bmatrix}\n",
    " b_{11} & \\cdots & b_{1p} \\\\ \n",
    " \\vdots & \\ddots & \\vdots \\\\ \n",
    " b_{n1} & \\cdots & b_{np} \\\n",
    "\\end{bmatrix}}\n",
    "\\underset{p \\times q}{\\begin{bmatrix}\n",
    " c_{11} & \\cdots & c_{1q} \\\\ \n",
    " \\vdots & \\ddots & \\vdots \\\\ \n",
    " c_{p1} & \\cdots & b_{pq} \\\n",
    "\\end{bmatrix}} \\\\\n",
    "&=\n",
    "\\underset{m \\times p}{\\begin{bmatrix}\n",
    " \\sum_i^n a_{1i} b_{i1} & \\cdots & \\sum_i^n a_{1i} b_{ip} \\\\ \n",
    " \\vdots &  \\ddots & \\vdots \\\\ \n",
    " \\sum_i^n a_{mi} b_{i1} & \\cdots  & \\sum_i^n a_{mi} b_{ip} \n",
    "\\end{bmatrix}}\n",
    "\\underset{p \\times q}{\\begin{bmatrix}\n",
    " c_{11} & \\cdots & c_{1q} \\\\ \n",
    " \\vdots & \\ddots & \\vdots \\\\ \n",
    " c_{p1} & \\cdots & b_{pq} \\\n",
    "\\end{bmatrix}} \\\\\n",
    "&=  \\underset{m \\times q}{\\begin{bmatrix}\n",
    "\\sum_j^p \\sum_i^n a_{1i} b_{ij} c_{j1}  & \\cdots  & \\sum_j^p  \\sum_i^n a_{1i} b_{ij} c_{jq} \\\\\n",
    " \\vdots & \\ddots & \\vdots \\\\ \n",
    "\\sum_j^p \\sum_i^n a_{mi} b_{ij}  c_{j1} & \\cdots  & \\sum_j^p \\sum_i^n a_{mi} b_{ij} c_{jq} \\\\\n",
    "\\end{bmatrix}}\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At row $x$, column $y$, the element of $\\mathbf{ABC}$ is $\\sum_j^p \\sum_i^n a_{xi} b_{ij} c_{jy}$, then"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, to proove the cyclic property, the shape of the matrices need to satisfy:\n",
    "\n",
    "* $\\mathbf{A}$: $m \\times n$\n",
    "* $\\mathbf{B}$: $n \\times p$\n",
    "* $\\mathbf{C}$: $p \\times m$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, we have"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "\\text{tr}{(\\underset{m \\times m}{\\mathbf{ABC})}}  &= \\text{tr}{(\\underset{m \\times n}{\\mathbf{A}} \\; \\underset{n \\times p}{\\mathbf{B}} \\; \\underset{p \\times m}{\\mathbf{C}} )} =\\sum_k^m \\sum_j^p \\sum_i^n a_{ki} b_{ij} c_{jk} \\\\\n",
    "\\text{tr}{(\\underset{n \\times n}{\\mathbf{BCA})}}  &= \\text{tr}{(\\underset{n \\times p}{\\mathbf{B}} \\; \\underset{p \\times m}{\\mathbf{C}} \\; \\underset{m \\times n}{\\mathbf{A}} )} = \\sum_i^n \\sum_k^m \\sum_j^p b_{ij} c_{jk} a_{ki} \\\\\n",
    "\\text{tr}{(\\underset{p \\times p}{\\mathbf{BCA})}}  &= \\text{tr}{(\\underset{p \\times m}{\\mathbf{C}} \\; \\underset{m \\times n}{\\mathbf{A}} \\; \\underset{n \\times p}{\\mathbf{B}} )} = \\sum_j^p \\sum_i^n \\sum_k^m  c_{jk} a_{ki} b_{ij} \\\\\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Therefore, the three are equal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### A simpler proof by induction for the more general case:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "\\underset{m \\times n}{\\mathbf{A}} \\; \\underset{n \\times m}{\\mathbf{B}}\n",
    "&= \n",
    "\\underset{m \\times n}{\\begin{bmatrix}\n",
    " a_{11} & \\cdots & a_{1n} \\\\ \n",
    " \\vdots & \\ddots & \\vdots \\\\ \n",
    " a_{m1} & \\cdots & a_{mn} \\\n",
    "\\end{bmatrix}}\n",
    "\\underset{n \\times m}{\\begin{bmatrix}\n",
    " b_{11} & \\cdots & b_{1m} \\\\ \n",
    " \\vdots & \\ddots & \\vdots \\\\ \n",
    " b_{n1} & \\cdots & b_{nm} \\\n",
    "\\end{bmatrix}} \n",
    "= \\underset{m \\times m}{\\begin{bmatrix}\n",
    " \\sum_i^n a_{1i} b_{i1} & \\cdots & \\cdots & \\cdots & \\sum_i^n a_{1i} b_{im} \\\\ \n",
    " \\vdots &  \\ddots & \\vdots & \\ddots & \\vdots \\\\ \n",
    " \\vdots &  \\ddots & \\sum_i^n a_{ji} b_{ij} & \\ddots & \\vdots\\\\ \n",
    " \\vdots &  \\ddots & \\vdots & \\ddots & \\vdots \\\\ \n",
    " \\sum_i^n a_{mi} b_{i1} & \\cdots  & \\cdots  & \\cdots & \\sum_i^n a_{mi} b_{im} \\\\\n",
    "\\end{bmatrix}}\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then,"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "\\text{tr}{(\\underset{m \\times n}{\\mathbf{A}} \\; \\underset{n \\times m}{\\mathbf{B}}})\n",
    "&= \\sum_j^m \\sum_i^n a_{ji} b_{ij}\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "\\underset{n \\times m}{\\mathbf{B}} \\; \\underset{m \\times n}{\\mathbf{A}}\n",
    "&= \n",
    "\\underset{n \\times m}{\\begin{bmatrix}\n",
    " b_{11} & \\cdots & b_{1m} \\\\ \n",
    " \\vdots & \\ddots & \\vdots \\\\ \n",
    " b_{n1} & \\cdots & b_{nm} \\\n",
    "\\end{bmatrix}} \n",
    "\\underset{m \\times n}{\\begin{bmatrix}\n",
    " a_{11} & \\cdots & a_{1n} \\\\ \n",
    " \\vdots & \\ddots & \\vdots \\\\ \n",
    " a_{m1} & \\cdots & a_{mn} \\\n",
    "\\end{bmatrix}}\n",
    "= \\underset{n \\times n}{\\begin{bmatrix}\n",
    " \\sum_j^m b_{1j} a_{j1} & \\cdots & \\cdots & \\cdots & \\sum_j^m b_{1j} a_{jn} \\\\ \n",
    " \\vdots &  \\ddots & \\vdots & \\ddots & \\vdots \\\\ \n",
    " \\vdots &  \\ddots & \\sum_j^m b_{ij} a_{ji} & \\ddots & \\vdots\\\\ \n",
    " \\vdots &  \\ddots & \\vdots & \\ddots & \\vdots \\\\ \n",
    " \\sum_j^m b_{nj} a_{j1} & \\cdots  & \\cdots  & \\cdots & \\sum_j^m b_{nj} a_{jn} \\\\\n",
    "\\end{bmatrix}}\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then,"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "\\text{tr}{(\\underset{n \\times m}{\\mathbf{B}} \\; \\underset{m \\times n}{\\mathbf{A}} })\n",
    "&= \\sum_i^n \\sum_j^m b_{ij} a_{ji}\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So \n",
    "\n",
    "$$\\text{tr}(\\mathbf{AB}) == \\text{tr}(\\mathbf{BA})$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we extend it to the more general case, In the case of $\\mathbf{tr}(\\mathbf{A_1} \\dots \\mathbf{A}_n)$,"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $\\mathbf{A}_1 \\dots A_{n-k} = \\mathbf{X}$, and $\\mathbf{A}_{n-k + 1} \\dots \\mathbf{A}_n = \\mathbf{Y}$, then"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "\\text{tr}(\\mathbf{A}_1 \\dots \\mathbf{A}_n) = \\text{tr}(\\mathbf{X Y}) &= \\text{tr}(\\mathbf{YX}) \\\\\n",
    "\\text{tr}(\\mathbf{A}_1 \\dots \\mathbf{A}_{n-k} \\mathbf{A}_{n-k + 1} \\dots \\mathbf{A}_n ) &= \\text{tr}(\\mathbf{A}_{n-k + 1} \\dots \\mathbf{A}_n \\mathbf{A}_1 \\dots \\mathbf{A}_{n-k}) \\\\\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "where $k \\in \\{1, ... n\\}$."
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}