notebooks/LA_matrix_definite.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 正定値性\n",
    "\n",
    "## Hermite行列\n",
    "\n",
    "行列$A$の転置行列の各成分を複素共役にしたものを随伴行列といいます。\n",
    "特に\n",
    "$$\n",
    "H^{\\dagger} = H\n",
    "$$\n",
    "のとき、$H$をHermite行列と言います。\n",
    "\n",
    "* Hermite行列の固有値は実数になります。証明：[エルミート行列の性質](https://risalc.info/src/Hermitian-matrix.html)\n",
    "* 異なる固有値の固有ベクトルは直行します。証明：[エルミート行列の性質](https://risalc.info/src/Hermitian-matrix.html)\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 実対称行列の正定値\n",
    "\n",
    "* $A$が正定値$\\Longleftrightarrow$ $\\forall x \\neq 0, \\quad x^{\\top} A x>0$ $\\Longleftrightarrow$ 固有値が正の実数\n",
    "    * $A$が正定値$\\Longleftrightarrow$ $\\det{A} > 0$の証明：\n",
    "        * [https://mathlandscape.com/positive-definite-matrix/](https://mathlandscape.com/positive-definite-matrix/)\n",
    "        * 帰納法でも可\n",
    "\n",
    "---\n",
    "\n",
    "**帰納法による証明**\n",
    "\n",
    "$n-1$のサイズの行列に対して、$A$が正定値$\\Longrightarrow$ $\\det{A} > 0$とする。\n",
    "このとき、$n$のサイズについてもこれが成り立つことを証明しよう。\n",
    "\n",
    "$\\alpha > 0$について、\n",
    "$A=\\left[\\begin{array}{cc}\\alpha & c \\\\ c^{\\top} & D\\end{array}\\right]$\n",
    "なる対称行列を考える。($\\alpha > 0$は正定値対称を保証するために必要。$x=[1, 0, 0, \\dots, 0]$みたいなベクトルを考えるとわかる。)\n",
    "\n",
    "このとき、$\\operatorname{det} A=\\alpha \\operatorname{det}\\left(D-\\frac{c^{\\top} c}{\\alpha}\\right)$の形になる。\n",
    "\n",
    "ここで、\n",
    "$$\n",
    "A^{\\prime}:=\\left[\\begin{array}{cc}\n",
    "\\alpha & 0 \\\\\n",
    "0 & D-\\frac{c^{\\top} c}{\\alpha}\n",
    "\\end{array}\\right]=\\left[\\begin{array}{cc}\n",
    "1 & 0 \\\\\n",
    "-\\frac{c^{\\top}}{\\alpha} & I\n",
    "\\end{array}\\right]\\left[\\begin{array}{cc}\n",
    "\\alpha & c \\\\\n",
    "c^{\\top} & D\n",
    "\\end{array}\\right]\\left[\\begin{array}{cc}\n",
    "1 & -\\frac{c}{\\alpha} \\\\\n",
    "0 & I\n",
    "\\end{array}\\right]\n",
    "$$\n",
    "\n",
    "について考えてみよう。このとき、$A$が正定値ならば、$A'=PAP^T$の形になっている$A'$も正定値でなければならない。\n",
    "よって、$D-\\frac{c^{\\top} c}{\\alpha}$も正定値。\n",
    "帰納法の仮定より$\\operatorname{det}\\left(D-\\frac{c^{\\top} c}{\\alpha}\\right)>0$なので、$\\det A>0$。証明終わり。\n",
    "\n",
    "---"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $A$が実対称行列であるとき、$A$が正定値 $\\Longleftrightarrow$ 全ての首座小行列式が正\n",
    "\n",
    "---\n",
    "\n",
    "**証明**\n",
    "\n",
    "$\\Longrightarrow$は簡単。$x=[1, 1, 1, 0, 0, \\dots, 0]$みたいなベクトルを選ぶと、首座小行列式も正定値対称であることがわかる。\n",
    "\n",
    "$\\Longleftarrow$は$A$の大きさ$n$についての帰納法を、行列式のやつと同様にすればわかる\n",
    "\n",
    "---"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $A$が実対称行列であるとき、$A$が半正定値 $\\Longleftrightarrow$ 全ての首小行列式が非負\n",
    "    * 全ての首座小行列式が非負でも半正定値とは限らない。例：$A=\\left(\\begin{array}{cc}0 & 0 \\\\ 0 & -1\\end{array}\\right)$\n",
    "\n",
    "---\n",
    "\n",
    "**証明**\n",
    "\n",
    "$\\Longrightarrow$は簡単。$x=[0, 0, 1, 1, 0, \\dots, 0]$みたいなベクトルを選ぶと、首小行列式も半正定値対称であることがわかる。\n",
    "\n",
    "$\\Longleftarrow$は$A$の大きさ$n$についての帰納法を、行列式のやつと同様にすればわかる。\n",
    "\n",
    "---"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $A$が正定値対称 $\\Longleftrightarrow$ $A^{-1}$も正定値対称\n",
    "\n",
    "---\n",
    "\n",
    "**証明**\n",
    "\n",
    "任意の$x\\neq 0$に対して、$x=Ay$となる$y=A^{-1}x\\neq 0$が存在。よって、\n",
    "$$\n",
    "x^{\\top} A^{-1} x=y^{\\top} A A^{-1} A y=y^{\\top} A y>0\n",
    "$$\n",
    "\n",
    "---"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Schur標準形\n",
    "\n",
    "$A$：複素正方行列 $(n\\times n)$　に対して、次を満たすユニタリ行列が存在する。\n",
    "\n",
    "$$\n",
    "A^{\\prime}=Q^{-1} A Q=\n",
    "\\begin{array}{ccc}\n",
    "\\lambda_1 & & * \\\\\n",
    "& \\ddots & \\\\\n",
    "0 & \\lambda_n &\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "つまり、$Q^* AQ=R$となるユニタリ行列$Q$と上三角行列$R$が存在する。\n",
    "\n",
    "**注意** 上三角行列になるならば、その対角成分はすべて固有値にならないといけないことに注意。"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**証明**\n",
    "\n",
    "$A$の大きさ$n$に関する帰納法で証明します。\n",
    "\n",
    "* $v$を$A$の固有ベクトルとして、$v^*v=1$で規格化されているとします。\n",
    "* $W$は$v$の直行補空間とします $W=\\{x|x^*v=0\\}$（$n-1$次元）\n",
    "* $u_1=v$, $u_2, \\dots, u_n$を$W$の正規直行基底とします。つまり、$u_i^*u_j=0$, $\\|u_i\\|^2=1$\n",
    "* $U$は$u_1, \\dots, u_n$を並べて得られる行列とします。\n",
    "\n",
    "このとき、次の式が成立する。\n",
    "\n",
    "![shur](figs/shur_proof.png)\n",
    "\n",
    "* 左上は$u_1^* A u_1=v^* A v = \\lambda$なので成立。\n",
    "* $\\lambda$の下側は$u_1^* A u_j=\\lambda v u_j$の形なので、正規直行基底の定義から０。\n",
    "\n",
    "ここで、帰納法の仮定から、$\\tilde{Q}^* \\tilde{A} \\tilde{Q}=\\tilde{R}$となるユニタリ行列$\\tilde{Q}$が存在。\n",
    "あとは自明な$Q$を$\\tilde{Q}$から構築すれば、$Q^*AQ$は上三角行列になる。"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**$A$が正規行列のとき**\n",
    "\n",
    "「$A$が正規行列 $\\Longleftrightarrow$ $R$が対角行列」　が成立します。\n",
    "\n",
    "まず、$A=Q R Q^*$ のとき、$A A^*=Q R R^* Q^*, A^* A=Q R^* R Q^*$の形に書けます。\n",
    "\n",
    "つまり、正規行列は$AA^*=A^*A$を満たす正方行列なので、\n",
    "$$\n",
    "A A^*=A^* A \\Leftrightarrow R R^*=R^* R\n",
    "$$\n",
    "\n",
    "が成り立つはずです。$RR^*$と$R^*R$の成分を比較すると、\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "R=\\left(r_{i j}\\right), & \\left(R R^*\\right)_{i i}=\\left|\\lambda_i\\right|^2+\\sum_{j>i}\\left|r_{i j}\\right|^2, \\\\\n",
    "& \\left(R^* R\\right)_{i i}=\\left|\\lambda_i\\right|^2+\\sum_{j<i}\\left|r_{j i}\\right|^2 .\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "です。よって、次が$i$に関する帰納法で示せます。\n",
    "$$\n",
    "R R^*=R^* R \\Leftrightarrow r_{i j}=0(i \\neq j)\n",
    "$$\n",
    "\n",
    "* $i=1$のとき、$(RR^*)_{11}=\\lambda_i^2$なので、$\\sum_{j>1}\\left|r_{i j}\\right|^2=0$です。\n",
    "* $i<k$で$[r_{ij}=0(i\\neq j)]$が成立しているとすると、$\\sum_{j<k}\\left|r_{j k}\\right|^2=0$なので、$\\left(R R^*\\right)_{k k}=\\left(R^* R\\right)_{k k}$ より, $\\sum_{j>k}\\left|r_{k j}\\right|^2=0$.\n",
    "\n",
    "よって、正規行列のときはSchur標準形で出てくる上三角行列が対角行列になります。"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rayleigh 商\n",
    "\n",
    "Hermite行列$A$に対して、\n",
    "\n",
    "$$\n",
    "R_A(x):=\\frac{x^* A x}{x^* x}\n",
    "$$\n",
    "\n",
    "をRayleigh商と言います。\n",
    "これは$x\\neq 0$なら実数になります。\n",
    "\n",
    "また、固有値$\\lambda$、固有ベクトル$u$に対して、$R_A(u)=\\lambda$になります。（よってHermite行列の固有値は実数です）\n",
    "\n",
    "このRayleigh性は最大固有値と最小固有値を書き換えるときに便利です。実際、$\\lambda_{\\max} = \\max_{x\\neq 0} R_A(x)$になります。（最小値も同様）\n",
    "\n",
    "### Courant-Fischerの定理\n",
    "\n",
    "上のRayleigh商は最大最小値以外にも一般化することができます。\n",
    "\n",
    "Hermite行列$A$の固有値$\\lambda_1 \\geq \\cdots \\geq \\lambda_n$に対して、\n",
    "\n",
    "$$\n",
    "\\lambda_k=\\max _{U_k} \\min \\left\\{R_A(x) \\mid x \\in U_k, x \\neq 0\\right\\}\n",
    "$$\n",
    "\n",
    "ここで$U_k$は$k$次元部分空間です。\n",
    "\n",
    "証明しましょう。固有値$\\lambda_1, \\dots, \\lambda_n$に対応した直行固有ベクトルを$u_1, \\dots, u_n$として、\n",
    "\n",
    "$V_k=\\operatorname{span}(u_1, \\dots, u_k)$, $W_l=\\operatorname{span}(u_{n-l+1}, \\dots, u_n)$\n",
    "とします。\n",
    "\n",
    "ここで、$x=\\alpha_1 u_1 + \\dots + \\alpha_k u_k$を考えましょう。これは$x\\in V_k$です。\n",
    "このRayleigh商は\n",
    "\n",
    "$$R_A(x)=\\frac{\\lambda_1 |\\alpha_1|^2 + \\dots + \\lambda_k |\\alpha_k|^2}{|\\alpha_1|^2 + \\dots + |\\alpha_k|^2}$$\n",
    "\n",
    "の形になります。（例えば$\\alpha_1 u_1 A \\alpha_1 u_1 = \\lambda_1 \\alpha_1^2$なので。）\n",
    "これをよく見ると、$R_A(x)$は$\\lambda_1, \\dots, \\lambda_k$の凸結合になっています。よって、$\\lambda_1$と$\\lambda_k$の間にあるわけですね。\n",
    "\n",
    "なので$\\forall x \\in V_k, \\lambda_1 \\geq R_A(x) \\geq \\lambda_k$が成り立ちます。\n",
    "同様にして、$\\forall x \\in W_l, \\lambda_{n-l+1} \\geq R_A(x) \\geq \\lambda_n$です。\n",
    "\n",
    "ここで、任意の$k$次元部分空間$U_k$に対して、$\\exists x \\neq 0, x \\in U_k \\cap W_{n-k+1}$が存在します。\n",
    "よって、$\\min \\left\\{R_A(x) \\mid x \\in U_k, x \\neq 0\\right\\} \\leq \\lambda_k$です。\n",
    "\n",
    "特に$U_k=V+k$なら等号が成立します。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}