Module 10: Linear Combinations of Other Objects

We'll start with a little re-writing, in a more convenient form:

• Although we used the notation $f(j)$ to indicate a function on the integers $j$, we will rename the numbers $$f(0),f(1),\ldots, f(j),\ldots,f(N-1)$$ to $$f_0,f_1,\ldots, f_j,\ldots,f_{N-1}$$

• Then, for notational symmetry, we'll rename the coefficients $$c_0^\prime, c_1^\prime, \ldots, c_{N-1}^\prime$$ to $$F_0, F_1, \ldots, F_{N-1}$$ so that the sum can be written $$f_j \eql \sum_{n=0}^{N-1} F_n e^{\frac{2\pi i nj}{N}}$$

• Now, because we allow the $F_n$'s to be complex, we must, for symmetry, let the $f_j$'s be complex as well.
        $\rhd$ This is because a complex linear combation can end up being complex.
  • In practice, of course, actual data is real-valued.
  • We can always write the real number $x$ as the complex number $x + i0$.
  • We will in fact get complex "data" when we change the $F_n$'s to achieve some goal (like noise removal).
  • So, henceforth, we'll assume that the $f_j$'s (the data) are complex.

• Next, use the symbol $\omega$ to denote the complex number $$\omega \eql e^{\frac{2\pi i}{N}}$$

• With this slight change in notation, the linear combinations become (one for each $f_j$): $$f_j \eql \sum_{n=0}^{N-1} F_n \omega^{nj}$$

  In-Class Exercise 11: Suppose $N=4$. Write out the unfolded sum for $f_3$.

• Notice that each $f_j$ is a linear combination of numbers (complex numbers).

• However, all our theory so far has been developed for:
  • Linear combinations of vectors
  • Linear combinations of functions (polynomials).

• One possibility: extend the theory to make it work for numbers.

  In-Class Exercise 12: What would the theory look like for this extension to linear combinations of numbers? Explore the meaning of span, independence, basis, dimension in this context.

• Let's try putting the numbers into vectors to see if we can make that work.

• The data can be put into a vector quite easily: $${\bf f} \eql \vecfour{f_0}{f_1}{\vdots}{f_{N-1}}$$

• Next, let's write the linear combinations for each $f_j$ one below another: $$\eqb{ f_0 & \eql & \sum_{n=0}^{N-1} F_n \omega^{n\times 0} & \eql & F_0 + F_1 + F_2 + + F_3 + \ldots + F_{N-1} \\ f_1 & \eql & \sum_{n=0}^{N-1} F_n \omega^{n\times 1} & \eql & F_0 + F_1 \omega^1 + F_2 \omega^2 + F_3 \omega^3 + \ldots + F_{N-1} \omega^{N-1} \\ f_2 & \eql & \sum_{n=0}^{N-1} F_n \omega^{n\times 2} & \eql & F_0 + F_1 \omega^{2} + F_2 \omega^4 + F_3 \omega^6 + \ldots + F_{N-1} \omega^{2(N-1)} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ f_{N-1} & \eql & \sum_{n=0}^{N-1} F_n \omega^{n\times (N-1)} & \eql & F_0 + F_1 \omega^{N-1} + F_2 \omega^{2(N-1)} + F_3 \omega^{3(N-1)} + \ldots + F_{N-1} \omega^{(N-1)(N-1)} }$$

  In-Class Exercise 13: Fill in the equation for $f_3$ above.

• Clearly, this is the same as $$\mat{f_0 \\ f_1 \\ f_2 \\ \vdots \\ f_{N-1} } \eql F_0 \mat{ 1 \\ 1 \\ 1 \\ \vdots \\ 1} + F_1 \mat{ 1 \\ \omega \\ \omega^2 \\ \vdots \\ \omega^{N-1}} + F_2 \mat{ 1 \\ \omega^2 \\ \omega^4 \\ \vdots \\ \omega^{2(N-1)}} + \ldots + F_{N-1} \mat{ 1 \\ \omega^{N-1} \\ \omega^{2(N-1)} \\ \vdots \\ \omega^{(N-1)(N-1)}}$$ (Think of the above as equations in the $F_k$ variables.)

• Let's name the vectors above: $${\bf d}_0 \eql \mat{ 1 \\ 1 \\ 1 \\ \vdots \\ 1} \;\;\;\;\;\; {\bf d}_1 \eql \mat{ 1 \\ \omega \\ \omega^2 \\ \vdots \\ \omega^{N-1}} \;\;\;\;\;\; {\bf d}_2 \eql \mat{ 1 \\ \omega^2 \\ \omega^4 \\ \vdots \\ \omega^{2(N-1)}} \;\;\;\;\;\; \ldots \;\;\;\;\;\; {\bf d}_{N-1} \eql \mat{ 1 \\ \omega^{N-1} \\ \omega^{2(N-1)} \\ \vdots \\ \omega^{(N-1)(N-1)}}$$

  In-Class Exercise 14: Write out the elements of ${\bf d}_3$.

• We've now expressed the (complex) data vector ${\bf f}$ as a linear combination of the (complex) vectors ${\bf d}_n$: $${\bf f} \eql F_0 {\bf d}_0 + F_1 {\bf d}_1 + F_2 {\bf d}_2 + F_3 {\bf d}_3 + \ldots + F_{N-1} {\bf d}_{N-1}$$

• We now cannot resist the urge to put these vectors into a matrix (as columns, of course). Define $${\bf D} \eql \mat{ 1 & 1 & 1 & \vdots & 1 \\ 1 & \omega & \omega^2 & \vdots & \omega^{N-1} \\ 1 & \omega^2 & \omega^4 & \vdots & \omega^{2(N-1)} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 1 & \omega^{N-1} & \omega^{2(N-1)} & \ldots & \omega^{(N-1)(N-1)} }$$

  In-Class Exercise 15: What is the fourth column of ${\bf D}$?

• With which the linear combination of vectors can now be written as $${\bf f} \eql {\bf D} {\bf F}$$ where ${\bf F}$ is the vector $${\bf F} \eql \vecfour{F_0}{F_1}{\vdots}{F_{N-1}}$$

• Or, when expanded out: $$\mat{f_0 \\ f_1 \\ f_2 \\ \vdots \\ f_{N-1} } \eql \mat{ 1 & 1 & 1 & \vdots & 1 \\ 1 & \omega & \omega^2 & \vdots & \omega^{N-1} \\ 1 & \omega^2 & \omega^4 & \vdots & \omega^{2(N-1)} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 1 & \omega^{N-1} & \omega^{2(N-1)} & \ldots & \omega^{(N-1)(N-1)} } \mat{F_0 \\ F_1 \\ F_2 \\ \vdots \\ F_{N-1} }$$

• In which case, if ${\bf D}^{-1}$ exists, $${\bf F} \eql {\bf D}^{-1} {\bf f}$$

• Terminology:
  • The computation of ${\bf F} = {\bf D}^{-1} {\bf f}$ is called the Discrete Fourier Transform (DFT).
  • Going the other way, ${\bf f} = {\bf D} {\bf F}$ is called the Inverse Discrete Fourier Transform (I-DFT).

• More terminology:
  • The matrix ${\bf D}^{-1}$ is called the DFT matrix.
  • The matrix ${\bf D}$ is called the inverse-DFT matrix.

Let's step back for a moment and summarize:

• We started with a function $f(t)$ and its Fourier representation $$f(t) \eql \sum_{n=-\infty}^{\infty} c_n e^{\frac{2\pi i n t}{T}}$$

• Two reasons led us to discretization:
  • The computation of the coefficients is complicated and inefficient.
  • Actual data in applications tends to be discrete
          $\rhd$ Example: sound is sampled in digital form.

• Then, with $N$ discrete data or a function discretized at $N$ points, we have $N$ values (numbers): $f(0),f(1),f(2),\ldots, f(N-1)$.

• We showed that, because of the properties of sine's and cosine's the discretized infinite linear combination becomes finite $$f(j) \eql \sum_{n=0}^{N-1} c_n^\prime e^{\frac{2\pi i nj}{N}}$$ which we rewrote (change of notation) as: $$f_j \eql \sum_{n=0}^{N-1} F_n \omega^{nj}$$

• Let's write out the equation for each $j$: $$\eqb{ f_0 & \eql & \sum_{n=0}^{N-1} F_n \omega^{n\times 0} & \eql & F_0 + F_1 + F_2 + + F_3 + \ldots + F_{N-1} \\ f_1 & \eql & \sum_{n=0}^{N-1} F_n \omega^{n\times 1} & \eql & F_0 + F_1 \omega^1 + F_2 \omega^2 + F_3 \omega^3 + \ldots + F_{N-1} \omega^{N-1} \\ f_2 & \eql & \sum_{n=0}^{N-1} F_n \omega^{n\times 2} & \eql & F_0 + F_1 \omega^{2} + F_2 \omega^4 + F_3 \omega^6 + \ldots + F_{N-1} \omega^{2(N-1)} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ f_{N-1} & \eql & \sum_{n=0}^{N-1} F_n \omega^{n\times (N-1)} & \eql & F_0 + F_1 \omega^{N-1} + F_2 \omega^{2(N-1)} + F_3 \omega^{3(N-1)} + \ldots + F_{N-1} \omega^{(N-1)(N-1)} }$$

• Then, we put this in vector form $${\bf f} \eql F_0 {\bf d}_0 + F_1 {\bf d}_1 + F_2 {\bf d}_2 + F_3 {\bf d}_3 + \ldots + F_{N-1} {\bf d}_{N-1}$$ with the understanding that ${\bf f}$ is the data in complex form (zero imaginary part).

• This expresses a complex vector as a linear combination of the special vectors $${\bf d}_0 \eql \mat{ 1 \\ 1 \\ 1 \\ \vdots \\ 1} \;\;\;\;\;\; {\bf d}_1 \eql \mat{ 1 \\ \omega \\ \omega^2 \\ \vdots \\ \omega^{N-1}} \;\;\;\;\;\; {\bf d}_2 \eql \mat{ 1 \\ \omega^2 \\ \omega^4 \\ \vdots \\ \omega^{2(N-1)}} \;\;\;\;\;\; \ldots \;\;\;\;\;\; {\bf d}_{N-1} \eql \mat{ 1 \\ \omega^{N-1} \\ \omega^{2(N-1)} \\ \vdots \\ \omega^{(N-1)(N-1)}}$$

We are now led to some burning questions:

• Are the special vectors ${\bf d}_0,{\bf d}_1,\ldots,{\bf d}_{N-1}$ independent?

• Do they form a basis? A basis for what space?

• How do we compute the coefficients ${\bf F}=(F_0,F_1,\ldots,F_{N-1})$?

• Why are we doing all this? Why is this useful?

Let's look into some of these questions next.