17
$\begingroup$

I just learned that if a matrix is orthogonal, its determinant can only be valued 1 or -1. Now, if I were presented with a large matrix where it would take a lot of effort to calculate its determinant, but I know it's orthogonal, is there a simpler way to find out whether the determinant is positive or negative than the standard way of calculating the determinant?

$\endgroup$
  • $\begingroup$ Triangular matrices; if you can do products fast in your head, read it off the diagonals. $\endgroup$ – IAmNoOne Aug 16 '14 at 23:23
  • 1
    $\begingroup$ The standard way of calculating determinant takes $O(n^3)$ time. I think it's not that bad. Anyway, for some (very few) special matrices, Gershgorin's theorem may be applicable. $\endgroup$ – Tunococ Aug 16 '14 at 23:24
  • 3
    $\begingroup$ I wonder if the sign of the determinant of a large matrix can be computed substantially faster than the determinant itself. $\endgroup$ – Conifold Aug 17 '14 at 0:52
  • $\begingroup$ If all of the entries are rational, and there is an odd $p$ that is not in the factorization of any of the denominators, then you could reduce the whole matrix modulo $p$ (turning $\frac{a}{b}$ into $ab^{-1}\mod{p}$) to get a leg up on bit operations while computing the determinant. If you can take $p=3$, that would work out best. $\endgroup$ – alex.jordan Aug 17 '14 at 22:16
  • $\begingroup$ Throwing some ideas in here - if we know that all of the eigenvalues are real, then we can simply compute the trace as by virtue of the eigenvalues all being $\pm 1$; if $j$ is the number of $1$ eigenvalues, then $tr(A) = j - (n-j)$, so solving for $j$ gives $\det(A) = (-1)^{n-j} = (-1)^{1/2*(n - tr(A))}$. Of course, this doesn't help much with the general problem, but it suggests that the reason this is hard is because of the possibility of complex eigenvalues, so maybe there's some way of dealing with those. $\endgroup$ – Andrew D Aug 17 '14 at 23:42
4
$\begingroup$

It depends on what "easy way" means. There is no known shortcut for determinants of orthogonal matrices, but most known algorithms will run faster for them. This is not detected by simple complexity estimates in terms of matrix size only. Such estimates assume that arithmetic operations are performed in constant time regardless of the size of numbers involved. This exactly ignores the advantage that orthogonal matrices have over worse conditioned ones.

If one takes into account the size of numbers appearing in computations using the bit cost, then instead of $O(n^3)$ one gets more nuanced $O^{\sim}\big(n^3(1+\log(\Delta(A)\|A\|))\big)$, where $\Delta(A)$ is the orthogonality defect of $A$ (soft $O^{\sim}$ means that logarithmic terms are not shown). This shows a clear advantage for orthogonal matrices, in general $\log(\Delta(A)\|A\|)$ can be $O^{\sim}(n\log\|A\|)$.

The $O(n^3)$ baseline comes from algorithms using standard methods and can be improved. Strassen proved that complexity of computing determinants is equivalent to that of matrix multiplication. The best known multiplication algorithm is Le Gall's with complexity $O(n^{2.3728639})$, better than the classical $O(n^3)$. But it seems to be unknown if the best exponent for orthogonal matrices is strictly smaller than for general ones. Even if it is not computation for them is still easier in bit cost.

$\endgroup$
  • 1
    $\begingroup$ It is perhaps worth noting that the sub-$n^3$ algorithms really are only better in the limit. The lower order terms for them are so large that you need extremely large matrices to see any improvement. GAP only switches algorithms at around $n=200000$, if I remember correctly, and my understanding of Le Gall's algorithm is that $n$ has to be so large that computers cannot store a general matrix of that size. I cannot say that authoritatively, but it is true in general that the asymptotically fastest algorithm need not be the fastest in actual practice. $\endgroup$ – zibadawa timmy Aug 17 '14 at 23:23
0
$\begingroup$

A slightly faster way than a brute force method would be to calculate the cross product (read: Hodge dual of the wedge product) of the first $n-1$ column, and compare the result to last column.

This unfortunately only cuts down $O(n)$ operations, so does not significantly alter the $O(n^3)$ complexity.

$\endgroup$
  • $\begingroup$ It sounds like you're saying you can determine the sign of the determinant of a $7\times7$ orthogonal matrix by just looking at the first 3 columns. That seems quite unlikely. $\endgroup$ – Gerry Myerson Aug 17 '14 at 1:43
  • $\begingroup$ @GerryMyerson - you are right, I forgot about the various permutations. $\endgroup$ – nbubis Aug 17 '14 at 1:55
0
$\begingroup$

The following appears to be a survey of results in this area: http://www4.ncsu.edu/~kaltofen/bibliography/02/KaVi02.pdf So looking through that and the references would be good. A quick look through of the paper indicates that the methods work better with matrices close to orthogonal ones, so I expect this to mean that the methods and error bounds for a known orthogonal matrix are relatively nice and predictable.

$\endgroup$
  • 1
    $\begingroup$ I read this one but they still seem to have $O(n^3)$ even for orthogonal matrices. Pan in his paper comet.lehman.cuny.edu/vpan/pdf/pan146.pdf pays attention to the constant in front of $n^3$ and perhaps that's the only way to distinguish determinant and sign algorithms. But he says he is not incorporating fast matrix multiplication which may get this below $O(n^3)$, but it's unclear if the difference will be in the order of growth, or again only in the constant. $\endgroup$ – Conifold Aug 17 '14 at 3:02
  • 1
    $\begingroup$ @Conifold Using fast matrix multiplication still doesn't make it fundamentally faster than just computing the determinant; IIRC there are $\Theta(M(n))$ algorithms for the determinant (where $M(n)$ is the time to multiply two $n\times n$ matrices). $\endgroup$ – Steven Stadnicki Aug 17 '14 at 4:20
  • $\begingroup$ @Steven Stadnicki I meant faster than $O(n^3)$ since matrix multiplication can be faster than that. $\endgroup$ – Conifold Aug 17 '14 at 22:03

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.