¿Con qué rapidez puedes determinar si los vectores son linealmente independientes?

Question

Supongamos que tiene $m$ vectores de valor real de longitud $n$ donde $n \geq m$ .

¿Con qué rapidez puedes determinar si son linealmente independientes?

En el caso de que $m = n$ Una forma de determinar la independencia sería calcular el determinante de la matriz cuyas filas son los vectores. Intenté buscar en Google y encontré que el algoritmo más conocido para calcular el determinante de una matriz cuadrada con $n$ las filas se ejecutan en $O \left ( n^{2.373} \right )$ . Esto pone un límite superior en el caso de que $m = n$ . Pero calcular el determinante parece una exageración. Además, no resuelve el caso en el que $n > m$ .

¿Existe un algoritmo mejor? ¿Cuál es el límite inferior teórico conocido de la complejidad de dicho algoritmo?

Answer 1

Formación de una matriz $A$ este problema equivale a determinar si $Ax = 0$ tiene soluciones no triviales. Resolver un sistema lineal puede descomponerse en una serie de multiplicaciones de matrices, por lo que siempre tendrá la complejidad del algoritmo de multiplicación de matrices más rápido.

Answer 2

Como dijo Christopher A. Wong esto se reduce a resolver $Ax=0$ y comprobar si hay una solución no trivial. Hay algunos enfoques para hacer esto en el caso $n>m$ . Una forma sería resolverlo encontrando la descomposición LU de $A$ y luego utilizando la sustitución hacia adelante y hacia atrás. Esto puede lograrse en $O(\frac{2}{3}n^3)$ operaciones en coma flotante. También puedes encontrar la descomposición QR de $A$ . Entonces el rango de $A$ será el mismo que el rango de $R$ . Desde $R$ es triangular es fácil ver su rango. Esto se puede lograr en $O(n^3)$ operaciones en coma flotante. Hay muchas formas de implementar la descomposición QR. Si vas a hacerlo, te sugiero que utilices el enfoque de la transformación de Householder, es el más estable numéricamente. Un buen lugar para leer sobre este tema es Fundamentals of Matrix Computations de Watkins.

Answer 3

Siga los siguientes pasos

1. Disponga los vectores en forma de matriz con cada vector representando una columna de la matriz.

2. Vectores de una matriz son siempre linealmente dependientes si el número de columnas es mayor que el número de filas (donde m > n ).

3. Vectores de una matriz con un número de filas mayor o igual que el número de columnas (donde n >= m ) son Linealmente independiente sólo si las operaciones elementales de fila sobre la matriz pueden convertirla en una matriz que contenga sólo Vectores de identidad mutuamente ortogonales (Un Vector de identidad es un Vector que tiene 1 como uno de los componentes y 0 como otros componentes). En caso contrario, los vectores son Dependencia lineal

Por lo tanto, lo único que se necesita es un algoritmo rápido para hacer operaciones de fila elemental en una matriz con n>=m para comprobar si los vectores que contiene pueden convertirse en Vectores de identidad mutuamente ortogonales

Si alguien piensa que esta respuesta es incorrecta, por favor demuéstrelo dando algunos contraejemplos de Matrices.