# How to know if the Fourier Transform is surjective

I am studing if I could modell a function using LUTs (ROMs) for a electronic digital design. I have two functions, a FFT and other function, S. S function system recive as input the output of the FFT system. Due there are 2000*2000 possibles values as input for my FFT system if my FFT is a inyective function then is not a good a idea to try modell S through a LUT because the set of the input of S system would be 2000*2000 and these are so many entries for a ROM in a FPGA, I think so... If FFT is surjective, maybe the 2000*2000 values of the input set of FFT system might be a smaller set of the FFT image, small enough to consider the save the values in a ROM. Thank you!

-
You need to define your domain and range spaces in order to have an appropriate notion of surjectivity. If the domain is $\mathbb{R}^n$, then write the discrete Fourier transform as a matrix operation and look at the properties of the matrix. From that, the answer will be obvious. –  cardinal Mar 17 '11 at 16:57