notebooks/LA_matrix_determinant.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 行列と行列式\n",
    "\n",
    "参考\n",
    "* [線形代数汎論](https://amzn.asia/d/cQQdYH2)\n",
    "\n",
    "意外と行列の定義とか用語、性質についての理解が浅いので、今回は教科書を参考に一気にやっていきましょう。\n",
    "\n",
    "\n",
    "## 行列\n",
    "\n",
    "*  代数系$K$上の$m\\times n$型の行列$A=[a_{ij}] \\quad (i=1, \\cdots, m; j=1,\\cdots, n)$の定義：\n",
    "$$\n",
    "A=     \\begin{bmatrix}\n",
    "         a_{11} & \\cdots && a_{1n}\\\\\n",
    "         \\vdots & \\ddots && \\vdots\\\\ \n",
    "         a_{m1} & \\cdots && a_{mn} \n",
    "     \\end{bmatrix}\n",
    "    ,\\quad a_{ij} \\in K\n",
    "$$\n",
    "* 下三角部分：$\\{a_{ij}\\mid i\\geq j\\}$\n",
    "* 上三角部分：$\\{a_{ij}\\mid i\\leq j\\}$\n",
    "* 上Hessenberg行列：$i > j+1$のとき$a_{ij}=0$\n",
    "* 下Hessenberg行列：$j > i+1$のとき$a_{ij}=0$\n",
    "$$\n",
    "A=   \\begin{bmatrix}\n",
    "         a_{11} & a_{12} && \\cdots &&& a_{1n}\\\\\n",
    "         a_{21} & a_{22} && \\cdots &&& a_{2n}\\\\ \n",
    "         0 & a_{32} && \\cdots &&& a_{3n}\\\\ \n",
    "         \\vdots & \\vdots && \\ddots &&& \\vdots\\\\ \n",
    "         0 & 0 && \\cdots &&& a_{mn} \n",
    "     \\end{bmatrix}\n",
    "    ,\\quad a_{ij} \\in K\n",
    "$$\n",
    "* 縦ベクトル：$m\\times 1$型の行列\n",
    "* 横ベクトル：$1\\times n$型の行列\n",
    "\n",
    "## 行列算\n",
    "\n",
    "* 行列積：$P = [p_{ij}]=AB$なる$l \\times n$型の行列\n",
    "    * $p_{ij}=\\sum^m_{k=1} a_{ik} b_{kj} \\quad (i=1, \\cdots, l; j=1, \\cdots, n)$\n",
    "    * ここで$A$は$l\\times m$型、$B$は$m \\times n$型の行列\n",
    "\n",
    "## Hermite行列とか\n",
    "\n",
    "* 共役：$K=\\mathbb{C}$（複素数体）のとき、ca$m\\times n$型の行列$A$の共役 $C=[c_{ij}]=\\overline{A}$\n",
    "    * $c_{ij}=\\overline{a}_{ij}$で定められる$m\\times n$型行列のこと。ここで$\\overline{a}_{ij}$は$a$の共役複素数。 \n",
    "* AのHermite共役$A^\\dag$：$(\\overline{A})^\\top=\\overline{A^\\top}$\n",
    "* $A$が正方行列のときの呼び方\n",
    "    * $A^\\top=-A$は反対称行列、交代行列、もしくは歪対称行列\n",
    "    * $A^\\dag=A$はHermite行列\n",
    "    * $A^\\dag=-A$は歪Hermite行列\n",
    "* 任意の正方行列に対して$A=\\frac{1}{2}(A+A^\\top)+\\frac{1}{2}(A-A^\\top)$と対称行列と反対称行列に分割可能\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 置換行列と基本行列\n",
    "\n",
    "$n$個のもの($1, 2, \\cdots, n$)を番号順に並べた並び方を基準にして、その並び方を$\\pi_1, \\pi_2, \\cdots, \\pi_n$に並び替えたとする。\n",
    "$\\pi_i$は$1, 2, \\cdots, n$のどれかに等しく、$i\\neq j$ならば$\\pi_i\\neq \\pi_j$である。このような並び替えを置換という。\n",
    "\n",
    "これは集合$V=\\{1, \\cdots, n\\}$のそれ自身への全単射であるともみなせる。置換$\\pi$は\n",
    "\n",
    "$$\n",
    "\\begin{pmatrix}\n",
    "&1 \\quad 2 \\quad \\cdots \\quad n\\\\\n",
    "&\\pi_1 \\quad \\pi_2 \\quad \\cdots \\quad \\pi_n \n",
    "\\end{pmatrix}\n",
    "$$\n",
    "のように表記されることもある。とくに$i_0$と$j_0$を入れ替える単純な置換は互換と呼ばれる。$(i_0, j_0)$と略記する。\n",
    "\n",
    "置換は複数回の互換の積の形で表せるが、その表現は一意ではない。例えば\n",
    "\n",
    "$$\n",
    "\\begin{pmatrix}\n",
    "&1, 2, 3\\\\\n",
    "&3, 1, 2\n",
    "\\end{pmatrix}\n",
    "= (1, 2)\\circ (2, 3) = (1, 3) \\circ (1, 2)\n",
    "$$\n",
    "\n",
    "のように、置換は複数の互換で表せる。しかし、その互換の総数の偶奇は一意である。総数が偶数のときは偶置換、奇数なら奇置換という。\n",
    "下の図（岩田先生のスライドより引用）のように置換の交差数を数えると偶置換であるか奇置換であるかは簡単にわかる。\n",
    "\n",
    "![determinant](figs/matrix_determinant.png)\n",
    "\n",
    "\n",
    "\n",
    "* 正方行列$P$の要素がどれも$0$か$1$に等しく、どの行、列にもちょうど$1$個だけ$1$があるとき、$P$は置換行列と呼ばれる。\n",
    "    * $m$次の置換行列の行$i$における$1$が列$j_i$にあるとき、$m\\times n$の行列$A$に対して、$PA$の行集合の順序は$A$の行集合の順序に次の置換を施すのと同じ\n",
    "    * $m$次の置換行列の行$i$における$1$が列$j_i$にあるとき、$n\\times m$の行列$B$に対して、$BP$の行集合の順序は$B$の列集合の順序に次の置換を施すのと同じ\n",
    "* 特に、ある$i_0$, $j_0$ ($i_0 \\neq j_0$)について、$p_{ii}=1$ ($i\\neq i_0, j_0$), $p_{i_0j_0}=p_{j_0i_0}-1$, $p_{i_0i_0}=p_{j_0j_0}=0$である置換行列は互換行列と呼ばれる。\n",
    "    * $PA$で行$i_0$と$j_0$を入れ替える。\n",
    "$$\n",
    "\\begin{pmatrix}\n",
    "&j_1 \\quad j_2 \\quad \\cdots \\quad j_m\\\\\n",
    "&1 \\quad 2 \\quad \\cdots \\quad m\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "* 基本行列：置換行列と次の２つの行列は合わせて基本行列と呼ぶ\n",
    "    * 行列$T$：$T(i_0;t)A$は$A$の行$i_0$を$t$倍する\n",
    "    * 行列$W$：$W(i_0,j_0;t)A$は$A$の行$j_0$を$t$倍して行$i_0$に加える\n",
    "\n",
    "任意の正則行列は基本行列の積で表せることに注意。\n",
    "* 例えば$S$が正則行列なら、一列目に必ず非０の値があるので、それを使って一列目を単位行列と同じ形にする。\n",
    "* これでできた$S'$も正則なので、二列目に必ず非０の値が存在するはず。これを使って二列目を単位行列と同じ形にする。\n",
    "* 以下同様\n",
    "* よって、$P_1P_2\\cdots S = I$となる基本行列$P_1P_2\\cdots$が存在するので、$S=(\\cdots P_2^{-1}P_1^{-1})$とすれば良い。基本行列の逆行列は基本行列だからOK。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "置換行列\n",
      "[[0 1 0]\n",
      " [1 0 0]\n",
      " [0 0 1]]\n",
      "行列A\n",
      "[[ 1  2  3]\n",
      " [11 12 13]\n",
      " [21 22 23]\n",
      " [31 32 33]]\n",
      "行列AP\n",
      "[[ 2  1  3]\n",
      " [12 11 13]\n",
      " [22 21 23]\n",
      " [32 31 33]]\n",
      "行列A.T\n",
      "[[ 1 11 21 31]\n",
      " [ 2 12 22 32]\n",
      " [ 3 13 23 33]]\n",
      "行列PA.T\n",
      "[[ 2 12 22 32]\n",
      " [ 1 11 21 31]\n",
      " [ 3 13 23 33]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "A = np.array([[1, 2, 3], [11, 12, 13], [21, 22, 23], [31, 32, 33]])  # 4 x 3\n",
    "P = np.array([[0, 1, 0], [1, 0, 0], [0, 0, 1]])\n",
    "\n",
    "print(\"置換行列\")\n",
    "print(P)\n",
    "\n",
    "print(f\"行列A\")\n",
    "print(A)\n",
    "print(f\"行列AP\")\n",
    "print(A @ P)\n",
    "\n",
    "print(f\"行列A.T\")\n",
    "print(A.T)\n",
    "print(f\"行列PA.T\")\n",
    "print(P @ A.T)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 部分行列と行列の分割\n",
    "\n",
    "* $m\\times n$型の行列$A=[a_{ij}]$の$r$本の行と$s$本の列を自然な順に配列してできる$r\\times s$の行列を$A$の部分行列と言う\n",
    "* ブロック行列：行列を部分行列に分割するやつ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "行列 A\n",
      "[[ 1  2  3  4]\n",
      " [11 12 13 14]\n",
      " [21 22 23 24]\n",
      " [31 32 33 44]]\n",
      "部分行列\n",
      "[[13 14]\n",
      " [23 24]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "A = np.array([[1, 2, 3, 4], [11, 12, 13, 14], [21, 22, 23, 24], [31, 32, 33, 44]])  # 4 x 4\n",
    "print(\"行列 A\")\n",
    "print(A)\n",
    "\n",
    "sub_A = A[[1, 2]][:, [2, 3]]\n",
    "print(\"部分行列\")\n",
    "print(sub_A)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## クロネッカー積（直積）\n",
    "\n",
    "$m_1\\times n_1$の行列$A=[a_{ij}]$と$m_2\\times n_2$の行列$B=[b_{ij}]$に対して、クロネッカー積$A\\otimes B$は\n",
    "$$\n",
    "A\\otimes B=   \\begin{bmatrix}\n",
    "         a_{11}B & a_{12}B && \\cdots &&& a_{1n_1} B\\\\\n",
    "         a_{21}B & a_{22}B && \\cdots &&& a_{2n_1} B\\\\\n",
    "         \\vdots & \\vdots && \\ddots &&& \\vdots\\\\ \n",
    "         a_{m_11}B & a_{m_12}B && \\cdots &&& a_{m_1n_1}B \n",
    "     \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "で定義される$(m_1m_2)\\times (n_1n_2)$の行列。\n",
    "\n",
    "---\n",
    "\n",
    "**クロネッカー積と方程式**\n",
    "\n",
    "* $Ax = y$を考えると、$y_i = \\sum_{j=1}^{n_1}a_{ij}x_j$であるから、$A=[a_{ij}]$は方程式の係数とみなせる。\n",
    "* $Bu = v$を考えると、$v_i = \\sum_{j=1}^{n_2}a_{ij}u_j$であるから、$B=[b_{ij}]$は方程式の係数とみなせる。\n",
    "\n",
    "ここで、$y$と$v$の変数の積による新しい$m_1 \\cdot m_2$個の変数（テンソル積とも呼ばれる）\n",
    "\n",
    "$w_1=y_1v_1$, $w_2=y_1 v_2$, ..., $w_{m_2}=y_1 v_{m_2}$, ..., $w_{(m_1 - 1)m_2 + 1} = y_{m_1} v_1$, ..., $w_{m_1 m_2}=y_{m_1}v_{m_2}$\n",
    "\n",
    "を考えよう。また、同様にして$x$と$u$のテンソル積\n",
    "\n",
    "$z_1=x_1u_1$, $z_2=x_1 u_2$, ..., $z_{m_2}=x_1 u_{m_2}$, ..., $z_{(m_1 - 1)m_2 + 1} = x_{m_1} u_1$, ..., $z_{m_1 m_2}=x_{m_1}u_{m_2}$\n",
    "\n",
    "も考える。このとき、\n",
    "\n",
    "$$w_i = \\sum_{j=1}^{n_1\\cdot n_2} (A \\otimes B)_{ij}z_{j}$$\n",
    "\n",
    "が成り立つ。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "行列 A\n",
      "[[ 1  2  3  4]\n",
      " [11 12 13 14]\n",
      " [21 22 23 24]]\n",
      "[[0.1  0.2  0.2  0.4  0.3  0.6  0.4  0.8 ]\n",
      " [0.12 0.22 0.24 0.44 0.36 0.66 0.48 0.88]\n",
      " [1.1  2.2  1.2  2.4  1.3  2.6  1.4  2.8 ]\n",
      " [1.32 2.42 1.44 2.64 1.56 2.86 1.68 3.08]\n",
      " [2.1  4.2  2.2  4.4  2.3  4.6  2.4  4.8 ]\n",
      " [2.52 4.62 2.64 4.84 2.76 5.06 2.88 5.28]]\n",
      "(6, 8)\n",
      "(8,)\n",
      "(6,)\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "A = np.array([[1, 2, 3, 4], [11, 12, 13, 14], [21, 22, 23, 24]])  # 3 x 4\n",
    "print(\"行列 A\")\n",
    "print(A)\n",
    "\n",
    "B = np.array([[0.1, 0.2], [0.12, 0.22]])  # 2 x 2\n",
    "\n",
    "AB = np.kron(A, B)\n",
    "print(AB)\n",
    "print(AB.shape)\n",
    "\n",
    "x = np.array([1, 2, 3, 4])\n",
    "u = np.array([11, 22])\n",
    "z = np.tensordot(x, u, axes=0).flatten()\n",
    "print(z.shape)\n",
    "\n",
    "y = A @ x\n",
    "v = B @ u\n",
    "w = np.tensordot(y, v, axes=0).flatten()\n",
    "print(w.shape)\n",
    "\n",
    "np.testing.assert_allclose(w, AB @ z, atol=1e-6)  # クロネッカー積とテンソル積の等号の確認"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 交代化演算子\n",
    "\n",
    "$i_k, j_k \\in \\{1, 2, \\cdots, n\\}$とする。\n",
    "$\\varepsilon_{j_1, \\cdots, j_r}^{i_1, \\cdots, i_r}$を、\n",
    "\n",
    "1. $\\{i_1, \\cdots, i_r\\}\\neq \\{j_1, \\cdots, j_r\\}$ or $\\{i_1, \\cdots, i_r\\}$の中に同じものがある or $\\{j_1, \\cdots, j_r\\}$の中に同じものがあるとき、\n",
    "$$\\varepsilon_{j_1, \\cdots, j_r}^{i_1, \\cdots, i_r}=0$$\n",
    "とする\n",
    "2. １以外であり、かつ\n",
    "    $$\n",
    "    \\begin{pmatrix}\n",
    "    &i_1, \\cdots, i_r\\\\\n",
    "    &j_1, \\cdots, j_r\n",
    "    \\end{pmatrix}\n",
    "    $$\n",
    "    が偶置換なら\n",
    "    $$\\varepsilon_{j_1, \\cdots, j_r}^{i_1, \\cdots, i_r}=1$$\n",
    "    奇置換なら\n",
    "    $$\\varepsilon_{j_1, \\cdots, j_r}^{i_1, \\cdots, i_r}=-1$$\n",
    "とする。\n",
    "\n",
    "このとき、$i_1, \\cdots, i_r$の順に添え字が並んでいる式$F_{i_1, \\cdots, i_r}$に対して、$F_{i_1, \\cdots, i_r}$をこの添字に対して交代化するというのは、\n",
    "\n",
    "$$\n",
    "F_{[i_1, \\cdots, i_r]}:= \\frac{1}{r!}\\sum_{j_1=1}^n \\cdots \\sum_{j_r=1}^n \\varepsilon_{i_1, \\cdots, i_r}^{j_1, \\cdots, j_r} F_{j_1\\cdots j_r}\n",
    "$$\n",
    "\n",
    "を作ることを言う。つまり、$F_{[i_1, \\cdots, i_r]}$は、$i_1, \\cdots, i_r$が全て異なるとき（それ以外では$F_{[i_1, \\cdots, i_r]}=0$）、$(i_1, \\cdots, i_r)$の置換$(j_1, \\cdots, j_r)$を添字に持つ式$F_{j_1, \\cdots, j_r}$を、置換が偶置換なら正の符号、奇置換なら負の符号をつけて加え合わせたものを、置換の総数$r!$で割ったものである。\n",
    "\n",
    "例えば、$F_[122]= 0$であり、また、\n",
    "\n",
    "$$F_[123]=\\frac{1}{6}(F_{123}+F_{231}+F_{312}-F_{213}-F_{132}-F_{321})$$\n",
    "\n",
    "である。\n",
    "\n",
    "また、$G_{i_1,\\cdots, i_r}=F_{[i_1,\\cdots, i_r]}$なら、$G_{i_1,\\cdots, i_r}$は添字${i_1,\\cdots, i_r}$について交代的であるという。つまり、$G$は添字の任意の２個を入れ替えると符号が変わる。　"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 行列式\n",
    "\n",
    "行列$A=[a_{ij}]$の$(i, j)$要素を$a_i^j$と書こう。\n",
    "$a_{j_1}^{i_1}\\cdots a_{j_r}^{i_r}$は$(i_k, j_k)$要素の積である。\n",
    "このとき、交代化演算子は\n",
    "$a_{j_1}^{[i_1}\\cdots a_{j_r}^{i_r]}=a_{[j_1}^{i_1}\\cdots a_{j_r]}^{i_r}=a_{[j_1}^{[i_1}\\cdots a_{j_r]}^{i_r]}$を満たす。\n",
    "\n",
    "これを使って、行列式は次で定義される\n",
    "\n",
    "$$\n",
    "\\det A = \\sum \\varepsilon_{j_1, \\cdots, j_n}^{1, \\cdots, n} a_{1 j_1}a_{2 j_2} \\cdots a_{n j_n}\n",
    "= n! a_{1}^{[1}\\cdots a_{n}^{n]}\n",
    "= n! a_{[1}^{1}\\cdots a_{n]}^{n}\n",
    "= n! a_{[1}^{[1}\\cdots a_{n]}^{n]}\n",
    "$$\n",
    "\n",
    "図と照らし合わせるとわかりやすい。\n",
    "1. 各行から、列の被りがないように一つづつインデックスを取ってきて、その積を考えると出てくる。\n",
    "2. 各行から選択するのは固定であり、列について交代化演算子を考えている\n",
    "2. 各列から選択するのは固定であり、行について交代化演算子を考えている\n",
    "\n",
    "![determinant](figs/matrix_determinant.png)\n",
    "\n",
    "\n",
    "### 行列式の性質\n",
    "\n",
    "1. 任意の$j(=1, \\cdots, n)$と$\\lambda (\\in K)$について、\n",
    "$$\\det[a_{\\cdot, 1}, a_{\\cdot, 2}, \\cdots, \\lambda a_{\\cdot, j}, \\cdots, a_{\\cdot, n}] = \n",
    "\\lambda\\det[a_{\\cdot, 1}, a_{\\cdot, 2}, \\cdots, a_{\\cdot, j}, \\cdots, a_{\\cdot, n}]\n",
    "$$\n",
    "2. 任意の$j$のとある$n$次元縦ベクトル$b$について\n",
    "$$\\det[a_{\\cdot, 1}, a_{\\cdot, 2}, \\cdots, a_{\\cdot, j} + b, \\cdots, a_{\\cdot, n}] = \n",
    "\\det[a_{\\cdot, 1}, a_{\\cdot, 2}, \\cdots, a_{\\cdot, j}, \\cdots, a_{\\cdot, n}]\n",
    "+ \\det[a_{\\cdot, 1}, a_{\\cdot, 2}, \\cdots, b, \\cdots, a_{\\cdot, n}]\n",
    "$$\n",
    "3. 列の交換で符号が反転\n",
    "4. 単位行列の行列式は１\n",
    "5. 一般の三角行列の行列式は対角成分の積（各列から一つづつ選択する処理を想像するとすぐわかるはず）"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 小行列式\n",
    "\n",
    "行列$A$の正方部分行列$A^{i_1\\cdots i_r}_{j_1 \\cdots j_r}$の行列式を$A$の$r$次の小行列式と呼ぶ。$|A|^{i_1,\\cdots, i_r}_{j_1,\\cdots, j_r}$と書く。\n",
    "特に$A^{i_1\\cdots i_r}_{i_1 \\cdots i_r}$の形のものを主小行列式、$A^{1\\cdots r}_{1 \\cdots r}$の形のものを首座小行列式と呼ぶ。\n",
    "\n",
    "![principle_minor](figs/principle_minor.png)\n",
    "![leading_principle_minor](figs/leading_principle_minor.png)\n",
    "\n",
    "## トレース\n",
    "\n",
    "省略\n",
    "\n",
    "## 余因子・余因子行列\n",
    "\n",
    "$n$次正方行列$A$の$(i, j)$要素$a_{ij}$の余因子は\n",
    "\n",
    "$$\\Delta^{i_1\\cdots i_r}_{j_1 \\cdots j_r}=(-1)^{i+j}|A|^{1, \\cdots, i-1, i+1, \\cdots, n}_{1, \\cdots, j-1, j+1, \\cdots, n}$$\n",
    "\n",
    "で定義される。\n",
    "これは$\\det A$を$a_{i j}$の１次式と見たときの$a_{i j}$の係数とみなせる。\n",
    "\n",
    "![cofactor](figs/cofactor.png)\n",
    "\n",
    "$\\hat{a}_{ij}=\\Delta_{j i}$なる$\\widehat{A}[\\hat{a}_{ij}]$を余因子行列と呼び、$\\operatorname{adj} A$と書く。$i j$の順番に注意。"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Laplace展開\n",
    "\n",
    "余因子を使うと行列式を展開できる。\n",
    "第$p$行に関して展開すると、\n",
    "\n",
    "$$\n",
    "\\operatorname{det} A=\\sum_{j=1}^n a_{p j} \\Delta_{p j}\n",
    "$$\n",
    "\n",
    "が成立する。つまり、行列式は、適当な行$p$について、その要素に要素の余因子をかけたものの和に等しい。\n",
    "Laplace展開をすると、$n$次正方行列の行列式を$n-1$次の行列式に分解しているともみなせる。これを繰り返すと、結局行列式の定義に帰着する。\n",
    "\n",
    "これを使うと、余因子行列$\\hat{A}$と$A$について、\n",
    "\n",
    "$$\\hat{A}A = A \\hat{A}=(\\operatorname{det} A) I$$\n",
    "\n",
    "が成り立つことが示せる。\n",
    "\n",
    "ここで、$A^{-1}:=\\frac{1}{\\operatorname{det} A} \\hat{A}$とおけば、\n",
    "\n",
    "$$A^{-1}A = I$$\n",
    "\n",
    "が成り立つことがわかり、これを逆行列の定義にできる。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 7.25004782e-01 -3.57640147e-17 -7.55218436e-17]\n",
      " [ 5.01022994e-18  7.25004782e-01 -9.06347948e-17]\n",
      " [-3.24351136e-18 -1.18007804e-16  7.25004782e-01]]\n",
      "0.7250047821162905 0.7250047821162906\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from itertools import product\n",
    "\n",
    "# A = np.array([[1, 2, 3], [11, 12, 13], [21, 22, 23]])  # 3 x 3\n",
    "A = np.random.randn(3, 3)  # 3 x 3\n",
    "\n",
    "# 余因子行列の計算（転置しないと余因子行列になりません）\n",
    "A_adj = np.zeros((3, 3))\n",
    "\n",
    "for i, j in product(range(3), range(3)):\n",
    "    A_ij = np.delete(np.delete(A, i, 0), j, 1)\n",
    "    delta = (-1) ** (i+1+j+1) * np.linalg.det(A_ij)\n",
    "    A_adj[i, j] = delta\n",
    "\n",
    "print(A @ A_adj.T)\n",
    "\n",
    "p = 1\n",
    "det_ = 0\n",
    "for j in range(3):\n",
    "    det_ += A_adj[p][j] * A[p][j]\n",
    "\n",
    "print(np.linalg.det(A), det_)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cramerの公式\n",
    "\n",
    "行列式を使うと、特定の線型方程式を要素ごとに求めることができます。\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "A & =\\left[\\boldsymbol{a}_1, \\cdots, \\boldsymbol{a}_n\\right]: \\text { 正則, } A \\boldsymbol{x}=\\boldsymbol{b} \\\\\n",
    "& \\Rightarrow x_j=\\frac{\\operatorname{det}\\left[\\boldsymbol{a}_1, \\cdots, \\boldsymbol{b}, \\cdots, \\boldsymbol{a}_n\\right]}{\\operatorname{det} A}\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "証明しましょう。逆行列の定義から、\n",
    "$$\n",
    "x_j=\\left(A^{-1} \\boldsymbol{b}\\right)_j=\\sum_{i=1}^n \\frac{\\hat{a}_{j i}}{\\operatorname{det} A} b_i=\\frac{1}{\\operatorname{det} A} \\sum_{i=1}^n \\Delta_{i j} b_i\n",
    "$$\n",
    "\n",
    "これについて、Laplace展開より、\n",
    "$$\n",
    "\\operatorname{det}\\left[\\boldsymbol{a}_1, \\cdots, \\boldsymbol{b}, \\cdots, \\boldsymbol{a}_n\\right]=\\sum_{i=1}^n \\Delta_{i j} b_i\n",
    "$$\n",
    "よってなりたちます。"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 積についての行列式\n",
    "\n",
    "$A$と$B$が$n$次正方行列のとき、　\n",
    "\n",
    "$$\n",
    "\\operatorname{det} A B=\\operatorname{det} A \\cdot \\operatorname{det} B\n",
    "$$\n",
    "\n",
    "が成り立ちます。\n",
    "\n",
    "証明しましょう。\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "M= & \\left(\\begin{array}{ll}\n",
    "I & B \\\\\n",
    "A & 0\n",
    "\\end{array}\\right), \\quad \\operatorname{det} M=\\operatorname{det}\\left(\\begin{array}{cc}\n",
    "I & B \\\\\n",
    "0 & -A B\n",
    "\\end{array}\\right)=(-1)^n \\operatorname{det}(A B) \\\\\n",
    "\\operatorname{det} M & =\\sum_\\sigma \\operatorname{sgn} \\sigma \\prod_{i=1}^{2 n} M_{i \\sigma(i)} \\\\\n",
    "& =(-1)^{n^2}\\left(\\sum_{\\sigma_A} \\operatorname{sgn} \\sigma_A \\prod_{i=1}^n A_{i \\sigma_A(i)}\\right)\\left(\\sum_{\\sigma_B} \\operatorname{sgn} \\sigma_B \\prod_{i=1}^n B_{i \\sigma_B(i)}\\right) \\\\\n",
    "& =(-1)^n \\operatorname{det} A \\operatorname{det} B\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "\n",
    "$A$が$m\\times n$行列、$B$が$n\\times m$行列のとき、\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& A: m \\times n \\text { 行列, } B: n \\times m \\text { 行列, } m \\leq n \\\\\n",
    "& \\Rightarrow \\operatorname{det} A B=\\sum_{J:|J|=m} \\operatorname{det} A[J] \\cdot \\operatorname{det} B[J] .\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "が成り立ちます。これをBinet-Cauchyの公式と言います。"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ブロック行列\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "M & =\\left(\\begin{array}{ll}\n",
    "A & B \\\\\n",
    "C & D\n",
    "\\end{array}\\right), A: \\text { 正則 } \\\\\n",
    "& \\Rightarrow \\operatorname{det} M=\\operatorname{det} A \\cdot \\operatorname{det}\\left(D-C A^{-1} B\\right)\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "が成り立ちます。証明は簡単です。\n",
    "まず、\n",
    "\n",
    "$$\n",
    "\\left(\\begin{array}{cc}\n",
    "I & O \\\\\n",
    "-C A^{-1} & I\n",
    "\\end{array}\\right)\\left(\\begin{array}{ll}\n",
    "A & B \\\\\n",
    "C & D\n",
    "\\end{array}\\right)=\\left(\\begin{array}{cc}\n",
    "A & B \\\\\n",
    "O & D-C A^{-1} B\n",
    "\\end{array}\\right)\n",
    "$$\n",
    "\n",
    "なので\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\operatorname{det}\\left(\\begin{array}{ll}\n",
    "A & B \\\\\n",
    "C & D\n",
    "\\end{array}\\right) & =\\operatorname{det}\\left(\\begin{array}{cc}\n",
    "A & B \\\\\n",
    "O & D-C A^{-1} B\n",
    "\\end{array}\\right) \\\\\n",
    "& =\\operatorname{det} A \\cdot \\operatorname{det}\\left(D-C A^{-1} B\\right)\n",
    "\\end{aligned}\n",
    "$$"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hadmardの不等式\n",
    "\n",
    "$$A=(a_{ij})$$\n",
    "が正定値対称であれば、\n",
    "$$\\det A\\leq \\prod_{i=1}^n a_{ii}$$\n",
    "\n",
    "が成立する。\n",
    "\n",
    "行列のサイズ$n$についての帰納法で証明します。\n",
    "\n",
    "$n=1$は明らかに成立。$\\det A\\leq \\prod_{i=1}^{n-1} a_{ii}$が成り立っているとします。　\n",
    "このとき、\n",
    "\n",
    "$A =\n",
    "\\left(\\begin{array}{ll}\n",
    "B & c \\\\\n",
    "c^T &\\delta \n",
    "\\end{array}\\right)\n",
    "$\n",
    "\n",
    "の形式で表すと、$B$は正定値対称です（$x=[0, 1, 1, 1,\\cdots]$みたいなのを考えましょう）\n",
    "\n",
    "すると、$\\det A=\\det B \\cdot (\\delta - c^T B^{-1} c) \\leq \\delta \\det B$\n",
    "\n",
    "であり、あとは帰納法の仮定で証明されます。　"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "shumi-VTLwuKSy-py3.9",
   "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.9.12"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "d6b7cac5e0d2ff733f340da4d53ae5ecfef7f7ad39623f5982b029a09306b36b"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}