Regular Representation
This section describes the method, regular_representation, which is
defined in the Monoid class, so it also holds for all classes that
inherit from Monoid, that is, Group, Ring, and Field.
With respect to rings and fields, though, the regular representation only applies to the additive abelian group of the ring or field.
References
Georgi, Howard (2018), “Lie algebras in particle physics: from isospin to unified theories”, CRC Press, Open Access
Huang, Jiaqi (2012), “Lie Groups and their applications to Particle Physics: A Tutorial for Undergraduate Physics Majors”, arXiv:2012.00834v1
Introduction
The following definition was adapted from [Georgi, 2018].
A representation of a group, \(G = \langle A, \circ \rangle\), is a mapping, \(V\), of the elements of \(G\) onto a set of linear operators with the following properties:
\(V(e) = \hat{1}\), where \(e\) is the group’s identity element and \(\hat{1}\) is the identity operator in the space on which the linear operators act
\(V(a_i) \cdot V(a_j) = V(a_i \circ a_j)\) for all \(a_i, a_j \in A\). That is, the group multiplication law, “\(\circ\)”, is mapped onto the operator multiplication law, “\(\cdot\)”.
The regular representation of a group is a mapping of each group element to an \(nxn\) matrix. In this case, \(\hat{1}\) is the \(nxn\) identity matrix.
Most often, the term regular representation applies to groups, but the definition of a regular representation and the algorithm, to be provided below, doesn’t preclude monoids from having regular representations also. The definition & algorithm require an algebra that has an identity element, but not necessarily inverses.
Algorithm
The following algorithm for computing a regular representation was adapted from [Huang, 2012].
Let \(G = \langle A, \circ \rangle\), be a group, where \(A = \{a_0, a_1, \dots , a_{n - 1}\}\) is the group’s set of elements, \(a_0 = e\) (the Group’s identity element), and “\(\circ\)” is its binary operator.
Also, let \(B = \{\hat{b}_0, \hat{b}_1, \dots , \hat{b}_{n-1} \}\) be the following set of \(nx1\) vectors:
\(\hat{b}_0 = \begin{bmatrix} 1 \\ 0 \\ 0 \\ \vdots \\ 0 \end{bmatrix}, \hat{b}_1 = \begin{bmatrix} 0 \\ 1 \\ 0 \\ \vdots \\ 0 \end{bmatrix}, \dots, \hat{b}_{n-1} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ \vdots \\ 1 \end{bmatrix}\)
Define a bijection between \(A\) and \(B\) as follows: \(V(a_i) = \hat{b}_i\) for \(i = 0, \dots , n - 1\).
Let “\(\cdot\)” denote matrix-vector multiplication, and define the \(nxn\) matrix,
\(C_k = (c^k_{ij})_{i,j=0,\dots,n-1}\)
where \(c^k_{ij} = \hat{b}_i^T \cdot V(a_k \circ V^{-1}(\hat{b}_j))\)
Then \(M = \{C_0, C_1, \dots , C_{n - 1}\}\) is the regular representation of the group \(G\), where the mapping between group elements and operators is \(a_i \leftrightarrow C_i\) for \(i = 0, \dots , n - 1\).
Example: Cyclic Group, \(Z_4\)
In this example, we’ll derive the regular representation of the cyclic group, \(Z_4\), with elements, \(A = \left\{ e, a, a^2, a^3 \right\}\).
>>> import finite_algebras as alg
>>> Z4 = alg.generate_cyclic_group(4)
>>> Z4.about(use_table_names=True)
** Group **
Name: Z4
Instance ID: 4820319744
Description: Autogenerated cyclic Group of order 4
Order: 4
Identity: '0'
Commutative? Yes
Cyclic?: Yes
Generators: ['3', '1']
Elements:
Index Name Inverse Order
0 '0' '0' 1
1 '1' '3' 4
2 '2' '2' 2
3 '3' '1' 4
Cayley Table (showing names):
[['0', '1', '2', '3'],
['1', '2', '3', '0'],
['2', '3', '0', '1'],
['3', '0', '1', '2']]
'<Group:Z4, ID:4820319744>'
NOTE:In the remaining discussion, “matrix” and “array” will be used interchangeably, but in code, the word “array” or “arr” will be used primarily.
regular_representation returns the following four items:
A dictionary mapping each group element to its corresponding matrix (array)
A dictionary mapping each matrix (in tuple-of-tuples form) to its corresponding group element
A function that takes a group element and returns the corresponding matrix
A function that takes a matrix and returns the corresponding group element
Now, here’s the computation of the regular representation of \(Z_4\):
>>> elem2arr_map, arr2elem_map, elem2arr_fnc, arr2elem_fnc = Z4.regular_representation()
The following code depicts the element-to-array mapping:
>>> for elem in Z4:
>>> print(repr(elem))
>>> print(elem2arr_map[elem])
>>> print()
'0'
[[1. 0. 0. 0.]
[0. 1. 0. 0.]
[0. 0. 1. 0.]
[0. 0. 0. 1.]]
'1'
[[0. 0. 0. 1.]
[1. 0. 0. 0.]
[0. 1. 0. 0.]
[0. 0. 1. 0.]]
'2'
[[0. 0. 1. 0.]
[0. 0. 0. 1.]
[1. 0. 0. 0.]
[0. 1. 0. 0.]]
'3'
[[0. 1. 0. 0.]
[0. 0. 1. 0.]
[0. 0. 0. 1.]
[1. 0. 0. 0.]]
Here is the array-to-element mapping.
NOTE: Dictionary keys must be immutable. But NumPy arrays are mutable.
So, the method, regular_representation, transforms a NumPy array
into a tuple-of-tuples, which are immutable, and then use it as a
dictionary key. The tuple-of-tuples are, essentially, a sparse matrix
representation, and this transformation works for both NumPy dense
arrays or SciPy sparse arrays.
>>> arr2elem_map
{((np.int64(0), np.int64(0)),
(np.int64(1), np.int64(1)),
(np.int64(2), np.int64(2)),
(np.int64(3), np.int64(3))): '0',
((np.int64(0), np.int64(3)),
(np.int64(1), np.int64(0)),
(np.int64(2), np.int64(1)),
(np.int64(3), np.int64(2))): '1',
((np.int64(0), np.int64(2)),
(np.int64(1), np.int64(3)),
(np.int64(2), np.int64(0)),
(np.int64(3), np.int64(1))): '2',
((np.int64(0), np.int64(1)),
(np.int64(1), np.int64(2)),
(np.int64(2), np.int64(3)),
(np.int64(3), np.int64(0))): '3'}
Here is an example function call using the element-to-array function:
>>> a3_arr = elem2arr_fnc('3')
>>> a3_arr
array([[0., 1., 0., 0.],
[0., 0., 1., 0.],
[0., 0., 0., 1.],
[1., 0., 0., 0.]])
And, here’s an example of the array-to-element function, that goes in the reverse direction:
>>> arr2elem_fnc(a3_arr)
'3'
Verification
The method, verify_regular_representation, verifies that the two
bulleted conditions in the Introduction section, above, hold true for a
given regular representation. It requires the two functions output by
the regular representation method: element-to-array & array-to-element,
in that order.
>>> Z4.verify_regular_representation(elem2arr_fnc, arr2elem_fnc)
True
Example: Klein-4 Group, \(V_4\)
In this example, we’ll derive the regular representation of the Klein-4 group, \(V_4\), with elements, \(A = \left\{ e, h, v, r \right\}\).
First, retrieve \(V_4\) from the built-in examples:
>>> import os
>>> aa_path = os.path.join(os.getenv("PYPROJ"), "abstract_algebra")
>>> alg_dir = os.path.join(aa_path, "Algebras")
>>> ex = alg.Examples(alg_dir) # Loads algebras & prints list below
======================================================================
Example Algebras
----------------------------------------------------------------------
19 example algebras are available.
Use "Examples[INDEX]" to retrieve a specific example,
where INDEX is the first number on each line below:
----------------------------------------------------------------------
0: A4 -- Alternating group on 4 letters (AKA Tetrahedral group)
1: D3 -- https://en.wikipedia.org/wiki/Dihedral_group_of_order_6
2: D4 -- Dihedral group on four vertices
3: Pinter29 -- Non-abelian group, p.29, 'A Book of Abstract Algebra' by Charles C. Pinter
4: RPS -- Rock, Paper, Scissors Magma
5: S3 -- Symmetric group on 3 letters
6: S3X -- Another version of the symmetric group on 3 letters
7: V4 -- Klein-4 group
8: Z4 -- Cyclic group of order 4
9: F4 -- Field with 4 elements (from Wikipedia)
10: mag_id -- Magma with Identity
11: Example 1.4.1 -- See: Groupoids and Smarandache Groupoids by W. B. Vasantha Kandasamy
12: Ex6 -- Example 6: http://www-groups.mcs.st-andrews.ac.uk/~john/MT4517/Lectures/L3.html
13: Q8 -- Quaternion Group
14: SD16 -- Semidihedral group of order 16
15: A5 -- Alternating group on 5 letters
16: F2 -- Field with 2 elements from paper: 236w06fields.pdf
17: Latin_Sqr -- Latin Square. A division algebra (AKA Quasigroup)
18: IP_Loop -- IP loop of small order
======================================================================
The \(V_4\) group is #7 in the list above:
>>> V4 = ex[7]
>>> V4.about()
** Group **
Name: V4
Instance ID: 4820949456
Description: Klein-4 group
Order: 4
Identity: 'e'
Commutative? Yes
Cyclic?: No
Elements:
Index Name Inverse Order
0 'e' 'e' 1
1 'h' 'h' 2
2 'v' 'v' 2
3 'r' 'r' 2
Cayley Table (showing indices):
[[0, 1, 2, 3], [1, 0, 3, 2], [2, 3, 0, 1], [3, 2, 1, 0]]
'<Group:V4, ID:4820949456>'
>>> elem2arr_map, X, Y, Z = V4.regular_representation() # tired of typing, hence X,Y,Z
>>> V4.verify_regular_representation(Y, Z)
True
>>> elem2arr_map
{'e': array([[1., 0., 0., 0.],
[0., 1., 0., 0.],
[0., 0., 1., 0.],
[0., 0., 0., 1.]]),
'h': array([[0., 1., 0., 0.],
[1., 0., 0., 0.],
[0., 0., 0., 1.],
[0., 0., 1., 0.]]),
'v': array([[0., 0., 1., 0.],
[0., 0., 0., 1.],
[1., 0., 0., 0.],
[0., 1., 0., 0.]]),
'r': array([[0., 0., 0., 1.],
[0., 0., 1., 0.],
[0., 1., 0., 0.],
[1., 0., 0., 0.]])}
Example: A Monoid
This example illustrates the regular representation method applied to a monoid.
>>> M6 = alg.generate_commutative_monoid(6)
>>> M6.about()
** Monoid **
Name: M6
Instance ID: 4822499408
Description: Autogenerated commutative Monoid of order 6
Order: 6
Identity: a1
Associative? Yes
Commutative? Yes
Cyclic?: No
Elements: ('a0', 'a1', 'a2', 'a3', 'a4', 'a5')
Has Cancellation? No
Has Inverses? No
Cayley Table (showing indices):
[[0, 0, 0, 0, 0, 0],
[0, 1, 2, 3, 4, 5],
[0, 2, 4, 0, 2, 4],
[0, 3, 0, 3, 0, 3],
[0, 4, 2, 0, 4, 2],
[0, 5, 4, 3, 2, 1]]
>>> elem2arr_map, X, Y, Z = M6.regular_representation()
>>> M6.verify_regular_representation(Y, Z)
True
>>> elem2arr_map
{'a0': array([[1., 1., 1., 1., 1., 1.],
[0., 0., 0., 0., 0., 0.],
[0., 0., 0., 0., 0., 0.],
[0., 0., 0., 0., 0., 0.],
[0., 0., 0., 0., 0., 0.],
[0., 0., 0., 0., 0., 0.]]),
'a1': array([[1., 0., 0., 0., 0., 0.],
[0., 1., 0., 0., 0., 0.],
[0., 0., 1., 0., 0., 0.],
[0., 0., 0., 1., 0., 0.],
[0., 0., 0., 0., 1., 0.],
[0., 0., 0., 0., 0., 1.]]),
'a2': array([[1., 0., 0., 1., 0., 0.],
[0., 0., 0., 0., 0., 0.],
[0., 1., 0., 0., 1., 0.],
[0., 0., 0., 0., 0., 0.],
[0., 0., 1., 0., 0., 1.],
[0., 0., 0., 0., 0., 0.]]),
'a3': array([[1., 0., 1., 0., 1., 0.],
[0., 0., 0., 0., 0., 0.],
[0., 0., 0., 0., 0., 0.],
[0., 1., 0., 1., 0., 1.],
[0., 0., 0., 0., 0., 0.],
[0., 0., 0., 0., 0., 0.]]),
'a4': array([[1., 0., 0., 1., 0., 0.],
[0., 0., 0., 0., 0., 0.],
[0., 0., 1., 0., 0., 1.],
[0., 0., 0., 0., 0., 0.],
[0., 1., 0., 0., 1., 0.],
[0., 0., 0., 0., 0., 0.]]),
'a5': array([[1., 0., 0., 0., 0., 0.],
[0., 0., 0., 0., 0., 1.],
[0., 0., 0., 0., 1., 0.],
[0., 0., 0., 1., 0., 0.],
[0., 0., 1., 0., 0., 0.],
[0., 1., 0., 0., 0., 0.]])}
Example: Sparse Matrix Output
Sparse matrix output is supported, but optional. By default, the matrices output by the regular representation method are dense arrays. SciPy sparse arrays can be output instead, by setting the input variable, sparse, to one of the following seven strings: “BSR”, “COO”, “CSC”, “CSR”, “DIA”, “DOK”, or “LIL”. Each one of the seven strings corresponds to one of the seven classes of sparse array supported by SciPy.
This example reuses the cyclic group, \(Z_4\), to demonstrate the Compressed Sparse Column (CSC) sparse matrix output.
>>> elem2arr_map, arr2elem_map, elem2arr_fnc, arr2elem_fnc = Z4.regular_representation("CSC")
>>> elem2arr_map
{'0': <Compressed Sparse Column sparse array of dtype 'int64'
with 4 stored elements and shape (4, 4)>,
'1': <Compressed Sparse Column sparse array of dtype 'int64'
with 4 stored elements and shape (4, 4)>,
'2': <Compressed Sparse Column sparse array of dtype 'int64'
with 4 stored elements and shape (4, 4)>,
'3': <Compressed Sparse Column sparse array of dtype 'int64'
with 4 stored elements and shape (4, 4)>}
The “raw” output, above, doesn’t reveal the contents of the sparse arrays, but printing them out helps, as shown below.
>>> for elem in Z4:
>>> print(elem)
>>> print(elem2arr_map[elem])
>>> print()
0
<Compressed Sparse Column sparse array of dtype 'int64'
with 4 stored elements and shape (4, 4)>
Coords Values
(0, 0) 1
(1, 1) 1
(2, 2) 1
(3, 3) 1
1
<Compressed Sparse Column sparse array of dtype 'int64'
with 4 stored elements and shape (4, 4)>
Coords Values
(1, 0) 1
(2, 1) 1
(3, 2) 1
(0, 3) 1
2
<Compressed Sparse Column sparse array of dtype 'int64'
with 4 stored elements and shape (4, 4)>
Coords Values
(2, 0) 1
(3, 1) 1
(0, 2) 1
(1, 3) 1
3
<Compressed Sparse Column sparse array of dtype 'int64'
with 4 stored elements and shape (4, 4)>
Coords Values
(3, 0) 1
(0, 1) 1
(1, 2) 1
(2, 3) 1
>>> arr2elem_map
{((np.int32(0), np.int32(0)),
(np.int32(1), np.int32(1)),
(np.int32(2), np.int32(2)),
(np.int32(3), np.int32(3))): '0',
((np.int32(0), np.int32(3)),
(np.int32(1), np.int32(0)),
(np.int32(2), np.int32(1)),
(np.int32(3), np.int32(2))): '1',
((np.int32(0), np.int32(2)),
(np.int32(1), np.int32(3)),
(np.int32(2), np.int32(0)),
(np.int32(3), np.int32(1))): '2',
((np.int32(0), np.int32(1)),
(np.int32(1), np.int32(2)),
(np.int32(2), np.int32(3)),
(np.int32(3), np.int32(0))): '3'}
>>> a3_arr = elem2arr_fnc('3')
>>> print(a3_arr)
<Compressed Sparse Column sparse array of dtype 'int64'
with 4 stored elements and shape (4, 4)>
Coords Values
(3, 0) 1
(0, 1) 1
(1, 2) 1
(2, 3) 1
>>> arr2elem_fnc(a3_arr)
'3'