{ "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": {} } ] }