The spark of Fourier matrices: Connections to vanishing sums and coprimeness

We consider conditions under which L rows of an N point DFT matrix form a matrix with spark L+1, i.e. a matrix with full spark. A matrix has spark L+1 if all L columns are linearly independent. This has application in compressed sensing for MRI and synthetic aperture radar, where measurements are under sampled Fourier measurements, and the observation matrix comprises certain rows of the DFT matrix. It is known that contiguous rows of the DFT matrix render full spark and that from such a base set one can build a suite of other sets of rows that maintain full spark. We consider an alternative base set of the form {0,1,⋯,K}∖{n}, and derive conditions on K, n and the prime factors of N, under which full spark is retained. We show that such a matrix has full spark iff there are no K distinct N-th roots of unity whose n-products form a vanishing sum, and leverage recent characterizations of vanishing sums of N-th roots of unity to establish the stated conditions.