All_groups_of_order_n.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Encontrando todos los posibles grupos de orden n computacionalmente "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En este Notebook presentamos un algoritmo que encuentra todos los posibles grupos de orden $n$ fijándose en las posibles tablas de Cayley que se pueden armar usando $n$ letras."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El problema es el siguiente: encontrar todas las matrices $n\\times n$ construibles con $n$ letras tales que una letra no aparezca más de dos veces en la misma fila y en la misma columna."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Usando *depth-first search*, encontramos todas las posibilidades de llenar la tabla cambiando los $-1$ por un número entre $0$ y $5$ de tal forma que el mismo número no aparezca dos veces en la misma fila y misma columna."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comenzamos escribiendo una serie de funciones auxiliares:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def discarter_for_rows(A):\n",
    "    '''\n",
    "    This function returns True if the matrix A is such that a number from 1 to 5 appears twice in\n",
    "    a row or in a column (that is, if the matrix is to be discarted).\n",
    "    '''\n",
    "    A = A.tolist()\n",
    "    rows_of_A = [A[k] for k in range(len(A))]\n",
    "    # print('rows: ' + str(rows_of_A))\n",
    "    for row in rows_of_A:\n",
    "        dict_of_repetitions = {value: row.count(value) for value in row}\n",
    "        # print('row: ' + str(row) + ', dict: ' + str(dict_of_repetitions))\n",
    "        for element in dict_of_repetitions:\n",
    "            if element != -1 and dict_of_repetitions[element] > 1:\n",
    "                return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def discard(A):\n",
    "    '''\n",
    "    This function checks whether a number (different from -1) appears twice in a row or \n",
    "    in a column.\n",
    "    '''\n",
    "    return discarter_for_rows(A) or discarter_for_rows(A.T)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from queue import LifoQueue, Queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def find_first_unvisited_position(A):\n",
    "    for i in range(1, len(A)):\n",
    "        for j in range(1, len(A)):\n",
    "            if A[i, j] == -1:\n",
    "                return (i,j)\n",
    "    \n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_finished(A):\n",
    "    return not -1 in A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Acá implementamos un análogo a DFS para encontrar todas las posibles soluciones:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 161,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dfs_in_A(A):\n",
    "    '''\n",
    "    This function returns a list of all solutions to the problem.\n",
    "    '''\n",
    "    list_of_solutions = []\n",
    "    stack = LifoQueue()\n",
    "    stack.put(A)\n",
    "    while not stack.empty():\n",
    "        A = stack.get()\n",
    "        if discard(A):\n",
    "            continue\n",
    "        if is_finished(A):\n",
    "            list_of_solutions.append(A)\n",
    "            continue\n",
    "        \n",
    "        position = find_first_unvisited_position(A)\n",
    "        for k in range(len(A)):\n",
    "            B = A.copy()\n",
    "            B[position] = k\n",
    "            stack.put(B)\n",
    "        # print('current list of solutions: ' + str(list_of_solutions))\n",
    "    return list_of_solutions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Una vez tenemos `dfs_in_A`, podemos implementar una función que toma un número $n$ y encuentra todas las matrices de tamaño $n\\times n$ que satisfacen la propiedad, fijando en la primera fila y columna el módulo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 162,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def find_all_matrices(number):\n",
    "    A = np.zeros((number, number))\n",
    "    for k in range(number):\n",
    "        A[0, k] = k\n",
    "        A[k, 0] = k\n",
    "    for i in range(1, number):\n",
    "        for j in range(1, number):\n",
    "            A[i, j] = -1\n",
    "    list_of_sols = dfs_in_A(A)\n",
    "    return list_of_sols"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.  1.  2.  3.]\n",
      " [ 1.  3.  0.  2.]\n",
      " [ 2.  0.  3.  1.]\n",
      " [ 3.  2.  1.  0.]]\n",
      "[[ 0.  1.  2.  3.]\n",
      " [ 1.  2.  3.  0.]\n",
      " [ 2.  3.  0.  1.]\n",
      " [ 3.  0.  1.  2.]]\n",
      "[[ 0.  1.  2.  3.]\n",
      " [ 1.  0.  3.  2.]\n",
      " [ 2.  3.  1.  0.]\n",
      " [ 3.  2.  0.  1.]]\n",
      "[[ 0.  1.  2.  3.]\n",
      " [ 1.  0.  3.  2.]\n",
      " [ 2.  3.  0.  1.]\n",
      " [ 3.  2.  1.  0.]]\n"
     ]
    }
   ],
   "source": [
    "list_of_solutions = find_all_matrices(4)\n",
    "for solution in list_of_solutions:\n",
    "    print(solution)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La segunda y la cuarta corresponden a $\\mathbb{Z}_4$ y al grupo $4$ de Klein respectivamente. La primera y la tercera son otras presentaciones de $\\mathbb{Z}_4$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 181,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def build_operation_from_matrix(A):\n",
    "    def multiply(a, b):\n",
    "        '''\n",
    "        Here we assume that a and b are numbers from 0 to len(A)-1.\n",
    "        '''\n",
    "        return int(A[a,b])\n",
    "    return multiply\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 189,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Z6_table = list_of_solutions[1] # we grab the second matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 190,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "sum_Z6 = build_operation_from_matrix(Z6_table)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 172,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum_Z6(3,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Pregroup:\n",
    "    def __init__(self, _matrix):\n",
    "        self.cayley_table = _matrix\n",
    "        self.multiply = build_operation_from_matrix(_matrix)\n",
    "    \n",
    "    def operate(self, a, b):\n",
    "        return int(self.cayley_table[a, b])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 195,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_pregroup_associative(pg):\n",
    "    n = len(pg.cayley_table)\n",
    "    associativity_flag = True\n",
    "    for a in range(n):\n",
    "        for b in range(n):\n",
    "            for c in range(n):\n",
    "                associativity_flag = associativity_flag and (pg.operate(a,pg.operate(b,c)) ==\n",
    "                                                                    pg.operate(pg.operate(a,b),c))\n",
    "    return associativity_flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 191,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Z6 = Pregroup(Z6_table)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 192,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 192,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_pregroup_associative(Z6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 184,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Klein_table = list_of_solutions[3]\n",
    "Klein = Pregroup(Klein_table)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 187,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 187,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_pregroup_associative(Klein)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 188,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 188,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Other_1_table = list_of_solutions[0]\n",
    "Other_1 = Pregroup(Other_1_table)\n",
    "is_pregroup_associative(Other_1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 194,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 194,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Other_2_table = list_of_solutions[2]\n",
    "Other_2 = Pregroup(Other_2_table)\n",
    "is_pregroup_associative(Other_2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 196,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "potential_groups_of_order_5 = find_all_matrices(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En las potenciales tablas de Cayley para grupos de orden 5 ya aparecen varias que no son asociativas."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 202,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_groups_from_matrix_list(list_of_matrices):\n",
    "    list_of_group_matrices = []\n",
    "    for matrix in list_of_matrices:\n",
    "        pregroup = Pregroup(matrix)\n",
    "        if is_pregroup_associative(pregroup):\n",
    "            list_of_group_matrices.append(matrix)\n",
    "    \n",
    "    return list_of_group_matrices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 204,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.  1.  2.  3.  4.]\n",
      " [ 1.  4.  3.  0.  2.]\n",
      " [ 2.  3.  1.  4.  0.]\n",
      " [ 3.  0.  4.  2.  1.]\n",
      " [ 4.  2.  0.  1.  3.]]\n",
      "[[ 0.  1.  2.  3.  4.]\n",
      " [ 1.  4.  0.  2.  3.]\n",
      " [ 2.  0.  3.  4.  1.]\n",
      " [ 3.  2.  4.  1.  0.]\n",
      " [ 4.  3.  1.  0.  2.]]\n",
      "[[ 0.  1.  2.  3.  4.]\n",
      " [ 1.  3.  4.  2.  0.]\n",
      " [ 2.  4.  1.  0.  3.]\n",
      " [ 3.  2.  0.  4.  1.]\n",
      " [ 4.  0.  3.  1.  2.]]\n",
      "[[ 0.  1.  2.  3.  4.]\n",
      " [ 1.  3.  0.  4.  2.]\n",
      " [ 2.  0.  4.  1.  3.]\n",
      " [ 3.  4.  1.  2.  0.]\n",
      " [ 4.  2.  3.  0.  1.]]\n",
      "[[ 0.  1.  2.  3.  4.]\n",
      " [ 1.  2.  4.  0.  3.]\n",
      " [ 2.  4.  3.  1.  0.]\n",
      " [ 3.  0.  1.  4.  2.]\n",
      " [ 4.  3.  0.  2.  1.]]\n",
      "[[ 0.  1.  2.  3.  4.]\n",
      " [ 1.  2.  3.  4.  0.]\n",
      " [ 2.  3.  4.  0.  1.]\n",
      " [ 3.  4.  0.  1.  2.]\n",
      " [ 4.  0.  1.  2.  3.]]\n"
     ]
    }
   ],
   "source": [
    "groups_of_order_5 = get_groups_from_matrix_list(potential_groups_of_order_5)\n",
    "for matrix in groups_of_order_5:\n",
    "    print(matrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En teoría, todas estas matrices deberían corresponder a diferentes presentaciones de $\\mathbb{Z}_5$. Queda la pregunta abierta: **¿hay una forma eficiente de determinar si dos grupos son isomorfos a través de sus tablas de Cayley?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cosas por hacer:\n",
    "- Contestar la pregunta del comentario anterior.\n",
    "- Implementar un par de funciones que determinen, a partir de la tabla de Cayley, si un pregrupo es modulativo e invertivo."
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}