defect


defect of a Kronecker product of Fourier matrices


Let $F=F_{N_1}\otimes...\otimes F_{N_r}$ be a Kronecker product of Fourier matrices (KpFm) of the total size $N=N_1\cdot...\cdot N_r$, where $$F_N=\left[\exp\frac{i2\pi\cdot jk}{N}\right]_{j,k=0,...,N-1}.$$ Then $D$$(F)$ is equal to the number of $1$'s sitting in $F$ and $d$$(F)$ is the number of $1$'s in the core of $F$. It follows from the fact that $F_{j,k}$'s are the eigenvalues of $\mathcal{J}_{{\small \frac{1}{\sqrt{N}}}F}$.

For example, for

$$F_2\otimes F_2 = \left[\begin{array}{rr}1&1\\1&-1\end{array}\right]\otimes \left[\begin{array}{rr}1&1\\1&-1\end{array}\right]= \left[\begin{array}{rrrr} 1& 1& 1& 1\\ 1&-1& 1&-1\\ 1& 1&-1&-1\\ 1&-1&-1&1 \end{array}\right]$$

we have $D$$(F_2\otimes F_2)=10$   $1$'s in $F_2\otimes F_2$ and $d$$(F_2\otimes F_2)=3$   $1$'s in its core.

If $F_1$ and $F_2$ are KpFm's such that their sizes are relatively prime, then $D$$(F_1\otimes F_2)=$ $D$$(F_1)$ $D$$(F_2)$.

$D$$(F)$ for $F=F_{N_1}\otimes...\otimes F_{N_r}$ of the total size $N=N_1\cdot...\cdot N_r$ can be calculated as:

$$D(F)=\sum_{i\in I_F}\frac{N}{{\rm ord}_{I_F}(i)},$$

where $I_F=\mathbb{Z}_{N_1}\times...\times\mathbb{Z}_{N_r}$ is the associated group and ${\rm ord}_{I_F}(i)$ denotes the order of $i$ in $I_F$.

If $F$ is of size $a^k$ for $a$ prime, then $D$$(F)$ is divided by $a^{k-1}$ and $d$$(F)$ is divided by $(a-1)^2$. Besides $D$$(F_a)=2a-1$ and $d$$(F_a)=0$.

For more details see sec. 4 in [143], sec. 5 in [125] and sec. 5 in [140].