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.