Hola,
En cuanto a lo primero, la eliminación gaussiana es en sí un algoritmo de complejidad \( \mathcal{O}(n^{3}) \) que llevará mediante una serie de transformaciones \( P_{1},\ldots ,P_{m} \) tu matriz a la identidad (por ser inversible), es decir, \( P_{1}\cdots P_{m}A=Id_{n} \)
En el segundo, \( AX=B \), si escalonas A tienes un sistema de ecuaciones sencillito.
Un saludo!