{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"[Oregon Curriculum Network](http://4dsolutions.net/ocn/)\n",
"\n",
"# The School of Tomorrow\n",
"\n",
"[Home Page](School_of_Tomorrow.ipynb)\n",
"\n",
"\n",
"\n",
"\n",
"# Group Theory\n",
"\n",
"Group Theory is usually presented as a branch of exploration that started with Galois Theory, which in turn traces to searching for [all roots of a polynomial](https://youtu.be/cxNq-hQwvn0), or at least knowing in principle how many one has.\n",
"\n",
"The concept of a Group only makes sense in connection with other concepts: Ring and Field.\n",
"\n",
"The School of Tomorrow does not aim to provide exhaustive treatment of topics touched on. You're in a web of windows, frames of reference. The School of Tomorrow is a hub of hyperlinks, floating in cyberspace (Cyberia)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Permutations\n",
"\n",
"One of the most abstract ways to understand Finite Groups, in a way that exercises coding skills, is to use permutations. A permutation is a reordering of elements. Think of pairing every lowercase letter with every other lowercase letter, throwing in a space."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'a': 's',\n",
" 'b': 'f',\n",
" 'c': 'l',\n",
" 'd': 'n',\n",
" 'e': 'x',\n",
" 'f': 'a',\n",
" 'g': 'b',\n",
" 'h': 'i',\n",
" 'i': 't',\n",
" 'j': 'j',\n",
" 'k': ' ',\n",
" 'l': 'r',\n",
" 'm': 'y',\n",
" 'n': 'z',\n",
" 'o': 'w',\n",
" 'p': 'k',\n",
" 'q': 'u',\n",
" 'r': 'g',\n",
" 's': 'c',\n",
" 't': 'p',\n",
" 'u': 'd',\n",
" 'v': 'm',\n",
" 'w': 'e',\n",
" 'x': 'q',\n",
" 'y': 'o',\n",
" 'z': 'v',\n",
" ' ': 'h'}"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from string import ascii_lowercase as letters\n",
"from random import shuffle\n",
"members = list(letters + \" \")\n",
"mem_copy = members[:]\n",
"shuffle(mem_copy)\n",
"p = {key:value for key, value in zip(members, mem_copy)}\n",
"p"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For a more complete implementation of a Permutation type, you might want to check these other resources:\n",
"\n",
"* [Permutations in 4Dsolutions Repo](https://github.com/4dsolutions/Python5/blob/master/Permutations.ipynb)\n",
"* [Permutation on repl.it](https://repl.it/@kurner/Permutations#main.py)\n",
"* [Socratica Channel, Definition of a Group](https://youtu.be/QudbrUcVPxk)\n",
"* [use the source luke](https://vlorblog.wordpress.com/2009/11/15/use-the-source-luke/) at [Vlorbik's Diner](https://vlorblog.wordpress.com/)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Links to Number Theory\n",
"\n",
"In Group Theory, we'll visit the idea of totatives, as we do in Number Theory as well. The totatives of N, multiplied modulo N, form a group. The totatives of N modulo N, when N is prime, form a field.\n",
"\n",
"The properties of a Group are often summarized with the acronym CAIN, which is somewhat a worplay on Abel, one of the founders of Group Theory.\n",
"\n",
"CAIN:\n",
"* Closure: given an operation $\\circ$, every $a \\circ b$ is in the group\n",
"* Associativity: $(a \\circ b) \\circ c \\equiv a \\circ (b \\circ c)$; Abelian groups commutative: $a \\circ b \\equiv b \\circ a$\n",
"* Inverse: every element has an inverse such that $a \\circ \\neg a \\equiv \\varepsilon \\equiv \\neg a \\circ a$\n",
"* Neutral element: one element $\\varepsilon$ serves as an identity such that $\\varepsilon \\circ a \\equiv a \\equiv a \\circ \\varepsilon$ "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here's a simple integer-like class that builds in the modulus, so we can use the standard operators yet have the operation carried out modulo N.\n",
"\n",
"We could flesh this out more. Subtracting is adding the additive inverse. Division is multiplying by the multiplicative inverse. That's why these two operations are, in a sense, \"syntactic sugar\" once we've defined an inverse vis-a-vis each of these operations."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"class Mod:\n",
" \n",
" _modulus = 12\n",
" \n",
" def __init__(self, n):\n",
" self.value = n % self._modulus\n",
" \n",
" def __eq__(self, other):\n",
" return self.value == other.value % self._modulus\n",
" \n",
" def __repr__(self):\n",
" return \"({} mod {})\".format(self.value, self._modulus)\n",
" \n",
" def __add__(self, other):\n",
" return type(self)(self.value + other.value)\n",
" \n",
" def __mul__(self, other):\n",
" return type(self)(self.value * other.value)\n",
" \n",
" def __pow__(self, n):\n",
" return type(self)(pow(self.value, n, self._modulus))\n",
" \n",
" def __hash__(self):\n",
" return self.value "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You'll find more details on the code below in [Number Theory](NumberTheory.ipynb)."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"def gcd(a, b):\n",
" while b:\n",
" b, a = a % b, b\n",
" return a\n",
"\n",
"def totatives(n):\n",
" return [totative for totative in range(1, n) \n",
" if gcd(totative, n) == 1]"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1, 5, 7, 11]"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"totatives(12)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"group_12 = map(Mod, totatives(12))"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(1 mod 12), (5 mod 12), (7 mod 12), (11 mod 12)]"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"list(group_12)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The ```itertools``` module (Standard Library) gives us a Cartesian Product, meaning we may quickly construct a Cayley Table for our group."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"from itertools import product"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [],
"source": [
"group_12 = map(Mod, totatives(12))\n",
"n = list(group_12)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(1 mod 12), (5 mod 12), (7 mod 12), (11 mod 12)]"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Iterators get \"used up\" in Python, meaning once you've traversed an iterator, you need to recreate it from scratch. The name ```table``` points to a listing of every member paired both with itself, and every other member of the group. \n",
"\n",
"The list comprehension makes multiplication the operator for this Cayley Table, and shows Closure, meaning every outcome, every product, is a member of the Group."
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [],
"source": [
"table = product(n, n)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(1 mod 12),\n",
" (5 mod 12),\n",
" (7 mod 12),\n",
" (11 mod 12),\n",
" (5 mod 12),\n",
" (1 mod 12),\n",
" (11 mod 12),\n",
" (7 mod 12),\n",
" (7 mod 12),\n",
" (11 mod 12),\n",
" (1 mod 12),\n",
" (5 mod 12),\n",
" (11 mod 12),\n",
" (7 mod 12),\n",
" (5 mod 12),\n",
" (1 mod 12)]"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"[a * b for a, b in table] # closure"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"table"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[]"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"list(table)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"What happens if the modulus N is prime? Then by definition, every number from 1 up to N-1 is a totative of N. The totient of N, where N is prime, is N-1.\n",
"\n",
"In this case, addition joins multiplication as an operator with group properties, while the distributive property connects the two operations thusly:\n",
"\n",
"$$\n",
"A * (B + C) = (A * B) + (A * C)\n",
"$$\n",
"\n",
"That means we have a Field.\n",
"\n",
"A Ring is between a Group and a Field in that it features two operations, but without inverses and/or closure for one of them."
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [],
"source": [
"Mod._modulus = 13"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [],
"source": [
"group_13 = map(Mod, totatives(13))\n",
"n = list(group_13) + [Mod(0)] # 0 is added yet has no multiplicative inverse"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"table = product(n, n) # Cayley Table\n",
"sums = [a + b for a, b in table] # check addition this time\n",
"all([the_sum in n for the_sum in sums]) # closure"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# What's an Algebra?\n",
"\n",
"Before being too quick to dive into some definition, lets start with etymology and talk about Al Jabr (الجبر) or bone-setting (metaphorically). Al Jabr is perhaps a root for both jabber and gibberish, which is what an algebra looks like to many, especially with algorithms added, from al-Khwarizmi (محمد بن موسی خوارزمی).\n",
"\n",
"An algebra provides a way of operating with elements according to familiar rules of addition, multiplication and so on. If group, ring and field properties emerge, and/or some kind of \"vector space\", then you have an algebra on your hands."
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Lets jump right in to the complex numbers and write a generator for matrices of this form, where a, b are any complex numbers:\n",
"\n",
"\\begin{bmatrix}\n",
"a & -b \\\\\n",
"b^{*} & a^{*}\n",
"\\end{bmatrix}\n",
"\n",
"The cryptic little asterisk superscript means \"conjugate of\". Matrices of this form will be closed under matrix multiplication, giving us [the germ of an algebra](http://www.zipcon.net/~swhite/docs/math/quaternions/matrices.html).\n",
"\n",
"Lets do some Python:"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [],
"source": [
"a = complex(1, 2)\n",
"a_star = a.conjugate()"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[ 150.+241.j, -195.-239.j],\n",
" [ 195.-239.j, 150.-241.j]])"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from numpy.random import randint\n",
"\n",
"def M():\n",
" \"\"\"Generates complex number matrices of a specific form.\n",
" Note Quaternions at this web page:\n",
" http://www.zipcon.net/~swhite/docs/math/quaternions/matrices.html\n",
" Expects numpy imported as np\n",
" \"\"\"\n",
" while True:\n",
" # using arbitrary ranges, these could be argument-driven\n",
" a = complex(randint(100, 199), randint(200, 299))\n",
" b = complex(randint(100, 199), randint(200, 299))\n",
" a_star = a.conjugate()\n",
" b_star = b.conjugate()\n",
" \n",
" M = np.zeros((2,2), dtype=complex) # initialize to all complex zeros\n",
" # being explicit about what's going in each cell of a 2x2 matrix\n",
" M[0,0] = a\n",
" M[0,1] = -b\n",
" M[1,0] = b_star\n",
" M[1,1] = a_star\n",
" yield M\n",
" \n",
"ms = M()\n",
"next(ms)"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [],
"source": [
"Matrix_A = next(ms)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we can start testing the claim of Closure (see above). Any random matrix of this form, times another of the same form, including itself, should give another matrix in that same form. That's what Closure means (you don't escape the group by means of its internally defined operation -- matrix multiplication in this case)."
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[-117104.+105840.j, -46872. -91854.j],\n",
" [ 46872. -91854.j, -117104.-105840.j]])"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Matrix_A @ Matrix_A"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So far so good. One may prove closure in this case, by means of Algebra.\n",
"\n",
"[Answering a Matrix-related question on Quora, with this code](https://qr.ae/pNeEz3)"
]
}
],
"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.7.9"
}
},
"nbformat": 4,
"nbformat_minor": 4
}