Fast change of basis in algebras (Q1205123)

The \(n\)-dimensional algebra \({\mathcal A}\) has basis \({\mathbf b}\). The structure constants relative to a new basis \({\mathbf c}\), with \({\mathbf b}Q={\mathbf c}\), can be computed in \(O(n^ 5)\) arithmetic operations. However, the authors show that the problem can be solved in time \(O(n^ 4)\). If \(M^ B(T)\) and \(M^ C(T)\) denote the matrices of a linear transformation \(T\) relative to the basis \({\mathbf b}\) and \({\mathbf c}\) respectively, then \(M^ C(L_{b_ i})=Q^{-1} M^ B(L_{b_ i})Q\) and since \(c_ i=\sum_{k=1}^ n q_{ki} b_ k\), it follows that \(M^ C(L_{c_ i})=\sum_{k=1}^ n q_{ki} M^ C(L_{b_ k})\). Computing \(Q^{- 1}\) can be done, using a straightforward \(O(n^ 3)\) method. The following steps involve matrix multiplications, which take time \(O(n^ 4)\). Finally, using the \(O(n^{2,376})\) method of \textit{D. Coppersmith} and \textit{S. Winograd} [Proc. of the 19th Annual ACM STOC, 1-6 (1987)], it is even possible to conclude that the structure constants can be found in time \(O(n^{3,376})\).