Unit singular value conjecture for discrete Fourier transform submatrix

Question

This question was motivated by Singular value decomposition of truncated discrete Fourier transform matrix

Consider for integers $1\leq k\leq N$, $1\leq n_0\leq N-k+1$ the $k\times k$ sub-unitary matrix $W(N,k,n_0)$ with elements $$[W(N,k,n_0)]_{nm}=N^{-1/2}e^{2\pi i(n-1)(m-1)/N},\;\;n_0\leq n,m\leq n_0+k-1.$$ This is a principal submatrix of the unitary discrete Fourier transform matrix $W(N,N,1)$. It is sub-unitary, so its singular values lie in the interval $[0,1]$.

Conjecture: A total of $\max(2k-N,0)$ singular values are precisely equal to 1.

I have not found this statement in the literature (cited here), which focuses on the accumulation of $k^2/N$ singular values near unity. Can one provide a proof of the conjecture?

_{Evidence for the conjecture follows from small-$N$ cases I examined, for example, the singular values squared of
$W(8,6,1)$ equal $\left\{1,1,1,1,\frac{1}{8} \left(\sqrt{\sqrt{2}+2}+2\right),\frac{1}{8} \left(2-\sqrt{\sqrt{2}+2}\right)\right\}$, and those of
$W(8,5,2)$ equal $\left\{1,1,\frac{1}{16} \left(\sqrt{16 \sqrt{2}+25}+7\right),\frac{1}{4},\frac{1}{16} \left(7-\sqrt{16 \sqrt{2}+25}\right)\right\}$, while those of
$W(8,4,3)$ equal $\left\{\frac{1}{4} \left(\sqrt{\sqrt{\sqrt{3}+2}+2}+2\right),\frac{1}{8} \left(\sqrt{2 \left(\sqrt{2}-\sqrt{6}+4\right)}+4\right),\frac{1}{8} \left(4-\sqrt{2 \left(\sqrt{2}-\sqrt{6}+4\right)}\right),\frac{1}{4} \left(2-\sqrt{\sqrt{\sqrt{3}+2}+2}\right)\right\}$.}

Answer 1

The conjecture is true. Moreover we show that if $W(N,N,1)$ is replaced by any unitary $N \times N$ matrix then $\max(2k-N,0)$ is still a lower bound on the multiplicity, and is usually sharp (though for $k<N$ there are easy exceptions such as the $N \times N$ identity matrix).

First observe that if $T$ is any "sub-unitary" matrix (i.e. $|Tv| \leq |v|$ for all $v$) then the vectors $v$ such that $|Tv| = |v|$ form a vector space whose dimension is the multiplicity of $1$ as a singular value of $T$. Indeed that multiplicity is the dimension of the $1$-eigenspace of $T^* T$; but if $T^* T v = v$ then $|Tv|^2 = (Tv,Tv) = (v, T^* T v) = |v|^2$, and conversely if $|v| = |Tv|$ then $|v|^2 = (v, T^* T v) \leq \left|v\right| \left|T^*T v\right| \leq |v|^2$ (since $\|T^* T\| \leq 1$), with equality only if $T^* T v = v$.

Now suppose $T$ is obtained as the principal $k \times k$ minor of an $N \times N$ unitary matrix $U$. Then for any $v \in {\bf C}^k$ we find $Tv$ by padding $v$ by $N-k$ zeros to a vector $\bar v \in {\bf C}^n$, applying $U$, and discarding the last $N-k$ entries of the result $U \bar v$. Therefore $|Tv| \leq |v|$ with equality if and only if $U\bar v$ is supported on the first $k$ coordinates. This identifies the space $\{ v : |Tv| = |v| \}$ with the kernel of the $k \times (N-k)$ submatrix of $U$ formed by intersecting the first $k$ rows with the last $N-k$ columns. Since this submatrix has rank at most $\min(N-k,k)$, its kernel has dimension at least $\max(2k-N,0)$.

In the special case that $U$ is the matrix of the discrete Fourier transform, any square submatrix supported on the first $m$ rows or the first $m$ columns is a Vandermonde matrix or its transpose, and is thus nonsingular. Therefore our $k \times (N-k)$ submatrix has a nonsingular square submatrix of order $\min(N-k,k)$. Hence it attains the upper bound $\min(N-k,k)$ on the rank of a $k \times (N-k)$ matrix, and the singular value $1$ has the lowest possible multiplicity $\max(2k-N,0)$, QED.

To show that this holds for "typical" unitary $U$, we need only observe that $m \times n$ matrices of rank $\min(m,n)$ form a nonempty open subset of the space of $m \times n$ matrices. Hence unitary matrices $U$ whose relevant $k \times (N-k)$ submatrix satisfies this condition form the preimage of an open set under a continuous map, and therefore constitute an open subset of the group ${\rm U}_N$ of unitary matrices. This open subset is nonempty because it contains the discrete Fourier transform, and is thus dense because ${\rm U}_N$ is connected.