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"?
 A: 
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.
A: 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.)
A: 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$.
A: 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)$$
A: 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.
A: 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.
