Solutions to Part IV Problems.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem IV.1.1\n",
    "\n",
    "$w=e^{2\\pi i/N}$ and $\\omega = e^{-2\\pi i/N} = \\bar{w}$, so we have the complex dot product between the $p$th row of $F$ and $q$th column of $\\Omega$, we have\n",
    "\n",
    "\\begin{align*}\n",
    "\\bar{p}^Tq &= 1 + \\bar{w}^p\\omega^q + \\dots + \\bar{w}^{(N-1)p}\\omega^{(N-1)q}\\\\\n",
    "&= 1 + \\omega^p\\omega^q + \\dots + \\omega^{(N-1)p}\\omega^{(N-1)q}\\\\\n",
    "&= 1 + \\omega^{p+q} + \\dots + \\omega^{(N-1)(p+q)}\\\\\n",
    "&= \\frac{1-\\omega^{N(p+q)}}{1-\\omega}\\\\\n",
    "&= \\frac{1-e^{-2\\pi i(p+q)}}{1-\\omega}\\\\\n",
    "&= 0\\\\\n",
    "\\end{align*}\n",
    "\n",
    "#### Problem IV.1.2\n",
    "\n",
    "$w=e^{2\\pi i/N}$, $w^M_N = (w_N)^M = \\left(e^{2\\pi i/N}\\right)^M = \\left(e^{2\\pi i/N}\\right)^{\\frac{N}{2}} = e^{\\pi i} = -1$\n",
    "\n",
    "\n",
    "#### Problem IV.1.3\n",
    "\n",
    "With $w=e^{2\\pi i/3} = -\\frac{1}{2} + \\frac{\\sqrt{3}}{2}i$, then $\\omega = \\bar{w} = -\\frac{1}{2} - \\frac{\\sqrt{3}}{2}i$\n",
    "\n",
    "$F_3 = \\begin{bmatrix}w^{0\\times 0} & w^{1\\times 0} & w^{2\\times 0} \\\\ w^{0\\times 1} & w^{1\\times 1} & w^{2\\times 1} \\\\ w^{0\\times 2} & w^{1\\times 2} & w^{2\\times 2} \\\\ \\end{bmatrix} = \\begin{bmatrix}1 & 1 & 1 \\\\ 1 & w & w^2 \\\\ 1 & w^2 & w^4\\end{bmatrix}$\n",
    "\n",
    "Then \n",
    "$\\Omega_3 = \\begin{bmatrix}1 & 1 & 1 \\\\ 1 & \\omega & \\omega^2 \\\\ 1 & \\omega^2 & \\omega^4\\end{bmatrix}$\n",
    "\n",
    "The permutation matrix is then $P_3=\\begin{bmatrix}1 & 0 & 0 \\\\ 0 & 0 & 1 \\\\ 0 & 1 & 0 \\end{bmatrix}$\n",
    "\n",
    "We have $F_3P_3 = \\begin{bmatrix}1 & 1 & 1 \\\\ 1 & w^2 & w \\\\ 1 & w^4 & w^2\\end{bmatrix} $\n",
    "\n",
    "Note, $w^2 = e^{4\\pi i/3} = e^{(2\\pi - 2\\pi /3)i} = e^{2\\pi i}e^{- 2\\pi i/3} = e^{- 2\\pi i/3}=\\omega$, and $w^4=w^2w^2 = \\omega^2$, $\\omega^2 = e^{-4\\pi i/3} = e^{(-2\\pi + 2\\pi /3)i}=e^{-2\\pi i}e^{2\\pi i/3} = e^{2\\pi i/3}=w$\n",
    "\n",
    "So we see that $\\Omega_3 = F_3P_3$.\n",
    "\n",
    "Similarly we can prove that $F_3 = \\Omega_3 P_3$.\n",
    "\n",
    "#### Problem IV.1.4\n",
    "\n",
    "$\\Omega_4 = \\begin{bmatrix}1 & 1 & 1 & 1 \\\\ 1 & -i & -1 & i \\\\ 1 & -1 & 1 & -1 \\\\ 1 & i & -1 & -i\\end{bmatrix}$\n",
    "\n",
    "So we have $c=\\Omega_4 f = \\begin{bmatrix}1 \\\\ -i \\\\ -1 \\\\ i \\end{bmatrix}$\n",
    "\n",
    "Now the $F_4 = \\begin{bmatrix}1 & 1 & 1 & 1 \\\\ 1 & i & -1 & -i \\\\ 1 & -1 & 1 & -1 \\\\ 1 & -i & -1 & i\\end{bmatrix}$\n",
    "we have $F_4 c = \\begin{bmatrix}0 \\\\ 4 \\\\ 0 \\\\ 0 \\end{bmatrix} = 4f$\n",
    "\n",
    "#### Problem IV.1.5\n",
    "\n",
    "With $N=3$, we have $w_3=e^{2\\pi i/3} = -\\frac{1}{2} + \\frac{\\sqrt{3}}{2}i$\n",
    "\n",
    "$F_3 = \\begin{bmatrix}w^{0\\times 0}_3 & w^{1\\times 0}_3 & w^{2\\times 0}_3 \\\\ w^{0\\times 1}_3 & w^{1\\times 1}_3 & w^{2\\times 1}_3 \\\\ w^{0\\times 2}_3 & w^{1\\times 2}_3 & w^{2\\times 2}_3 \\\\ \\end{bmatrix} = \\begin{bmatrix}1 & 1 & 1 \\\\ 1 & w_3 & w^2_3 \\\\ 1 & w^2_3 & w^4_3\\end{bmatrix}$\n",
    "\n",
    "The permutation matrix for the even-odd rows is \n",
    "\n",
    "\\begin{align*}\n",
    "P &= \\begin{bmatrix} 1 & 0 & 0 & 0 &0 & 0 \\\\ 0 & 0 & 1 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 1\\end{bmatrix}\n",
    "\\end{align*}\n",
    "\n",
    "And the Matrix $D_3 = \\begin{bmatrix} 1 & 0 & 0 \\\\ 0 & w_6 & 0 \\\\ 0 & 0 & w^2_6\\end{bmatrix}$\n",
    "\n",
    "We have \n",
    "\n",
    "\\begin{align*}\n",
    "F_6 &= \\begin{bmatrix}I_3 & D_3 \\\\ I_3 & -D_3 \\end{bmatrix} \\begin{bmatrix}F_3 & 0 \\\\ 0 & F_3 \\end{bmatrix}P \\\\\n",
    "&= \\begin{bmatrix} 1 & 0 & 0 & 1 &0 & 0 \\\\ 0 & 1 & 0 & 0 & w_6 & 0 \\\\ 0 & 0 & 1 & 0 & 0 & w^2_6 \\\\ 1 & 0 & 0 & -1 & 0 & 0 \\\\ 0 & 1 & 0 & 0 & -w_6 & 0 \\\\ 0 & 0 & 1 & 0 & 0 & -w^2_6\\end{bmatrix} \\begin{bmatrix}1 & 1 & 1 & 0 & 0 & 0 \\\\ 1 & w_3 & w^2_3 & 0 & 0 & 0 \\\\ 1 & w^2_3 & w^4_3 &0 & 0 & 0 \\\\ 0 & 0 & 0 & 1 & 1 & 1 \\\\ 0 & 0 & 0 &1 & w_3 & w^2_3 \\\\0 & 0 & 0 & 1 & w^2_3 & w^4_3\\end{bmatrix} \\begin{bmatrix} 1 & 0 & 0 & 0 &0 & 0 \\\\ 0 & 0 & 1 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 1\\end{bmatrix}\\\\\n",
    "&= \\begin{bmatrix} 1 & 0 & 0 & 1 &0 & 0 \\\\ 0 & 1 & 0 & 0 & w_6 & 0 \\\\ 0 & 0 & 1 & 0 & 0 & w^2_6 \\\\ 1 & 0 & 0 & -1 & 0 & 0 \\\\ 0 & 1 & 0 & 0 & -w_6 & 0 \\\\ 0 & 0 & 1 & 0 & 0 & -w^2_6\\end{bmatrix} \\begin{bmatrix}1 & 0 & 1 & 0 & 1 & 0 \\\\ 1 & 0 & w_3 & 0 & w^2_3 & 0 \\\\ 1 & 0 & w^2_3 & 0 & w^4_3 &0 \\\\ 0 & 1 & 0 & 1 & 0 & 1 \\\\ 0 & 1 & 0 & w_3 & 0 & w^2_3 \\\\0 & 1 & 0 & w^2_3 & 0 & w^4_3\\end{bmatrix}\\\\\n",
    "&= \\begin{bmatrix} 1 & 1 & 1 & 1 &1 & 1 \\\\ 1 & w_6 & w_3 & w_3w_6 & w^2_3 & w_6w^2_3 \\\\ 1 & w^2_6 & w^2_3 & w^2_3w^2_6 & w^4_3 & w^2_6w^4_3 \\\\ 1 & -1 & 1 & -1 & 1 & -1 \\\\ 1 & -w_6 & w_3 & -w_3w_6 & w^2_3 & -w_6w^2_3 \\\\ 1 & -w^2_6 & w^2_3 & -w_3w_6 & w^4_3 & -w^2_6w^4_3\\end{bmatrix}\\\\\n",
    "\\end{align*}\n",
    "\n",
    "Since we have $w_3 = w^2_6, w^3_6 = -1, w^4_3 = w_3$, it's easy to check that the $F_6$ is the correct matrix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem IV.1.6\n",
    "If $N=6$, We have $w=e^{2\\pi i/6}$, then \n",
    "\n",
    "$1+w+w^2+w^3+w^4+w^5 = \\frac{1-w^6}{1-w} = \\frac{1-e^{2\\pi i}}{1-w} = 0$\n",
    "\n",
    "#### Problem IV.1.7\n",
    "\n",
    "Since $\\int^{\\pi}_{-\\pi} \\cos(nx)dx = 0$ for any $n$, and $\\int^{\\pi}_{-\\pi} \\cos(nx)\\cos(mx)dx = 0$, when $n\\ne m$, we have\n",
    "\n",
    "* $2\\pi a_0 = \\int^{\\pi}_{-\\pi}f(x)dx = \\pi$, we have $a_0 = \\frac{1}{2}$\n",
    "* $\\int^{\\pi}_{-\\pi}\\cos(x)f(x)dx = \\int^{\\pi/2}_{-\\pi/2}\\cos(x)dx = 2$, $\\int^{\\pi}_{-\\pi}a_1\\cos^2(x)dx=a_1\\pi$, so $a_1 = \\frac{\\pi}{2}$\n",
    "\n",
    "#### Problem IV.1.8\n",
    "\n",
    "If $A$ is orthogonal, then $a_i$ are orthogonal to each other. Also we have $AA^T=QQ^T=I$, so $AA^Tx=x$.\n",
    "The $n$ pieces in $AA^Tx$ are orthogonal vectors to each other. We can treat $a_i$ as basis functions. \n",
    "Since $a^T_ia_i = 1$, that's equivalent to normalize the $b_k$ in Fourier matrix $F$, so we have $F\\Omega = I$\n",
    "\n",
    "\n",
    "#### Problem IV.1.9\n",
    "* $f=\\frac{1}{4}\\begin{bmatrix}1 \\\\ 0 \\\\ 1 \\\\ 0 \\end{bmatrix} $, so we have \n",
    "\n",
    "$x = \\Omega_4f = \\frac{1}{4}\\begin{bmatrix}1 & 1 & 1 & 1 \\\\ 1 & -i & -1 & i \\\\ 1 & -1 & 1 & -1 \\\\ 1 & i & -1 & -i\\end{bmatrix} \\begin{bmatrix}1 \\\\ 0 \\\\ 1 \\\\ 0 \\end{bmatrix} = \\begin{bmatrix}\\frac{1}{2} \\\\ 0 \\\\ \\frac{1}{2} \\\\ 0 \\end{bmatrix}$\n",
    "\n",
    "* $f = \\frac{1}{4}\\begin{bmatrix}0 \\\\ 0 \\\\ 0 \\\\ 1 \\end{bmatrix}$, so we have \n",
    "\n",
    "$y = \\Omega_4f = \\frac{1}{4}\\begin{bmatrix}1 & 1 & 1 & 1 \\\\ 1 & -i & -1 & i \\\\ 1 & -1 & 1 & -1 \\\\ 1 & i & -1 & -i\\end{bmatrix} \\begin{bmatrix}0 \\\\ 0 \\\\ 0 \\\\ 1 \\end{bmatrix} = \\frac{1}{4}\\begin{bmatrix}1 \\\\ i \\\\ -1 \\\\ -i \\end{bmatrix}$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem IV.2.1\n",
    "\n",
    "* The convolution of $c$ and $d$: $c * d = (6,5,14,5,6)$\n",
    "* The cyclic convolution: $c\\circledast d= (11, 11, 14)$\n",
    "\n",
    "#### Problem IV.2.2\n",
    "\n",
    "\\begin{align*}\n",
    "\\left(\\sum^2_{m=0}w^{km}c_m\\right)\\left(\\sum^2_{n=0}w^{kn}d_n\\right) &= \\left(c_0+w^kc_1+w^{2k}c_2\\right)\\left(d_0+w^kd_1+w^{2k}d_2\\right)\\\\\n",
    "&= c_0d_0 + w^kc_0d_1 + w^{2k}c_0d_2 + w^kc_1d_0 + w^{2k}c_1d_1 + w^{3k}c_1d_2 + w^{2k}c_2d_0 + w^{3k}c_2d_1 + w^{4k}c_2d_2\\\\\n",
    "&= c_0d_0 + w^kc_0d_1 + w^{2k}c_0d_2 + w^kc_1d_0 + w^{2k}c_1d_1 + c_1d_2 + w^{2k}c_2d_0 + c_2d_1 + w^kc_2d_2\\\\\n",
    "&= (c_0d_0 + c_1d_2+ c_2d_1) + w^k(c_0d_1 + c_1d_0+ c_2d_2) + w^{2k}(c_0d_2  + c_1d_1  + c_2d_0)  \\\\\n",
    "&= (c\\circledast d)_0 + w^k(c\\circledast d)_1 + w^{2k}(c\\circledast d)_2  \\\\\n",
    "&= \\sum^2_{p=0}w^{kp}(c\\circledast d)_p\\\\\n",
    "\\end{align*}\n",
    "\n",
    "#### Problem IV.2.3\n",
    "\n",
    "If $c*d=e$, we are basically flipping the $d$ vector w.r.t. $y$-axis, and shift it towards $c$ vector such that they have overlaps. Whenever they overlap, we multiply the corresponding elements and add the sums. It's clear that each element in $c$ will multiply with each element of $d$ one and only once as the flipped $d$ shifting forward. Each element of $e$ is a sum of a subset of these products. Since each product only happens once, their total sum should be the same regardless how we add them up. Then we have $(\\sum c_i)(\\sum d_i) = \\sum e_i$. \n",
    "\n",
    "#### Problem IV.2.4\n",
    "\n",
    "We have $(CD)q_k = CDq_k = C\\lambda_k(D)q_k = \\lambda_k(D)Cq_k = \\lambda_k(D)\\lambda_k(C)q_k$, on the other hand\n",
    "$(CD)q_k = \\lambda_k(CD)q_k$, so we have $\\lambda_k(CD) = \\lambda_k(D)\\lambda_k(C)$\n",
    "\n",
    "#### Problem IV.2.5\n",
    "\n",
    "We have $F_4 = \\begin{bmatrix}1 & 1 & 1 & 1 \\\\ 1 & i & -1 & -i \\\\ 1 & -1 & 1 & -1 \\\\ 1 & -i & -1 & i\\end{bmatrix}$\n",
    "\n",
    "The eigenvalues of $C$ are $F_4c = \\begin{bmatrix}1 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix}$ \n",
    "\n",
    "The three roots for $1+z+z^2+z^3=0$ are $z=e^{2\\pi ki/4}$, for $k=1,2,3$\n",
    "\n",
    "#### Problem IV.2.6\n",
    "\n",
    "The eigenvalues of $C$ is $Fc$, when $Fc$ has no zeroes, that means no zero eigenvalues, so the matrix $C$ is invertible. \n",
    "\n",
    "$\\sum^{N-1}_0 c_je^{ij\\theta} = \\begin{bmatrix}1 & e^{\\theta i} & \\dots & e^{(N-1)\\theta i}\\end{bmatrix}\\begin{bmatrix}c_0\\\\c_1\\\\ \\vdots \\\\ c_{N-1}\\end{bmatrix}$\n",
    "\n",
    "When $\\theta = \\frac{2\\pi}{N}$, we have $e^{\\theta i} = e^{2\\pi i/N} = w$, so the sum is exactly the dot product of each row of $F$ with $c$. And we want each dot product to be nonzero, exactly as required in the statement.\n",
    "\n",
    "#### Problem IV.2.7\n",
    "\n",
    "Since $Fe=(Fc).*(Fd)$, we have $Fd = (Fe)./(Fc)$, then we apply deconvolution, to get $d=F^{-1}((Fe)./(Fc)) = \\frac{1}{N}\\Omega((Fe)./(Fc))$, where $./$ indicates element-wise division.\n",
    "\n",
    "#### Problem IV.2.8\n",
    "\n",
    "The solution follows quickly from Cauchy-Schwarz inequality: $c^T(S^nc)=\\langle c,S^nc\\rangle^2\\leq \\langle c,c\\rangle\\langle S^nc, S^nc\\rangle=\\langle c,c\\rangle^2=||c||=c^Tc$. \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem IV.3.1\n",
    "\n",
    "A matrix is invertible when it has no zero eigenvalues, so for $A\\oplus B$ to be invertible, we want $\\lambda_i + \\mu_j \\ne 0$ for every $i,j$. If (eigenvalue of $A$) = - (eigenvalue of $B$), then $A \\oplus B$ is not invertible, its rank is less than $n^2$. \n",
    "\n",
    "Example: \n",
    "$A = \\begin{bmatrix} 1 & 2 \\\\ 3 & 4 \\end{bmatrix}$, and $B=\\begin{bmatrix} -4 & 2 \\\\ 3 & -1 \\end{bmatrix}$\n",
    "\n",
    "Then we have $A\\oplus B = A\\otimes I_2 + I_2 \\otimes B = \\begin{bmatrix} I_2 & 2I_2 \\\\ 3I_2 & 4I_2 \\end{bmatrix} + \\begin{bmatrix} B & 0 \\\\ 0 & B \\end{bmatrix}+ \\begin{bmatrix} I_2 + B & 2I_2 \\\\ 3I_2 & 4I_2 +B \\end{bmatrix} = \\begin{bmatrix} -3 & 2 & 2 & 0  \\\\ 3 & 0 & 0 & 2 \\\\ 3 & 0 & 0 & 2 \\\\ 0 & 3 & 3 & 3 \\end{bmatrix}$\n",
    "\n",
    "which is rank -3.\n",
    "\n",
    "#### Problem IV.3.2\n",
    "\n",
    "Suppose the eigenvalues of $A$ and $B$ are $\\lambda_i$ and $\\mu_i$ respectively. Since both matrices are symmetric positive definitie, their eigenvalues are all positive. \n",
    "\n",
    "* $A\\otimes B$: Its eigenvalues are products of $\\lambda\\mu$, which are all greater than 0.\n",
    "* $A\\oplus B$: Its eigenvalues are sums of $\\lambda + \\mu$, which are all greater than 0 as well.\n",
    "\n",
    "So we conclude that $A\\otimes B$ and $A\\oplus B$ are all positive definite. The symmetric is clear from their definitions as well.\n",
    "\n",
    "#### Problem IV.3.3\n",
    "\n",
    "Note, multiplying $P$ in front of a matrix permutates its rows, while multiplying $P$ on the back of a matrix permutates its columns. \n",
    "\n",
    "Let the size of $A$ be $m\\times n$, and the size of $B$ be $M\\times N$.\n",
    "\n",
    "Consider the $(i-1)M+k$th row in $A\\otimes B$, this row comes from the product of the $i$th row from $A$, $a_{i,}$, with the $k$th row from $B$, i.e. $b_{k,}$. This row looks like\n",
    "\n",
    "\\begin{align*}\n",
    "a_{i1}b_{k1},a_{i1}b_{k2},\\dots, a_{i1}b_{kN},a_{i2}b_{k1},a_{i2}b_{k2},\\dots,a_{i2}b_{kN},\\dots, a_{i(n-1)}b_{k1},a_{i(n-1)}b_{k2},\\dots,a_{i(n-1)}b_{kN},a_{in}b_{k1},a_{in}b_{k2},\\dots,a_{in}b_{kN}\\\\\n",
    "\\end{align*}\n",
    "\n",
    "To have the same elements of $b_{kq}a_{ip} = a_{ip}b_{kq}$ in the matrix of $B\\otimes A$, they are on the row of $(k-1)m+i$. This row looks like\n",
    "\n",
    "\\begin{align*}\n",
    "b_{k1}a_{i1},b_{k1}a_{i2},\\dots, b_{k1}a_{in},b_{k2}a_{i1},b_{k2}a_{i2},\\dots,b_{k2}a_{in},\\dots, b_{k(N-1)}a_{i1},b_{k(N-1)}a_{i2},\\dots,b_{k(N-1)}a_{in},b_{kN}a_{i1},b_{kN}a_{i2},\\dots,b_{kN}a_{in}\\\\\n",
    "\\end{align*}\n",
    "\n",
    "So we should switch every $(i-1)M+k$th row in $A\\otimes B$ with the $(k-1)m+i$th row. \n",
    "\n",
    "We also need switch the columns in $B\\otimes A$ as well, consider the entry of $b_{kq}a_{ip}$ of $B\\otimes A$, its column position is $(q-1)n+p$. The element from $A\\otimes B$ with the same value, i.e. $a_{ip}b_{kq}$ is at the position of $(p-1)N+q$ So we need swtich all columns between $(q-1)n+p$ and $(p-1)N+q$. \n",
    "\n",
    "Combine the two conditions together, we see that $P$ should switch rows satisfying following condition:\n",
    "\n",
    "$(i-1)M+k = (q-1)n+p$ and $(k-1)m+i = (p-1)N+q$\n",
    "\n",
    "* For $A\\otimes B$, its eigenvalues are always the products of eigenvalues from $A$ and $B$, this is also true for $B\\otimes A$, so their eigenvalues are the same. \n",
    "\n",
    "#### Problem IV.3.4\n",
    "\n",
    "According to equation (19), we have \n",
    "\n",
    "$y = (F\\otimes G)x = (F\\otimes G)vec(X) = vec(GXF^T) = Y$\n",
    "\n",
    "#### Problem IV.3.5\n",
    "\n",
    "We have $x=vec(X) = vec(G^{-1}B(F^{-1})^T) = (F^{-1}\\otimes G^{-1})vec(B) = (F^{-1}\\otimes G^{-1})b$, notice that $F^{-1}\\otimes G^{-1}$ is the inverse of $F\\otimes G$, multiply both sides by $F\\otimes G$, we have\n",
    "\n",
    "$(F\\otimes G)x = b$, which recovers the original equation.\n",
    "\n",
    "Solving $Ax=b$ is on the order of $O(n^3)$, where $n$ is the dimension of matrix $A$. We have $(F\\otims G)x=b$, where $(F\\otimes G)$ has a dimension of $n^2\\times n^2$, so the total cost to solve $b$ using the original equation is $O\\left((n^2)^3\\right) = O(n^6)$. \n",
    "\n",
    "With the equivalent system, we have to find $Z$ with $GZ=B$, and then find $X$ from $XF^T=Z$, both costs are $O(n^3)$ because all the matrices are size $n$. \n",
    "\n",
    "\n",
    "#### Problem IV.3.6\n",
    "\n",
    "If an image look like its pixels produced a Kronecker product $A\\otimes B$, that means the intensity at each pixel is a product of a scalar (from $A$) with a constant matrix $B$. So the image might have a pattern of grids, on each grid, the content of the image are simliar to each other and differ just by a constant ratio. \n",
    "\n",
    "#### Problem IV.3.7\n",
    "\n",
    "We can follow the same pattern for 1D FFT as in IV.1, e.g. equation (11), where we decompose the Fourier matrix $\\Omega_N$ into $\\Omega_{\\frac{N}{2}$, and recurse until there's only 1 element in the matrix. \n",
    "\n",
    "In 2D, it now involves Kronecker product which is more complicate. \n",
    "Since in 2D DFT, we apply 1D DFT twice on rows and columns, so we probably can count them independently here, so \n",
    "\n",
    "For an $n$ by $n$ image, since we have reductions from both dimensions, the final count for size $n=2^l$ is reduced from $n^2n^2=n^4$ to $\\frac{1}{4}n^2l = \\frac{1}{4}n^2 log_2(n)$\n",
    "\n",
    "Each level $l$ will need $\\frac{1}{4}n^2$ calculations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem IV.4.1\n",
    "\n",
    "Let $h_k = \\frac{j\\pi k h}{N+1}$, pick the $k$th row in equation (3), we have \n",
    "\n",
    "$\\sin h_{k-1} - 2\\sin h_k + \\sin h_{k+1} = \\lambda_j \\sin h_k$, solve for $\\lambda_j$, we have\n",
    "\n",
    "$\\lambda_j = \\frac{\\sin h_{k-1} + \\sin h_{k+1}}{\\sin h_k} - 2 = \\frac{2\\sin \\frac{h_{k-1} + h_{k+1}}{2} \\cos \\frac{h_{k-1} - h_{k+1}}{2}}{\\sin h_k}  -2 = \\frac{2\\sin h_k \\cos h_1}{\\sin h_k} - 2 = 2(\\cos h_1 - 1) = 2(\\cos \\frac{j\\pi h}{N+1} - 1)$\n",
    "\n",
    "#### Problem IV.4.2\n",
    "\n",
    "Suppose matrix $D$ has eigenvalues of $\\lambda$ and eigenvectors of $u$,\n",
    "\n",
    "For $K=I\\otimes D + D\\otimes I = I \\oplus D$, from Kronecker section IV.3, the eigenvalues of $K$ are $\\lambda_{ij}=\\lambda_i + \\lambda_j =2(\\cos \\frac{(i+j)\\pi h}{N+1} - 2) $ and eigenvectors are: $u_{ij} = u_i \\otimes u_j$\n",
    "\n",
    "#### Problem IV.4.3\n",
    "\n",
    "The Laplace with 3 variables is $\\frac{\\partial^2{u}}{\\partial{x}^2}+\\frac{\\partial^2{u}}{\\partial{y}^2} + \\frac{\\partial^2{u}}{\\partial{z}^2} = f(x,y,z)$\n",
    "\n",
    "In 2D grid, we have $x,y$ discrete points on a $N\\times N$ grid, and we need compute the derivatives on all the $(x_i,y_i)$ grid points w.r.t. $x$ and $y$ separately. So for $x$ component, we have $K_x=I_N\\otimes D_N$, which has $N^2$ points. Also $K_y = D_N \\otimes I_N$.\n",
    "\n",
    "Now in 3D grid, we will have $x,y,z$ on $N^3$ discrete points. We need compute the derivatives w.r.t $x,y,z$ each on $N^3$ cubic grid points. Suppose we have the 2D matrix $K_x$, that is for one $z$ value, image we repeat this for $N$ of $z$ values, that requires a $I_N \\otimes K_x = I_N \\otimes I_N \\otimes D_N$ matrix, which has $N^3$ dimension. \n",
    "\n",
    "Similarly we find the $K_y,K_z$, so the final $K = K_x + K_y + K_z = I_N \\otimes I_N \\otimes D_N + I_N \\otimes D_N \\otimes I_N + D_N \\otimes I_N \\otimes I_N$\n",
    "\n",
    "#### Problem IV.4.4\n",
    "\n",
    "Similiarly, we have $F3 = F\\otimes F \\otimes F$ in 3D."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem IV.5.1\n",
    "\n",
    "When $F(\\lambda) = \\log\\lambda$, we have $F(A(\\theta)) = \\log A(\\theta)$, from equation (3), we have $\\lim_{n\\to \\infty} \\frac{1}{n}\\sum^{n-1}_{k=0} F(\\lambda_k) = \\lim_{n\\to \\infty} \\frac{1}{n}\\sum^{n-1}_{k=0} \\log \\lambda_k = \\lim_{n\\to \\infty} \\frac{1}{n}\\log\\prod^{n-1}_{k=0} \\lambda_k = \\lim_{n\\to \\infty} \\frac{1}{n}\\log (det A) = \\frac{1}{2\\pi}\\int^{2\\pi}_0 F(A(\\theta))d\\theta = \\frac{1}{2\\pi}\\int^{2\\pi}_0 \\log(A(\\theta))d\\theta$\n",
    "\n",
    "This is exactly equation (2)\n",
    "\n",
    "#### Problem IV.5.2\n",
    "\n",
    "$F(\\lambda) = \\lambda^2$, then equation (3) gives the limit of the average eigenvalue of $A^2$.\n",
    "\n",
    "* (a) $A(\\theta) = a_1e^{i\\theta} + a_0 + a_{-1}e^{-i\\theta}$, $A^2(\\theta) =a^2_1e^{2i\\theta} + 2a_0a_1e^{i\\theta} + (a^2_0 +2a_1a_{-1}) + 2a_0a_{-1}e^{-i\\theta} + a^2_{-1}e^{-2i\\theta}$\n",
    "\n",
    "On the other hand, for $A^2=AA$, we have the $A^2_{ii} = \\sum_k a_{ik}a_{ki} = a_{i,i-1}a_{i-1,i} + a_{i,i}a_{i,i} + a_{i,i+1}a_{i+1,i} = a_1a_{-1} + a^2_0 + a_{-1}a_1 = a^2_0 + 2a_1a_{-1}$\n",
    "\n",
    "Similarly we have $A^2_{i,i+1} = \\sum_k a_{ik}a_{k,i+1} = a_{i,i-1}a_{i-1,i+1} + a_{i,i}a_{i,i+1} + a_{i,i+1}a_{i+1,i+1} = a_1\\times 0 + a_0a_{-1} + a_{-1}a_0 = 2a_0a_{-1}$\n",
    "\n",
    "$A^2_{i,i+2} = \\sum_k a_{ik}a_{k,i+2} = a_{i,i-1}a_{i-1,i+2} + a_{i,i}a_{i,i+2} + a_{i,i+1}a_{i+1,i+2} = a_1\\times 0 + a_0\\times 0 + a_{-1}a_{-1} = a^2_{-1}$\n",
    "\n",
    "So we see that $A^2$ symbol is $(A(\\theta))^2$.\n",
    "\n",
    "* (b) $\\int^{2\\pi}_0 A^2(\\theta) d\\theta =\\int^{2\\pi}_0 \\left( a^2_1e^{2i\\theta} + 2a_0a_1e^{i\\theta} + (a^2_0 +2a_1a_{-1}) + 2a_0a_{-1}e^{-i\\theta} + a^2_{-1}e^{-2i\\theta}\\right)d\\theta = \\int^{2\\pi}_0 \\left( e^{2i\\theta} - 4e^{i\\theta} + 6 - 4e^{-i\\theta} + e^{-2i\\theta}\\right)d\\theta = \\int^{2\\pi}_0 (6+2\\cos(2\\theta)+8\\cos(\\theta)d\\theta = 12\\pi$ \n",
    "\n",
    "#### Problem IV.5.3\n",
    "\n",
    "It's easy to verify that $(LU)_{44} = (-\\frac{3}{4})(-1) + (1)(\\frac{5}{4}) = 2$. \n",
    "\n",
    "$det(A) = det(LU) = det(L)det(U) = 1\\times 5 = 5$\n",
    "\n",
    "#### Problem IV.5.4\n",
    "\n",
    "$(-e^{-i\\theta}+1)(-e^{i\\theta}+1) = 1 -e^{-i\\theta} -e^{i\\theta} + 1 = -e^{-i\\theta} + 2 -e^{i\\theta}$\n",
    "\n",
    "We see that in the limit $a_{-1} = a_1 = -1$\n",
    "\n",
    "This agrees with the $LU$ in the limit, that is $(-1)(-1) + (1)(1) = 2$\n",
    "\n",
    "#### Problem IV.5.5\n",
    "\n",
    "Suppose in the last column of $A$, we have $A_{n-1,n}=a, A_{n,n}=b$, so with $A^TA=S$, we have $a^2+b^2=5$, and $ab=-2$, solve the equations we have $(a,b)=(-2,1),(2,-1),(1,-2),(-1,2)$\n",
    "\n",
    "Since $5-2e^{i\\theta}-2e^{-i\\theta} = (-e^{i\\theta}+2)(-e^{-i\\theta}+2)$, the diagonal term should be 2, so we have $a=-1,b=2$\n",
    "\n",
    "#### Problem IV.5.6\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "When N =  100 , The last column approaches to:  [-1.  2.]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from scipy.linalg import toeplitz\n",
    "N=100\n",
    "k = np.array([5,-2])\n",
    "row1 = np.hstack([k, np.zeros(N-2)])\n",
    "S = toeplitz(row1, row1)\n",
    "L = np.linalg.cholesky(S)\n",
    "print('When N = ', N, ', The last column approaches to: ', L.transpose()[-2:, N-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem IV.6.1\n",
    "\n",
    "The Laplacian matrix for a triangle graph is: $A^TA=\\begin{bmatrix}2 & -1 & -1 \\\\ -1 & 2 & -1 \\\\ -1 & -1 & 2\\end{bmatrix}$\n",
    "\n",
    "The Laplacian matrix for a square graph is: $A^TA=\\begin{bmatrix}2 & -1 & 0 & -1 \\\\ -1 & 2 & -1 & 0 \\\\ 0 & -1 & 2 & -1 \\\\ -1 & 0 & -1 & 2\\end{bmatrix}$\n",
    "\n",
    "#### Problem IV.6.2\n",
    "\n",
    "According to the property of Laplacian matrix $G=A^TA$, the diagonal entry counts the edges meeting at node $i$, for complete graph, each node has connection with all other nodes, so the count of edges is $n-1$. \n",
    "\n",
    "Also, the off-diagonal entry is $-1$ when an edge connects nodes $i$ and $j$, for complete graph, every node is connected with another node, so for each pair of $i,j$, where $i\\ne j$, there's an edge connecting them, and corresponding entry should be -1. \n",
    "\n",
    "So for complete graph with $n$ nodes, the diagonal entries are all $n-1$, all other entries are -1. \n",
    "\n",
    "#### Problem IV.6.3\n",
    "\n",
    "We have the incidence matrix $A=\\begin{bmatrix}-1 & 1 & 0 \\\\ -1 & 0 & 1 \\\\ 0 & -1 & 1\\end{bmatrix}$, and the weight matrix $C=\\begin{bmatrix}c_1 & 0 & 0 \\\\ 0 & c_2 & 0 \\\\ 0 & c_3 & 0 \\end{bmatrix}$, \n",
    "\n",
    "so $K=A^TCA = \\begin{bmatrix}c_1+c_2 & -c_1 & -c_2 \\\\ -c_1 & c_1 + c_3 & -c_3 \\\\ -c_2 & -c_3 & c_2 + c_3\\end{bmatrix}$\n",
    "\n",
    "\n",
    "#### Problem IV.6.4\n",
    "\n",
    "Let the columns of $A^T$ be $a_1,a_2,\\dots, a_n$, then we have $A^T=\\begin{bmatrix}a_1 & \\dots & a_n\\end{bmatrix}$ and $A=\\begin{bmatrix}a^T_1 \\\\ \\dots \\\\ a^T_n\\end{bmatrix}$, let $C=\\begin{bmatrix}c_1 & \\dots & 0 \\\\ \\dots & c_i & 0 \\\\ 0 & \\dots & c_n\\end{bmatrix}$\n",
    "\n",
    "So we apply column times row twice here, and $K=A^T(CA) = A^T \\begin{bmatrix}c_1a^T_1 \\\\ \\dots \\\\ c_na^T_n\\end{bmatrix} = c_1a_1a^T_1 + \\dots + c_na_na^T_n $\n",
    "\n",
    "#### Problem IV.6.5\n",
    "\n",
    "Since $A^Tw=0$, we see that the left null space of $A$, i.e. $N(A^T)$ has a dimension of 0, so the column space of $A$, i.e. $c(A)$ has a dimension of $m-0=m$, which means the rows of $A$ are all independent for  a tree. \n",
    "\n",
    "\n",
    "#### Problem IV.6.6 TODO\n",
    "\n",
    "See the wiki definition of [planar graph](https://en.wikipedia.org/wiki/Planar_graph)\n",
    "\n",
    "\n",
    "#### Problem IV.6.7\n",
    "\n",
    "* (a) From problem IV.6.2, we have $A^TA=\\begin{bmatrix}3 & -1 & -1 \\\\ -1 & 3 & -1 \\\\ -1 & -1 & 3 \\end{bmatrix}$\n",
    "\n",
    "* (b) From loops we find the $6-4+1=3$ solutions to Kirchhoff's Law $A^Tw=0$:\n",
    "\n",
    "We assume we have a matrix $A=\\begin{bmatrix} -1 & 0 & 1 & 0 \\\\ 0 & 0 & -1 & 1 \\\\ 0 & 1 & 0 & -1 \\\\ 1 & -1 & 0 & 0 \\\\ 0 & 1 & -1 & 0 \\\\ -1 & 0 & 0 & 1\\end{bmatrix}$, from this matrix, we can tell the flow of current (from which node to which) and use them to generate the solutions to Kirchhoff's law.\n",
    "\n",
    "From the four loops of $(x_1, x_3,x_4)$, $(x_3,x_4,x_2)$, $(x_1, x_4, x_2)$ and $(x_1, x_3, x_2)$ we find 4 solutions: \n",
    "\n",
    "$y_1 = \\begin{bmatrix}1 \\\\ 1 \\\\ 0 \\\\ 0 \\\\ 0 \\\\ -1\\end{bmatrix}$, $y_2 = \\begin{bmatrix}0 \\\\ 1 \\\\ 1 \\\\ 0 \\\\ -1 \\\\ 0\\end{bmatrix}$, $y_3 = \\begin{bmatrix}0 \\\\ 0 \\\\ 1 \\\\ 1 \\\\ 0 \\\\ 1\\end{bmatrix}$, and $y_4 = \\begin{bmatrix}1 \\\\ 0 \\\\ 0 \\\\ 1\\\\ 1 \\\\ 0\\end{bmatrix}$\n",
    "\n",
    "It's easy to see that $y_1+y_3 = y_2 + y_4$, so there are only 3 independent solutions. Pick any of three should be fine.\n",
    "\n",
    "#### Problem IV.6.8 TODO\n",
    " \n",
    "#### Problem IV.6.9\n",
    "\n",
    "Pick a $A=\\begin{bmatrix} -1 & 1 & 0 \\\\ 0 & -1 & 1 \\\\ -1 & 0 & 1 \\end{bmatrix}$.\n",
    "\n",
    "$G=A^TA = \\begin{bmatrix}2 & -1 & -1 \\\\ -1 & 2 & -1 \\\\ -1 & -1 & 2\\end{bmatrix}$, solve for eigenvalues, we find its \n",
    "\n",
    "$\\lambda_1=\\lambda_2 = 3, \\lambda_3 = 0$. \n",
    "\n",
    "The eigenvectors are not completely determined because $G$ has a repeated eigenvalue $\\lambda = 3$.\n",
    "\n",
    "Solve for eigenvectors using eigenvalue 3, so we have the eigenvector $v_1 = \\frac{1}{\\sqrt{6}} \\begin{bmatrix} 1 \\\\ 1 \\\\ -2 \\end{bmatrix}$, $v_2 = \\frac{1}{\\sqrt{2}} \\begin{bmatrix} 1 \\\\ -1 \\\\ 0 \\end{bmatrix}$, note we need to make $v_2$ orthogonal to $v_1$\n",
    "\n",
    "Compute the left singular vectors as : $u_1 = \\frac{1}{\\sqrt{2}}\\begin{bmatrix}0 \\\\ -1 \\\\ -1\\end{bmatrix}$, $u_2 = \\frac{1}{\\sqrt{6}}\\begin{bmatrix}-2 \\\\ 1 \\\\ -1\\end{bmatrix}$\n",
    "\n",
    "so we have $A=U\\Sigma V^T = \\begin{bmatrix}0 & -\\frac{2}{\\sqrt{6}}\\\\ -\\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{6}} \\\\ -\\frac{1}{\\sqrt{2}} & -\\frac{1}{\\sqrt{6}}\\end{bmatrix}\\begin{bmatrix}\\sqrt{3} & 0 \\\\ 0 & \\sqrt{3}\\end{bmatrix} \\begin{bmatrix}\\frac{1}{\\sqrt{6}} & \\frac{1}{\\sqrt{6}} & -\\frac{2}{\\sqrt{6}} \\\\ \\frac{1}{\\sqrt{2}} & -\\frac{1}{\\sqrt{2}} & 0\\end{bmatrix}$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem IV.7.1\n",
    "\n",
    "Solve for $z$ we find that $z=\\begin{bmatrix}2c \\\\ c \\\\ -c \\\\ -2c \\end{bmatrix}$, we see that the cut is in the middle because the top half are positive and the lower half are negative. It's easy to check that $\\begin{bmatrix}1 & 1 & 1 & 1 \\end{bmatrix} Dz=0$\n",
    "\n",
    "\n",
    "\n",
    "#### Problem IV.7.2\n",
    "\n",
    "For the cut in the middle, we have $P={1,2}$ and $Q={3,4}$. \n",
    "For $i$ in $P$ and $j$ not in $P$, we have \n",
    "\n",
    "$\\text{links}(P) = \\sum w_{ij} = w_{13} + w_{14} + w_{23} + w_{24} = 4$, and the size of $P$ is \n",
    "\n",
    "$\\text{size}(P) = \\sum w_{ij} = w_{11} + w_{12} + w_{22} + w_{21} = 4$\n",
    "\n",
    "Similarly we have $\\text{links}(Q) = 4$, and $\\text{size}(Q) = 4$, so we compute the normalized cut weight:\n",
    "\n",
    "$\\text{Ncut}(P,Q) = \\frac{\\text{links}(P)}{\\text{size}(P)} + \\frac{\\text{links}(Q)}{\\text{size}(Q)} = \\frac{4}{4} + \\frac{4}{4} = 2$\n",
    "\n",
    "This is larger than the cut between 1 and 2 or the cut between 3 and 4, which has $\\text{Ncut}(P,Q) = 3+\\frac{3}{6} > 2$\n",
    "\n",
    "#### Problem IV.7.3\n",
    "\n",
    "$c_P = (1+2)/2 = 1.5$, $c_Q = (3+4)/2 = 3.5$. So we have\n",
    "\n",
    "$D_P = (1-c_P)^2 + (2-c_P)^2 = 0.25 + 0.25 = 0.5$ and $D_Q = (3-c_Q)^2 + (4-c_Q)^2 = 0.5$, \n",
    "so $D= D_P + D_Q = 1$.\n",
    "\n",
    "The k-means algorithm will still assign 1,2 to $P$ and 3,4 to $Q$ in the next step.\n",
    "\n",
    "#### Problem IV.7.4\n",
    "\n",
    "If we start the k-means algorithm with $P={1,2,3}$ and $Q={4}$, the centroids are $c_P=2, c_Q=4$. Then we have\n",
    "Point 3 is at the equal distance to $c_P$ and $c_Q$. We need assign point 3 to $Q$ to be able to move to the minimum cut.\n",
    "\n",
    "\n",
    "#### Problem IV.7.5\n",
    "\n",
    "\n",
    "$D_P = (1-2)^2 + (2-2)^2 + (3-2)^2 = 2$ and $D_Q = (4-4)^2 = 0$, so the $D=D_P+D_Q=2$. \n",
    "\n",
    "#### Problem IV.7.6\n",
    "\n",
    "For the 2 by 4 mesh of 8 nodes, I make nodes $x_1-x_4$ on the left half, with $x_1,x_4$ on diagonal. Similarly, $x_5-x_8$ are on the right side, with $x_5, x_8$ on diagonal. With weight $C=I$, we have the matrix $A^TCA = \\begin{bmatrix}2 & -1 & -1 & 0 & 0 & 0 & 0 & 0 \\\\-1 & 3 & 0 & -1 & -1 & 0 & 0 & 0 \\\\ -1 & 0 & 2 & -1 & 0 & 0 & 0 & 0 \\\\0 & -1 & -1 & 3 & 0 & 0 & -1 & 0  \\\\0 & -1 & 0 & 0 & 3 & -1 & -1 & 0 \\\\ 0 & 0 & 0 & 0 & -1 & 2 & 0 & -1 \\\\ 0 & 0 & 0 & -1 & -1 & 0 & 3 & -1\\\\0 & 0 & 0 & 0 & 0 & -1 & -1 & 2 \\end{bmatrix}$\n",
    "\n",
    "\n",
    "From the calculation below, we see that $\\lambda_2 = 0.2712864461218309$, the corresponding $z$ has the top half with negative values and the bottom half with positive values, this cuts the nodes in the middle, where $x_1-x_4$ belong to one cluster and $x_5-x_8$ belong to another."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lambda 2:  (0.2712864461218309+0j)\n",
      "second eigenvector:  [-0.45468835 -0.20798678 -0.45468835 -0.20798678  0.20798678  0.45468835\n",
      "  0.20798678  0.45468835]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([1.33226763e-15])"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#### Problem IV.7.6\n",
    "import numpy as np\n",
    "import scipy as sp\n",
    "a = np.array([[2, -1, -1, 0, 0, 0, 0, 0], [-1, 3, 0, -1, -1, 0, 0, 0], \n",
    "              [-1, 0, 2, -1, 0, 0, 0, 0], [0, -1, -1, 3, 0, 0, -1, 0], \n",
    "              [0, -1, 0, 0, 3, -1, -1, 0], [0, 0, 0, 0, -1, 2, 0, -1], \n",
    "              [0, 0, 0, -1, -1, 0, 3, -1], [0, 0, 0, 0, 0, -1, -1, 2]])\n",
    "D = np.diag(np.diag(a))\n",
    "v, L = sp.linalg.eig(a, D)\n",
    "#np.argmin(v), np.iscomplex(v)\n",
    "vi = np.argsort(v)\n",
    "print('lambda 2: ', v[vi[1]])\n",
    "z = L[:, vi[1]]\n",
    "print('second eigenvector: ', z)\n",
    "np.matmul(np.ones(8).reshape(1,8), np.matmul(D, z))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem IV.7.7 TODO\n",
    "\n",
    "#### Problem IV.7.8\n",
    "\n",
    "We define the minimum distance $D^*$ between two clusters to be the minimum distance among all distances between the points from cluster $P$ to points in cluster $Q$. \n",
    "\n",
    "Suppose we separate all the points into two clusters $P,Q$, By observation, the maximum of the minimum distance can be achieved by either:\n",
    "* Put point $(0,4)$ into one cluster\n",
    "* Put point $(0,8)$ into one cluster\n",
    "* Put points $(0,4),(0,8)$ into one cluster\n",
    "\n",
    "All three ways of clustering have the minimum distance $D^* = 4$, which is the largest among all possible clusterings. \n",
    "\n",
    "#### Problem IV.7.9\n",
    "\n",
    "If we start with 5 clusters, then first, we combine the two closest clusters at $(0,0)$ and $(1,0)$, then we have:\n",
    "\n",
    "* $k=4$, combine $(0,0)$ and $(1,0)$ into one cluster, $P_1=(0.5,0), P_2=(3,0), P_3=(0,4), P_4=(0,8)$\n",
    "* $k=3$, combine $(0,0),(1,0), (3,0)$ into one cluster, $P_1=(\\frac{4}{3},0), P_2=(0,4), P_3=(0,8)$\n",
    "* $k=2$, combine $(0,4),(0,8)$ into one cluster, $P_1=(\\frac{4}{3},0), P_2=(0,6)$\n",
    "\n",
    "#### Problem IV.7.10\n",
    "\n",
    "The minimum spanning tree found by Dijkstra's algorithm is: $(8,0)\\to(4,0)\\to (0,0)\\to (1,0)\\to (3,0)$\n",
    "\n",
    "#### Problem IV.7.11\n",
    "\n",
    "Use greedy inclusion to find the minimum spanning tree:\n",
    "\n",
    "* The shortest edge is between $(0,0)$ and $(1,0)$, add it to the tree\n",
    "* The second shortest edge is between $(1,0), (3,0)$, add it to the tree\n",
    "* The next one is from $(0,4)$ to $(0,0)$\n",
    "* The last one is from $(0,8)$ to $(0,4)$\n",
    "\n",
    "The whole tree connects from $(8,0)\\to(4,0)\\to (0,0)\\to (1,0)\\to (3,0)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem IV.8.1\n",
    "\n",
    "The 5 edges from $A_2$ does NOT make up a spanning tree because there's a loop: from row node 1 to column node 1 to row node 2 to column node 2 and back to row node 1.\n",
    "\n",
    "#### Problem IV.8.2 TODO\n",
    "\n",
    "We can have $A_4=\\begin{bmatrix}A_{11} & A_{12} & & & \\\\A_{21} & & A_{23} & & \\\\ & A_{32} &  &  & A_{35} \\\\ & & & A_{44} & \\\\ & & A_{53} & &A_{55}\\end{bmatrix}$\n",
    "\n",
    "To have a completion to a rank-1 matrix, we must have the entries of $A_4$ to have determinant of 0 for any square submatrix larger than 1.\n",
    "\n",
    "#### Problem IV.8.3\n",
    "\n",
    "When a graph is connected, it means for any two nodes, we can find a path, that connects the pair of nodes. \n",
    "\n",
    "To connect $N$ nodes, we need at least $N-1$ edges to span all the nodes, so we have $M\\ge N-1$.\n",
    "\n",
    "For any given node, if we count the unique edges of all paths from it to all the other nodes. Since in connected graph, the node is connected to all other nodes, the lengths of paths have to range from 1 to $N-1$. And the maximum length has to be $N-1$, if it's larger than $N-1$ you have a cycle.\n",
    "\n",
    "Let $l(i,j)$ be the maximum length of unique edges from node $i$ to $j$, then the maximum of $l(i,j)$ among all $i,j$ has to be $N-1$, suppose node $p,q$ has the maximum length $N-1$. We claim that $M\\le N-1$. Otherwise, there must exist an edge $k$, that is not on the path from $p$ to $q$, meaning exists nodes not on the path of $p\\to q$. Since the length between $p,q$ is $N-1$, there are already $N$ nodes, this contradicts with extra nodes coming from edge $k$. So we have $M\\le N-1$.\n",
    "\n",
    "We then conclude that $M=N-1$.\n",
    "\n",
    "\n",
    "\n",
    "#### Problem IV.8.4\n",
    "\n",
    "If a graph is connected with $N$ nodes and $N-1$ edges, then we know that is a spanning tree. We can use similar argument from problem IV.8.3, or as below.\n",
    "\n",
    "We can show this like below. We first start with any two 'one-line-cluster's, where we start with any node, e.g. $x_1$, since there always is a path between $x_1$ and all other nodes, there must be a node that's directly connected with $x_1$, label this $x_2$, do this continuously until $x_i$, where none of the rest points directly connects with $x_i$. This will be a 'one-line=cluster', with $i-1$ edges. For a connected graph, the minimum number of nodes in a 'one-line-cluster' is 2. \n",
    "\n",
    "Suppose we have another 'one-line-cluster' with $j$ nodes, so its number of edges is $j-1$. \n",
    "\n",
    "Now we claim that if these two clusters compose a connected graph, there has to be $i+j-1$ edges, i.e. only 1 edge connected from cluster $i$ to $j$. If there are more than 1 intra-cluster edge, then we can easily see that a cycle is formed. \n",
    "\n",
    "So for any 'one-line-cluster' of size $K$, we have $K-1$ edges. \n",
    "\n",
    "So for a connected graph, we start with any two 'one-line-cluster' and form a larger cluster, gradually adding 'one-line-cluster' one-by-one, we see that the final number of edges should be $N-1$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem IV.9.1\n",
    "\n",
    "We form the square matrix $Y^TX = X = \\begin{bmatrix}1 & 2 \\\\ 2 & 1 \\end{bmatrix}$, we need find the SVD for this matrix. \n",
    "\n",
    "let $K=Y^TX$, then we have $K^TK = \\begin{bmatrix}5 & 4 \\\\ 4 & 5 \\end{bmatrix}$, the eigenvalues are $\\lambda_1 = 9, \\lambda_2 = 1$, with eigenvectors: $v_1 = \\frac{1}{\\sqrt{2}}\\begin{bmatrix}1 \\\\ 1 \\end{bmatrix}$, and $v_2 = \\frac{1}{\\sqrt{2}}\\begin{bmatrix}1 \\\\ -1 \\end{bmatrix}$, these are the right singular vectors as well, The corresponding left singular vectors are $u_1 = \\frac{1}{\\sqrt{2}}\\begin{bmatrix}1 \\\\ 1 \\end{bmatrix}$ and $u_2 = \\frac{1}{\\sqrt{2}}\\begin{bmatrix}-1 \\\\ 1 \\end{bmatrix}$, in the end we have\n",
    "\n",
    "$K= U\\Sigma V^T = \\frac{1}{\\sqrt{2}}\\begin{bmatrix}1 & -1 \\\\ 1 & 1 \\end{bmatrix}\\begin{bmatrix}3 & 0 \\\\ 0 & 1 \\end{bmatrix} \\frac{1}{\\sqrt{2}}\\begin{bmatrix}1 & 1 \\\\ 1 & -1 \\end{bmatrix}$. \n",
    "\n",
    "The orthogonal matrix $Q$ that minimizes the norm is $Q=UV^T = \\begin{bmatrix}0 & 1 \\\\ 1 & 0 \\end{bmatrix}$, the minimal nor is: 4.\n",
    "\n",
    "If we let $Q=\\begin{bmatrix}\\cos\\theta & -\\sin\\theta \\\\ \\sin\\theta & \\cos\\theta\\end{bmatrix}$, then we have\n",
    "\n",
    "\\begin{align*}\n",
    "\\|X-YQ\\|^2_F &= \\|X - Q\\|^2_F \\\\\n",
    "&= \\|\\begin{bmatrix}1 & 2 \\\\ 2 & 1 \\end{bmatrix} - \\begin{bmatrix}\\cos\\theta & -\\sin\\theta \\\\ \\sin\\theta & \\cos\\theta\\end{bmatrix}\\|^2_F \\\\ \n",
    "&= \\|\\begin{bmatrix}1-\\cos\\theta & 2+\\sin\\theta \\\\ 2-\\sin\\theta & 1-\\cos\\theta\\end{bmatrix}\\|^2_F \\\\\n",
    "&= (1-\\cos\\theta)^2 + (2+\\sin\\theta)^2 + (2-\\sin\\theta)^2 + (1-\\cos\\theta)^2 \\\\\n",
    "&= 2(1-\\cos\\theta)^2 + 2(4 + \\sin^2\\theta)\\\\\n",
    "&= 2(1-2\\cos\\theta+\\cos^2\\theta+ 4 + \\sin^2\\theta)\\\\\n",
    "&= 2(6-2\\cos\\theta)\\\\\n",
    "\\end{align*}\n",
    "\n",
    "This is minimized when $\\theta = 2\\pi k$, where $k=0,1,\\dots$\n",
    "\n",
    "So $Q=\\begin{bmatrix}1 & 0 \\\\ 0 & 1 \\end{bmatrix}$, the minimal norm is 8.  It misses the optimal $Q$ computed above, which is caused by the assumption that the off diagonal entries are opposite of each other. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 2,  0],\n",
       "       [ 0, -2]])"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy  as np\n",
    "u = np.array([[1, -1], [1, 1]])\n",
    "v = np.array([[1, 1], [1, -1]])\n",
    "m = np.array([[3, 0], [0, 1]])\n",
    "np.matmul(np.matmul(u, m), v.transpose())\n",
    "np.matmul(v.transpose(), u)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem IV.10.1\n",
    "\n",
    "$D=\\begin{bmatrix}0 & 1 & 6 \\\\1 & 0 & 1 \\\\ 6 & 1 & 0 \\end{bmatrix}$ and $d_1 = \\begin{bmatrix} 0 \\\\ 1 \\\\ 6 \\end{bmatrix}$, according to equation (4), we have $G=\\begin{bmatrix}0 & 0 & 0 \\\\ 0 & 1 & 3 \\\\ 0 & 3 & 6 \\end{bmatrix}$, This is not positive semidefinite, because its eigenvalues are $\\lambda_1 = 0$, $\\lambda_2 = \\frac{7+\\sqrt{61}}{2}$ and $\\lambda_3 = \\frac{7-\\sqrt{61}}{2} < 0$\n",
    "\n",
    "#### Problem IV.10.2\n",
    "\n",
    "$D=\\begin{bmatrix}0 & 9 & 25 \\\\9 & 0 & 16 \\\\ 25 & 16 & 0 \\end{bmatrix}$ and $d_1 = \\begin{bmatrix} 0 \\\\ 9 \\\\ 25 \\end{bmatrix}$, according to equation (4), we have $G=\\begin{bmatrix}0 & 0 & 0 \\\\ 0 & 9 & 9 \\\\ 0 & 9 & 25 \\end{bmatrix}$\n",
    "\n",
    "We solve the $X$ using eigenvalue/eigenvectors of $G$ as below. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Eigenvalues of G: \n",
      " [29.04159458  4.95840542  0.        ]\n",
      "Eigenvectors of G: \n",
      " [[ 0.          0.          1.        ]\n",
      " [ 0.40965605  0.91224006  0.        ]\n",
      " [ 0.91224006 -0.40965605  0.        ]]\n",
      "Dot product of column  0  with column  0  is:  1.0\n",
      "Dot product of column  0  with column  1  is:  0.0\n",
      "Dot product of column  0  with column  2  is:  0.0\n",
      "Dot product of column  1  with column  0  is:  0.0\n",
      "Dot product of column  1  with column  1  is:  1.0\n",
      "Dot product of column  1  with column  2  is:  0.0\n",
      "Dot product of column  2  with column  0  is:  0.0\n",
      "Dot product of column  2  with column  1  is:  0.0\n",
      "Dot product of column  2  with column  2  is:  1.0\n",
      "The G with eigenvectors: \n",
      " [[ 0.  0.  0.]\n",
      " [ 0.  9.  9.]\n",
      " [ 0.  9. 25.]]\n",
      "The calculated G: \n",
      " [[ 0.  0.  0.]\n",
      " [ 0.  9.  9.]\n",
      " [ 0.  9. 25.]]\n",
      "The X is: \n",
      " [[ 0.          2.20764686  4.91608482]\n",
      " [ 0.          2.03132847 -0.91220068]\n",
      " [ 0.          0.          0.        ]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "def find_X(G):\n",
    "    v, L = np.linalg.eig(G)\n",
    "    print('Eigenvalues of G: \\n', v)\n",
    "    print('Eigenvectors of G: \\n', L)\n",
    "\n",
    "    n = G.shape[0]\n",
    "    \n",
    "    W = np.identity(n)\n",
    "    for i in range(n):\n",
    "        # Check orthogonality\n",
    "        for j in range(n):\n",
    "            d = np.dot(L[:,i], L[:,j])\n",
    "            print('Dot product of column ', i, ' with column ', j, ' is: ', d)\n",
    "        W[i,i]= v[i]\n",
    "    Gk = np.matmul(np.matmul(L, W), L.transpose())\n",
    "    print('The G with eigenvectors: \\n', Gk)\n",
    "    X = np.matmul(np.sqrt(W), L.transpose())\n",
    "    # This recovers G as well\n",
    "    Gc = np.matmul(X.transpose(), X)\n",
    "    print('The calculated G: \\n', Gc)\n",
    "    print('The X is: \\n', X)    \n",
    "    return X\n",
    "    \n",
    "G= np.array([[0, 0, 0], [0, 9, 9], [0, 9, 25]])\n",
    "X = find_X(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "We find another X: \n",
      " [[3. 3.]\n",
      " [0. 4.]]\n"
     ]
    }
   ],
   "source": [
    "G= np.array([[9, 9], [9, 25]])\n",
    "L = np.linalg.cholesky(G)\n",
    "X = L.transpose()\n",
    "print('We find another X: \\n', X)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem IV.10.3\n",
    "\n",
    "$D=\\begin{bmatrix}0 & 1 & 1 & 1 \\\\1 & 0 & 1 & 1 \\\\ 1 & 1 & 0 & 1 \\\\ 1 & 1 & 1 & 0 \\end{bmatrix}$ and $d_1 = \\begin{bmatrix} 0 \\\\ 1 \\\\ 1\\\\ 1 \\end{bmatrix}$, according to equation (4), we have $G=\\begin{bmatrix}0 & 0 & 0 & 0 \\\\ 0 & 1 & \\frac{1}{2} & \\frac{1}{2}\\\\ 0 & \\frac{1}{2} & 1 & \\frac{1}{2}\\\\ 0 & \\frac{1}{2} & \\frac{1}{2} & 1 \\end{bmatrix}$\n",
    "\n",
    "The points lie in $R^3$ here. \n",
    "\n",
    "We solve the $X$ using eigenvalue/eigenvectors of $G$ as below. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The final X: \n",
      " [[1.         0.5        0.5       ]\n",
      " [0.         0.8660254  0.28867513]\n",
      " [0.         0.         0.81649658]]\n"
     ]
    }
   ],
   "source": [
    "#G= np.array([[0, 0, 0, 0], [0, 1, 0.5, 0.5], [0, 0.5, 1, 0.5], [0, 0.5, 0.5, 1]])\n",
    "# Since numpy.linalg.eig() doesn't return orthogonal eigenvector matrix, so we use cholesky here\n",
    "G= np.array([[1, 0.5, 0.5], [0.5, 1, 0.5], [0.5, 0.5, 1]])\n",
    "L = np.linalg.cholesky(G)\n",
    "X = L.transpose()\n",
    "print('The final X: \\n', X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.3779644730092272"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1/np.sqrt(7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}