Para matrices, ¿cómo deducir$AB$ usando$A^2, B^2, (A+B)^2$ y así sucesivamente (cualquier matriz cuadrada)?

Question

Supongamos que el cuadrado de la matriz se puede calcular en$O(n^c)$ de tiempo, mostrar que cualquier multiplicación de matriz cuadrada se puede hacer en el mismo$O(n^c)$ de tiempo.

El problema que tengo es que$AB$ y$BA$ siempre ocurren junto con los mismos coeficientes. Entonces, no puedo obtener$AB$ solamente.

Gracias de antemano y cualquier sugerencia es bienvenida.

Answer 1

No puede recuperar$AB$ de los valores de$A^2, B^2$ y$(A+B)^2$. Por ejemplo, supongamos $$ A = \ pmatrix {1 \\ & -1}, \ B = \ pmatrix {1 & x \\ & -1}. $$ Entonces$AB$ depende de$x$ pero$A^2=B^2=I$ y$(A+B)^2=4I$ son matrices constantes.

Editar. Por cierto, WolframAlpha no parece calcular$(A+B)^2$ correctamente . No sé por qué.

Answer 2

Gracias por la ayuda.

Recibí la inspiración de un "paso a paso" la pregunta aquí (T4 c).

Lo primero que se puede argumentar que, dado que la multiplicación de la matriz de necesidades para controlar al menos $n^2$ números, por lo tanto es, al menos, de la orden de $O(n^2)$, $c≥2$.

Entonces para cualquier $n*n$ matrices $A$$B$, vamos a $X, Y$ dos $2n*2n$ matrices: $$X=\left[\begin{array}{l}A&0\\0&0\end{array}\right], Y=\left[\begin{array}{l}0&B\\0&0\end{array}\right]$$

Entonces tenemos $$XY + YX = \left[\begin{array}{l}0&AB\\0&0\end{array}\right]$$ Combinado con que

$$(X+Y)^2-X^2-Y^2 = XY + YX$$

Podemos obtener $AB$ mediante el uso de tres plazas: $A+B, A$$B$.

Ya que el coste $O(n^c)$ para multiplicar dos $n*n$ matrices, se tarda $(2*n)^c=2^c*n^c$, para calcular cualquiera de $XY + YX, X^2$$ Y^2$.

Por lo tanto, en total, este método es de $O(n^c)$.

Answer 3

La pregunta por el OP-al menos la parte en el TÍTULO - es interesante (por Desgracia, su respuesta es no...). user1551 , el uso de un ad hoc par $(A,B)$, mostraron que, en general, $AB$ no puede ser recuperado. Sin embargo, de forma genérica, a mí me parece que podemos recuperar $AB$ e incluso más.

Considere la posibilidad genérica de las matrices de $A_0,B_0$ (por ejemplo, elegir al azar) y dar, a un solver, las matrices $A_0^2,B_0^2,(A_0+B_0)^2$. Entonces, simulaciones numéricas parecen mostrar que el sistema de $X^2=A_0^2,Y^2=B_0^2,(X+Y)^2=(A_0+B_0)^2$ sólo tiene dos soluciones: $(A_0,B_0)$$(-A_0,-B_0)$. En particular, $A_0B_0$ puede ser recuperado; permanece para demostrarlo...