How ill-conditioned can submatrices of the Fourier matrix be?

The discrete Fourier transform matrix is one of the most important matrices in linear algebra, and submatrices of it arise in a variety of applications. Though the discrete Fourier transform matrix is unitary, its submatrices can be exponentially ill-conditioned, an obstacle to accurate computation. This work resolves the exact rate of the exponential ill-conditioning for square submatrices with contiguous rows and columns. As a consequence, we obtain a tight upper bound of $2 G/π$ on the exponential rate for all submatrices with contiguous columns, where $G$ is Catalan's constant. These results follow from a more general analysis of Vandermonde and Vandermonde-like matrices for which similarly tight bounds are developed.

Source: arXiv:2604.15135v1 - http://arxiv.org/abs/2604.15135v1 PDF: https://arxiv.org/pdf/2604.15135v1 Original Link: http://arxiv.org/abs/2604.15135v1