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

<p>The number of basis states before the Fourier transform is 120, the number of group elements. </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-12-15T18:52:07.910Z
2015-12-15T19:39:36.727Z
2015-12-15T19:39:36.727Z
Peter Shor 
<p><strong>My question:</strong>
What is the dimension of the Fourier transform for $S_5$?</p>

<p><strong>My effort:</strong></p>

<p>The dimensions of the seven irreps of $S_5$ are $1,1,4,4,5,5,6$. According to the <a href="http://www.cs.umd.edu/~amchilds/teaching/w13/l06.pdf" rel="nofollow">notes</a> 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.</p>

<p>$$
\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)
$$</p>

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

<p>$$
\begin{pmatrix}
(1) &amp; (0) &amp; (0) &amp; (0) &amp; (0) &amp; (0) &amp; (0) \\
(0) &amp; (1) &amp; (0) &amp; (0) &amp; (0) &amp; (0) &amp; (0) \\
(0) &amp; (0) &amp; (4) &amp; (0) &amp; (0) &amp; (0) &amp; (0) \\
(0) &amp; (0) &amp; (0) &amp; (4) &amp; (0) &amp; (0) &amp; (0) \\
(0) &amp; (0) &amp; (0) &amp; (0) &amp; (5) &amp; (0) &amp; (0) \\
(0) &amp; (0) &amp; (0) &amp; (0) &amp; (0) &amp; (5) &amp; (0) \\
(0) &amp; (0) &amp; (0) &amp; (0) &amp; (0) &amp; (0) &amp; (6) 
\end{pmatrix}
$$</p>

<p>Here $(i)$ is an $i \times i$ matrix.</p>

<p>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.</p>

<p><strong>Am I doing it right?</strong></p>

CC BY-SA 3.0
2015-12-07T22:46:59.793Z
It would be nice if someone could explain why I am getting negative vote.
Omar Shehab
CC BY-SA 3.0
2015-12-07T23:05:40.600Z
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.
Peter Shor 
CC BY-SA 3.0
2015-12-08T04:14:41.980Z
@PeterShor, which matrix elements in the direct sum should not be considered for basis vectors?
Omar Shehab
CC BY-SA 3.0
2015-12-08T15:19:34.093Z
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.
Sasho Nikolov
CC BY-SA 3.0
2015-12-09T02:27:20.057Z
I think I understand what I did wrong.
Omar Shehab
<quantum-computing><quantum-information><physics><gr.group-theory><fourier-analysis>
Dimension of the Fourier transform for $S_5$
Omar Shehab
# Dimension of the Fourier transform for $S_5$

(Asked by: username_0 on 2015-12-07)

**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](http://www.cs.umd.edu/~amchilds/teaching/w13/l06.pdf) 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?**

**Tags:** quantum-computing, quantum-information, physics, gr.group-theory, fourier-analysis
> **Comments:**
> **username_0**: It would be nice if someone could explain why I am getting negative vote.  
> **username_1**: 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.  
> **username_0**: @PeterShor, which matrix elements in the direct sum should not be considered for basis vectors?  
> **username_2**: 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.  
> **username_0**: I think I understand what I did wrong.  

---

## 1 answers

### Answer by username_1 on 2015-12-15. Score: 5 | Accepted answer

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.


---

