4
$\begingroup$

To repeat the question, let $A$ be a square matrix. We wish to determine if $A$ is nonsingular, that is, invertible. One way is compute its determinant and check if it is nonzero. However, if $A$ is invertible, calculating its determinant gives us strictly more information that knowing that it is nonzero.

Although the naive complexity for calculating the determinant is $O(n!)$, faster $O(n^3)$ algorithms exist. It does not seem unreasonable to suppose that their might be an algorithm that checks for nonsingularity that has strictly lower complexity than the fastest algorithms known for computing the determinant. Is such an algorithm known to exist? Can such an algorithm exist? (I am quite ignorant in these areas of computational complexity)

I am primarily interested in the case where $A$ is a real or complex matrix, but the case of rational matrices, or matrices over finite fields are also of interest. Feel free to discuss matrices over an arbitrary ring if you think it can clarify this discussion.

Thanks in advance for any insight you can spare!

  • 3
    [Gaussian elimination](http://en.wikipedia.org/wiki/Gaussian_elimination) (i.e, row-reduction).2012-11-18
  • 0
    Doesn't row reduction have arithmetic complexity $O(n^3)$?2012-11-18
  • 1
    @Isaac: yes, but this is already substantially better than the naive complexity of computing the determinant, which first of all contains $n!$ terms...2012-11-18
  • 0
    @QiaochuYuan: True, but I am not asking about the naive complexity so much as the complexity of the fastest algorithms known to exist. One can compute determinants with complexity $O(n^3)$.2012-11-18
  • 0
    @Isaac: Using row reduction, for instance. I’m offering it as a starting point.2012-11-18
  • 0
    @Isaac: in that case, you should clarify your question. "Computing the determinant" is not an operation that has a well-defined complexity until you specify an algorithm you're using to compute it.2012-11-18
  • 0
    @QiaochuYuan Thanks, I'll do just that.2012-11-18
  • 3
    Note that over the field of two elements, computing the determinant is equivalent to determining singularity.2012-11-18
  • 0
    @BrianM.Scott : I'm a little confused as to what you are suggesting (for which I apologize). One can use row reduction to check for nonsingularity just as one uses row reduction to compute the determinant. In any event, don't these computations have the same complexity?2012-11-18
  • 0
    In finite precision arithemetic, there is no way you can determine whether a real or complex matrix is nonsingular or not. The best you can do is to calculate the *distance to the nearest singular matrix* as a reference.2012-11-18
  • 2
    Of course. When I made my original comment, I wasn’t paying attention to who posted the question, so I wasn’t assuming awareness of that fact: in my experience many undergraduates know only cofactors. Had I noticed who was asking, I’d not have bothered.2012-11-18

1 Answers 1