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, :math:`G = \langle A, \circ \rangle`, is a mapping, :math:`V`, of the elements of :math:`G` onto a set of linear operators with the following properties: - :math:`V(e) = \hat{1}`, where :math:`e` is the group’s identity element and :math:`\hat{1}` is the identity operator in the space on which the linear operators act - :math:`V(a_i) \cdot V(a_j) = V(a_i \circ a_j)` for all :math:`a_i, a_j \in A`. That is, the group multiplication law, “:math:`\circ`”, is mapped onto the operator multiplication law, “:math:`\cdot`”. The regular representation of a group is a mapping of each group element to an :math:`nxn` matrix. In this case, :math:`\hat{1}` is the :math:`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 :math:`G = \langle A, \circ \rangle`, be a group, where :math:`A = \{a_0, a_1, \dots , a_{n - 1}\}` is the group’s set of elements, :math:`a_0 = e` (the Group’s identity element), and “:math:`\circ`” is its binary operator. Also, let :math:`B = \{\hat{b}_0, \hat{b}_1, \dots , \hat{b}_{n-1} \}` be the following set of :math:`nx1` vectors: :math:`\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 :math:`A` and :math:`B` as follows: :math:`V(a_i) = \hat{b}_i` for :math:`i = 0, \dots , n - 1`. Let “:math:`\cdot`” denote matrix-vector multiplication, and define the :math:`nxn` matrix, :math:`C_k = (c^k_{ij})_{i,j=0,\dots,n-1}` where :math:`c^k_{ij} = \hat{b}_i^T \cdot V(a_k \circ V^{-1}(\hat{b}_j))` Then :math:`M = \{C_0, C_1, \dots , C_{n - 1}\}` is the regular representation of the group :math:`G`, where the mapping between group elements and operators is :math:`a_i \leftrightarrow C_i` for :math:`i = 0, \dots , n - 1`. Example: Cyclic Group, :math:`Z_4` ---------------------------------- In this example, we’ll derive the regular representation of the cyclic group, :math:`Z_4`, with elements, :math:`A = \left\{ e, a, a^2, a^3 \right\}`. .. code:: ipython3 >>> import finite_algebras as alg >>> Z4 = alg.generate_cyclic_group(4) >>> Z4.about(use_table_names=True) .. parsed-literal:: ** 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']] .. parsed-literal:: '' 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: 1. A dictionary mapping each group element to its corresponding matrix (array) 2. A dictionary mapping each matrix (in tuple-of-tuples form) to its corresponding group element 3. A function that takes a group element and returns the corresponding matrix 4. A function that takes a matrix and returns the corresponding group element Now, here’s the computation of the regular representation of :math:`Z_4`: .. code:: ipython3 >>> elem2arr_map, arr2elem_map, elem2arr_fnc, arr2elem_fnc = Z4.regular_representation() The following code depicts the element-to-array mapping: .. code:: ipython3 >>> for elem in Z4: >>> print(repr(elem)) >>> print(elem2arr_map[elem]) >>> print() .. parsed-literal:: '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. .. code:: ipython3 >>> arr2elem_map .. parsed-literal:: {((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: .. code:: ipython3 >>> a3_arr = elem2arr_fnc('3') >>> a3_arr .. parsed-literal:: 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: .. code:: ipython3 >>> arr2elem_fnc(a3_arr) .. parsed-literal:: '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. .. code:: ipython3 >>> Z4.verify_regular_representation(elem2arr_fnc, arr2elem_fnc) .. parsed-literal:: True Example: Klein-4 Group, :math:`V_4` ----------------------------------- In this example, we’ll derive the regular representation of the Klein-4 group, :math:`V_4`, with elements, :math:`A = \left\{ e, h, v, r \right\}`. First, retrieve :math:`V_4` from the built-in examples: .. code:: ipython3 >>> 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 .. parsed-literal:: ====================================================================== 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 :math:`V_4` group is #7 in the list above: .. code:: ipython3 >>> V4 = ex[7] >>> V4.about() .. parsed-literal:: ** 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]] .. parsed-literal:: '' .. code:: ipython3 >>> elem2arr_map, X, Y, Z = V4.regular_representation() # tired of typing, hence X,Y,Z .. code:: ipython3 >>> V4.verify_regular_representation(Y, Z) .. parsed-literal:: True .. code:: ipython3 >>> elem2arr_map .. parsed-literal:: {'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. .. code:: ipython3 >>> M6 = alg.generate_commutative_monoid(6) >>> M6.about() .. parsed-literal:: ** 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]] .. code:: ipython3 >>> elem2arr_map, X, Y, Z = M6.regular_representation() .. code:: ipython3 >>> M6.verify_regular_representation(Y, Z) .. parsed-literal:: True .. code:: ipython3 >>> elem2arr_map .. parsed-literal:: {'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, :math:`Z_4`, to demonstrate the Compressed Sparse Column (CSC) sparse matrix output. .. code:: ipython3 >>> elem2arr_map, arr2elem_map, elem2arr_fnc, arr2elem_fnc = Z4.regular_representation("CSC") >>> elem2arr_map .. parsed-literal:: {'0': , '1': , '2': , '3': } The “raw” output, above, doesn’t reveal the contents of the sparse arrays, but printing them out helps, as shown below. .. code:: ipython3 >>> for elem in Z4: >>> print(elem) >>> print(elem2arr_map[elem]) >>> print() .. parsed-literal:: 0 Coords Values (0, 0) 1 (1, 1) 1 (2, 2) 1 (3, 3) 1 1 Coords Values (1, 0) 1 (2, 1) 1 (3, 2) 1 (0, 3) 1 2 Coords Values (2, 0) 1 (3, 1) 1 (0, 2) 1 (1, 3) 1 3 Coords Values (3, 0) 1 (0, 1) 1 (1, 2) 1 (2, 3) 1 .. code:: ipython3 >>> arr2elem_map .. parsed-literal:: {((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'} .. code:: ipython3 >>> a3_arr = elem2arr_fnc('3') >>> print(a3_arr) .. parsed-literal:: Coords Values (3, 0) 1 (0, 1) 1 (1, 2) 1 (2, 3) 1 .. code:: ipython3 >>> arr2elem_fnc(a3_arr) .. parsed-literal:: '3'