# Fourier transform matrices

1. Apr 30, 2014

### jmomo

1. The problem statement, all variables and given/known data
(i) Verify that 5 is a primitive 4th root of unity in F13.
(ii) Let F be the 4x4 matrix whose (i, j)th entry is 5ij in F13 for i, j = 0,1,2, 3.
Compute F(hat) and verify that F(hat)F= I.

2. Relevant equations
The matrix F(hat) is called the inverse discrete Fourier transform of F.

3. The attempt at a solution
I have already solved part (i):
Since 52 = 15 = -1 (mod 13) and 54 = (-1)2 = 1 (mod 13), we conclude that 5 is a primitive 4th root of unity in F13.

But I do not know how to obtain matrix F for part (ii), but I understand that F(hat) is the inverse matrix of F, so if I can find matrix F then I can easily solve for matrix F(hat). If someone can please help me out I'd really appreciate it.

2. Apr 30, 2014

### LCKurtz

For those of us not familiar with this area and your notation, you need to give us definitions.

1. What is $F_{13}$? I'm guessing integers mod 13?

2. What does $5_{ij}$ mean?

3. What is the definition of $\hat F$?

3. Apr 30, 2014

### Zondrina

$F$ is defined as the Discrete Fourier Transform, it looks like this:

http://gyazo.com/8d9c1acfec21ff3a180cc0b94d43e706

Notice the entries $(ω)$ are just the e'th root of primitive unity raised to powers.

Also $\hat F$ is defined as the Inverse Discrete Fourier Transform. It satisfies $F^{-1} = \frac{1}{e} \hat F$ where the entries in $\hat F$ happen to be the inverses of the entries in $F$.

4. Apr 30, 2014

### jmomo

1. F_13 is a field of 13 elements.

2. My apologies, I meant to write 5^(ij).

3. I already defined that above. The matrix F(hat) is called the inverse discrete Fourier transform of matrix F.

5. Apr 30, 2014

### Zondrina

Start by writing down $F$. It shouldn't be too difficult to find $\hat F$ afterwards.

6. Apr 30, 2014

### jmomo

That was my original question stated above. I do not understand how to write down F and wanted to see if anyone knew how to come up with the matrix for F so then I can easily obtain F(hat).

7. Apr 30, 2014

### Zondrina

I posted it in my post above, but here it is again:

http://gyazo.com/8d9c1acfec21ff3a180cc0b94d43e706

Now, the question wants you to compute each matrix entry, namely:

$(5^{i \space \times \space j}) \mod 13$ for $i, j = 0, 1, 2, 3$.

What do $i$ and $j$ equal for the first row, first column entry in your matrix?

Now how about the first row, second column entry? Second row, first column?

Etc. Notice $5$ is the 4th primitive root of unity.