For matrices, how to deduce $AB$ using $A^2, B^2, (A+B)^2$ and so on (any matrix squares)? Assume matrix square can be calculated in $O(n^c)$ time, show that any square matrix multiplication can be done in the same $O(n^c)$ time.
The problem I got is that $AB$ and $BA$ always occur together with same coefficients. So that I cannot get $AB$ only.
Thanks in advance and any suggestion is welcomed.
 A: You cannot recover $AB$ from the values of $A^2, B^2$ and $(A+B)^2$. For instance, suppose
$$
A=\pmatrix{1\\ &-1},
\ B=\pmatrix{1&x\\ &-1}.
$$
Then $AB$ depends on $x$ but $A^2=B^2=I$ and $(A+B)^2=4I$ are constant matrices.
Edit. Incidentally, WolframAlpha does not seem to compute $(A+B)^2$ correctly. I don't know why.
A: Thanks for the help.
I got inspired from a "step-by-step" question here (Q4 c).
We can first argue that since matrix multiplication needs to handle at least $n^2$ numbers, therefore it is at least of order $O(n^2)$, that is, $c≥2$.
Then for any $n*n$ matrices $A$ and $B$, let $X, Y$ be two $2n*2n$ matrices, such:
$$X=\left[\begin{array}{l}A&0\\0&0\end{array}\right], Y=\left[\begin{array}{l}0&B\\0&0\end{array}\right]$$
Then we have 
$$XY + YX = \left[\begin{array}{l}0&AB\\0&0\end{array}\right]$$
Combined with that
$$(X+Y)^2-X^2-Y^2 = XY + YX$$
We can get $AB$ using three squares: $A+B, A$ and $B$. 
Since it cost $O(n^c)$ to multiply two $n*n$ matrices, it takes $(2*n)^c=2^c*n^c$ to calculate either of $XY + YX, X^2$ and $ Y^2$. 
Hence in total, this method is of $O(n^c)$.
A: The question asked by the OP -at least the part in the TITLE- is interesting (Unfortunately, his answer is not...). user1551 , using an ad hoc couple $(A,B)$, showed that, generally speaking, $AB$ cannot be recovered. Yet, generically, it seems to me that we can recover $AB$ and even more.
Consider generic matrices $A_0,B_0$ (for example, randomly choose them) and give, to a solver, the matrices $A_0^2,B_0^2,(A_0+B_0)^2$. Then, numerical simulations seem to show that the system $X^2=A_0^2,Y^2=B_0^2,(X+Y)^2=(A_0+B_0)^2$ has only two solutions: $(A_0,B_0)$ and $(-A_0,-B_0)$. In particular, $A_0B_0$ can be recovered; it remains to prove it...
EDIT. Answer to @ Tianchi Cai. Def: Let $(a_{ij})_{ij},(b_{ij})_{ij}$ be independent commuting indeterminates over $\mathbb{Q}$; in other words, the $(a_{ij})_{ij},(b_{ij})_{ij}$are elements of transcendental extension of $\mathbb{Q}$ and they are mutually transcendental over $\mathbb{Q}$. Then the matrices $A,B$ are called "generic matrices" over $\mathbb{Q}$.
In particular, $A,B$ have distinct non-zero eigenvalues in the algebraic closure $K$ of $\mathbb{Q}((a_{ij})_{ij},(b_{ij})_{ij})$, $AB\not= BA$, $A,B$ have no common eigenvectors,...
