Rank-deficient submatrices of Kronecker products of Fourier matrices Original Research Article

We provide a set of maximal rank-deficient submatrices of a Kronecker product of two matrices Acircle times operatorB, and in particular the Kronecker product of Fourier matrices F=Fn1circle times operatorcdots, three dots, centeredcircle times operatorFnk. We show how in the latter case, maximal rank-deficient submatrices can be constructed as tilings of rank-one blocks. Several such tilings may be associated to any subgroup of the Abelian group image that corresponds to the matrix F. The maximal rank-deficient submatrices of F are also related to an uncertainty principle for Fourier transforms over finite Abelian groups, for which we can then obtain stronger versions.