Let $A$ be a $n\times n$ matrix over a commutative ring. I'm looking for a good method to compute its adjugate matrix.


My current approach is to use the Cayley-Hamilton theorem:
$$\text{adj}(A) = -(A^{n-1} + c\_1A^{n-2}+\ldots +c\_{n-2}A+c\_{n-1}\text{I})
$$
where $$\lambda^n + c\_1\lambda^{n-1} + \ldots + c\_{n-1}\lambda +c\_n = \det(\lambda\text{I}-A).$$
i.e. the $c\_i$ are the coefficients of the characteristic polynomial, which I can determine using the Berkowitz algorithm. In particular, I never have to make divisions, so all works over an arbitrary commutative ring.


However, this method needs $\mathcal{O}(n^4)$ arithmetical ring operations, so there might be better alternatives. I hope for something like $\mathcal{O}(n^3)$, as for matrix inversion over a field.



Compute adjugate matrix over commutative ring
A reference dated 2001-2003 is <http://www4.ncsu.edu/~kaltofen/bibliography/01/KaVi01.pdf>


Over a commutative ring, the complexities of the calculation of $\det(A)$ and $adj(A)$ are the same. With the standard multiplication, the authors obtain a bit-complexity in $n^{10/3+\epsilon}N^{1+\epsilon}$ where $N$ is the length of the entries of $A$. Yet, the programming seems complicated ; there is a simpler method with exponent $3.5$.


Conclusion: If you have a robust and simple method with exponent $4$, then it is perfect.


