groups_SOLUTIONS.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "id": "adbe2e21",
      "metadata": {
        "id": "adbe2e21"
      },
      "source": [
        "# Introduction to Groups\n",
        "### In this notebook, we will implement functions for testing matrix representations of groups.\n",
        "\n",
        "Learning Goals:\n",
        "1. Understand the requirements for a group.\n",
        "2. Test if a set of matrices satisfy the requirements for a group.\n",
        "3. Generate a group from a subset of elements.\n",
        "3. Compute the multiplication table for a group."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "id": "c03ee812",
      "metadata": {
        "id": "c03ee812",
        "outputId": "c195c0f7-4da1-4b62-ad33-e8fc886fb146"
      },
      "outputs": [],
      "source": [
        "import itertools\n",
        "from collections import defaultdict\n",
        "\n",
        "import matplotlib.pyplot as plt\n",
        "import numpy as np"
      ]
    },
    {
      "attachments": {},
      "cell_type": "markdown",
      "id": "b3f8daae",
      "metadata": {
        "id": "b3f8daae"
      },
      "source": [
        "## A group is a set decorated with a binary operations ($\\cdot$) that satisfy the following criteria\n",
        "1. Associativity: for all $a, b, c$ in group $G$, $(a \\cdot b) \\cdot c = a \\cdot (b \\cdot c)$ \n",
        "2. There exists a <u>unique</u> identity element $e$ such that for all $a$ in group G, $e \\cdot a$ = $a \\cdot e$ = $a$\n",
        "3. For every $a$ in G, there exists an element $b$ such that $a \\cdot b = b \\cdot a = e$"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "id": "84a1354c",
      "metadata": {
        "id": "84a1354c"
      },
      "outputs": [],
      "source": [
        "def permutation_group(n):\n",
        "    elements = []\n",
        "    for p in itertools.permutations(range(n)):\n",
        "        m = np.zeros((n, n))\n",
        "        m[range(n), p] = 1\n",
        "        elements.append(m)\n",
        "    return np.stack(elements, axis=0)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "id": "bc125b35",
      "metadata": {
        "id": "bc125b35"
      },
      "outputs": [],
      "source": [
        "p2 = permutation_group(2)\n",
        "p3 = permutation_group(3)\n",
        "p4 = permutation_group(4)\n",
        "p3_dup_id = np.concatenate([p3, np.eye(3)[np.newaxis]])\n",
        "p3_dup_elem = np.concatenate([p3, p3[1][np.newaxis]])\n",
        "p3_missing_id = p3[1:]\n",
        "p3_missing_elem = p3[:-1]\n",
        "# test_group(p3_dup_id)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "id": "8d61dc5c",
      "metadata": {
        "id": "8d61dc5c"
      },
      "outputs": [],
      "source": [
        "def test_membership_index(test, members, tol=1e-6):\n",
        "    \"\"\"Determine if test matrix in member matrices and return indices of match.\n",
        "    Inputs:\n",
        "        test: np.array shape [d, d] or [m, d, d]\n",
        "        tol: float numerical tolerance \n",
        "        members: np.array shape [n, d, d]\n",
        "    Output:\n",
        "        If test is in member, returns index / indices that match. Otherwise empty list.\n",
        "        Hint: Use np.nonzero, np.all, and np.any. Be mindful of your axes!\n",
        "    \"\"\"\n",
        "    if test.ndim == members.ndim - 1:\n",
        "        test = test[np.newaxis]\n",
        "\n",
        "    assert test.shape[1:] == members.shape[1:]\n",
        "    diff = test[np.newaxis, :] - members[:, np.newaxis]  # Since we have floats checking close to zero is easiest\n",
        "    diff = diff.reshape(len(members), len(test), -1)  # [members, test, :]\n",
        "    equal = np.all(np.abs(diff) < tol, axis=2)  # [members, test] True if equal\n",
        "    return np.nonzero(equal)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "id": "9f4f3d8d",
      "metadata": {
        "id": "9f4f3d8d"
      },
      "outputs": [],
      "source": [
        "# test_membership_index\n",
        "assert np.equal(test_membership_index(p3, p3), np.arange(6).reshape(1, -1).repeat(2, axis=0)).all()\n",
        "assert np.allclose(test_membership_index(p3, p3), np.arange(6).reshape(1, -1).repeat(2, axis=0))\n",
        "assert np.equal(test_membership_index(np.arange(9).reshape(3, 3), p3), (np.array([]), np.array([]))).all()\n",
        "assert np.allclose(test_membership_index(np.arange(9).reshape(3, 3), p3), (np.array([]), np.array([])))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "id": "6f480169",
      "metadata": {
        "id": "6f480169"
      },
      "outputs": [],
      "source": [
        "def test_membership(test, members, tol=1e-6):\n",
        "    \"\"\"Determine if test matrix in member matrices and return True / False / ValueError for duplicates.\n",
        "    Inputs:\n",
        "        test: np.array shape [d, d]\n",
        "        tol: float numerical tolerance\n",
        "        members: np.array shape [n, d, d]\n",
        "    Output:\n",
        "        If len(test.shape) == 2, return True if match or False if no match\n",
        "        If len(test.shape) == 3, return list of True / False values\n",
        "        Hint: Remember to handle all cases!\n",
        "    \"\"\"\n",
        "    i, j = test_membership_index(test, members, tol=1e-6)\n",
        "\n",
        "    if test.ndim == 2:\n",
        "        return len(i) > 0\n",
        "\n",
        "    out = np.zeros(len(test), dtype=bool)\n",
        "    out[j] = True\n",
        "    return out\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 7,
      "id": "a3a231ad",
      "metadata": {
        "id": "a3a231ad"
      },
      "outputs": [],
      "source": [
        "# test_membership\n",
        "assert np.equal(test_membership(p3[::-1], p3), [True] * 6).all()\n",
        "assert np.equal(test_membership(np.arange(9).reshape(3, 3), p3), False).all()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 8,
      "id": "d3ccdc56",
      "metadata": {
        "id": "d3ccdc56"
      },
      "outputs": [],
      "source": [
        "def generate_new_elements(matrices, max_recurse=10, tol=1e-6):\n",
        "    \"\"\"Generate new group elements from matrices (group representations)\n",
        "    Input:\n",
        "        matrices: np.array of shape [n, d, d] of known elements\n",
        "        max_recurse: maximum dept of recursion\n",
        "    Output:\n",
        "        new: np.array of shape [m, d, d] of new elements with shape [0, d, d] if no new element\n",
        "    \"\"\"\n",
        "    _, d, d2 = matrices.shape\n",
        "    assert d == d2\n",
        "    new = np.zeros((0, d, d))\n",
        "    if max_recurse == 0:\n",
        "        yield new\n",
        "    for i, m in enumerate(matrices):\n",
        "        new_elements = np.einsum(\"ij,djk->dik\", m, matrices[i:])\n",
        "        membership = test_membership(new_elements, matrices, tol)\n",
        "        # Any matrices not in original matrices (False) are new\n",
        "        new = new_elements[~membership]\n",
        "        if new.shape[0] != 0:\n",
        "            yield new\n",
        "            break\n",
        "    if new.shape[0] != 0:\n",
        "        for new in generate_new_elements(\n",
        "            np.concatenate([matrices, new], axis=0), max_recurse - 1, tol\n",
        "        ):\n",
        "            yield new\n",
        "    else:\n",
        "        yield new\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 9,
      "id": "9b86a600",
      "metadata": {
        "id": "9b86a600"
      },
      "outputs": [],
      "source": [
        "# generate_new_elements\n",
        "assert(np.allclose(np.concatenate([p for p in generate_new_elements(p3)]), np.empty([0, 3, 3])))\n",
        "assert(np.allclose(np.concatenate([p for p in generate_new_elements(p3[:-1])]), p3[-1:]))\n",
        "assert(np.allclose(np.concatenate([p for p in generate_new_elements(p3[:-2])]), p3[-2:]) or\n",
        " np.allclose(np.concatenate([p for p in generate_new_elements(p3[:-2])]), p3[-2:][[1, 0]]))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 10,
      "id": "0cf52d97",
      "metadata": {
        "id": "0cf52d97"
      },
      "outputs": [],
      "source": [
        "def test_closed(matrices, tol=1e-6):\n",
        "    \"\"\"Tests if group is closed.\n",
        "    Input:\n",
        "        matrices: np.array of shape [n, d, d]\n",
        "        tol: float numerical tolerance\n",
        "    Output:\n",
        "        True if closed and False if not.\n",
        "        Hint: Use generate_new_elements.\n",
        "    \"\"\"\n",
        "    for new in generate_new_elements(matrices):\n",
        "        if new.shape[0] != 0:\n",
        "            return False\n",
        "    return True"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 11,
      "id": "c9bddb9d",
      "metadata": {
        "id": "c9bddb9d"
      },
      "outputs": [],
      "source": [
        "# test_closed\n",
        "assert(test_closed(p2))\n",
        "assert(test_closed(p2[:-1])) # identity\n",
        "assert(test_closed(p3))\n",
        "assert(not test_closed(p3[:-1]))\n",
        "assert(not test_closed(p3[:-2]))\n",
        "assert(test_closed(p4))\n",
        "assert(not test_closed(p4[:-1]))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 12,
      "id": "258823c0",
      "metadata": {
        "id": "258823c0"
      },
      "outputs": [],
      "source": [
        "def test_identity(matrices, tol=1e-6):\n",
        "    \"\"\"Tests if identity is present in matrices.\n",
        "    Input:\n",
        "        matrices: np.array of shape [n, d, d]\n",
        "        tol: float numerical tolerance\n",
        "    Output:\n",
        "        False if no identity,\n",
        "        (i, m) if identity is present where i is index and m is matrix,\n",
        "        raises ValueError if multiple identities.\n",
        "    \"\"\"\n",
        "    identity = []\n",
        "    for i, m in enumerate(matrices):\n",
        "        new_elements = np.einsum('ij,djk->dik', m, matrices)\n",
        "        if np.allclose(new_elements, matrices, rtol=tol):\n",
        "            identity.append((i, m))\n",
        "    if len(identity) == 0:\n",
        "        return False\n",
        "\n",
        "    if len(identity) == 1:\n",
        "        return identity[0]\n",
        "\n",
        "    raise ValueError(\"Multiple identities {}.\".format(ids))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 13,
      "id": "95dec2ea",
      "metadata": {
        "id": "95dec2ea"
      },
      "outputs": [],
      "source": [
        "assert(not test_identity(p3[1:]))\n",
        "assert(test_identity(p3)[0] == 0)\n",
        "assert(np.allclose(test_identity(p3)[1], np.eye(3)))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 14,
      "id": "aceb5a07",
      "metadata": {
        "id": "aceb5a07"
      },
      "outputs": [],
      "source": [
        "def test_inverses(matrices, tol=1e-6):\n",
        "    \"\"\"Tests inverses for matrices.\n",
        "    Input:\n",
        "        matrices: np.array of shape [n, d, d]\n",
        "        tol: float numerical tolerance\n",
        "    Output:\n",
        "        np.array of shape [n] if single inverse exist for all elements,\n",
        "        otherwise raises ValueError.\n",
        "    \"\"\"\n",
        "    if not test_identity(matrices):\n",
        "        raise ValueError(\"missing identity\")\n",
        "    i, identity = test_identity(matrices)\n",
        "    inverses = []\n",
        "    for i, m in enumerate(matrices):\n",
        "        new_elements = np.einsum('ij,djk->dik', m, matrices)\n",
        "        result = new_elements - identity\n",
        "        inv_index = np.nonzero(np.all(np.all(np.abs(result) < tol, axis=-1), axis=-1))[0]\n",
        "        if inv_index.shape[0] != 1:\n",
        "            raise ValueError(\"Number of inverses incorrect {} should be 1\".format(inv_index.shape[0]))\n",
        "        inverses.append(inv_index)\n",
        "    return np.concatenate(inverses, axis=0)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 15,
      "id": "5647a464",
      "metadata": {
        "id": "5647a464"
      },
      "outputs": [],
      "source": [
        "# test_inverses\n",
        "assert(np.equal(test_inverses(p3), np.array([0, 1, 2, 4, 3, 5])).all())\n",
        "assert(np.equal(test_inverses(np.eye(3).reshape(1, 3, 3)), np.array([0])).all())"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 16,
      "id": "b92503bd",
      "metadata": {
        "id": "b92503bd"
      },
      "outputs": [],
      "source": [
        "def test_group(matrices, tol=1e-6):\n",
        "    \"\"\"Tests whether the matrices form a group.\n",
        "    Input:\n",
        "        matrices: np.array of shape [n, d, d]\n",
        "        tol: float numberical tolerance\n",
        "    Output:\n",
        "        True if group, False if not.\n",
        "    \"\"\"\n",
        "    # Test identity\n",
        "    try:\n",
        "        assert test_identity(matrices) \n",
        "    except:\n",
        "        print(\"Multiple or missing identity element(s).\")\n",
        "        return False\n",
        "    # Test for inverses (and duplicates)\n",
        "    try:\n",
        "        test_inverses(matrices, tol)\n",
        "    except:\n",
        "        print(\"Does not contain all inverses or duplicate elements.\")\n",
        "        return False\n",
        "    # Test closed\n",
        "    if not test_closed(matrices):\n",
        "        print(\"Not closed.\")\n",
        "        return False\n",
        "    print(\"Elements form a group!\")\n",
        "    return True "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 17,
      "id": "4d14d7f2",
      "metadata": {
        "id": "4d14d7f2",
        "outputId": "e15cbae9-5944-4554-8a14-403a427adf8a"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Elements form a group!\n",
            "Multiple or missing identity element(s).\n",
            "Does not contain all inverses or duplicate elements.\n",
            "Multiple or missing identity element(s).\n",
            "Not closed.\n"
          ]
        }
      ],
      "source": [
        "# test_group\n",
        "assert test_group(p3) == True\n",
        "assert test_group(p3_dup_id) == False\n",
        "assert test_group(p3_dup_elem) == False\n",
        "assert test_group(p3_missing_id) == False\n",
        "assert test_group(p3_missing_elem) == False"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 18,
      "id": "dbd314b6",
      "metadata": {
        "id": "dbd314b6"
      },
      "outputs": [],
      "source": [
        "def make_multiplication_table(matrices, tol=1e-6):\n",
        "    \"\"\"Makes multiplication table for group.\n",
        "    Input:\n",
        "        matrices: np.array of shape [n, d, d]\n",
        "        tol: float numberical tolerance\n",
        "    Output:\n",
        "        Group multiplication table.\n",
        "        np.array of shape [n, n] where entries correspond to indices of first dim of matrices.\n",
        "    \"\"\"\n",
        "    n, d, d2 = matrices.shape\n",
        "    assert d == d2\n",
        "    mtables = np.einsum('nij,mjk->nmik', matrices, matrices)\n",
        "    result = mtables.reshape(1, n, n, d, d) - matrices.reshape(n, 1, 1, d, d)\n",
        "    indices = np.nonzero(np.all(np.all(np.abs(result) < tol, axis=-1), axis=-1))\n",
        "    indices = np.stack(indices)\n",
        "    table = np.zeros([n, n], dtype=np.int32)\n",
        "    table[indices[1], indices[2]] = indices[0]\n",
        "    return table"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 19,
      "id": "50e695c7",
      "metadata": {
        "id": "50e695c7"
      },
      "outputs": [],
      "source": [
        "# make_multiplication_table\n",
        "assert(np.equal(make_multiplication_table(p2), np.array([[0, 1], [1, 0]])).all())\n",
        "assert(np.equal(make_multiplication_table(p3), np.array([[0, 1, 2, 3, 4, 5],\n",
        "       [1, 0, 3, 2, 5, 4],\n",
        "       [2, 4, 0, 5, 1, 3],\n",
        "       [3, 5, 1, 4, 0, 2],\n",
        "       [4, 2, 5, 0, 3, 1],\n",
        "       [5, 3, 4, 1, 2, 0]], dtype=np.int32)).all())"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "provenance": []
    },
    "gpuClass": "standard",
    "kernelspec": {
      "display_name": "base",
      "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.10.9"
    },
    "vscode": {
      "interpreter": {
        "hash": "f26faf9d33dc8b83cd077f62f5d9010e5bc51611e479f12b96223e2da63ba699"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 5
}