I know the best algorithm to solve a linear system in $\mathbb{R}$ with $n$ variables is Coppersmith-Winograd's algorithm, which has a complexity of $$ O\left(n^{2.376}\right). $$ How much easier is it to simply determine whether the same system has any solution?

More precisely, given a system of $m$ equations and $n$ unknowns, what is the complexity of establishing whether it has any solution?


Whether or not Coppersmith-Winograd is the "best" algorithm depends on your circumstances, of course. CW and algorithms like it are usually considered impractical due to high constant factors. Strassen's algorithm is more common in practice.

But since computational complexity is what you are interested in, CW was beaten quite recently.

As far as we know, calculating the determinant of a matrix, or eigenvalue estimation, or anything else that could be used to determine if a matrix is singular or not are at least as complex as matrix multiplication.

  • $\begingroup$ Does "As far as we know" mean that someone has given a reduction from matrix multiplication to determining whether it has a solution? Or is it just a commonly held "feeling"? $\endgroup$ Jan 17 '19 at 13:33
  • $\begingroup$ Thanks for your answer. I'm also curious about what @j_random_hacker asked. Is there any reference for this claim? $\endgroup$
    – Gio
    Jan 18 '19 at 14:37
  • $\begingroup$ Yes. See Bunch & Hopcroft, "Triangular Factorization and Inversion by Fast Matrix Multiplication". apps.dtic.mil/dtic/tr/fulltext/u2/754790.pdf Essentially, if two matrices of order $n$ can be multiplied in $M(n) = \Omega(n^2)$ time, then triangular factorisation, inversion, and determinant calculation can be performed in $O(M(n))$ time. $\endgroup$
    – Pseudonym
    Jan 21 '19 at 13:20

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.