## Linear Representations

1. Homomorphism $\alpha: G \rightarrow GL(n,k)$ where n is the dimension of a vector space over field $k$. That is $n \times n $ matrices.
2. A group action $G \times X \rightarrow X:(g,x) \mapsto x$ where 
 >1. $X$ is vector space and 
 >2. $(gh)x) = g(hx)$
 >3. $ex=x$
 >4. $g(u + v) = gu + gv$
 >5. $g(ρv) = ρ(gv)$

---
A group action on a set of finite size is a subgroup of permutations, they may be represented as special matrices of size n 

for example:  $\begin{pmatrix}
1 & 2 & 3\\ 
2 & 1 & 3
\end{pmatrix} \Leftrightarrow  
\begin{pmatrix}
0 & 1 & 0\\ 
1 & 0 & 0\\ 
0 & 0 & 1
\end{pmatrix}$

---

A 1-dimensional representation is simply a homomorphism to multiplicative group of the field.

$g \mapsto 1$ is the trivial representation.

a 1-dimensional representation is constant on each conjugacy class 

for $S_n$: 

$g \mapsto \left 
\{\begin{matrix}
1 & if \ g \ is \ even \\ 
-1 & if \ g \ is \ odd
\end{matrix}\right.$

for $D_4$:  
$r^4=1, c^2=1, (rc)^2=1 \Rightarrow c=\pm1,r=\pm1$  
there are 4 1-dimensional representations

&nbsp;

2-dimensional representations of $S_3$: $\langle s, t \vert s^3,t^2, st=ts^2  \rangle$ over $\mathbb{C}$  
suppose $s$ has a eigenvector $v_1$ with eigenvalue $\lambda \ne 1, \ \lambda^3=1, \ \lambda = \exp(i2\pi/3)$  
$s(tv_1) = ts^2v_1=\lambda^2(tv_1) \Rightarrow s \mapsto \begin{pmatrix}
\lambda & 0 \\ 
0 & \lambda^2
\end{pmatrix}$ and the next eigenvector is $v_2==tv_1$  
on the other hand $tv_1=v_2, tv_2=v_1 \Rightarrow t \mapsto \begin{pmatrix}
0 & 1 \\ 
1 & 0
\end{pmatrix}$

the other case is $s \mapsto \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$, then t will be free: $t \mapsto \begin{pmatrix} \lambda & 0 \\ 0 & \mu \end{pmatrix}$, $\lambda,\mu=\pm1$

&nbsp;

The representation $\alpha$ of $G$ in the vector space $V$ over $k$ is said to
be **simple (irreducible)** if no proper subspace of $V$ is stable under $G$.

$dim \ \alpha \le \vert G \vert$

A simple representation of a finite abelian group over $\mathbb{C}$ is necessarily 1-dimensional. (commutative matrices can be diagonalised simultaneously)


**Arithmetic of Representations**

$\alpha:g \mapsto A(g), \  \beta:g \mapsto B(g), \ \alpha+\beta: g \mapsto \begin{pmatrix} A(g) & 0 \\ 0 & B(g)\end{pmatrix}$. The representation space is  $V \oplus W$

$\alpha:g \mapsto A(g), \  \beta:g \mapsto B(g), \ \alpha\beta: g \mapsto A(g) \otimes B(g)$. . The representation space is  $V \otimes W$

> $\alpha+\beta=\beta+ \alpha$  
> $\alpha+(\beta+\gamma)=(\alpha+\beta)+ \gamma$  
> $\alpha\beta=\beta \alpha$  
> $\alpha(\beta\gamma)=(\alpha\beta) \gamma$  
> $\alpha(\beta+\gamma)=\alpha\beta+ \alpha\gamma$  

Conjugacy: if $\alpha$ is the representation of $G$ in $V$, $\alpha^*$ is the representation of $G$ in dual space $V^*$  
$\alpha:g \mapsto A(g), \ \alpha^* \mapsto (A(g)^{-1})^\prime$

> $(\alpha^*)^*=\alpha$  
> $(\alpha+\gamma)^*=\alpha^*+\beta^*$  
> $(\alpha\beta)^*=\alpha^*\beta^*$  

&nbsp;

The represenation is said to be **semisimple** if it is expressible as a sum of simple representations:
$\alpha = \sigma_1+\sigma_2+ ... + \sigma_r$ .
Equivalently each stable subspace $U \subset V$ has at least one complementary stable subspace $W$, ie $V=U \oplus W$.

---

Let $Q$ be a positive (hermitian) form in $\mathbb{R}^n$ ($\mathbb{C}^n$). Avaraging it over group: 
$P(u,v) =\frac{1}{\vert G\vert} \sum_ {g \in G} Q(gu,gv)$

$P(u,v)=0 \Rightarrow gu \perp gv \ for \ all \ g \in G$ and $u \in U \Rightarrow v \in U^{\bot}$

---

**Maschke’s Theorem**: Suppose α is a representation of the finite
group $G$ over $k$ ($\vert G \vert \ne 0 \ in \ k$). Then α is semisimple.

The expression for a semisimple representation $\alpha$ as a sum of simple parts $\alpha = \sigma_1+\sigma_2+ ... + \sigma_r$ is unique up to order.

The character $\chi_\alpha:G \rightarrow k$ is defined as $\chi(g)=tr(\alpha(g))$
> $\chi_{\alpha+\beta}(g)=\chi_\alpha(g)+\chi_\beta(g)$  
> $\chi_{\alpha\beta}(g)=\chi_\alpha(g)\chi_\beta(g)$  
> $\chi_{\alpha^*}(g)=\chi_{\alpha}(g^{-1})$  
> $\chi_{1}(g)=1$  
> $\chi_\alpha(e)=dim \alpha$  

Two representations are equivalent if and only if their characters are equal:
> $\alpha = \beta \Leftrightarrow \chi_\alpha(g)=\chi_\beta(g) \ for \ all \ g\in G$

For representations of $G$ over $C$
>$\chi (I) = n$  
>$\vert \chi(g) \vert \le n$,  
>$\vert \chi(g) \vert = n$ implies $g = e^{iθ}I$  
>$\chi$ is constant on any given conjugacy class of $G$  
>$\chi (g^{−1}) = \chi^*(g)$  
>$\chi(g)$ is an algebraic number for all $g$.

1. The number of simple representations of $G$ over $C$ is equal to the number of conjugacy classes in $G$
2. The dimensions of the simple representations $σ_1, . . . , σ_s$ of $G$ over $C$ satisfy the relation  
>$dim^2 σ_1 + · · · + dim^2 σ_s = \vert G \vert$.
3. The dimension of each simple representation $σ_i$ divides the order of the group: $dim σ_i\> |\> \vert G \vert$.

$\alpha$ is representation of $G$ and $\beta$ is representation of $H$, then $\alpha \times \beta$ (over $U \otimes V$) is representation of $G \times H$. and $\alpha \times \beta$ is simple iff $\alpha$ and $\beta$ are simple.



Theorem. A representation of $G$ is irreducible if and only if $\sum_{g \in G} |\chi(g)|^2 = \vert G \vert$

The characters are orthogonal, that is: $\sum_{i=1}^{r} r_i (\chi^p_i)^* \chi^q_i = |G|\delta_{pq}$ and $\sum_{p=1}^r (\chi^p_i)^* \chi^q_j = \frac{|G|}{r_i}\delta_{ij}$  
where $p,q$ denote representations, $\chi^p_i$ is the character of $i$th conjugacy calss in $p$th irreducable representation, and $r_i$ is size of $i$th conjugacy class.

Theorem. If $\rho$ is an arbitrary representation of $G$ with character $\chi$, and $\rho^p$ are the
inequivalent irreducible representations of $G$ with characters $\chi^p$, then $\rho = \bigoplus_p c_p \rho^p$, where 
$c_p = \frac{1}{|G|} \sum_{i=1}^{r} r_i (\chi_i^p)^*\chi_i$

The regular representation contains $dim \rho^p$ instances of each irreducible representation: $\chi_i^R = \sum (dim \rho^p)\chi_i^p$






```python
# Z3 sympy exercises
import sympy.combinatorics.permutations as P
import sympy.combinatorics.named_groups as G
from sympy.matrices import eye
from sympy import *
init_printing(use_latex='mathjax')
P.Permutation.print_cyclic
c = G.CyclicGroup(3)
el = [e for e in c.elements]
el.sort(key=lambda x: c.coset_rank(x))
display(el)
m = eye(3)
regR = [m.permuteFwd(e) for e in el]
display(regR)
lamda = symbols('lamda')
poly=[factor(p.charpoly(lamda)) for p in regR]
display(poly)
(p1,d1) = regR[1].diagonalize()

(p2,d2) = regR[2].diagonalize()
#display(d1)

p1_=simplify(p1**-1)
display([simplify(p1_*regR[1]*p1),simplify(p1_*regR[2]*p1)])


```


$$\left [ \left( 2\right), \quad \left( 0\; 1\; 2\right), \quad \left( 0\; 2\; 1\right)\right ]$$



$$\left [ \left[\begin{matrix}1 & 0 & 0\\0 & 1 & 0\\0 & 0 & 1\end{matrix}\right], \quad \left[\begin{matrix}0 & 1 & 0\\0 & 0 & 1\\1 & 0 & 0\end{matrix}\right], \quad \left[\begin{matrix}0 & 0 & 1\\1 & 0 & 0\\0 & 1 & 0\end{matrix}\right]\right ]$$



$$\left [ \left(\lambda - 1\right)^{3}, \quad \left(\lambda - 1\right) \left(\lambda^{2} + \lambda + 1\right), \quad \left(\lambda - 1\right) \left(\lambda^{2} + \lambda + 1\right)\right ]$$



$$\left [ \left[\begin{matrix}1 & 0 & 0\\0 & - \frac{1}{2} - \frac{\sqrt{3} i}{2} & 0\\0 & 0 & - \frac{1}{2} + \frac{\sqrt{3} i}{2}\end{matrix}\right], \quad \left[\begin{matrix}1 & 0 & 0\\0 & - \frac{1}{2} + \frac{\sqrt{3} i}{2} & 0\\0 & 0 & - \frac{1}{2} - \frac{\sqrt{3} i}{2}\end{matrix}\right]\right ]$$



```python
w = exp(I*2*pi/3)
display(w,w.expand(complex=true))
m = Matrix([[0,-1],[1,-1]])
display([m,m.inv(),m*m])
```


$$e^{\frac{2 \pi}{3} i}$$



$$- \frac{1}{2} + \frac{\sqrt{3} i}{2}$$



$$\left [ \left[\begin{matrix}0 & -1\\1 & -1\end{matrix}\right], \quad \left[\begin{matrix}-1 & 1\\-1 & 0\end{matrix}\right], \quad \left[\begin{matrix}-1 & 1\\-1 & 0\end{matrix}\right]\right ]$$


3 representations over $C$: >$\{1,1,1\}$ $\{1,w,w^2\}$ $\{1,w^2,w\}$

not trivial representation over $N$: $\begin{bmatrix}
1 & 0\\ 
0 & 1
\end{bmatrix}$, 
$\begin{bmatrix}
0 & -1\\ 
1 & -1
\end{bmatrix}$,
$\begin{bmatrix}
-1 & 1\\ 
-1 & 0
\end{bmatrix}$

not trivial orthogonal representation over $R$: $\begin{bmatrix}
1 & 0\\ 
0 & 1
\end{bmatrix}$, 
$\begin{bmatrix}
-\frac{1}{2} & -\frac{\sqrt 3}{2}\\ 
\frac{\sqrt 3}{2} & -\frac{1}{2}
\end{bmatrix}$,
$\begin{bmatrix}
-\frac{1}{2} & \frac{\sqrt 3}{2}\\ 
-\frac{\sqrt 3}{2} & -\frac{1}{2}
\end{bmatrix}$



## Pauli matrices

$\{±I,±iI,±X,±iX,±Y,±iY,±Z,±iZ\}$
One of Generator Sets: $\langle iI,X,Y \rangle$

Center is $\{±I,±iI\}$




```python
e, X, Y, Z = symbols('e X Y Z')

t = [e,X,Y,Z]
pauliSymbols = [e,X,Y,Z]
pauliSymbols.extend([-l for l in t])
pauliSymbols.extend([I*l for l in t])
pauliSymbols.extend([-I*l for l in t])

display([(e,pauliSymbols[e]) for e in range(16)])
```


$$\left [ \left ( 0, \quad e\right ), \quad \left ( 1, \quad X\right ), \quad \left ( 2, \quad Y\right ), \quad \left ( 3, \quad Z\right ), \quad \left ( 4, \quad - e\right ), \quad \left ( 5, \quad - X\right ), \quad \left ( 6, \quad - Y\right ), \quad \left ( 7, \quad - Z\right ), \quad \left ( 8, \quad i e\right ), \quad \left ( 9, \quad i X\right ), \quad \left ( 10, \quad i Y\right ), \quad \left ( 11, \quad i Z\right ), \quad \left ( 12, \quad - i e\right ), \quad \left ( 13, \quad - i X\right ), \quad \left ( 14, \quad - i Y\right ), \quad \left ( 15, \quad - i Z\right )\right ]$$



```python
from sympy.combinatorics.perm_groups import PermutationGroup
e8 = P.Permutation([8,9,10,11, 12,13,14,15, 4,5,6,7,  0,1,2,3])
e1 = P.Permutation([1,0,11,14, 5,4,15,10,   9,8,7,2,  13,12,3,6])
e2 = P.Permutation([2,15,0,9,  6,11,4,13,   10,3,8,5, 14,7,12,1])
display(e8)
display(e1)
display(e2)

p = PermutationGroup(e8,e1,e2)
display(p.degree)
p.center()
```


$$\left( 0\; 8\; 4\; 12\right)\left( 1\; 9\; 5\; 13\right)\left( 2\; 10\; 6\; 14\right)\left( 3\; 11\; 7\; 15\right)$$



$$\left( 0\; 1\right)\left( 2\; 11\right)\left( 3\; 14\right)\left( 4\; 5\right)\left( 6\; 15\right)\left( 7\; 10\right)\left( 8\; 9\right)\left( 12\; 13\right)$$



$$\left( 0\; 2\right)\left( 1\; 15\right)\left( 3\; 9\right)\left( 4\; 6\right)\left( 5\; 11\right)\left( 7\; 13\right)\left( 8\; 10\right)\left( 12\; 14\right)$$



$$16$$





$$PermutationGroup([
    (15),
    (0 4)(1 5)(2 6)(3 7)(8 12)(9 13)(10 14)(11 15),
    (0 8 4 12)(1 9 5 13)(2 10 6 14)(3 11 7 15),
    (0 12 4 8)(1 13 5 9)(2 14 6 10)(3 15 7 11)])$$




```python
from sympy.combinatorics.free_groups import free_group
from sympy.combinatorics.fp_groups import FpGroup
from sympy.combinatorics.fp_groups import low_index_subgroups
F, i, x, y = free_group("i, x y")
G = FpGroup(F, [i**4, x**2, i*x*i**-1*x**-1, y**2, i*y*i**-1*y**-1, (x*y)**4, i*i*x*y*x**-1*y**-1])
print("Order is:",G.order())
l = low_index_subgroups(G,16)
print("SubGroup Count is:",len(l))
#for t in l:
#    print(len(t.table))
```

    Order is: 16
    SubGroup Count is: 20


## Fourier transforms

Let $f$ be a function which maps group elements to complex numbers. For an irreducible representation $\rho$ of $G$, of dimension $d_\rho$, we define the Fourier transform of $f$ to be: $$\widehat{f}(\rho) \equiv \sqrt{\frac{d_\rho}{|G|}} \sum_{g \in G} f(g) \rho(g)$$

Inverse fourier transform will be: $$f(g) = \frac{1}{\sqrt{|G|}} \sum_{\rho in \widehat{G}} \sqrt{d_{\rho}} tr(\widehat{f}(\rho) \rho(g^{-1}))$$

for $Z_n$ the formules simplify to usual finite discrete fourier transforms.



## Links

[breif intro to Representations of finite groups](https://www.maths.tcd.ie/pub/Maths/Courseware/GroupRepresentations/FiniteGroups.pdf)

[combinatorics, Permutation Group](http://www.di.fc.ul.pt/~jpn/r/combinatorics/combinatorics.html)

[EFFICIENT COMPUTATION OF THE FOURIER TRANSFORM ON FINITE GROUPS](https://www.ams.org/journals/jams/1990-03-02/S0894-0347-1990-1030655-4/S0894-0347-1990-1030655-4.pdf)

[RECENT RESULTS IN GENERALIZED FAST FOURIER TRANSFORMS](https://www.math.hmc.edu/seniorthesis/archives/2005/emalm/emalm-2005-expository.pdf)


https://en.wikipedia.org/wiki/Noncommutative_harmonic_analysis





a6642b3eac4cee4c72c917829c97b87fbb527e4a
ipynb
Jupyter Notebook
Math/IntroToGroups2.ipynb
gate42qc/seminars
35ff77b902d9c2ede619fd6e2d9c3e80d20d78de
MIT
2018-12-07T10:02:06.000Z
2019-11-24T19:30:03.000Z
Math/IntroToGroups2.ipynb
gate42qc/seminars
35ff77b902d9c2ede619fd6e2d9c3e80d20d78de
MIT
Math/IntroToGroups2.ipynb
gate42qc/seminars
35ff77b902d9c2ede619fd6e2d9c3e80d20d78de
MIT
2019-08-22T12:07:40.000Z
2019-08-22T12:07:40.000Z
Qwen/Qwen-72B
1. YES
2. YES