Find Z2 rank.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##Find Z2 Matrix Rank\n",
    "###By Python\n",
    "**Algorithm**: Gaussian Elimination (GE) with pivoting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "# find Z2 rank of integer matrix\n",
    "def Z2rank(mat):\n",
    "    # mat input as numpy.matrix, and destroyed on output!\n",
    "    # caller must ensure mat contains only 0 and 1.\n",
    "    nr, nc = mat.shape # get num of rows and cols\n",
    "    r = 0 # current row index\n",
    "    for i in range(nc): # run through cols\n",
    "        if r == nr: # row exhausted first\n",
    "            return r # row rank is full, early return\n",
    "        if mat[r, i] == 0: # need to find pivot\n",
    "            found = False # set a flag\n",
    "            for k in range(r + 1, nr):\n",
    "                if mat[k, i]: # mat[k, i] nonzero\n",
    "                    found = True # pivot found in k\n",
    "                    break\n",
    "            if found: # if pivot found in k\n",
    "                mat[[r, k], :] = mat[[k, r], :] # row swap\n",
    "            else: # if pivot not found\n",
    "                continue # done with this col\n",
    "        # pivot has moved to mat[r, i], perform GE\n",
    "        for j in range(r + 1, nr):\n",
    "            if mat[j, i]: # mat[j, i] nonzero\n",
    "                mat[j, i:] = (mat[j, i:] + mat[r, i:])%2\n",
    "        r += 1 # rank inc\n",
    "    # col exhausted, last nonvanishing row indexed by r\n",
    "    return r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example**: consider the matrix\n",
    "$$A=\\left(\\begin{matrix}0&1&1\\\\1&0&1\\\\1&1&0\\end{matrix}\\right).$$\n",
    "Its rank over real field is different from its rank over Z2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 1 1]\n",
      " [1 0 1]\n",
      " [1 1 0]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = np.matrix([[0,1,1],[1,0,1],[1,1,0]])\n",
    "print(A)\n",
    "Z2rank(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 1 1]\n",
      " [1 0 1]\n",
      " [1 1 0]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = np.matrix([[0,1,1],[1,0,1],[1,1,0]])\n",
    "print(A)\n",
    "np.linalg.matrix_rank(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "###By Fortran"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "z2rank - Function signature:\n",
      "  r = z2rank(mat)\n",
      "Required arguments:\n",
      "  mat : input rank-2 array('i') with bounds (nr,nc)\n",
      "Return objects:\n",
      "  r : int\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from fortran_ext import z2rank\n",
    "print(z2rank.__doc__)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 1 1]\n",
      " [1 0 1]\n",
      " [1 1 0]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = np.matrix([[0,1,1],[1,0,1],[1,1,0]])\n",
    "print(A)\n",
    "z2rank(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###Bechmark"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "As = []\n",
    "for k in range(100):\n",
    "    n = np.random.randint(3, 30)\n",
    "    As.append(np.matrix(np.random.randint(2, size=(n,n))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%reload_ext snakeviz"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " \n",
      "*** Profile stats marshalled to file '/var/folders/tl/lwpcq5qj049ftcj7pvhkzv_h0000gn/T/tmpqhqnw0'. \n"
     ]
    }
   ],
   "source": [
    "%snakeviz [z2rank(A) for A in As]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " \n",
      "*** Profile stats marshalled to file '/var/folders/tl/lwpcq5qj049ftcj7pvhkzv_h0000gn/T/tmpm4_631'. \n"
     ]
    }
   ],
   "source": [
    "%snakeviz [Z2rank(A) for A in As]"
   ]
  },
  {
   "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.3.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}