Classical Matrix-Vector multiplication Complexity of standard matrices
Essentially, your are asking why people believe that DFT or DHT do not have linear size arithmetic circuits. First, researcher tried to find such circuits for decades but did not succeed. Second, there are superlinear lower bounds (Morgenstern's theorem, see the book by Bürgisser, Clausen, Shokrollahi) in restricted models. From Morgenstern's theorem, in follows that in linear arithmetic circuits of linear size over the complex numbers  for the DFT, the absolute values of the constants used in the circuit go to infinity as $n$ goes to infinity.