# How is the Fourier transform “linear”?

A "linear" function usually means one who's graph is a straight line, or that involves no powers higher than 1. And yet, many sources will tell you that the Fourier transform is a "linear transform".

Both the discrete and continuous Fourier transforms fundamentally involve the sine and cosine functions. These functions are about as non-linear as you can get. They are transcendental. They are solutions to differential equations. They are infinite-degree polynomials. They have infinity turning points. (So, not straight lines at all.) In the discrete case, you take a finite sum with them, but in the continuous case you compute an integral with them! This all sounds highly non-linear to me...

Then again, apparently "linear" is one of those mathematical terms that has many, many meanings. (Much like "normal" means a few trillion different things depending on the exact context in question.) And perhaps not all of those meanings are actually related.

So, my question is, in which exact sense is the Fourier transform considered "linear"?

-
The answers illustrate this, but you need to get clear in your mind what is linear and what is not. The fourier transform operates on functions. It is not the functions which are linear, but the transform. To use your idea of a line, given two functions $f$ and $g$ you can use the same equation as for a straight line between points: $(1-\lambda)f+\lambda g$ to interpolate between functions. A linear transformation like the fourier transform will respect that in the sense that it doesn't matter whether you do the transformation first or the interpolation first, you get the same result. –  Mark Bennet May 4 '12 at 9:12
There are a lot of mathematical terms that have many, many meanings, but linear is not one of them! In almost every context I have seen it used, a thing $T$ is linear if some analogue of $T(ax+by) = aT(x) + bT(y)$ holds. –  Rahul May 4 '12 at 9:54
Indeed your standard linear functions of the form $f(x) = ax + b$ aren't actually linear at all when $b \ne 0$ (since linear functions map 0 to 0). These straight line functions comprise the more general class of affine transformations –  Conor May 4 '12 at 13:18

Let $f$, $g$ be functions of a real variable and let $F(f)$ and $F(g)$ be their fourier transforms. Then the fourier transform is linear in the sense that, for complex numbers $a$ and $b$,

$$F(af + bg) = a F(f) + b F(g)$$

i.e. it has the same notion of linearity that you may be used to from linear algebra. This is not a quirk - it expresses the fact that functions form an infinite dimensional vector space, with addition and multiplication by a scalar defined in the obvious way:

$$(f+g)(x) = f(x) + g(x)$$ $$(af)(x) = a f(x)$$

-
So a linear combination of functions yields a linear combination of spectrums? Well, I guess that makes sense then... –  MathematicalOrchid May 4 '12 at 9:15

Linear in this context has nothing to do with the geometry of the graphs of functions under consideration. It is used in the sense that the functions themselves form a vector space, i.e., you can add functions and take multiples of a function with a real number. The linearity of the fourier transform means that if you take the transform of a sum of functions, it is the same as the sum of the fourier transforms of the functions, and the same holds for real multiples of functions.

-
More compactly: if $F(t)$ is the Fourier transform of $f(s)$, and $G(t)$ is the transform of $g(s)$, then the Fourier transform of $a\,f(s)+b\,g(s)$ (where $a$ and $b$ are constants) is $a\,F(t)+b\,G(t)$. Note that this is the same behavior as with differentiation and integration; if you know the definition of the Fourier transform as an integral, then the linearity shouldn't be much of a shock. –  Guess who it is. May 4 '12 at 9:02

The Fourier transform is linear as a function whose domain consists of functions, that is, the sum of the Fourier transforms of two functions is the same as the Fourier transform of the sum. Same with scalars. For more information, see Properties of the Fourier transform (Wikipedia).

The term linear is actually fairly consistently used. That is, a transformation $T$ of vector spaces is called linear if $T(ax+by)=aT(x)+bT(y)$ for scalars $a,b$. If you think of things this way, you will see that your favourite linear functions on $\mathbb{R}$ are specific cases of this.

-
+1 for the nice "sum of the transform = transform of the sum" argument –  Joao Tavora May 4 '12 at 9:40

A "linear" function usually means one who's graph is a straight line, or that involves no powers higher than 1.

That isn't the definition of linear, and doesn't really make sense in the context of the Fourier transformation, which is an operation on functions (what would the graph of a function of functions look like?). Instead linearity is defined as follows:

Let $F$ be a field and $V,W$ be vector spaces over $F$. The function $f:V\to W$ is linear if for any $a,b\in F$ and $u,v\in V$, $f(au+bv)=af(u)+bf(v)$.

In this case, the vector spaces are spaces of functions.

-
The concept of "spaces of functions" sounds intriguing... Clearly I must go and research this concept. –  MathematicalOrchid May 4 '12 at 9:16

Note that the discrete version of the Fourier transform can be represented as a matrix applied to a vector to produce another vector. (Moreover, that matrix can be inverted.)

-

While the previous answers correctly made it clear that straight lines are not was defines a linear transformation, it is actually possible to visualise more general linear transformations with such lines. However, you need to come clear about where these lines lie: it has nothing to do with the trigonometric functions' graphs. After all, these functions are just special elements of the domain of the Fourier transform.

What matters is the graph of the transform itself. As was already said, the Fourier transform maps functions to functions, which is considerably more complicated than mapping numbers to numbers. However, functions form a vector space: naïvely, you can write a tuple something like $$\begin{pmatrix} \vdots \\ f(0) \\ f(0.000\ldots0001) \\ f(0.000\ldots0002) \\ \vdots \\ f(1) \\ \vdots \end{pmatrix}$$ of all the function values. Strictly this space is infinite-dimensional, but in many applications you're only interested in some finite range and resolution anyway, making the space finite-dimensional. Still rather too big to visualise, but for the extreme case $n=2$ it's actually almost possible: our "functions" $f(x)$ can now be seen as points in a plane with coordinate $(f(x_1),f(x_2)) =: (f_0,f_1)$. The Fourier transform reduces to just two different modes as well: "in phase" and "anti-phase" or "frequency $0$" and "frequency $1$", i.e. \begin{aligned} F_0 &= \left(\sqrt{\tfrac12},\sqrt{\tfrac12}\right) \\ F_1 &= \left(-\sqrt{\tfrac12},\sqrt{\tfrac12}\right) \end{aligned} That shows already a matrix representation of the (inverse) Fourier transform, and a matrix representation is enough to show that the transformation is linear. But you still don't see the lines, all right...

The graph of this Fourier-transform function (which maps now $\mathbb{R}^2\to\mathbb{R}^2$) lives in $\mathbb{R}^4$. Still a bit bulky that space, but let's look a 3-dimensional subspace: we put in only values where the coefficient of $F_1$ is zero, i.e. the part of the graph we look at consists of triples $$\begin{pmatrix} a_0 \\ a_0\cdot(F_0)_0 + 0 \\ a_0\cdot(F_0)_1 + 0 \end{pmatrix} = \begin{pmatrix} a_0 \\ \sqrt{\tfrac12}a_0 \\ \sqrt{\tfrac12}a_0 \end{pmatrix}$$ and if we follow the path of these points take through $\mathbb{R}^3$ while varying $a_0$ we see – exactly: a straight line, leading away from the origin in an oblique angle!

The actual graph is not a line, but a plane in $\mathbb{R}^4$.

-