Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 '13 at 11:26
9  
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 '13 at 12:27
2  
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 '13 at 13:07
1  
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. –  Steven Stadnicki Apr 6 at 7:04
add comment

3 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

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.

As mentioned in the comments, for the other 2 cases the notion of determinant doesn't directly make sense, so that needs more clarification.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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