{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Using recursion to find determinant.\n",
      "\n",
      "$\\newcommand{\\matrix}[3]{\\begin{pmatrix}#1_{11} & \\cdots & #1_{1#3} \\\\ \\vdots & \\ddots & \\vdots \\\\ #1_{#21} & \\cdots & #1_{#2#3} \\end{pmatrix}}$ $\\newcommand{\\amatrix}[1]{\\matrix{A}{#1}{#1}}$\n",
      "Recall the high school method of finding determinant.\n",
      "\\begin{equation}\n",
      "\\det \\amatrix{n} = \\sum_{i=1}^n (-1)^{i-1} a_{1i} \\det A^{1i} \n",
      "\\end{equation}\n",
      "where $A^{1i}$ is obtained from $A$ by deleting the row and column containing $a_{1i}$.\n",
      "\n",
      "## Given a matrix, finding its cofactors\n",
      "Write a function `cofactor(A, i, j)`, which given a matrix `A` and a position `(i, j)`, *returns* the cofactor $A^{ij}$.\n",
      "\n",
      "## Determinant.\n",
      "Now using recursion, write a function `determinant(A)`, which given a matrix `A`, *returns* its determinant."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def cofactor(A, i, j) :\n",
      "    r = len(A) # = number of rows\n",
      "    if r == 0 :\n",
      "        print \"Cannot of cofactors of an empty matrix.\"\n",
      "        rmat = [] # matrix to be returned\n",
      "    else :\n",
      "        c = len(A[0]) # number of columns\n",
      "        if i < 0 or i >= r or j < 0 or j >= c :\n",
      "            print \"Either %d or %d is out of range.\" % (i, j)\n",
      "            rmat = None\n",
      "        else :\n",
      "            rmat = []\n",
      "            for k in range(r) :\n",
      "                if k != i :\n",
      "                    rmatrow = []\n",
      "                    for l in range(c) :\n",
      "                        if l != j :\n",
      "                            rmatrow.append(A[k][l])\n",
      "                    rmat.append(rmatrow)\n",
      "    return rmat"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Example\n",
      "A = [[1,2,3], [4,5,6], [7,8,9]]\n",
      "print cofactor(A, 0,2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[[4, 5], [7, 8]]\n"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def determinant(A) :\n",
      "    r = len(A) # number of rows in A\n",
      "    if r == 0 :\n",
      "        print \"Empty matrix. Using a convention that determinant is zero.\"\n",
      "        det = 0\n",
      "    else :\n",
      "        c = len(A[0])\n",
      "        if r != c :\n",
      "            print \"Determinant can only by computed for square matrices.\"\n",
      "            det = None\n",
      "        else :\n",
      "            if r == 1 :\n",
      "                det = A[0][0]\n",
      "            else :\n",
      "                det = 0\n",
      "                sign = 1\n",
      "                for i in range(r) :\n",
      "                    det += sign * A[0][i] * determinant(cofactor(A, 0, i))\n",
      "                    sign *= -1\n",
      "    return det"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Example\n",
      "print determinant(A)\n",
      "print determinant([[1, 2, 4], [0, 2, 4], [0, 0, 4]])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n",
        "8\n"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Matrix as a sum of a symmetric and a skew symmetric matrix.\n",
      "Write a function `decompose(A)`, which given a square matrix `A` of size $n$, *returns* a pair `(B, C)` of square matrices of size $n$ such that $A = B + C$ and $B$ is symmetric, while $C$ is anti-symmetric.\n",
      "\n",
      "#### Hint\n",
      "$A = (A + A^t)/2 + (A - A^t)/2$."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def decompose(A) :\n",
      "    r = len(A)\n",
      "    if r == 0 :\n",
      "        dec = ([], [])\n",
      "    else :\n",
      "        c = len(A[0])\n",
      "        if r != c :\n",
      "            print \"Cannot decompose matrices which are not square.\"\n",
      "            dec = None\n",
      "        else :\n",
      "            B = []\n",
      "            C = []\n",
      "            for i in range(r) :\n",
      "                Brow = []\n",
      "                Crow = []\n",
      "                for j in range(r) :\n",
      "                    Brow.append((A[i][j] + A[j][i])/2.0)\n",
      "                    Crow.append((A[i][j] - A[j][i])/2.0)\n",
      "                B.append(Brow)\n",
      "                C.append(Crow)\n",
      "            dec = (B, C)\n",
      "    return dec"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Examples\n",
      "print decompose([])\n",
      "print decompose([[]])\n",
      "print decompose(A)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "([], [])\n",
        "Cannot decompose matrices which are not square.\n",
        "None\n",
        "([[1.0, 3.0, 5.0], [3.0, 5.0, 7.0], [5.0, 7.0, 9.0]], [[0.0, -1.0, -2.0], [1.0, 0.0, -1.0], [2.0, 1.0, 0.0]])\n"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Checking if a list of lists of numbers is actually a matrix\n",
      "Till now in class, we have been assuming that the list of lists, a user inputs is actually a matrix, i.e. all the rows have the same number of elements. Write a code `is_matrix(lst_of_lsts)` which takes a list of lists of numbers as input and returns `True` if the list of lists represent a matrix, `False` otherwise. Basically you have to check if all the sublists have the same number of elements."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def is_matrix(l) :\n",
      "    r = len(l)\n",
      "    if r == 0 :\n",
      "        ismatrix = True\n",
      "    else :\n",
      "        c = len(l[0])\n",
      "        ismatrix = True\n",
      "        for i in range(1, r) :\n",
      "            if len(l[i]) != c :\n",
      "                ismatrix = False\n",
      "    return ismatrix"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Example\n",
      "print is_matrix([])\n",
      "print is_matrix([[1, 3, 4]])\n",
      "print is_matrix([[], [], []])\n",
      "# print is_matrix([1, 2, 4])\n",
      "print is_matrix([[1], [3,4], [5]])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "True\n",
        "True\n",
        "True\n",
        "False\n"
       ]
      }
     ],
     "prompt_number": 8
    }
   ],
   "metadata": {}
  }
 ]
}