# Understanding Matrix Formula with Scant Knowledge of Linear Algebra

$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})$

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?

2. 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?

3. 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.

-
Please limit your use of boldface to only the necessary. –  Arturo Magidin May 22 '12 at 23:42
If you want to understand this material, you really do need to know some linear algebra. I think it would be a very good idea for you to study linear algebra. You'll find it has many other applications in computer science as well. –  Robert Israel May 23 '12 at 0:21

Though I know that you urged answerers to keep the math language to a minimum, in this case I think that knowledge of math language is the issue. Probably googling for the words in bold below will help.

1. If you look up the term $\textbf{matrix multiplication}$, this question will likely be cleared up. The author is saying that if you multiply a matrix $M$ by the $k$th standard basis vector (in this case a matrix with one column and $n$ rows, where are rows are $0$ except for the $k$th row which has a $1$ in it), the answer is exactly the $k$th column of the matrix $M$.

2. Here the term to look up is $\textbf{basis}$. The author is using the fact that since the columns of $M$ are orthogonal, they are $\textbf{linearly independent}$. Since there are $n$ columns, that means the columns form a basis for $n$-dimensional space. What the author is saying is that every vector can be written as a $\textbf{linear combination}$ of the columns of $M$.

3. The "Fourier basis" is just what is described in item 3 above. To write a vector in the Forier basis is to say how to write it as a linear combination of the columns of $M$.

-
Oops, I just realized that matrix multiplication was indeed the title of your question... –  James May 22 '12 at 23:40
Thank You James! –  user26649 May 23 '12 at 1:58

I'll just take on part of point number 2.

There is no inherent sense of length and angle and other geometric concepts in spaces of dimension greater than 3, so we define those concepts in such a way as to extend the properties that are familiar from 2 and 3 dimensions. In particular, we define the length of a vector $\bf v$, denoted by $\|{\bf v}\|$, by $$\|{\bf v}\|=\sqrt{{\bf v}\cdot{\bf v}}$$ and we define the angle $\theta$ between vectors $\bf v$ and $\bf w$ by $${\bf v}\cdot{\bf w}=\|{\bf v}\|\|{\bf w}\|\cos\theta,\qquad0\le\theta\le\pi$$ By these definitions, saying two vectors meet at a right angle is the same thing as saying their dot product is zero.

-