Elegir una base ortonormal en la que un operador lineal tiene una matriz dispersa

Question

Dado que un operador lineal $T$ en un $n$ -espacio vectorial dimensional $V$ (sobre $ \mathbb R$ ), quiero encontrar una base orthonormal para $V$ en la que la matriz de $T$ es escasos (tiene muchos ceros). ¿Cuántos ceros puedo conseguir?

Formulación equivalente: ¿cuál es el mayor número $k=k(n)$ de tal manera que cada verdadero $n \times n$ La matriz es ortogonalmente equivalente a una matriz con al menos $k$ cero entradas?

---

Actualizado con resultados parciales

1. Ya que el grupo ortogonal $O(n)$ tiene una dimensión $ \frac12 n(n-1)$ se deduce que $$k(n) \le \frac12 n(n-1) \tag {1}$$ De hecho, el conjunto de todas las matrices con $k$ entradas particulares establecidas en $0$ es un $(n^2-k)$ -el espacio vectorial dimensional, de ahí su órbita bajo $A \mapsto O^TAO$ ( $O$ ortogonal) tiene como máximo $n^2-k+ \frac12 n(n-1)$ dimensiones. (La dimensión Hausdorff puede ser usada aquí para hacer esto riguroso.)

2. Por otro lado, el respuesta de Omnomnomnom da un límite inferior $$k(n) \ge \left\lceil \frac12 n(n-2) \right\rceil \tag {2}$$ Queda un hueco aquí. Es fácil ver que $k(2)=0$ (por ejemplo, una rotación genérica del plano tiene una matriz completa en cada base ortonormal), por lo que (2) es agudo en este caso. Para $n=3$ las desigualdades dan $2 \le k(3) \le 3$ ¿Cuál de ellos es afilado?

3. La misma pregunta podría hacerse para las matrices complejas y la equivalencia unitaria. Dejemos que $k_{ \mathbb C}(n)$ denotan el análogo de $k(n)$ para este caso. Ya que la dimensión real de $U(n)$ es $n^2$ se deduce que $$k_{ \mathbb C}(n) \le \left\lfloor \frac12 n^2 \right\rfloor\tag {3}$$ En la dirección opuesta, Omnomnomnom señaló el límite inferior $$k_{ \mathbb C}(n) \ge \frac12 n(n-1) \tag {4}$$ También hay un hueco aquí.

Answer 1

Tenemos $k_{\mathbb{C}}(n)=k(n)=\frac12n(n-1)$ para todos $n > 2$ (para $n=2$ tenemos $k_{\mathbb{C}}(2)=1$ , $k(2)=0$ ).

En primer lugar, mostraré que se trata de límites superiores antes de demostrar que se pueden alcanzar. Utilizaré el hecho de que un mapa suave de un $m$ dimensional (o unión finita de $m$ dimensiones) a una $n$ no puede estar en un colector dimensional a menos que $n\le m$ . En la pregunta se señala que $k(n)\le\frac12n(n-1)$ así que me limitaré a ver el caso complejo. El espacio ${\rm U}(n)$ de $n\times n$ matrices unitarias tiene dimensión $n^2$ y el espacio ${\rm GL}_{\mathbb{C}}(n)$ del complejo $n\times n$ tiene dimensión $2n^2$ . Si $U$ es unitaria tal que $U^HAU$ tiene $k$ cero entradas, entonces $V^HAV$ también tiene $k$ entradas cero, donde $V=DU$ para una matriz unitaria diagonal $D$ . Por ejemplo, siempre es posible elegir $D$ tal que el primer elemento no nulo de cada fila de $V$ es real. Dejar que $R$ sea el espacio de $n\times n$ matrices unitarias cuyo primer elemento no nulo en cada fila es real, esto tiene dimensión $n(n-1)$ . Dejar $S$ sea el $n\times n$ matrices complejas con al menos $k$ cero entradas, esto tiene la dimensión $2(n^2-k)$ . Necesitamos el mapa $R\times S\to {\rm GL}_{\mathbb{C}}(n)$ , $(U,M)\mapsto UMU^H$ para estar en. Así que, $$ {\rm dim}(R\times S)=n(n-1)+2(n^2-k)\ge{\rm dim}(GL_{\mathbb{C}}(n))=2n^2, $$ así que, de nuevo, $k\le\frac12n(n-1)$ .

Ahora, podemos demostrar el límite inferior. En la pregunta se ha observado que $k_{\mathbb{C}}\ge\frac12n(n-1)$ ya que todas las matrices complejas pueden ponerse en forma triangular superior mediante una descomposición de Schur. Por tanto, sólo queda el caso real. Para los enteros positivos $n_1+n_2+\cdots+n_m=n$ podemos expresar un $n\times n$ matriz $A$ en forma de bloque $$ A=\pmatrix{ A_{11} & A_{12} &\cdots&&A_{1m}\\ A_{21}&A_{22}&\cdots&&A_{2m}\\ \vdots&&\ddots&&\vdots\\ \\ A_{m1}&A_{m2}&\cdots&& A_{mm} } $$ donde $A_{ij}$ es un $n_i\times n_j$ matriz real. Tal y como señala Omnomnomnom utilizando la forma real de Schur, sustituyendo entonces $A$ por $Q^TAQ$ para la ortogonalidad $Q$ se puede hacer para que sea triangular superior en bloque ( $A_{ij}=0$ para $i > j$ ) y tal que cada $n_i$ es 1 o 2. Podemos tomar $n_1=n_2=\cdots=n_r=2$ y $n_{r+1}=n_{r+2}=\cdots=n_m=1$ (donde $r\in\{0,1,\ldots,m\}$ es el número de pares conjugados complejos de valores propios de $A$ ). Los términos no nulos por debajo de la diagonal de $A$ corresponden entonces a los siguientes términos diagonales de los elementos diagonales del bloque $A_{ii}$ . Hay $r$ de estos, así que $A$ tiene al menos $\frac12n(n-1)-r$ entradas cero por debajo de la diagonal. No podemos eliminar estos restos $r$ por debajo de las entradas no nulas de la diagonal, pero podemos introducir un $r$ ceros por encima de la diagonal. Obsérvese en primer lugar que si $Q$ es una matriz real en forma de bloque $Q=(Q_{ij})_{i,j=1,\ldots,n}$ con $Q_{ij}=0$ para $i\not=j$ (es decir, diagonal en bloque) con cada $Q_{ii}$ ortogonal, entonces $Q$ es ortogonal. Además, $B=Q^TAQ$ tiene forma de bloque $B=(B_{ij})$ con $B_{ij}=Q_{ii}^TA_{ij}Q_{jj}$ . Así que, $B$ también es triangular superior en bloque.

(1) Para cualquier $k < m$ con $n_k=2$ existe una matriz ortogonal de bloques diagonales $Q$ tal que $B=Q^TAQ$ tiene entradas en bloque $B_{ij}=A_{ij}$ para $i,j\not=k$ y $B_{km}$ tiene una entrada cero.

Para demostrarlo, dejemos que $v\in\mathbb{R}^2$ sea la primera columna de $A_{km}$ y $R$ ser un $2\times2$ matriz de rotación con $R^Tv=(\lVert v\rVert,0)^T$ . Entonces, $R^TA_{km}$ es triangular superior y dejando que $Q$ sea la matriz diagonal de bloques con $Q_{kk}=R$ y todos los demás elementos de la diagonal del bloque son la identidad da el resultado.

Mientras $r < m$ o, de forma equivalente, $A$ tiene al menos un valor propio real, podemos aplicar esto para que $A_{rm}$ tiene una entrada cero, entonces para que $A_{r-1,m}$ tiene una entrada cero, y así sucesivamente para terminar con cada $A_{im}$ teniendo una entrada cero para $i\le r$ . Si $r=m$ o, de forma equivalente, $A$ no tiene valores propios reales, podemos utilizar lo siguiente.

(2) Si $i < j$ es tal que $n_i=n_j=2$ entonces existe una matriz ortogonal de bloques diagonales $Q$ tal que $B=Q^TAQ$ tiene entrada en bloque $B_{ij}$ siendo diagonal.

Por el descomposición del valor singular existe $2\times2$ matrices ortogonales $R,S$ con $R^TA_{ij}S$ siendo diagonal. Entonces, dejando que $Q$ sea la matriz diagonal de bloques con $Q_{ii}=R$ , $Q_{jj}=S$ y todas las demás entradas diagonales son la identidad da el resultado.

Ahora, en el caso de que $n > 2$ y $A$ tiene todos los valores propios complejos (por lo que $r=m\ge2$ ), podemos aplicar (2) para hacer $A_{r-1,r}$ diagonal para que tenga dos entradas nulas. Aplicando iterativamente (1) con $i=r-2,r-3,\ldots$ introduce una entrada cero en cada uno de los bloques $A_{im}$ para $i\le r-2$ . Esto pone $A$ en forma triangular de bloque superior con $r$ ceros por encima de la diagonal.

Answer 2

Con Triangularización de Schur se puede obtener el resultado ligeramente mejorado de $\frac 12 n(n-1)$ entradas nulas en el caso complejo, suponiendo que la matriz tiene exclusivamente valores propios reales.

Para una matriz real con valores propios complejos, siempre podemos poner la matriz en su "forma Schur real", que es una forma "bloque-triangular superior". Es decir, para $A \in \mathbb{R}^{n\times n}$ existe una matriz ortogonal $Q$ para lo cual $$ Q^TAQ = \pmatrix{ A_1 &&&*\\ &A_2&&\\ &&\ddots&\\ 0&&& A_k } $$ Donde cada $A_i$ es $1\times 1$ o un $2\times 2$ matriz real con un par conjugado de valores propios complejos.

Esto significa que para cualquier $A$ siempre podemos elegir una matriz ortogonalmente equivalente con al menos $\frac 12 n(n-1) - n/2 = \frac 12 n(n-2)$ cero entradas, es decir, al menos $\lceil \frac 12 n(n-2) \rceil$ cero entradas.

Espero que le resulte útil.

---

Puede ser posible generalizar su último resultado.

Para cualquier impar $n$ , cualquier $T \in \mathbb{R}^{n\times n}$ debe tener algún vector propio $v_1$ .

Por lo tanto, considere cualquier transformación $A$ con dimensión impar. Podemos escribir $T = Q^TAT$ de la forma anterior, insistiendo en que $A_1$ ser un $1 \times 1$ matriz. Es decir, para algunos $a \in \mathbb{R}$ podemos escribir $$ Q^TAQ = \pmatrix{ a &&&*\\ 0&A_2&&\\ \vdots&&\ddots&\\ 0&0&& A_k } $$ Obsérvese que la primera columna de $Q$ (llámalo $q_1$ ) es un vector propio, y que $a$ es el valor propio correspondiente. Si $T$ es no invertible (lo que es cierto si y sólo si $A$ es invertible), podemos insistir en $a=0$ y tenemos nuestra entrada extra de cero como se desea.

Si $T$ no es invertible, creo que podríamos establecer $v_1 = q_1$ y elegir una nueva base $v_2,\dots,v_n$ cubriendo $P =$ el lapso de $q_2,\dots,q_n$ . Tal vez haya alguna forma de elegir $v_2,\dots,v_n$ para que $v_2 \in P \cap T(P)$ y mantenemos esta forma triangular superior en bloque.

Supongo que es un tema de reflexión.

Answer 3

Aquí hay una prueba de que $k(3)=3$ .

Dejemos que $T:\mathbb R^3\to\mathbb R^3$ sea un operador lineal. Si el núcleo de $T$ no es trivial, elija un vector en el núcleo como uno de los elementos de la base; esto crea $3$ ceros en la matriz ya. Supongamos que $T$ es invertible. Como el espacio es impar-dimensional, $T$ tiene al menos un vector propio (el polinomio característico tiene al menos una raíz real). Sea $v_1$ sea un vector propio normalizado de $T$ . Sea $P$ sea el subespacio bidimensional ortogonal a $v_1$ . Desde $T^{-1}P$ también es bidimensional, la intersección $P\cap T^{-1}P$ contiene una línea. Sea $v_2$ sea un vector unitario en la línea, y observe que $Tv_2 \perp v_1$ . Por último, complete la base con $v_3=v_1\times v_2$ .

En la base $v_1,v_2,v_3$ la matriz de $T$ tiene la forma $$\begin{pmatrix} * & 0 & * \\ 0 & * & * \\ 0 & * & * \end{pmatrix} $$ Así, $k(3)\ge 3$ . La desigualdad inversa se deduce de (1) en la pregunta.

Answer 4

Si todos los valores propios son distintos, entonces la matriz es totalmente diagonalizable por lo que habría $n^2 - n = n(n-1)$ ceros. Si algunos valores propios son idénticos, entonces la matriz es sólo diagonalizable en bloque; si hay $m\le n$ valores propios distintos con $n_1$ a $n_m$ siendo el número de vectores con ese valor propio, entonces los bloques serían $n_i \times n_i$ cuadrados y podríamos garantizar al menos $n^2 - \sum_{i=1}^mn_i^2$ ceros.

Por desgracia, el peor caso para esta línea de razonamiento es cuando todos los valores propios son idénticos. En ese caso no puede demostrar ningún cero en absoluto.

El $k$ -los números que se investigan aquí pueden utilizarse para reforzar el resultado anterior. Dado que la restricción del operador lineal al $i$ El bloque debe seguir teniendo $k(n_i)$ ceros forzados, podemos garantizar al menos $n^2 - \sum_{i=1}^mn_i^2 + \sum_{i=1}^mk(n_i)$ ceros, que será un número mayor si al menos uno $n_i\ge 3$ (para que $k(n_i)>0$ ).

Si pensamos en la matriz real como una matriz compleja, entonces su forma normal de Jordan tendrá como máximo $n$ entradas no nulas en la diagonal y $\sum_{i=1}^m(n_i-1) = n-m$ entradas no nulas en la superdiagonal. Por lo tanto, no obtendríamos más que $2n-m$ entradas no nulas y al menos $n^2 - 2n + m$ ceros. Sin embargo, la JNF de una matriz real no es necesariamente real en sí misma, a menos que todos los valores propios sean también reales, por lo que obtener tantos ceros en el caso general requeriría permitir valores complejos (sólo en la diagonal principal) en la JNF.