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.
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
- Any nonzero morphism between two irreps is an isomorphism.
- Any nonzero morphism from an irrep to itself is an isomorphism.
- 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.
- 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
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) \]So we can also think the characters are complex-valued class functions.
There's a very nice theorem about the inner products of characters.
I don't have time to prove this at the moment. It's not too hard, though.
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$.
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$?
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.
I will share it with my other friends as the information is really very useful. Keep sharing your excellent work.Buy Hgh Online USA
ReplyDeleteThank 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
ReplyDeleteThe 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
ReplyDeleteI’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!.. 릴게임
ReplyDeleteI 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! 먹튀검증
ReplyDeleteCool stuff you have got and you keep update all of us. test bank nursing
ReplyDeleteThankyou for this wondrous post, I am glad I observed this website on yahoo. 먹튀검증
ReplyDeletethanks this is good blog. 먹튀검증
ReplyDeleteYes, 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. 온라인바둑이
ReplyDeleteImpressive 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
ReplyDeleteThis 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
ReplyDeleteAn 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
ReplyDeleteGovernment jobs in 2022
Government jobs in KPK
ReplyDeleteWelcome to the future! Financing made easy with Prof. Mrs. DOROTHY JEAN INVESTMENTS
ReplyDeleteHello, 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.
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
ReplyDeleteMany 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
ReplyDeleteFirst, 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
ReplyDeleteDramacool Watch drama asian Online for free releases in all asian countires with English subtitles on Dramacool
ReplyDelete