Take the tour ×

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}$.

share|improve this question
I guess both tasks have time complexity $O(n^3)$. –  Hagen von Eitzen Jun 30 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). –  darij grinberg Jun 30 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. –  Marc van Leeuwen Dec 7 at 13:07
add comment

2 Answers

Determinate comes first, and generally easier to figure out by definition not matter which R we are considering. (special situation exists when R is a field other than an principal ideal domain thus every nonsingular matrix has inverse)

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer


