# Morgenstern proof for FFT lower bound

I looked at my notes from a class about fast forier transform , and the professor proved in class theorem thanks to Morgenstern , first he defined linear algorithm as a algorithm that inly uses multiplications by scalar and addtions, that he stated Morgenstern's theorem the following way

Every linear algorithm that computes DFT (Discrete Fourier Transform) , in which the scalar are bounded in their absolute value by $C$ , takes at least $\Omega_C(n\log{n})$ addition operations.

I haven't understood his proof , if someone can give me guidlines to the proof I'll be more than happy :) [right now my proof of the theorem looks like a mess]

p.s.: In class he said we will write in each step the coeffiecents of the linear function that was just computed , then he defined a "computation advancment function" , I didn't understand his definition of this function , it was definied something like $\phi(k)=$ maximum determinant of n$\times$n matrices that were computed untill the k'th step [I probably copied wrong]

• The problem lies in the following two facts: I literally couldn't understand what I wrote in my notebook(The proffesor went really fast) I nned the proof from class because I am scribing a class including this theorem.(it was the last class so no one except me wrote at that time) I am not asking for proof but I haven't undertood the start of the proof , maybe after understanding what he meant when he defined the computation advancment function it would be clearer how to prove this theorem – UserB95 Feb 19 '15 at 0:00
• I ask for guidelines not proof because few lines confused me , and I don't have the intution for why the theorem is correct. – UserB95 Feb 19 '15 at 0:00
• A source where the proof is readible will be also super :) [I haven't found one] – UserB95 Feb 19 '15 at 0:06

Morgenstern first defines the notion of a linear algorithm. A linear algorithm gets as input $x_1,\ldots,x_n$ and its goal is to compute some $y_1,\ldots,y_m$, each of which is a (specific) linear combination of $x_i$s. The algorithm proceeds in steps, starting with step $n+1$. At step $t$, the algorithm computes $x_t = \lambda_t x_i + \mu_t x_j$ for some $i,j < t$. At the end of the computation, for each $i$, $y_i = x_j$ for some $j$.

For example, here is an algorithm computing the unnormalized DFT on 2 variables: $$x_3 \gets x_1 + x_2 \\ x_4 \gets x_1 - x_2$$ Similarly, the unnormalized two dimensional DFT on $2^2$ variables is computed by: $$x_5 \gets x_1 + x_2 \\ x_6 \gets x_1 - x_2 \\ x_7 \gets x_3 + x_4 \\ x_8 \gets x_3 - x_4 \\ x_9 \gets x_5 + x_7 \\ x_{10} \gets x_5 - x_7 \\ x_{11} \gets x_6 + x_8 \\ x_{12} \gets x_6 - x_8$$

We can view each $x_t$ as an $n$-dimensional vector which gives the linear combination of $x_1,\ldots,x_n$ producing $x_t$; call this vector $v_t$. The vectors $v_1,\ldots,v_n$ are just the $n$ basis vectors.

Morgenstern defines the quantity $\Delta_t$, which is the maximum magnitude of the determinant of any square submatrix of the matrix $V_t$ whose rows are $v_1,\ldots,v_t$.

Lemma. Let $c \geq 1/2$. If $|\lambda_s|,|\mu_s| \leq c$ for all $s$ then $\Delta_{n+t} \leq (2c)^t$.

Proof. The proof is by induction on $t$. When $t = 0$, this is easy to verify directly since $V_n$ is just the identity matrix. Consider now any $t > 0$. Every square submatrix of $V_t$ is either a square submatrix of $V_{t-1}$, in which case its determinant is at most $(2c)^{t-1} \leq (2c)^t$ by induction, or it involves the new row $v_t = \lambda_t v_i + \mu_t v_j$. In the latter case, we can write the square submatrix $A$ as $A = \lambda_t B + \mu_t C$, where $B,C$ are square submatrices of $V_{t-1}$ (replace the relevant part of $v_t$ by the corresponding parts of $v_i$ and $v_j$). Since the determinant is a linear function of any of its rows, $\det(A) = \lambda_t \det(B) + \mu_t(C)$. By induction, $|\det(B)|,|\det(C)| \leq (2c)^{t-1}$, and so $$|\det(A)| \leq |\lambda_t| |\det(B)| + |\mu_t| |\det(C)| \leq c(2c)^{t-1} + c(2c)^{t-1} = (2c)^t.$$

Corollary. Computing the DFT on $n$ variables using a linear algorithm with bounded coefficients requires $\Omega(n\log n)$ steps.

Proof. The determinant of the DFT matrix is $n^{n/2}$. Hence any linear algorithm computing the DFT in $t$ steps satisfies $\Delta_t \geq n^{n/2}$. If the bound on the coefficients is $c$, then the lemma shows that $(2c)^t \geq n^{n/2}$ and so $t = \Omega(n\log n)$.

Remark. Strassen has shown that any algebraic algorithm (algorithm involving $+,-,\cdot,/$) for computing the DFT can be transformed to a linear algorithm using the same number of steps.

Morganstern's original paper is here:

Jacques Morgenstern. Note on a lower bound on the linear complexity of the fast Fourier transform. J. ACM, 20(2):305–306, April 1973.

• I do't have access to this – UserB95 Feb 19 '15 at 7:29