day 22 - determinant.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def determinant(x):\n",
    "    if x.size == 1:\n",
    "        return x[0, 0]\n",
    "    \n",
    "    # pivot\n",
    "    i = np.abs(x[:, 0]).argmax()\n",
    "    pivot = x[i, 0]\n",
    "    if np.abs(pivot) < 1e-15:\n",
    "        return 0\n",
    "    \n",
    "    # gauss elimination\n",
    "    n = len(x)\n",
    "    y = x - x[:, 0].reshape(n, 1) @ (x[i, :] / x[i, 0]).reshape(1, n)\n",
    "    y = y[np.arange(n) != i, 1:]\n",
    "\n",
    "    # recursion\n",
    "    return pivot * (-1) ** (i % 2) * determinant(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0.86407152, -0.48119607, -0.60195809, -0.15813597, -0.25164858],\n",
       "       [-0.45656693, -0.86405085, -0.26996402,  0.00863821, -0.42482759],\n",
       "       [ 0.62699481, -0.15693623,  0.88928594, -0.59483779,  0.45047394],\n",
       "       [ 0.27561899,  0.08707643, -0.63000059,  0.19882408,  0.17816101],\n",
       "       [-0.36012304, -0.47399834,  0.17859948,  0.23234741,  0.65332936]])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X = np.random.rand(5, 5) * 2 - 1\n",
    "X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.14322328293127826"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "determinant(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}