{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Practice Session\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider a matrix $A_n$ of size $n\\times n$\n",
    "$$\n",
    "A_n = \n",
    "    \\begin{pmatrix}\n",
    "        2 & -1 & 0 & 0 & \\dots & 0 & -1 \\\\\n",
    "        -1 & 2 & -1 & 0 & \\dots & 0 & 0 \\\\\n",
    "        0  & -1 & 2 & -1 & \\dots & 0 & 0 \\\\\n",
    "        \\dots & \\dots & \\dots& \\dots& \\dots& \\dots & \\dots\\\\\n",
    "        \\dots & \\dots & \\dots& \\dots& \\dots& \\dots & \\dots\\\\\n",
    "        0 & 0 & \\dots & \\dots & -1 & 2 & -1 \\\\\n",
    "        -1 & 0 & \\dots & \\dots & 0 & -1 & 2\n",
    "    \\end{pmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Properties\n",
    "\n",
    "* Symmetric: $A^T = A$ \n",
    "* Hermitian: $A^* = A$ (hence real eigenvalues)\n",
    "* Singular (take sum of all rows)\n",
    "* Non-negative definite: $(Ax, x) \\geq 0$ for each $x\\in\\mathbb{C}^{n\\times 1}$\n",
    "* Sparse: $\\mathcal{O}(n)$ non-zero elements\n",
    "* Toeplitz\n",
    "* Circulant\n",
    "* Discretization of an operator $A$ on unifrom grid:\n",
    "$$\n",
    "\\begin{split}\n",
    "Au \\equiv &\\frac{d^2 u(x)}{dx^2}, \\quad x\\in (0,1)\\\\\n",
    "u(0) &= u(1) \\\\\n",
    "u'(0) &= u'(1)\n",
    "\\end{split}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Eigenvalues\n",
    "\n",
    "As we know circulants have eigenvalues equal to the multiplication of the Fourier matrix by circulant's first column:\n",
    "$$\n",
    "\\begin{pmatrix}\n",
    "\\lambda_1 \\\\ \\lambda_2 \\\\ \\lambda_3 \\\\ \\vdots \\\\ \\lambda_n\n",
    "\\end{pmatrix} =\n",
    "\\begin{pmatrix}\n",
    "1 & 1 & 1 & \\dots & 1 \\\\\n",
    "1 & w^{1\\cdot 1}_n & w^{1\\cdot 2}_n & \\dots & w^{1\\cdot (n-1)}_n\\\\\n",
    "1 & w^{2\\cdot 1}_n & w^{2\\cdot 2}_n & \\dots & w^{2\\cdot (n-1)}_n\\\\\n",
    "\\dots & \\dots & \\dots &\\dots &\\dots \\\\\n",
    "1 & w^{(n-1)\\cdot 1}_n & w^{(n-1)\\cdot 2}_n & \\dots & w^{(n-1)\\cdot (n-1)}_n\\\\\n",
    "\\end{pmatrix}\n",
    "\\begin{pmatrix}\n",
    "2 \\\\ -1 \\\\ 0 \\\\ \\vdots \\\\0 \\\\ -1\n",
    "\\end{pmatrix} =\n",
    "\\begin{pmatrix}\n",
    "2 -1 -1 \\\\ 2 - w_n^{1} - w_n^{n-1} \\\\ 2 - w_n^{2} - w_n^{2(n-1)} \\\\ \\vdots \\\\ 2 - w_n^{(n-1)} - w_n^{(n-1)(n-1)}\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "Thus, \n",
    "$$\n",
    "\\lambda_k = 2 - w_n^k - w_n^{k(n-1)} = 2 - w_n^k - w_n^{-k} = 2 - e^{-\\frac{2\\pi i}{n}k} - e^{\\frac{2\\pi i}{n}k} = 2 - 2 \\cos \\frac{2\\pi k}{n} = 4 \\sin^2 \\frac{\\pi k}{n},\n",
    "$$\n",
    "So, $$\\lambda_k  = 4 \\sin^2 \\frac{\\pi k}{n} \\geq 0, \\quad k=0,1,\\dots, n-1$$\n",
    "Therefore, our matrix is non-negative definite. Note that $\\lambda_0 = 0$, hence matrix is singular."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Norms\n",
    "$$\n",
    "\\begin{split}\n",
    "\\|A_n\\|_F &= \\left((-1)^2 (n-1) + (-1)^2 (n-1) + 2^2 n + (-1)^2 + (-1)^2\\right)^{1/2} = \\sqrt{6n} \\\\\n",
    "\\|A_n\\|_1 &= \\lvert -1\\lvert + \\lvert 2\\lvert + \\lvert -1\\lvert = 4 \\\\\n",
    "\\|A_n\\|_\\infty &= \\lvert -1\\lvert + \\lvert 2\\lvert + \\lvert -1\\lvert = 4 \\\\\n",
    "\\|A_n\\|_2 &= \\max_i |\\lambda_i| = \n",
    "\\begin{cases}\n",
    "    4 \\sin^2 \\frac{\\pi n/2}{n} = 4,  & \\text{if } n \\text{ is even }  \\\\\n",
    "    4 \\sin^2 \\frac{\\pi ({n-1})/2}{n}, &  \\text{if } n \\text{ is odd }\n",
    "\\end{cases}\n",
    "\\\\\n",
    "\\end{split}\n",
    "$$\n",
    "Note, that $\\|A_n\\|_2 = \\max_i |\\lambda_i|$ only for Hermitian matrices!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}