Encontrar un vector ortogonal de un subespacio

Question

Suponga que usted estuviera dado de vectores $a_1,\dots,a_n \in \mathbb{R}^m$, entonces ¿cómo podría usted calcular el vector ortogonal a la lista de vectores? Tenga en cuenta que se le permite regresar el vector cero sólo si los vectores span $\mathbb{R}^m$.

Pensé en ello durante un tiempo, y el mejor que podía hacer era formar la matriz con estos vectores como filas y escoger un vector a partir de la nullspace. Hay una forma más fácil y más rápido? Tal vez algo geométricas como de Gram-Schmidt podría ser posible.

Gracias!

Answer 1

Aquí está el algoritmo determinista.

Deje $A$ $m \times n$ matriz de sus vectores $$A = \pmatrix{a_0 & a_1 & \cdots & a_n}$$ Uso de la factorización QR de la misma $$A = QR$$ de modo que el P de la matriz contendrá todo el espacio nulo usted está buscando: $$A = \pmatrix{Q_1 & Q_2}\pmatrix{R_1 \\ 0}$$ Desde $Q$ es ortonormales $$\pmatrix{Q_1^\top \\ Q_2^\top}A = \pmatrix{R_1 \\ 0}$$ Para especificar completamente el espacio nulo, se puede ver aquí que es $Q_2$ $$Q_2^\top A = 0$$

Answer 2

Esta es una muy buena ocasión para aplicar el teorema fundamental del álgebra lineal en relación a los cuatro subespacios fundamentales de una matriz. (La pregunta correctamente contestada por muzzlator ya, me acaba de añadir una explicación más detallada a continuación y espero que sea útil para algunas personas.)

En primer lugar, el uso de $a_1,\dots,a_n \in \mathbb{R}^m$ para formar un $m\times n$ matriz $A$, con cada vector como una columna de la matriz. La dimensión de la columna en el espacio de $A$ es designado como $r$, el número de vectores linealmente independientes entre vectores $a_j, (j=1\dots n)$, e $r$ es también el rango de $A$. Entonces el problema de encontrar alguna vector ortogonal a $a_1,\dots, a_n$ es equivalente a encontrar la solución en la "izquierda nullspace" de $A$, designado como $N(A^T)$, por la solución de la siguiente ecuación:

$$A^T x = 0.$$

$A^T$ $n\times m$ , y la dimensión de $N(A^T) = m-r$. (En realidad, lo que encontramos aquí es el complemento ortogonal de la original subespacio. Esto es mucho mejor que encontrar sólo algunos vectores ortogonales.) Si el original de la lista de vectores span $\mathbb{R}^m$, significa que el rango de $A$ es igual a $m$, y la dimensión de la izquierda nullspace es $m-r = m-m =0$. Así que, en este caso, la única solución (el ortogonal del vector) es el vector cero, $(0,\dots, 0)$.

Eliminación de Gauss (para obtener la forma escalonada de la matriz) es el método para encontrar la solución a $A^Tx=0$. Por otro lado, las bacterias Gram-Schmidt es el proceso para construir una normalizado ortogonal ("ortonormales") después de que han encontrado los vectores en $N(A^T)$.

En tu post, estás en lo correcto uso de los vectores como las filas de una matriz, por lo que no es necesario transponer la matriz para encontrar la respuesta. (Personalmente prefiero mantener la matriz como un $m\times n$ matriz tanto como sea posible.)

Answer 3

No debería ser, de hecho, de una manera más rápida. Esto es porque Elementales de fila operaciones no cambian la fila de espacio a la hora de resolver $A^T x = 0$. Usted ha descrito a sí mismo como habiendo ya hecho esto, pero no tenemos que resolver todo el nullspace encontrar algo en ella (a menos que usted ya no está haciendo esto?).

Aquí es un pensamiento, empezar con cualquier no-vector cero y encontrar un valor distinto de cero componente. Eliminar ese componente en todos los demás vectores (teóricamente). Elija cualquier otro componente, si todos los demás vectores (después de la reducción de la fila) tiene un $0$, $(-a_2, a_1, \dots, 0)$ es ortogonal a sus vectores. De lo contrario, repita este proceso en el más pequeño de la matriz producida por la primera entrada distinto de cero que ver. Si $m \leq n$ y este proceso no finaliza después de $m$ se comprueban los componentes, no es sólo la solución trivial. Si $n < m$ y el algoritmo no finaliza después de $n$ se comprueban los componentes, a continuación, calcular $e_{n+1} \cdot a_i$ por cada $i$ y el uso de esta para producir un vector ortogonal por la elección de las coordenadas pertinentes en el primer $n+1$ artículos.

Esto significa un total de $\frac{\min\{m,n\}^2}{2} + m \max\{n-m, 0\}$ de las operaciones son más o menos es todo lo que necesita en el peor.