1
$\begingroup$

It has been claimed in this paper (page 2 last paragraph) that Matrix powering is equivalent to determinant computation.

https://www.cse.iitk.ac.in/users/manindra/algebra/depth-four.pdf

Does anybody why is this the case?

$\endgroup$
2
$\begingroup$

It states that matrix powering is computationaly equivalent to computation.
From another angle, Coppersmith–Winograd algorithm for matrix multiplication has complexity $\mathcal O(n^{2.373})$ and the same complexity is for determinant computation by fast multiplication.
The result comes from Triangularization and inversion via fast multiplication by James R. Bunch and John E. Hopcroft

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Look at the paper by Stephen Cook (numbered $[3]$ in the references of the paper you have mentioned). There, in proposition $5.2$ in page $13$, he shows the "computational equivalence" between matrix powering and determinant computation (and other problems).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Perhaps you should add the paper’s title, and if possible, a link. $\endgroup$ – Yuval Filmus Feb 19 '19 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.