I became aware of this question by way of an answer on Meta and feel I must push back against the comment of DonAntonio and the answer of amWhy.
Uniqueness of the solution of the system
$$
\begin{aligned}
x_1&=3\\
x_2&=2\\
x_3&=3
\end{aligned}
$$
is obvious and needs no proof. What is there to prove? Is it conceivable that if you plug in numbers other than $3,$ $2,$ and $3$ for $x_1,$ $x_2,$ and $x_3$ you might obtain three true statements?
The determinant is a complicated object, and by bringing it in in this situation, you are making something simple appear much more difficult than it actually is.
Here's what I think you were probably getting at: Let's start with a simpler analogue. Is the solution of the equation $x=2$ unique? Of course is is: $2$ is the only solution. Now $x=2$ may be the end result of simplifying a more complicated equation, such as $13x=26.$ The latter is a special case of the general equation $ax=b.$ It is certainly the case that the latter has a unique solution if and only if $a\ne0.$ If $a=0,$ then there is no solution unless $b=0,$ in which case there are infinitely many solutions.
Likewise, the matrix equation $Ax=b,$ where $A$ is a square matrix and $x$ and $b$ are column vectors, has a unique solution if and only if $\det A\ne0.$ If $\det A=0,$ then it has either no solution or infinitely many solutions.
So it is helpful to introduce the determinant to make statements about the nature of the solution set of the general equation $Ax=b.$ But for concrete $A$ and $b,$ it is usually more efficient to row reduce the system than to compute $\det A.$ (More precisely, computing $\det A$ is best done by actually performing row reduction, but there is no need to mention determinants if you are row reducing to solve a concrete problem.) The end result of the row-reduction process will tell you whether there is a unique solution or not.
The only thing that might need proof is that the three row operations (swapping rows, multiplying a row by a non-zero number, adding a multiple of one row to another row) preserve the solution set. That is generally proved in a linear algebra course, and you can probably assume it from that point on. If not, let $S$ be a system and let $S'$ be the system that results from applying a row operation. You just need to prove that any solution to $S$ is a solution to $S',$ and that any solution to $S',$ is a solution to $S.$ This is straightforward, but it seems like overkill to do it in every row reduction problem you perform.
Best Answer
The fastest matrix multiplication algorithm is an important open mathematical question
The Wikipedia page https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm#Sub-cubic_algorithms shows how the fast known asymptotic algorithm has evolved through time:
This begs the question: how close can we get to
O(n^2), which is of course a lower bound since we have to read2 * n^2inputs at least once?Proving the upper lower bound, even non constructively, would make you instantly famous. Wikipedia lists it as an "Unsolved problem in computer science".
The constant factor for the better algorithms is so large though that it makes them impractical for most matrix sizes found in practice today, and I doubt this will change if new algorithms are found.
Therefore any practical real world answer will come down to optimizing against a given machine model, which is an important software / hardware engineering optimization question, but not of much mathematical interest.
Personal guess about solving for single variables: I don't think you can reduce complexity like that in general, since the entire system is coupled. How would you know that your solution for some variables also satisfies the entire global solution?