Computing the matrices for the Number Theoretic Transform

I am familiar with Fourier Transform and computing the DFT and FFT matrix for fast multiplication of integers. However, this is the first time I work with NTT applied to polynomial rings of the form $$\mathbb{Z}_q[x]/x^{n} + 1$$.

Say for small q=5 and $$n$$=2. My elements consists of all polynomials of degree at most $$n-1$$ with coefficients in $$\mathbb{Z}_{q}$$. All arithmetic of coefficients is done in $$\mathbb{Z}_{q}$$.

Now to obtain the $$n$$-th primitive root of unity $$w$$: I can express q = Nk + 1 = 22 + 1. I can let N=2 the NTT sample size and k=2. I let r = 2 (be a primitive root of q). I can compute w as $$w = r^k \pmod{q}= 4 \pmod{5} = 4$$ and confirm $$w^{k} \equiv 1 \pmod{q}$$. $$4^{2} = 16 \pmod{q} = 1$$

First question: this method to obtain $$w$$ is correct?

My 2 by 2 matrix would have this form:

$$\begin{matrix} 1 & 1\\ 1 & w \end{matrix}$$

Now, to consider higher powers of w, say we are working with larger ring and have a 3 by 3 matrix. Let NTT_matrix = $$\begin{matrix} 1 & 1 & 1 \\ 1 & w & w^2 \\ 1 & w^2 & w^3 \\ \end{matrix}$$

Second question: to compute the backward matrix, Let NTT_inv_matrix =

$$\begin{matrix} 1 & 1 & 1 \\ 1 & w & w^{-2} \\ 1 & w^{-2} & w^{-3} \\ \end{matrix}$$

multiplied by $$N^{-1}$$.

To compute the negative powers of $$w$$, I can just take multiplicative inverse of the corresponding element in the forward matrix and multiply them by $$N^{-1}$$ (the multiplicative inverse of the sample size $$N$$)?

So for example, say I have this entry in the forward matrix: $$w^3 = 4^3 \pmod{5} = 64 \pmod{5} = 4$$ The corresponding element in the backward matrix would be $$w^-3$$. To compute it, is the same as $$(w^{3})^{-1}\pmod{5}$$? in this case the multiplicative inverse, MI, of $$w^3\pmod{5}$$ would also be 4 since $$4*4 \equiv 1 \pmod{5}$$. And the MI(N) in mod 5 is 3 since $$3*2 \equiv 1 \pmod{5}$$. So then, to compute $$w^{-3} = MI(w^{3})*MI(N) = 4 * 3 = 12 \pmod{5} = 2$$?

Third question: So after I populate both matrices, I can multiply polynomials a(x) and b(x) by taking their coefficient tuples. For each polynomial, I proceed as follows: If a(x) = x + 3 = (a1=1, a0=3) so its tuple is just v = (1, 3). I can apply transform via matrix-vector multiplication v*NTT_matrix = v. Same for b(x) say I get v2. Then v3 = v`*v2 and finally, answer = NTT_inv_matrix(v3). Correct?

Fourth question: This should give me the same answer as multiplying a(x)b(x) with the standard convolution formula correct ?

Fifth question, to define such a ring $$\mathbb{Z}_q[x]/x^{n} + 1$$, it is required that $$q$$ be prime to ensure a multiplicative inverse for all elements except 0, and also $$x^{n} + 1$$ must be irreducible in $$\pmod{q}$$, correct?

One can take $$q$$ to be nonprime, and use a ring. Under certain conditions this can enable you to evaluate the NTT for more general lengths $$N.$$
The number theoretic transform may be meaningful modulo $$q$$, even when the modulus is not prime, provided a principal root of order $$N$$ exist.
Examples are the Fermat Number Transform with $$q= 2^k+1$$ and Mersenne Number Transform with $$q= 2^k-1$$.