Conjetura del valor singular unitario para la submatriz de la transformada discreta de Fourier

Question

Esta pregunta fue motivada por Descomposición del valor singular de la matriz de la transformada discreta de Fourier truncada

Considere para los enteros $1\leq k\leq N$ , $1\leq n_0\leq N-k+1$ el $k\times k$ matriz subunitaria $W(N,k,n_0)$ con elementos $$[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.$$ Se trata de una submatriz principal del unitario matriz de la transformada discreta de Fourier $W(N,N,1)$ . Es subunitaria, por lo que sus valores singulares se encuentran en el intervalo $[0,1]$ .

Conjetura: Un total de $\max(2k-N,0)$ los valores singulares son precisamente iguales a 1.

No he encontrado esta afirmación en la literatura (citada ici ), que se centra en la acumulación de $k^2/N$ valores singulares cerca de unidad. ¿Se puede aportar una prueba de la conjetura?

_{Las pruebas de la conjetura se desprenden de las pequeñas <span class="math-container">$N$</span> casos que examiné, por ejemplo, los valores singulares al cuadrado de<br><span class="math-container">$W(8,6,1)$</span> igual <span class="math-container">$\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}$</span> y los de<br><span class="math-container">$W(8,5,2)$</span> igual <span class="math-container">$\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}$</span> mientras que los de<br><span class="math-container">$W(8,4,3)$</span> igual <span class="math-container">$\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}$</span> .}

Answer 1

La conjetura es cierta. Además, demostramos que si $W(N,N,1)$ se sustituye por cualquier unidad $N \times N$ matriz entonces $\max(2k-N,0)$ sigue siendo un límite inferior de la multiplicidad, y suele ser agudo (aunque para $k<N$ hay excepciones fáciles como la $N \times N$ matriz de identidad).

En primer lugar, observe que si $T$ es cualquier matriz "subunitaria" (es decir $|Tv| \leq |v|$ para todos $v$ ) entonces los vectores $v$ tal que $|Tv| = |v|$ forman un espacio vectorial cuya dimensión es la multiplicidad de $1$ como valor singular de $T$ . En efecto, esa multiplicidad es la dimensión del $1$ -eigenspace de $T^* T$ ; pero si $T^* T v = v$ entonces $|Tv|^2 = (Tv,Tv) = (v, T^* T v) = |v|^2$ , y a la inversa, si $|v| = |Tv|$ entonces $|v|^2 = (v, T^* T v) \leq \left|v\right| \left|T^*T v\right| \leq |v|^2$ (ya que $\|T^* T\| \leq 1$ ), con igualdad sólo si $T^* T v = v$ .

Supongamos ahora que $T$ se obtiene como el principal $k \times k$ menor de un $N \times N$ matriz unitaria $U$ . Entonces, para cualquier $v \in {\bf C}^k$ encontramos $Tv$ por relleno $v$ por $N-k$ ceros a un vector $\bar v \in {\bf C}^n$ , aplicando $U$ y descartando el último $N-k$ entradas del resultado $U \bar v$ . Por lo tanto, $|Tv| \leq |v|$ con igualdad si y sólo si $U\bar v$ es compatible con el primer $k$ coordenadas. Esto identifica el espacio $\{ v : |Tv| = |v| \}$ con el núcleo de la $k \times (N-k)$ submatriz de $U$ formada por la intersección de la primera $k$ filas con el último $N-k$ columnas. Como esta submatriz tiene un rango máximo de $\min(N-k,k)$ , su núcleo tiene una dimensión de al menos $\max(2k-N,0)$ .

En el caso especial de que $U$ es la matriz de la transformada discreta de Fourier, cualquier submatriz cuadrada apoyada en la primera $m$ filas o la primera $m$ columnas es una matriz de Vandermonde o su transpuesta, y por lo tanto es no singular. Por lo tanto, nuestra $k \times (N-k)$ tiene una submatriz cuadrada no singular de orden $\min(N-k,k)$ . Por lo tanto, alcanza el límite superior $\min(N-k,k)$ en el rango de un $k \times (N-k)$ y el valor singular $1$ tiene la menor multiplicidad posible $\max(2k-N,0)$ , QED .

Para demostrar que esto es válido para los unitarios "típicos" $U$ sólo tenemos que observar que $m \times n$ matrices de rango $\min(m,n)$ forman un subconjunto abierto no vacío de el espacio de $m \times n$ matrices. Por lo tanto, las matrices unitarias $U$ cuyo correspondiente $k \times (N-k)$ submatriz satisface esta condición forma la preimagen de un conjunto abierto bajo un mapa continuo, y por tanto constituyen un subconjunto abierto del grupo ${\rm U}_N$ de matrices unitarias. Este subconjunto abierto no es vacío porque contiene la transformada discreta de de Fourier discreta, y por tanto es denso porque ${\rm U}_N$ está conectado.