-3
$\begingroup$

My question: What is the dimension of the Fourier transform for $S_5$?

My effort:

The dimensions of the seven irreps of $S_5$ are $1,1,4,4,5,5,6$. According to the notes of Andrew Childs, the Fourier transform is a unitary transformation from the group algebra, $\mathbb{C} S_5$,to a complex vector space whose basis vectors correspond to matrix elements of the irreps of $S_5$, $\oplus_{\sigma \in \hat{S_5}} \left(\mathbb{C}^{d_\sigma} \otimes \mathbb{C}^{d_\sigma}\right)$. Here the complete set of irreps of $S_5$ (which are unique up to isomorphism) is $\hat{S_5}$. We expand the direct sum of the irreps here.

$$ \oplus_{\sigma \in \hat{S_5}} \left(\mathbb{C}^{d_\sigma} \otimes \mathbb{C}^{d_\sigma}\right) = \left(\mathbb{C}^{d_{\sigma_1}} \otimes \mathbb{C}^{d_{\sigma_1}}\right) \oplus \left(\mathbb{C}^{d_{\sigma_2}} \otimes \mathbb{C}^{d_{\sigma_2}}\right) \oplus \left(\mathbb{C}^{d_{\sigma_3}} \otimes \mathbb{C}^{d_{\sigma_3}}\right) \oplus \left(\mathbb{C}^{d_{\sigma_4}} \otimes \mathbb{C}^{d_{\sigma_4}}\right) \oplus \left(\mathbb{C}^{d_{\sigma_5}} \otimes \mathbb{C}^{d_{\sigma_5}}\right) \oplus \left(\mathbb{C}^{d_{\sigma_6}} \otimes \mathbb{C}^{d_{\sigma_6}}\right) \oplus \left(\mathbb{C}^{d_{\sigma_7}} \otimes \mathbb{C}^{d_{\sigma_7}}\right)\\ = \left(\mathbb{C}^1 \otimes \mathbb{C}^1\right) \oplus \left(\mathbb{C}^1 \otimes \mathbb{C}^1\right) \oplus \left(\mathbb{C}^4 \otimes \mathbb{C}^4\right) \oplus \left(\mathbb{C}^4 \otimes \mathbb{C}^4\right) \oplus \left(\mathbb{C}^5 \otimes \mathbb{C}^5\right) \oplus \left(\mathbb{C}^5 \otimes \mathbb{C}^5\right) \oplus \left(\mathbb{C}^6 \otimes \mathbb{C}^6\right) $$

So, the direct sum is a $26 \times 26$ matrix. The shape of the direct sum is:

$$ \begin{pmatrix} (1) & (0) & (0) & (0) & (0) & (0) & (0) \\ (0) & (1) & (0) & (0) & (0) & (0) & (0) \\ (0) & (0) & (4) & (0) & (0) & (0) & (0) \\ (0) & (0) & (0) & (4) & (0) & (0) & (0) \\ (0) & (0) & (0) & (0) & (5) & (0) & (0) \\ (0) & (0) & (0) & (0) & (0) & (5) & (0) \\ (0) & (0) & (0) & (0) & (0) & (0) & (6) \end{pmatrix} $$

Here $(i)$ is an $i \times i$ matrix.

According to the note there is one basis vector for each matrix element. So, there are $26^2 = 676$ basis vectors. The Fourier transform will also be a $26 \times 26$ matrix.

Am I doing it right?

$\endgroup$

closed as off-topic by Kaveh, R B, David Eppstein, András Salamon, Joshua Grochow Dec 16 '15 at 4:43

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kaveh, R B, David Eppstein, András Salamon, Joshua Grochow
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ It would be nice if someone could explain why I am getting negative vote. $\endgroup$ – Omar Shehab Dec 7 '15 at 22:46
  • 6
    $\begingroup$ No, you're doing it wrong. You need to use the identity $120 = 1^2 + 1^2 + 4^2 + 4^2 + 5^2 + 5^2 + 6^2$. The group algebra $\mathbb{C}S_5$ has dimension 120, so the dimension of the Hilbert space of the Fourier transform is also 120. You get 676 because you're assuming that all matrix elements are basis vectors. They're not. $\endgroup$ – Peter Shor Dec 7 '15 at 23:05
  • $\begingroup$ @PeterShor, which matrix elements in the direct sum should not be considered for basis vectors? $\endgroup$ – Omar Shehab Dec 8 '15 at 4:14
  • 4
    $\begingroup$ You should ask this kind of question on math.stackexchange.com. You seem to have a basic misunderstanding of what a direct sum of vector spaces is. $\endgroup$ – Sasho Nikolov Dec 8 '15 at 15:19
  • $\begingroup$ I think I understand what I did wrong. $\endgroup$ – Omar Shehab Dec 9 '15 at 2:27
5
$\begingroup$

A quantum Fourier transform is a unitary operation, so the number of basis states of the input and output must be the same.

The number of basis states before the Fourier transform is 120, the number of group elements.

The number of basis states after the Fourier transform is 120, in this case broken up according to the identity $$ 120=1^2+1^2+4^2+4^2+5^2+5^2+6^2. $$ This is because there are seven irreducible representations of $S_5$, which have dimensions $1$, $1$, $4$, $4$, $5$, $5$, and $6$. The Fourier transform of $S_5$ can be represented as the direct sum of $7$ matrices, where the matrix corresponding to an irrep of dimension $d$ has size $d \times d$. You can take the basis states of the output of the Fourier transform to be all the elements of these 7 matrices.

In fact, if the dimensions of the irreps of a finite group are $d_1$, $d_2$, $\ldots$, $d_k$, the identity $$ |G| = \sum_{j=1}^k d_j^2 $$ holds in general, and the basis states of the output of the Fourier transform can be taken to be matrix elements corresponding to an irrep.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.