The Representation Theory of the Discrete Fourier Transform

Functions on Groups

Given a finite group $G$, I want to consider the algebra of complex-valued functions on $G$ (i.e. $\{f:G \to \C\}$).

Why? There are several reasons to study this algebra of functions. From a purely group-theoretic perspective, it is interesting because it can help you understand groups better. Today, however, I'll mostly focus on applications to CS.

What algebra structure are we using?

There are multiple choices of algebra structure on the set of functions $\{f:G \to \C\}$. Addition and scalar multiplication are pretty straightforward; clearly they should be done pointwise. You might also want to multiply the functions pointwise. This defines a perfectly fine algebra, but then nothing in our algebra actually depends on the group structure. We want to take advantage of the group structure to study these functions. So we won't define multiplication this way. Instead, we take the slightly stranger definition that \[ f_1 * f_2 (g) := \sum_{g_1 g_2 = g} f_1(g_1)\cdot f_2(g_2) \] We call this product convolution.

The group algebra $\C[G]$ is the algebra of complex-valued functions on $G$ with pointwise addition and scalar multiplication, and convolution as the product.

Miscellaneous facts about $\C[G]$

For $h \in G$, we define the $\delta$-function \[ \delta_h(g) := \begin{cases} 1 & g = h\\0 & \text{otherwise}\end{cases} \] With the convolution product, the multiplicative identity is the function $\delta_e$.

You can check that \[ f \star \delta_e(g) = \sum_{g_1g_2 = g} f(g_1) \delta_e(g_2) = f(g)\delta_e(e) = f(g) \] One useful basis for $\C[G]$ is given by $\{\delta_h\;|\;h \in G\}$.

We can define a hermitian product on $\C[G]$ by \[ \inrp {f_1} {f_2} := \frac 1 {|G|} \sum_{g \in G} f_1(g) \cdot \overline{f_2(g)} \]

Example: $\C[\Z/n\Z]$

Suggestively, I'll denote $\delta_k$ by $x^k$. Then, elements of $\C[\Z/n\Z]$ are sums $a = \sum_{i=0}^{n-1} a_i x^i$. The product is given by \[ a\cdot b = \sum_{i = 0}^{n-1} \left[\sum_{j + k = i} a_j b_k \right]x^i \] So we see that $\C[\Z/n\Z] = \C[x]/(x^n-1)$. This is an important example for CS applications.

One useful tool for studying rings is studying modules over that ring. This trick will be very helpful to us.

Modules over $\C[G]$

Let $M$ be a module over $\C[G]$. First, we note that we can use our action of $\C[G]$ on $M$ to define an action of $\C$ on $M$. Simply define $\lambda \cdot m := (\lambda \delta_e) \cdot m$ for all $m \in M$. You can check that this makes $M$ into a complex vector space. Since $\delta_e$ is the multiplicative identity, it commutes with every element of $\C[G]$. So the action of every other element of $\C[G]$ on $M$ is linear with respect to this $\C$-action.

Furthermore, given a $\C$-vector space structure on $M$, the $\C[G]$ module structure is entirely determined by how each $\delta_g$ acts on $M$. So we can describe $M$ as a complex vector space along with a map $\rho:G \to \Aut(M)$.

Representations

A representation of $G$ is a vector space $V$ along with a homomorphism $\rho:G \to \Aut(M)$. We will denote this representation $(V, \rho)$, or just $V$.
Given a representation $(V, \rho)$, a subrepresentation is a linear subspace $W \subseteq V$ such that $g\cdot w \in W$ for all $w \in W$. Note that this makes $W$ into a representation of $G$.
A representation is called irreducible if its only subrepresentations are $\{0\}$ and itself. I'll call irreducible $G$-representations irreps.
A $G$-linear map (or morphism) between representations $(V, \rho)$, $(W, \pi)$ is a linear map $\phi: V \to W$ such that $\phi \circ \rho(g) = \pi(g) \circ \phi$ for all $g \in G$. We denote the set of all such morphisms between representations $V$ and $W$ by $\Hom_G(V, W)$ (Note that the particular action of $G$ on $V$ and $W$ is important, but we don't write $\rho$ and $\pi$ explicitly because the notation is already kind of long).
  1. Any nonzero morphism between two irreps is an isomorphism.
  2. Any nonzero morphism from an irrep to itself is an isomorphism.
  1. Let $E, F$ be irreps. Suppose $\phi : E \to F$. $\ker \phi$ is a linear subspace of $E$. And if $\phi(v) = 0$, then $\phi(gv) = g \phi(v) = 0$. So $\ker \phi$ is $G$-invariant. Similarly, $\im \phi$ is a linear subspace of $F$. And if $w = \phi(v)$, then $gw = \phi(gv)$. So $\im \phi$ is also $G$-invariant. Since $E$ and $F$ are irreducible, this means that $\ker \phi$ and $\im \phi$ are either 0 or the whole vector space. If $\phi$ is nonzero, we must have $\ker \phi \neq E$, $\im \phi \neq 0$. So $\phi$ must be an isomorphism.
  2. Let $\phi:E \to E$ be a nonzero morphism. Since we are working over $\C$, it must have a nonzero eigenvalue $\lambda$. Thus, $\phi - \lambda \I$ is not an isomorphism. By (a), it must be 0. So $\phi = \lambda \I$.

Characters

Given a representation $(V, \rho)$, we define an associated character $\chi_V:G \to \C$ given by $\chi_V(g) = \Tr[\rho(g)]$.

Now we've gone full circle and come back to $\C[G]$.

Note: $\chi_V$ is constant on conjugacy classes of $G$.

\[ \chi_V(hgh^{-1}) = \Tr[\rho(hgh^{-1})] = \Tr[\rho(h)\rho(g)\rho(h^{-1})] = \Tr[\rho(g)\rho(h^{-1})\rho(h)] = \Tr[\rho(g)] = \chi_V(g) \]
A class function is a function on $G$ that is constant on conjugacy classes.

So we can also think the characters are complex-valued class functions.

There's a very nice theorem about the inner products of characters.

$\inrp {\chi_V} {\chi_W} = \dim \Hom_G(V, W)$

I don't have time to prove this at the moment. It's not too hard, though.

For irreps $E, F$, we have \[ \inrp {\chi_E} {\chi_F} = \begin{cases} 1 & E \cong F\\0 & \text{otherwise}\end{cases} \]

Therefore, the characters of irreps are an orthonormal subset of the group algebra.

Fact: the number of irreducible representations of $G$ is the same as the number of conjugacy classes of $G$. Therefore, characters of irreps form a basis for the space of class functions on $G$.

If $G$ is abelian, the characters of irreps form an orthonormal basis for $\C[G]$.

Example: $\C[\Z/n\Z]$

Recall that $\C[\Z/n\Z] = \C[x]/(x^n-1)$, the ring of polynomials modulo $(x^n-1)$. What do these look like in the irreducible character basis?

What are the irreps of $\Z/n\Z$?

Irreducible representations of abelian groups are 1-dimensional.
Let $(E, \rho)$ be an irrep of an abelian group $G$. Fix $g \in G$. For every $h \in G$, $\rho(g)\rho(h) = \rho(gh) = \rho(hg) = \rho(h)\rho(g)$. Thus, $\rho(g)$ is a $G$-morphism from $E$ to $E$. By Schur's lemma, it must be a scalar multiple of the identity. This is true for every element of $g$. Therefore, every subspace of $E$ is a subrepresentation. Since $E$ is irreducible, this means that $E$ must have no nontrivial subspaces. So $E$ must be one-dimensional.

Thus, to find the irreps of $\Z/n\Z$, we only have to consider homomorphisms $\phi : \Z/n\Z \to \Aut[\C] = \C \setminus \{0\}$. Since $\Z/n\Z$ is cyclic, these homomorphisms are determined by $\phi(1)$. Since 1 has order $n$ in $\Z/n\Z$, $\phi(1)$ must be an $n$th root of unity. Let $\omega$ be a primitive $n$th root of unity. Then for all $k = 0, \ldots, n-1$ we get a homomorphism $\phi_k : \Z/n\Z \to \C$ given by $\phi_k(1) = \omega^k$. Since we have found $n$ irreducible representations, we have them all. Since the representations are all 1-dimensional, these are also the irreducible characters.

We can express a function on $\Z/n\Z$ in the character basis by taking its inner products with the irreducible characters. \[ \inrp {\phi_k} f = \sum_{\ell=0}^{n-1} \phi_k(\ell) \overline{f(\ell)} = \sum_{\ell=0}^{n-1} \overline{f(\ell)} \omega^{\ell k}\] Recall, we expressed these functions $f$ as $f = \sum_{\ell = 0}^{n-1} f(\ell) x^{\ell}$. So this is essentially evaluating the polynomial on $\omega^k$. This also looks a lot like the Fourier transform. In fact, it is the Discrete Fourier Transform.

If we write the function as a column vector, we can express this operation by the matrix \[ \begin{pmatrix} 1 & 1 & 1 & 1 & \cdots & 1\\ 1 & \omega & \omega^2 & \omega^3 & \cdots & \omega^{n-1}\\ 1 & \omega^2 & \omega^4 & \omega^6 & \cdots & \omega^{2(n-1)}\\ 1 & \omega^3 & \omega^6 & \omega^9 & \cdots & \omega^{3(n-1)}\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & \omega^{n-1} & \omega^{2(n-1)} & \omega^{3(n-1)} & \cdots & \omega^{(n-1)(n-1)} \end{pmatrix} \begin{pmatrix} \overline{f(0)}\\ \overline{f(1)}\\ \overline{f(2)}\\ \overline{f(3)}\\ \vdots\\ \overline{f(n-1)} \end{pmatrix} \] It turns out that because this matrix is so regularly-structured, we can compute this matrix-vector product really quickly. The Fast Fourier Transform lets us compute this in $O(n \log n)$ time, which is must faster than the naive $O(n^2)$ time for regular matrix-vector products. The Fast Fourier Transform has applications all over CS. It's used in signal processing, data compression (e.g. image processing), solving PDEs, multiplying polynomials, multiplying integers, and convolution, among other things.

18 comments:

  1. I will share it with my other friends as the information is really very useful. Keep sharing your excellent work.Buy Hgh Online USA

    ReplyDelete
  2. Thank you because you have been willing to share information with us. we will always appreciate all you have done here because I know you are very concerned with our. Sandy Hook Parent

    ReplyDelete
  3. The post is written in very a good manner and it contains many useful information for me.I high appreciate this post. It’s hard to find the good from the bad sometimes, but I think you’ve nailed it! would you mind updating your blog with more information I admit, I have not been on this web page in a long time... however it was another joy to see It is such an important topic and ignored by so many, even professionals. I thank you to help making people more aware of possible issues.Same day COVID 19 Test in Houston

    ReplyDelete
  4. I’ve been searching for some decent stuff on the subject and haven't had any luck up until this point, You just got a new biggest fan!.. 릴게임

    ReplyDelete
  5. I really loved reading your blog. It was very well authored and easy to understand. Unlike other blogs I have read which are really not that good.Thanks alot! 먹튀검증

    ReplyDelete
  6. Cool stuff you have got and you keep update all of us. test bank nursing

    ReplyDelete
  7. Thankyou for this wondrous post, I am glad I observed this website on yahoo. 먹튀검증

    ReplyDelete
  8. Yes, I am entirely agreed with this article, and I just want say that this article is very helpful and enlightening. I also have some precious piece of concerned info !!!!!!Thanks. 온라인바둑이

    ReplyDelete
  9. Impressive web site, Distinguished feedback that I can tackle. Im moving forward and may apply to my current job as a pet sitter, which is very enjoyable, but I need to additional expand. Regards. jostoto

    ReplyDelete
  10. This is very educational content and written well for a change. It's nice to see that some people still understand how to write a quality post! FORMULÁŘ ŽÁDOSTI O VÍZA USA

    ReplyDelete
  11. An interesting discussion may be worth comment. I do think that you simply write on this topic, it will not certainly be a taboo subject but normally consumers are insufficient to communicate on such topics. To a higher. Cheers
    Government jobs in 2022

    ReplyDelete
  12. Welcome to the future! Financing made easy with Prof. Mrs. DOROTHY JEAN INVESTMENTS

    Hello, Have you been looking for financing options for your new business plans, Are you seeking for a loan to expand your existing business, Do you find yourself in a bit of trouble with unpaid bills and you don’t know which way to go or where to turn to? Have you been turned down by your banks? MRS. DOROTHY JEAN INVESTMENTS says YES when your banks say NO. Contact us as we offer financial services at a low and affordable interest rate of 2% for long and short term loans. Interested applicants should contact us for further loan acquisition procedures via profdorothyinvestments@gmail.com

    We invest in all profitable projects with cryptocurrencies. I'm here to share an amazing life changing opportunity with you. its called Bitcoin / Forex trading options, Are you interested in earning a consistent income through binary/forex trade? or crypto currency trading. An investment of $100 or $200 can get you a return of $2,840 in 7 days of trading and you get to do this from the comfort of your home/work. It goes on and on The higher the investment, the higher the profits. Your investment is safe and secured and payouts assured 100%. if you wish to know more about investing in Cryptocurrency and earn daily, weekly OR Monthly in trading on bitcoin or any cryptocurrency and want a successful trade without losing Contact MRS.DOROTHY JEAN INVESTMENTS profdorothyinvestments@gmail.com

    categories of investment

    Cryptocurrency
    Loan Offer
    Mining Plan
    Business Finance Plan
    Binary option Trade Plan
    Forex trade Plan
    Stocks market Trade Plan
    Return on investment (ROI) Plan
    Gold and Silver Trade Plan
    Oil and Gas Trade Plan
    Diamond Trade Plan
    Agriculture Trade Plan
    Real Estate Trade Plan

    YOURS IN SERVICE
    Mrs. Dorothy Pilkenton Jean
    Financial Advisor on Bank Instruments,
    Private Banking and Client Services
    Email Address: profdorothyinvestments@gmail.com
    Operation: We provide Financial Service Such As Bank Instrument
    From AA Rate Banks, Cash Loan,BG,SBLC,BOND,PPP,MTN,TRADING,FUNDING MONETIZING etc.

    ReplyDelete
  13. Tonton drama adaptasi novel Risik Pada Hati Full Episod karya Hanni Ramsul dibintangi oleh Alif Satar, Ummi Nazeera dan Zara Zyaa akan menemui penonton di slot Akasia TV3

    ReplyDelete
  14. Many Malaysians have pivoted their focus to new hobbies and online entertainment. Streaming services are all the rage during the pandemic and it’s becoming a staple in many Malaysian households. Kepala Episod

    ReplyDelete
  15. First, you need to get a formal education. Although you can technically become an interior designer without a degree, it will be difficult to find work without one. There are plenty of schools that offer interior design programs, so do your research and find one that’s right for you. How to become an interior designer

    ReplyDelete
  16. Dramacool Watch drama asian Online for free releases in all asian countires with English subtitles on Dramacool

    ReplyDelete

Powered by Blogger.