$n$ is a power of $2$.
$M =\pmatrix{ 1& x_0 & x_0^2 & \dots &x_0^{n-1}\\\ 1& x_1 & x_1^2 & \dots &x_1^{n-1}\\&& \vdots\\1& x_{n-1} & x_{n-1}^{2} & \dots &x_{n-1}^{n-1}\\}$
$\matrix M$ is the matrix a vector of the coefficient values of a polynomial of degree $n-1$ is multiplied by to get a vector of value representation values of the polynomial. Let $w$ by a complex $n^{th}$ root of unity.
$M_n(w) =\pmatrix{ 1& 1 & 1 & \dots &1\\\ 1& w & w^2 & \dots &w^{n-1}\\1& w^2 & w^4 & \dots &w^{2(n-1)}\\&& \vdots\\1& w^j & w^{2j} & \dots &w^{(n-1)j}\\1& w^{n-1} & w^{2(n-1)} & \dots &w^{(n-1)(n-1)}}$
The $(j,k)^{th}$ entry is $w^{jk}$. Multiplication by $\matrix M = \matrix M_n(w)$ maps the $k^{th}$ coordinate axis (the vector with all zeros except for a $1$ at position $k$) onto the $k^{th}$ column of $M$. The columns of $\matrix M$ are orthogonal to each other. Therefore, they can be thought of as the axes of an alternative coordinate system, which is often called the Fourier Basis. The effect of multiplying a vector by $\matrix M$ by is to rotate it from the standard basis, with the usual set of axes, into the Fourier basis, which is defined by the columns of $M$. The Fast Fourier Transform is thus a change of basis, a rigid rotation. The inverse of $\matrix M$ is the opposite rotation, from the Fourier basis back into the standard basis. When we write out the orthogonality condition precisely, we will be able to read off this inverse transformation with ease:
Inversion Formula: $\matrix M_n(w)^{-1} = \frac{1}{n}\matrix M_n(w^{-1})$
What does the text mean by "Multiplication by $\matrix M = \matrix M_n(w)$ ... onto the $k^{th}$ column of $\matrix M$"? To multiply by the matrix wouldn't you simply use the dot product? What does the $k^{th}$ column have to do with anything?
The columns of $M$ being "orthogonal" doesn't mean they are actually right angled - their dot product just equals $0$. Therefore why is there a relation being made to the literal right angle relation between the axes of a coordinate system? What does a coordinate system have to do with this?
What exactly is the Fourier Basis Coordinate System? Wikipedia only seems to provide info on the Fourier Series.
Please limit math usage to only the necessary - I have almost no knowledge in linear algebra. I am trying to understand the Fast Fourier Transform through a computer science perspective for interpolation from value representation of a polynomial to coefficient representation.