Created
January 23, 2023 22:50
-
-
Save mariogeiger/c93deddb401f9b5fc45c318cac3cfcc8 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "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": 6, | |
| "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": 35, | |
| "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": 36, | |
| "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": 38, | |
| "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": 34, | |
| "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": 41, | |
| "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": 42, | |
| "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": 43, | |
| "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": 44, | |
| "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": 63, | |
| "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": 64, | |
| "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": 65, | |
| "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": 66, | |
| "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": 67, | |
| "id": "b92503bd", | |
| "metadata": { | |
| "id": "b92503bd" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def test_group(matrices, tol=1e-6):\n", | |
| " \"\"\"Tests whether matrices for group representation.\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": 68, | |
| "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": 69, | |
| "id": "dbd314b6", | |
| "metadata": { | |
| "id": "dbd314b6" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def make_multiplication_table(matrices, tol=1e-6):\n", | |
| " \"\"\"Tests whether matrices for group representation.\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": 70, | |
| "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())" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "id": "0aae0f5c", | |
| "metadata": { | |
| "id": "0aae0f5c" | |
| }, | |
| "source": [ | |
| "## Let's test to see if the following elements form a group" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 71, | |
| "id": "86a231fb", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 129 | |
| }, | |
| "id": "86a231fb", | |
| "outputId": "b98e643d-139c-4e94-de59-cd8e8b6841a7" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAgMAAAClCAYAAADBAf6NAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjYuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8o6BhiAAAACXBIWXMAAA9hAAAPYQGoP6dpAAADUElEQVR4nO3Y0W3CMBRAUaiYgv/+s0TFBJ2yEyCWYArUKUhHaCQgVnLP+baUJ9mxrryfpmnaAQBZH6MHAADGEgMAECcGACBODABAnBgAgDgxAABxYgAA4sQAAMQd5i58/H6+c45FnI+n0SPkXR8/i3/z6+N78W++2uV+Gz3CU7bw7404u+5dXmHO2fUyAABxYgAA4sQAAMSJAQCIEwMAECcGACBODABAnBgAgDgxAABxYgAA4sQAAMSJAQCIEwMAECcGACBODABAnBgAgDgxAABxYgAA4sQAAMSJAQCIEwMAECcGACBODABAnBgAgDgxAABxYgAA4sQAAMSJAQCIEwMAECcGACBODABAnBgAgDgxAABxYgAA4sQAAMSJAQCIEwMAECcGACBODABAnBgAgDgxAABxYgAA4sQAAMSJAQCIEwMAECcGACBODABAnBgAgLjD3IXn4+mNYyzjcr+NHuEpW9iDEda+77udva+y7+Nt4f6Yw8sAAMSJAQCIEwMAECcGACBODABAnBgAgDgxAABxYgAA4sQAAMSJAQCIEwMAECcGACBODABAnBgAgDgxAABxYgAA4sQAAMSJAQCIEwMAECcGACBODABAnBgAgDgxAABxYgAA4sQAAMSJAQCIEwMAECcGACBODABAnBgAgDgxAABxYgAA4sQAAMSJAQCIEwMAECcGACBODABAnBgAgDgxAABxYgAA4sQAAMSJAQCIEwMAECcGACBODABAnBgAgDgxAABxh9EDLOl8PI0e4SmX+230CKu09n3fAme3a+17v4X74/r4f42XAQCIEwMAECcGACBODABAnBgAgDgxAABxYgAA4sQAAMSJAQCIEwMAECcGACBODABAnBgAgDgxAABxYgAA4sQAAMSJAQCIEwMAECcGACBODABAnBgAgDgxAABxYgAA4sQAAMSJAQCIEwMAECcGACBODABAnBgAgDgxAABxYgAA4sQAAMSJAQCIEwMAECcGACBODABAnBgAgDgxAABxYgAA4sQAAMSJAQCIEwMAECcGACBODABAnBgAgDgxAABxYgAA4sQAAMTtp2maRg8BAIzjZQAA4sQAAMSJAQCIEwMAECcGACBODABAnBgAgDgxAABxYgAA4v4AE1ktkag5/8kAAAAASUVORK5CYII=", | |
| "text/plain": [ | |
| "<Figure size 640x480 with 3 Axes>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| } | |
| ], | |
| "source": [ | |
| "m1 = np.eye(3)\n", | |
| "m2 = m1.copy()\n", | |
| "m3 = m2.copy()\n", | |
| "m2[:,0:2] = m2[:,[1, 0]]\n", | |
| "m3[:,1:] = m3[:,[2, 1]]\n", | |
| "m1, m2, m3\n", | |
| "fig, ax = plt.subplots(nrows=1, ncols=3)\n", | |
| "for a, m in zip(ax, [m1, m2, m3]):\n", | |
| " a.imshow(m)\n", | |
| " a.axis('off')" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 72, | |
| "id": "68f464cb", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 129 | |
| }, | |
| "id": "68f464cb", | |
| "outputId": "aaefd620-e80c-4b20-cf69-e94711862337" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAgMAAAClCAYAAADBAf6NAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjYuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8o6BhiAAAACXBIWXMAAA9hAAAPYQGoP6dpAAADWElEQVR4nO3Y0WkCQRRA0YlYRLAKmwhWkCpTgdiE//m3DDclZInosLnnfD/YBzMLl3lblmUZAEDWbvYCAMBcYgAA4sQAAMSJAQCIEwMAECcGACBODABAnBgAgLj92sGP3ecz92CF8+06e4WH7d6/X/5Nd3c+d/dv/sPd3frZnw7H2Ss87HL/+nXGywAAxIkBAIgTAwAQJwYAIE4MAECcGACAODEAAHFiAADixAAAxIkBAIgTAwAQJwYAIE4MAECcGACAODEAAHFiAADixAAAxIkBAIgTAwAQJwYAIE4MAECcGACAODEAAHFiAADixAAAxIkBAIgTAwAQJwYAIE4MAECcGACAODEAAHFiAADixAAAxIkBAIgTAwAQJwYAIE4MAECcGACAODEAAHFiAADixAAAxIkBAIgTAwAQJwYAIE4MAECcGACAODEAAHFiAADi9msHz7frE9d4jdPhOHuFh2x9/zHGuNxnb7BNW///3N2urZ/91v+9tbwMAECcGACAODEAAHFiAADixAAAxIkBAIgTAwAQJwYAIE4MAECcGACAODEAAHFiAADixAAAxIkBAIgTAwAQJwYAIE4MAECcGACAODEAAHFiAADixAAAxIkBAIgTAwAQJwYAIE4MAECcGACAODEAAHFiAADixAAAxIkBAIgTAwAQJwYAIE4MAECcGACAODEAAHFiAADixAAAxIkBAIgTAwAQJwYAIE4MAECcGACAODEAAHFiAADixAAAxIkBAIgTAwAQt187eDocn7jGa5xv19krPOQ/nMEMWz/3MZx9lbs739b3H2OMy/33GS8DABAnBgAgTgwAQJwYAIA4MQAAcWIAAOLEAADEiQEAiBMDABAnBgAgTgwAQJwYAIA4MQAAcWIAAOLEAADEiQEAiBMDABAnBgAgTgwAQJwYAIA4MQAAcWIAAOLEAADEiQEAiBMDABAnBgAgTgwAQJwYAIA4MQAAcWIAAOLEAADEiQEAiBMDABAnBgAgTgwAQJwYAIA4MQAAcWIAAOLEAADEiQEAiBMDABAnBgAgTgwAQJwYAIA4MQAAcWIAAOLEAADEiQEAiHtblmWZvQQAMI+XAQCIEwMAECcGACBODABAnBgAgDgxAABxYgAA4sQAAMSJAQCI+wErnjAlcICLNQAAAABJRU5ErkJggg==", | |
| "text/plain": [ | |
| "<Figure size 640x480 with 3 Axes>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| } | |
| ], | |
| "source": [ | |
| "new_matrices = np.concatenate(list(generate_new_elements(np.stack([m1, m2, m3], axis=0))), axis=0)\n", | |
| "n, _, _ = new_matrices.shape\n", | |
| "fig, ax = plt.subplots(nrows=1, ncols=3)\n", | |
| "for a, m in zip(ax, new_matrices):\n", | |
| " a.imshow(m)\n", | |
| " a.axis('off')" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 73, | |
| "id": "8jsJbzqFwb2t", | |
| "metadata": { | |
| "id": "8jsJbzqFwb2t" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "all_elements = np.concatenate([np.stack([m1, m2, m3], axis=0), new_matrices], axis=0)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 74, | |
| "id": "03f20e6e", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "03f20e6e", | |
| "outputId": "cc47d04c-b0c9-4f73-94f9-fb8fb2b83dc1" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "array([0, 1, 2, 5, 4, 3])" | |
| ] | |
| }, | |
| "execution_count": 74, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "test_inverses(all_elements)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 75, | |
| "id": "7d47c17d", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "7d47c17d", | |
| "outputId": "7068061c-fde9-4b13-a7ed-ea915e92a8b8" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "True" | |
| ] | |
| }, | |
| "execution_count": 75, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "test_closed(all_elements)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 76, | |
| "id": "a7fb4ac2", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 79 | |
| }, | |
| "id": "a7fb4ac2", | |
| "outputId": "3c9889d1-085c-470f-eabe-fabf08eeb98a" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAgQAAABaCAYAAADHGU44AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjYuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8o6BhiAAAACXBIWXMAAA9hAAAPYQGoP6dpAAACLUlEQVR4nO3YsY3bMBiA0e8MDxG4T+8lAk+QKTOB4SXcpzcyhZUqRYoDDkp+WMK9V0sESZPGB70ty7IEAHxqh1dPAAB4PUEAAAgCAEAQAAAJAgAgQQAAJAgAgAQBAFAdP/rg89fXyXl0OZ1Hx590e/5Y9d63w/f/PJO/XR/3sbGnf6+1e+qcvm+r53TS5B2oOnz5ueo9e/q+re7pZ/g/9YUAABAEAIAgAAASBABAggAASBAAAAkCACBBAAAkCACABAEAkCAAABIEAECCAABIEAAACQIAIEEAACQIAIAEAQCQIAAAEgQAQIIAAEgQAAAJAgCgOn70wcvpPDiNuj7uY2NPz32tyTXXdtc9ac9rnj4Pa+35nE6fh9tzdPjV9vx/utU9nVz3Vu6+LwQAgCAAAAQBAJAgAAASBABAggAASBAAAAkCACBBAAAkCACABAEAkCAAABIEAECCAABIEAAACQIAIEEAACQIAIAEAQCQIAAAEgQAQIIAAKiOr57AH5fTeWzs6+M+Nva/mFzztK3u6bTJdU+fh9tz3XvT89rznq41fX+2uu5Je97Trdx9XwgAAEEAAAgCACBBAAAkCACABAEAkCAAABIEAECCAABIEAAACQIAIEEAACQIAIAEAQCQIAAAEgQAQIIAAEgQAAAJAgAgQQAAJAgAgAQBAJAgAACqt2VZlldPAgB4LV8IAABBAAAIAgAgQQAAJAgAgAQBAJAgAAASBABAggAAqH4DHlZT2RCtrLgAAAAASUVORK5CYII=", | |
| "text/plain": [ | |
| "<Figure size 640x480 with 6 Axes>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| } | |
| ], | |
| "source": [ | |
| "fig, ax = plt.subplots(nrows=1, ncols=all_elements.shape[0])\n", | |
| "for (i, element) in enumerate(all_elements):\n", | |
| " ax[i].imshow(element)\n", | |
| " ax[i].axis('off')" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 77, | |
| "id": "f23c65d6", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 283 | |
| }, | |
| "id": "f23c65d6", | |
| "outputId": "b06dee8e-d0ed-4b25-a625-0eccc029a296" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "<matplotlib.image.AxesImage at 0x10ec9b040>" | |
| ] | |
| }, | |
| "execution_count": 77, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| }, | |
| { | |
| "data": { | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZgAAAGdCAYAAAAv9mXmAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjYuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8o6BhiAAAACXBIWXMAAA9hAAAPYQGoP6dpAAAUcklEQVR4nO3df2zVhb3/8Xdp14M/ShUFpKOgxglBVowohK9zOmESriG6myyGcDO+bHfJlrJIiMnSZHdocpfy176aSRjZ3PjjjgtuCZqYqWM4IIsysaQ3oJkRvy7Wi9C5ZC2t16O25/7xzbe7XMXLAd7n42kfj+STrCefw+d1FuTpOR9aGyqVSiUA4AKbVPQAAMYngQEghcAAkEJgAEghMACkEBgAUggMACkEBoAUTbW+4OjoaBw/fjxaWlqioaGh1pcH4DxUKpU4depUtLW1xaRJn/wepeaBOX78eLS3t9f6sgBcQH19fTFr1qxPPKfmgWlpaYmIiC/E30VTfKbWly/Uh7ffWPSEmuu/qVT0hEK8v+DdoicU4u/n9RY9oeb+adorRU+oqcGh0Zhz05/G/iz/JDUPzP//WKwpPhNNDRMrMNE0uegFNddYmpiBmXTxaNETClG6dIL9Mx0RU1om5q3ss7nFMTH/nwEgncAAkEJgAEghMACkEBgAUggMACkEBoAUAgNACoEBIIXAAJBCYABIITAApBAYAFIIDAApBAaAFAIDQAqBASCFwACQQmAASCEwAKQQGABSCAwAKQQGgBTnFJgtW7bE1VdfHZMnT44lS5bEiy++eKF3AVDnqg7Mrl27YuPGjbFp06Y4fPhwLFy4MFasWBH9/f0Z+wCoU1UH5oc//GF885vfjHXr1sX8+fPjxz/+cVx88cXxs5/9LGMfAHWqqsC8//770dPTE8uXL//bLzBpUixfvjxeeOGFj31OuVyOwcHB0w4Axr+qAvPOO+/EyMhIzJgx47THZ8yYESdOnPjY53R3d0dra+vY0d7efu5rAagb6X+LrKurKwYGBsaOvr6+7EsC8CnQVM3JV155ZTQ2NsbJkydPe/zkyZNx1VVXfexzSqVSlEqlc18IQF2q6h1Mc3NzLFq0KPbu3Tv22OjoaOzduzeWLl16wccBUL+qegcTEbFx48ZYu3Zt3HzzzbF48eJ4+OGHY3h4ONatW5exD4A6VXVg7rvvvvjzn/8c3//+9+PEiRNx4403xjPPPPORG/8ATGxVByYiYv369bF+/foLvQWAccTPIgMghcAAkEJgAEghMACkEBgAUggMACkEBoAUAgNACoEBIIXAAJBCYABIITAApBAYAFIIDAApBAaAFAIDQAqBASCFwACQQmAASCEwAKQQGABSCAwAKQQGgBQCA0CKpqIu/OHtN0Y0TS7q8oVoeq6n6Ak1V/7HG4ueUIjSv11c9IRC/PMdR4qeUHPf6/980RNqqjz0QUT837M61zsYAFIIDAApBAaAFAIDQAqBASCFwACQQmAASCEwAKQQGABSCAwAKQQGgBQCA0AKgQEghcAAkEJgAEghMACkEBgAUggMACkEBoAUAgNACoEBIIXAAJBCYABIITAApBAYAFIIDAApqg7MgQMHYtWqVdHW1hYNDQ3xxBNPJMwCoN5VHZjh4eFYuHBhbNmyJWMPAONEU7VPWLlyZaxcuTJjCwDjSNWBqVa5XI5yuTz29eDgYPYlAfgUSL/J393dHa2trWNHe3t79iUB+BRID0xXV1cMDAyMHX19fdmXBOBTIP0jslKpFKVSKfsyAHzK+D4YAFJU/Q5maGgojh07Nvb1G2+8Eb29vTF16tSYPXv2BR0HQP2qOjAvvfRSfOlLXxr7euPGjRERsXbt2ti+ffsFGwZAfas6MHfccUdUKpWMLQCMI+7BAJBCYABIITAApBAYAFIIDAApBAaAFAIDQAqBASCFwACQQmAASCEwAKQQGABSCAwAKQQGgBQCA0AKgQEghcAAkEJgAEghMACkEBgAUggMACkEBoAUAgNAiqaiLtx/UykaS6WiLl+Io//SW/SEmlvRVvSCYtzSO1L0hEJ8bt//LnpCzc3+aWPRE2rqww/fi4inzupc72AASCEwAKQQGABSCAwAKQQGgBQCA0AKgQEghcAAkEJgAEghMACkEBgAUggMACkEBoAUAgNACoEBIIXAAJBCYABIITAApBAYAFIIDAApBAaAFAIDQAqBASCFwACQQmAASCEwAKQQGABSVBWY7u7uuOWWW6KlpSWmT58e9957b7z66qtZ2wCoY1UFZv/+/dHZ2RkHDx6MPXv2xAcffBB33XVXDA8PZ+0DoE41VXPyM888c9rX27dvj+nTp0dPT0988YtfvKDDAKhvVQXmvxsYGIiIiKlTp57xnHK5HOVyeezrwcHB87kkAHXinG/yj46OxoYNG+LWW2+NBQsWnPG87u7uaG1tHTva29vP9ZIA1JFzDkxnZ2ccPXo0du7c+YnndXV1xcDAwNjR19d3rpcEoI6c00dk69evj6eeeioOHDgQs2bN+sRzS6VSlEqlcxoHQP2qKjCVSiW+853vxO7du2Pfvn1xzTXXZO0CoM5VFZjOzs7YsWNHPPnkk9HS0hInTpyIiIjW1ta46KKLUgYCUJ+qugezdevWGBgYiDvuuCNmzpw5duzatStrHwB1quqPyADgbPhZZACkEBgAUggMACkEBoAUAgNACoEBIIXAAJBCYABIITAApBAYAFIIDAApBAaAFAIDQAqBASCFwACQQmAASCEwAKQQGABSCAwAKQQGgBQCA0AKgQEghcAAkKKpqAu/v+DdmHTxaFGXL8T3+j9f9ISa+/DORUVPKMQ/T3+s6AmFeOJfbyt6Qs01Pfd80RNqq/LBWZ/qHQwAKQQGgBQCA0AKgQEghcAAkEJgAEghMACkEBgAUggMACkEBoAUAgNACoEBIIXAAJBCYABIITAApBAYAFIIDAApBAaAFAIDQAqBASCFwACQQmAASCEwAKQQGABSCAwAKQQGgBRVBWbr1q3R0dERU6ZMiSlTpsTSpUvj6aefztoGQB2rKjCzZs2KzZs3R09PT7z00ktx5513xj333BMvv/xy1j4A6lRTNSevWrXqtK9/8IMfxNatW+PgwYNxww03XNBhANS3qgLzX42MjMQvf/nLGB4ejqVLl57xvHK5HOVyeezrwcHBc70kAHWk6pv8R44ciUsvvTRKpVJ861vfit27d8f8+fPPeH53d3e0traOHe3t7ec1GID6UHVg5s6dG729vfGHP/whvv3tb8fatWvjlVdeOeP5XV1dMTAwMHb09fWd12AA6kPVH5E1NzfHddddFxERixYtikOHDsUjjzwS27Zt+9jzS6VSlEql81sJQN057++DGR0dPe0eCwBEVPkOpqurK1auXBmzZ8+OU6dOxY4dO2Lfvn3x7LPPZu0DoE5VFZj+/v742te+Fm+//Xa0trZGR0dHPPvss/HlL385ax8AdaqqwDz22GNZOwAYZ/wsMgBSCAwAKQQGgBQCA0AKgQEghcAAkEJgAEghMACkEBgAUggMACkEBoAUAgNACoEBIIXAAJBCYABIITAApBAYAFIIDAApBAaAFAIDQAqBASCFwACQQmAASCEwAKRoKurCfz+vN0qXfqaoyxdi1yuLip5Qc6/9y2NFTyjEsn/4RtETCvHZ554vekLN/ft3/1fRE2pqpPxexP958qzO9Q4GgBQCA0AKgQEghcAAkEJgAEghMACkEBgAUggMACkEBoAUAgNACoEBIIXAAJBCYABIITAApBAYAFIIDAApBAaAFAIDQAqBASCFwACQQmAASCEwAKQQGABSCAwAKQQGgBQCA0CK8wrM5s2bo6GhITZs2HCB5gAwXpxzYA4dOhTbtm2Ljo6OC7kHgHHinAIzNDQUa9asiZ/85Cdx+eWXX+hNAIwD5xSYzs7OuPvuu2P58uX/47nlcjkGBwdPOwAY/5qqfcLOnTvj8OHDcejQobM6v7u7Ox566KGqhwFQ36p6B9PX1xf3339//OIXv4jJkyef1XO6urpiYGBg7Ojr6zunoQDUl6rewfT09ER/f3/cdNNNY4+NjIzEgQMH4tFHH41yuRyNjY2nPadUKkWpVLowawGoG1UFZtmyZXHkyJHTHlu3bl3Mmzcvvvvd734kLgBMXFUFpqWlJRYsWHDaY5dccklcccUVH3kcgInNd/IDkKLqv0X23+3bt+8CzABgvPEOBoAUAgNACoEBIIXAAJBCYABIITAApBAYAFIIDAApBAaAFAIDQAqBASCFwACQQmAASCEwAKQQGABSCAwAKQQGgBQCA0AKgQEghcAAkEJgAEghMACkEBgAUjQVdeF/mvZKTGmZWH174l9vK3pCzX1v/ueLnlCIpud6ip5QiA/vXFT0hJorL3y36Ak1Nfrue2d97sT6Ex6AmhEYAFIIDAApBAaAFAIDQAqBASCFwACQQmAASCEwAKQQGABSCAwAKQQGgBQCA0AKgQEghcAAkEJgAEghMACkEBgAUggMACkEBoAUAgNACoEBIIXAAJBCYABIITAApBAYAFJUFZgHH3wwGhoaTjvmzZuXtQ2AOtZU7RNuuOGG+O1vf/u3X6Cp6l8CgAmg6jo0NTXFVVddlbEFgHGk6nswr732WrS1tcW1114ba9asiTfffPMTzy+XyzE4OHjaAcD4V1VglixZEtu3b49nnnkmtm7dGm+88UbcdtttcerUqTM+p7u7O1pbW8eO9vb28x4NwKdfVYFZuXJlfPWrX42Ojo5YsWJF/PrXv46//vWv8fjjj5/xOV1dXTEwMDB29PX1nfdoAD79zusO/WWXXRbXX399HDt27IznlEqlKJVK53MZAOrQeX0fzNDQULz++usxc+bMC7UHgHGiqsA88MADsX///vjTn/4Uzz//fHzlK1+JxsbGWL16ddY+AOpUVR+RvfXWW7F69er4y1/+EtOmTYsvfOELcfDgwZg2bVrWPgDqVFWB2blzZ9YOAMYZP4sMgBQCA0AKgQEghcAAkEJgAEghMACkEBgAUggMACkEBoAUAgNACoEBIIXAAJBCYABIITAApBAYAFIIDAApBAaAFAIDQAqBASCFwACQQmAASCEwAKQQGABSNNX6gpVKJSIiBodGa33pwo2U3yt6Qs2Vhz4oekIhPqxMvN/fEREffjjxfo+PvjtS9ISaGv2PckT87c/yT9JQOZuzLqC33nor2tvba3lJAC6wvr6+mDVr1ieeU/PAjI6OxvHjx6OlpSUaGhpqdt3BwcFob2+Pvr6+mDJlSs2uWzSve+K87on4miMm5usu8jVXKpU4depUtLW1xaRJn3yXpeYfkU2aNOl/rF6mKVOmTJjfhP+V1z1xTMTXHDExX3dRr7m1tfWsznOTH4AUAgNAigkTmFKpFJs2bYpSqVT0lJryuifO656IrzliYr7uennNNb/JD8DEMGHewQBQWwIDQAqBASCFwACQYsIEZsuWLXH11VfH5MmTY8mSJfHiiy8WPSnVgQMHYtWqVdHW1hYNDQ3xxBNPFD0pXXd3d9xyyy3R0tIS06dPj3vvvTdeffXVomel27p1a3R0dIx9093SpUvj6aefLnpWTW3evDkaGhpiw4YNRU9J9eCDD0ZDQ8Npx7x584qedUYTIjC7du2KjRs3xqZNm+Lw4cOxcOHCWLFiRfT39xc9Lc3w8HAsXLgwtmzZUvSUmtm/f390dnbGwYMHY8+ePfHBBx/EXXfdFcPDw0VPSzVr1qzYvHlz9PT0xEsvvRR33nln3HPPPfHyyy8XPa0mDh06FNu2bYuOjo6ip9TEDTfcEG+//fbY8fvf/77oSWdWmQAWL15c6ezsHPt6ZGSk0tbWVunu7i5wVe1ERGX37t1Fz6i5/v7+SkRU9u/fX/SUmrv88ssrP/3pT4ueke7UqVOVz33uc5U9e/ZUbr/99sr9999f9KRUmzZtqixcuLDoGWdt3L+Def/996OnpyeWL18+9tikSZNi+fLl8cILLxS4jGwDAwMRETF16tSCl9TOyMhI7Ny5M4aHh2Pp0qVFz0nX2dkZd99992n/fI93r732WrS1tcW1114ba9asiTfffLPoSWdU8x92WWvvvPNOjIyMxIwZM057fMaMGfHHP/6xoFVkGx0djQ0bNsStt94aCxYsKHpOuiNHjsTSpUvjvffei0svvTR2794d8+fPL3pWqp07d8bhw4fj0KFDRU+pmSVLlsT27dtj7ty58fbbb8dDDz0Ut912Wxw9ejRaWlqKnvcR4z4wTEydnZ1x9OjRT/fn0xfQ3Llzo7e3NwYGBuJXv/pVrF27Nvbv3z9uI9PX1xf3339/7NmzJyZPnlz0nJpZuXLl2P/u6OiIJUuWxJw5c+Lxxx+Pb3zjGwUu+3jjPjBXXnllNDY2xsmTJ097/OTJk3HVVVcVtIpM69evj6eeeioOHDhQ6H8aopaam5vjuuuui4iIRYsWxaFDh+KRRx6Jbdu2FbwsR09PT/T398dNN9009tjIyEgcOHAgHn300SiXy9HY2Fjgwtq47LLL4vrrr49jx44VPeVjjft7MM3NzbFo0aLYu3fv2GOjo6Oxd+/eCfEZ9URSqVRi/fr1sXv37njuuefimmuuKXpSYUZHR6NcLhc9I82yZcviyJEj0dvbO3bcfPPNsWbNmujt7Z0QcYmIGBoaitdffz1mzpxZ9JSPNe7fwUREbNy4MdauXRs333xzLF68OB5++OEYHh6OdevWFT0tzdDQ0Gn/VvPGG29Eb29vTJ06NWbPnl3gsjydnZ2xY8eOePLJJ6OlpSVOnDgREf/vP4500UUXFbwuT1dXV6xcuTJmz54dp06dih07dsS+ffvi2WefLXpampaWlo/cW7vkkkviiiuuGNf33B544IFYtWpVzJkzJ44fPx6bNm2KxsbGWL16ddHTPl7Rf42tVn70ox9VZs+eXWlubq4sXry4cvDgwaInpfrd735XiYiPHGvXri16WpqPe70RUfn5z39e9LRUX//61ytz5sypNDc3V6ZNm1ZZtmxZ5Te/+U3Rs2puIvw15fvuu68yc+bMSnNzc+Wzn/1s5b777qscO3as6Fln5Mf1A5Bi3N+DAaAYAgNACoEBIIXAAJBCYABIITAApBAYAFIIDAApBAaAFAIDQAqBASCFwACQ4j8BFyeHn5qGy2cAAAAASUVORK5CYII=", | |
| "text/plain": [ | |
| "<Figure size 640x480 with 1 Axes>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| } | |
| ], | |
| "source": [ | |
| "# Note that multiplication table demonstrates the rearrangement theorem\n", | |
| "# Multiplication by a group element to all elements, contains each element only once\n", | |
| "table = make_multiplication_table(all_elements)\n", | |
| "plt.imshow(table)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 78, | |
| "id": "9de71269", | |
| "metadata": { | |
| "id": "9de71269" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "import itertools\n", | |
| "from itertools import combinations" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 79, | |
| "id": "e3594355", | |
| "metadata": { | |
| "id": "e3594355" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "from functools import reduce\n", | |
| "\n", | |
| "def factors(n): \n", | |
| " return set(reduce(list.__add__,\n", | |
| " ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 80, | |
| "id": "742066ea", | |
| "metadata": { | |
| "id": "742066ea" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def find_subgroups(group):\n", | |
| " \"\"\"Find all subgroups of group.\n", | |
| " Input:\n", | |
| " group: np.array of shape [n, d, d]\n", | |
| " Output:\n", | |
| " Yields tuples of elements that form subgroup.\n", | |
| " \"\"\"\n", | |
| " n, d, d2 = group.shape\n", | |
| " table = make_multiplication_table(group)\n", | |
| " assert d == d2\n", | |
| " for f in factors(n):\n", | |
| " for c in combinations(range(n), f):\n", | |
| " subtable = table[np.array(list(c))][:, np.array(list(c))] \n", | |
| " if set(c) == set(subtable.reshape(-1)):\n", | |
| " yield c" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 81, | |
| "id": "df2bda0d", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "df2bda0d", | |
| "outputId": "b754832a-7c12-449d-ca6a-232ef436ef12" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "{(0,), (0, 1), (0, 1, 2, 3, 4, 5), (0, 2), (0, 3, 5), (0, 4)}" | |
| ] | |
| }, | |
| "execution_count": 81, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "set(list(find_subgroups(all_elements)))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 82, | |
| "id": "f77de2cb", | |
| "metadata": { | |
| "id": "f77de2cb", | |
| "outputId": "d319fa5f-fca5-41e0-f042-bbe8849ad828" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "{(0,), (0, 1, 2)}" | |
| ] | |
| }, | |
| "execution_count": 82, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "set(list(find_subgroups(p3[[0, 3, 4]])))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 83, | |
| "id": "7d8859e3", | |
| "metadata": { | |
| "id": "7d8859e3" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def right_coset(subgroup, group, tol=1e-6):\n", | |
| " table = make_multiplication_table(group)\n", | |
| " subgroup_indices = test_membership_index(subgroup, group, tol=1e-6)[0]\n", | |
| " sets = set()\n", | |
| " for i in table[subgroup_indices].T:\n", | |
| " sets.add(frozenset(i))\n", | |
| " return set(sets)\n", | |
| "\n", | |
| "def left_coset(subgroup, group, tol=1e-6):\n", | |
| " table = make_multiplication_table(group)\n", | |
| " subgroup_indices = test_membership_index(subgroup, group, tol=1e-6)[0]\n", | |
| " sets = set()\n", | |
| " for i in table[:, subgroup_indices]:\n", | |
| " sets.add(frozenset(i))\n", | |
| " return set(sets)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 84, | |
| "id": "277e5e28", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "277e5e28", | |
| "outputId": "a3eb586b-f1b8-4ade-dfbe-5d0d4980ce5b" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "{frozenset({4, 5}), frozenset({0, 1}), frozenset({2, 3})}" | |
| ] | |
| }, | |
| "execution_count": 84, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "right_coset(all_elements[[0,1]], all_elements)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 85, | |
| "id": "db97c8bb", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "db97c8bb", | |
| "outputId": "e8600a6e-aea5-4ded-92a2-0171f2a31d92" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "{frozenset({2, 4}),\n", | |
| " frozenset({1, 4}),\n", | |
| " frozenset({3, 5}),\n", | |
| " frozenset({1, 2}),\n", | |
| " frozenset({0, 3}),\n", | |
| " frozenset({0, 5})}" | |
| ] | |
| }, | |
| "execution_count": 85, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "right_coset(all_elements[[0,3]], all_elements)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 86, | |
| "id": "1f0a5f13", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "1f0a5f13", | |
| "outputId": "983d9fc2-7a75-4657-9ed5-c02da85a7a26" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "{frozenset({2, 4}),\n", | |
| " frozenset({1, 4}),\n", | |
| " frozenset({3, 5}),\n", | |
| " frozenset({1, 2}),\n", | |
| " frozenset({0, 3}),\n", | |
| " frozenset({0, 5})}" | |
| ] | |
| }, | |
| "execution_count": 86, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "left_coset(all_elements[[0,3]], all_elements)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "id": "IXjZqPnuxMev", | |
| "metadata": { | |
| "id": "IXjZqPnuxMev" | |
| }, | |
| "source": [ | |
| "## Conjugation and Class" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 87, | |
| "id": "8824e436", | |
| "metadata": { | |
| "id": "8824e436" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def conjugacy(group):\n", | |
| " n, d, d2 = group.shape\n", | |
| " assert d == d2\n", | |
| " sets = set()\n", | |
| " inverses = test_inverses(group)\n", | |
| " table = make_multiplication_table(group)\n", | |
| " for i in range(n):\n", | |
| " sets.add(frozenset(table[inverses, table[i]]))\n", | |
| " return sets" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 88, | |
| "id": "S-CvQYmFw7Wv", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "S-CvQYmFw7Wv", | |
| "outputId": "4a19f6af-b145-4f43-be61-d005e864b4a7" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "[(0,), (0, 1), (0, 2), (0, 4), (0, 3, 5), (0, 1, 2, 3, 4, 5)]" | |
| ] | |
| }, | |
| "execution_count": 88, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "list(find_subgroups(all_elements))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 89, | |
| "id": "0f7f7199", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "0f7f7199", | |
| "outputId": "2c2caf94-cd26-4cd4-fce8-ecd683f995eb" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "{frozenset({1, 2, 4}), frozenset({0}), frozenset({3, 5})}" | |
| ] | |
| }, | |
| "execution_count": 89, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "conjugacy(all_elements)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 90, | |
| "id": "jxy8uHqsy0pP", | |
| "metadata": { | |
| "id": "jxy8uHqsy0pP" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def selfconjugate_subgroups(group):\n", | |
| " id = test_identity(group)\n", | |
| " inv = test_inverses(group)\n", | |
| " subgroups = list(find_subgroups(group))\n", | |
| " conj = list(conjugacy(all_elements))\n", | |
| " for s in subgroups:\n", | |
| " conj_set = set()\n", | |
| " for e in s:\n", | |
| " for c in conj:\n", | |
| " if e in c:\n", | |
| " conj_set.update(set(c))\n", | |
| " if conj_set == set(s):\n", | |
| " yield s" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 91, | |
| "id": "g6nfLGULz49e", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "g6nfLGULz49e", | |
| "outputId": "c7ba6f93-a242-42de-c050-79a6b3246352" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "[(0,), (0, 3, 5), (0, 1, 2, 3, 4, 5)]" | |
| ] | |
| }, | |
| "execution_count": 91, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "list(selfconjugate_subgroups(all_elements))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "id": "SShl8C49vT88", | |
| "metadata": { | |
| "id": "SShl8C49vT88" | |
| }, | |
| "source": [ | |
| "## Factor Group" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 92, | |
| "id": "35f5c8fd", | |
| "metadata": { | |
| "id": "35f5c8fd", | |
| "outputId": "3ba95fb5-fb00-480c-8465-c3148595949f" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "{frozenset({1, 2, 4}), frozenset({0, 3, 5})}" | |
| ] | |
| }, | |
| "execution_count": 92, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "right_coset(all_elements[[0,3,5]], all_elements)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 93, | |
| "id": "i0bXVJ5K3ApC", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "i0bXVJ5K3ApC", | |
| "outputId": "b6bd099f-82db-42a8-a768-a0c2fae0f5ef" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "array([{1, 2}, {3, 4}], dtype=object)" | |
| ] | |
| }, | |
| "execution_count": 93, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "np.array([set([1, 2]), set([3, 4])])" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 94, | |
| "id": "wvmGmHb22nOl", | |
| "metadata": { | |
| "id": "wvmGmHb22nOl" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def factor_group(selfconj_sub, group):\n", | |
| " rc = right_coset(all_elements[[0,3,5]], all_elements)\n", | |
| " table = make_multiplication_table(group)\n", | |
| " new_table = np.empty([len(rc), len(rc)], dtype=set)\n", | |
| " int_table = np.empty([len(rc), len(rc)], dtype=np.int32)\n", | |
| " for i,r in enumerate(list(rc)):\n", | |
| " for j,q in enumerate(list(rc)):\n", | |
| " # print(i, r, j, q)\n", | |
| " # print(table[list(r), list(q)])\n", | |
| " sub_table = set(\n", | |
| " table[list(r), list(q)].reshape(-1).tolist()\n", | |
| " )\n", | |
| " new_table[i, j] = sub_table\n", | |
| " which_coset = np.nonzero([sub_table.issubset(s) for s in rc])[0]\n", | |
| " int_table[i, j] = which_coset\n", | |
| "\n", | |
| " return rc, new_table, int_table" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 95, | |
| "id": "Bd2po1vM3iJq", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "Bd2po1vM3iJq", | |
| "outputId": "c819c0ec-668d-4d48-9027-eefe953b2a3e" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "({frozenset({1, 2, 4}), frozenset({0, 3, 5})},\n", | |
| " array([[{0}, {1, 2, 4}],\n", | |
| " [{1}, {0, 3, 5}]], dtype=object),\n", | |
| " array([[1, 0],\n", | |
| " [0, 1]], dtype=int32))" | |
| ] | |
| }, | |
| "execution_count": 95, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "factor_group(all_elements[[0,3,5]], all_elements)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "id": "718e45d8", | |
| "metadata": { | |
| "id": "718e45d8" | |
| }, | |
| "source": [ | |
| "## Chocolates and Generators\n", | |
| "This is based on a puzzle Mario and I were told once, I don't think this is an exact reproduction of the puzzle but it goes something like this.\n", | |
| "A demon challenges you to a game. There are n coins that are in a random configuration of heads up and down. You win the game if all the coins are heads up. You are allowed to take the following actions: 1) Flip all the coins at once and 2) The demon flips a single coin at random (this is the part that I think departs from the game -- I think the demon is suppose to actively try to make you not win -- but i think in that case then you can't win for n > 2). Describe an deterministic algorithm that is guaranteed to result in winning." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 96, | |
| "id": "1a8a1f78", | |
| "metadata": { | |
| "id": "1a8a1f78" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "n = 4\n", | |
| "flip_all = -np.eye(n)\n", | |
| "flip_one = np.repeat(np.eye(n)[np.newaxis,], n, axis=0)\n", | |
| "for i in range(n):\n", | |
| " flip_one[i, i, i] = -1" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 97, | |
| "id": "2e103f78", | |
| "metadata": { | |
| "id": "2e103f78" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "new = np.concatenate(list(generate_new_elements(flip_one, max_recurse=1000)), axis=0)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 98, | |
| "id": "630705e5", | |
| "metadata": { | |
| "id": "630705e5" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "all_elements = np.concatenate([flip_one, new])" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 99, | |
| "id": "b058c0f4", | |
| "metadata": { | |
| "id": "b058c0f4", | |
| "outputId": "ae187a8b-efa7-48a9-9a68-e112e9daacca" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "(16, 4, 4)" | |
| ] | |
| }, | |
| "execution_count": 99, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "all_elements.shape" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 100, | |
| "id": "d5e9409b", | |
| "metadata": { | |
| "id": "d5e9409b" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def rand_state(n, seed=42):\n", | |
| "# np.random.seed(seed)\n", | |
| " return np.random.randint(0, 2, size=n)*2 - 1" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 101, | |
| "id": "4670a242", | |
| "metadata": { | |
| "id": "4670a242" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def test_win(x):\n", | |
| " return np.allclose(x, np.ones_like(x))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 102, | |
| "id": "a984279d", | |
| "metadata": { | |
| "id": "a984279d" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def flipall(x):\n", | |
| " return -1 * x\n", | |
| "\n", | |
| "def flipone(x):\n", | |
| " n = len(x)\n", | |
| " i = np.random.randint(0, n)\n", | |
| " y = x.copy()\n", | |
| " y[i] = -1 * x[i]\n", | |
| " return y" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 103, | |
| "id": "17ea81ca", | |
| "metadata": { | |
| "id": "17ea81ca" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def play(x, i=0, max_recurse=1000):\n", | |
| " if i > max_recurse:\n", | |
| " return False\n", | |
| " x = flipone(x)\n", | |
| "# print(x)\n", | |
| " i += 1\n", | |
| " if test_win(x):\n", | |
| " return i\n", | |
| " x = flipall(x)\n", | |
| "# print(x)\n", | |
| " i += 1\n", | |
| " if test_win(x):\n", | |
| " return i\n", | |
| " return play(x, i=i, max_recurse=max_recurse)\n", | |
| " " | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 104, | |
| "id": "d487f637", | |
| "metadata": { | |
| "id": "d487f637", | |
| "outputId": "f9c0b831-eb72-42d2-8c20-e9ba8622269b" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "23" | |
| ] | |
| }, | |
| "execution_count": 104, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "play(rand_state(6))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 105, | |
| "id": "4ddf4210", | |
| "metadata": { | |
| "id": "4ddf4210", | |
| "outputId": "48a61a60-bf13-4655-ae2c-d114fbba7559" | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "array([-1, 1, -1, 1])" | |
| ] | |
| }, | |
| "execution_count": 105, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "flipone(np.array([1, 1, -1, 1]))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "e0f9ffc2", | |
| "metadata": { | |
| "id": "e0f9ffc2" | |
| }, | |
| "outputs": [], | |
| "source": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "264c53a0", | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [] | |
| } | |
| ], | |
| "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 | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment