using PyPlot, LinearAlgebra

A = [ 2 -1  0  0  0  0 -1
     -1  2 -1  0  0  0  0
      0 -1  2 -1  0  0  0
      0  0 -1  2 -1  0  0
      0  0  0 -1  2 -1  0
      0  0  0  0 -1  2 -1
     -1  0  0  0  0 -1  2]

eigvals(A)

ω₇ = exp(2π*im / 7)

ω₇ = cis(2π / 7)

fig = figure()
#@manipulate for n in slider(1:20, value=7)
for n in 1:6
    ω = exp(2π*im/n)
    display(
    withfig(fig) do
        for j = 1:n
            z = ω ^ j
            plot([0,real(z)], [0,imag(z)], ls="solid", color=(1,.7,.7))
            plot(real(z), imag(z), "ro")
            text(real(z), imag(z), "\$\\omega_{$n}^{$j}\$")
        end
        axis("square")
        grid()
        xlabel("real part")
        ylabel("imaginary part")
        title("$n-th roots of unity")
        xlim(-1.2,1.2)
        ylim(-1.2,1.2)
    end
    )
end

# define a function to create the n×n matrix F for any n:
F(n) = [exp((2π*im/n)*j*k) for j=0:n-1, k=0:n-1]

round.(F(4))

round.(inv(F(7)) * A * F(7), digits=3) # F⁻¹AF = Λ, rounded to 3 digits

eigvals(A)

diag(inv(F(7)) * A * F(7)) # diagonal entries

F(7) * A[:,1] # DFT of first row/column of A

eigvals(A)

round.(F(7)' * F(7), digits=3)

using FFTW

fft(A[:,1]) # computes the same thing as F(7) * A[:,1], but much faster