# Which is easier to work out: determinant or inverse?

Suppose $A\in M_n(R)$ be a $n\times n$ matrix over some ring $R$. Which of the following two tasks is easier?

1. to work out $\det(A)$;

2. to work out $A^{-1}$.

More specifically, I want to know the answers according to the following different settings of $R$:

1. $R$ is commutative;

2. $R$ is non-commutative.

3. $R$ is ring group $\mathbb{Z}_n[\mathbb{G}]$ for (1) commutative group $\mathbb{G}$, (2) non-commutative group $\mathbb{G}$.

• I guess both tasks have time complexity $O(n^3)$. Jun 30 '13 at 11:26
• In Cases 2 and 3, the notion of a determinant doesn't even make sense (there are various fixes for that in specific situations, but there is not one canonical fix). Jun 30 '13 at 12:27
• The question is not very well posed. Apart from the point raised in the previous comment, one should realise that for $R$ commutative and inverse exists only if the determinant is invertible, which is in general a very restrictive condition. Does "working out $A^{-1}$" involve deciding whether it exists (in which case most likely one has to compute the determinant in some way or another to do so), or do we have a guarantee that it does, and are only asked to compute it? This makes a very different computational problem. Dec 7 '13 at 13:07
• From a computational-complexity perspective, in the commutative case both of these are well-known to be equivalent to matrix multiplication at least up to a logarithmic factor in the size of the matrix - and IIRC, even logarithmic factors can be absorbed with the right approach. Apr 6 '14 at 7:04

For the case of commutative rings, from a complexity theoretic viewpoint, computing the inverse of a matrix, computing the determinant of a matrix, and computing a matrix multiplication all have the same complexity. This was shown in the 70s by Strassen, of the well-known Strassen multiplication. That gives a complexity of $O(n^{2.81})$ for the above operations; the current record is, I believe, $O(n^{2.38})$. This is, by the way, complexity counted in operations on $R$ and (maybe) some logarithmic factors are being ignored.
A matrix has inverse only if the determine of the matrix is a unit x (have inverse) in the ring R, and its inverse has determine $x^{-1}$ in R.
When R is not p.i.d.(principal ideal domain), like $Z_n[G]$, then the concept of determinate and inverse is not well-defined, as the normal form of a group does not exist.
Recently, I realize that the computing determinant might be harder than computing the inverse. Since if the matrices are defined over a non-commutative ring $R$, the computing $\det(A)$ for $A\in M_n(R)$ seems very hard. However, let $d=|M_n(R)|=|R|^{n^2}$. That is, the semigroup $M_n(R)$ with respect to matrix multiplication has order $d$. Thus, $A^{d-1}=A^{-1}$, which can be efficiently worked out by employing the so-called square-and-multiply" method.