# What is the fastest algorithm to establish whether a linear system in $\mathbb{R}$ has a solution?

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?

• 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. – Pseudonym Jan 21 '19 at 13:20