# Does the Fourier matrix $F_n$ represent a (tensor) multiplicative function?

At "Complex Hadamard Matrices", I found that, two Kronecker (tensor) products of Fourier matrices $k_1$ and $k_2$ are equivalent, if and only if $k_2$ can be obtained from $k_1$ by a combination of an arbitrary number of operations from the set:

• changing the order of Kronecker product factors,
• replacing a subproduct $F_{m(k)}⊗F_{m(k+1)}$ by the factor $F_{m(k)⋅m(k+1)}$ only if $m(k)$ and $m(k+1)$ are relatively prime,
• replacing a factor $F_{ab}$ by the subproduct $F_a⊗F_b$ only if $a$ and $b$ are relatively prime [Ta05].

Especially the last two bullets reminded me to what I've read here "Multiplicative function":

In number theory, a multiplicative function is an arithmetic function $f(n)$ of the positive integer $n$ with the property that $f(1) = 1$ and whenever $a$ and $b$ are coprime, then $$f(ab) = f(a)\cdot f(b).$$

My Question:

Since $F_1=1$, does this mean that the Fourier matrix $F_n$ represents kind of a (tensor) multiplicative function?

-
Oog - I believe there's a sense in which this is true (and that this decomposition even leads to the classic FFT algorithms) but it's been far too long since I've looked at this. Hopefully someone can come along with a more complete answer, but this is at least a tentative 'yes' comment. :-) – Steven Stadnicki Aug 26 '13 at 18:48