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!