12
$\begingroup$

I have just started auditing Linear Algebra, and the first thing we learned was how to solve a system of linear equations by reducing it to row echelon form (or reduced row echelon form). I know how to solve a system of linear equations using determinants, and so the using row echelon form seems to be very inefficient and an easy way to make mistakes.

The lecturer seemed to indicate that this will be useful in the future for something else, but a friend who has a PhD in mathematics said it is totally useless.

Is this true? Is this technique totally useless or is there some "higher mathematics" field/ technique where row echelon form will be useful?

$\endgroup$
3
  • 2
    $\begingroup$ This is kind of a dead thread, but ... No one seemed to mention what I consider an obvious point: You can't use determinants if your matrix $A$ is not square! ... Also, you get a better set of equations that your solution(s) must satisfy. In particular, if there are infinitely many solutions, you can describe them (using parameterization). $\endgroup$
    – Christopher Carl Heckman
    Mar 13, 2016 at 23:28
  • 1
    $\begingroup$ I know that this post is completely outdated. Anyway, play the experiment of solving a $5\times5$ system with paper and pencil, comparing Cramer and Gaussian elimination. You'll never ask the question again ! $\endgroup$
    – user65203
    Aug 19, 2017 at 13:07
  • 1
    $\begingroup$ And also note that an efficient way to compute determinants is... Gaussian elimination. $\endgroup$
    – user65203
    Aug 19, 2017 at 13:08

6 Answers 6

Reset to default
25
$\begingroup$

Go beyond 2 x 2 and row echelon form is the way to solve systems of linear equations. This stuff is not done by hand, but by a computer. Row echelon form is much, much faster than using determinants (Cramer's formula). Ask someone who works in numerical analysis about this. Your friend with the Ph.D. is clearly unaware of the needs of applied math.

In pure math, Cramer's formula is very important for some proofs (and I personally prefer it for conceptual reasons over the algorithmic row echelon business, but then I don't work in numerical analysis). In applied math problems that give rise to systems of linear equations, you typically face equations in hundreds of variables. You are not going to solve that with a determinant. Moreover, if a computer needed to find a determinant of a 100 x 100 matrix it would not use the sum of 100! terms as in the Laplace expansion formula for determinants, but instead apply faster algorithms (the QR algorithm).

Your profile says you are studying economics. At some point when you may need to deal with some system of linear equations in economics and have the computer solve it for you, the method of solution could be treated as a black box in the same way most people drive without knowing how a car really works. But the reality is that if it were not for the algorithm of reducing to row echelon form, the computer couldn't solve systems of hundreds of equations rapidly.

$\endgroup$
5
  • $\begingroup$ Interesting! I solve systems of equations by hand (3x3,) always using determinants. That is how we do in Economics, at least in the two universities where I have studied here in Australia. $\endgroup$
    – Vivi
    Aug 8, 2010 at 4:03
  • 1
    $\begingroup$ Er, the QR algorithm is for finding eigenvalues. Though I suppose one could multiply all together the eigenvalues returned, but that I think is too pedestrian a use for the "crown jewel of numerical linear algebra". Maybe you meant the "QR decomposition"? Still, Gaussian elimination takes at least half the effort of QR decomposition! $\endgroup$
    – J. M. ain't a mathematician
    Aug 8, 2010 at 9:58
  • $\begingroup$ J.: Yes, I should have just referred to Gaussian elimination for computing the determinant. $\endgroup$
    – KCd
    Aug 8, 2010 at 19:58
  • $\begingroup$ Note also that Gaussian Elimination is hardly the end all and be all of numerical solutions to linear systems... the Cholesky decomposition as well as iterative methods such as Conjugate Gradient or multigrid methods can all be much faster or robust in practical applications. $\endgroup$
    – user7530
    Mar 3, 2011 at 20:58
  • $\begingroup$ In fact in applied math you often encounter linear systems with hundreds of thousands or millions of variables. $\endgroup$
    – littleO
    Aug 19, 2017 at 13:45
17
$\begingroup$

Gaussian elimination on an $n \times n$ matrix takes takes on the order of $n^3$ operations, where an operation is an addition, subtraction, multiplication, or a division. By contrast, computing determinants using the cofactor expansion takes $n!$ operations, which is much, much longer.

For example, consider a $100 \times 100$ matrix. Then $100^3$ is a million, and a million operations can be done by a typical laptop in under a second; but $100!$ is approximately $1$ followed by $158$ zeros, which would take even a supercomputer more time than the age of the universe.

In fact, I believe the opposite of your claim is true: if you want to compute determinants, the best way is to to reduce to echelon form.

$\endgroup$
6
  • $\begingroup$ Presumably Vivi's only experience in solving systems of equations is 2 x 2 or maybe 3 x 3. For 2 x 2 systems, determinants are pretty easy to compute by cofactor expansion. I doubt anyone computes a 2 x 2 determinant using Gaussian elimination. So it would be better to say "the opposite of your claim is true if there are more than 2 variables, and esp. when there are lots of variables." $\endgroup$
    – KCd
    Aug 8, 2010 at 3:19
  • $\begingroup$ Also, often equations will be such that reducing to Echlon form is relatively easy $\endgroup$
    – Casebash
    Aug 8, 2010 at 3:35
  • $\begingroup$ +1 for comparing the computational burden of the two methods. @KCd: I would agree that Cramer's is conceptually the best for solving a 2-by-2 by hand, but this old USENET posting by Pete Stewart shows that for a computer, Gaussian behaves much better: tinyurl.com/22cz4v (hint: it's all in the "condition number") $\endgroup$
    – J. M. ain't a mathematician
    Aug 8, 2010 at 10:11
  • $\begingroup$ While it's true that computing determinants through cofactor expansion is factorial time, there do exist n^3 (and asymptotically faster) determinant algorithms as well. Your answer is a little misleading; it implies that the reason Gaussian elimination is preferable is because computing determinants is always so impossibly slow. $\endgroup$
    – Larry Wang
    Aug 8, 2010 at 13:49
  • $\begingroup$ @KH - I don't think my answer is misleading; in fact, I explicitly pointed out that you can compute determinants by reducing to echelon form. $\endgroup$
    – morgan
    Aug 8, 2010 at 18:53
10
$\begingroup$

alexx already covered much of what I had wanted to say, so allow me to share something that had been written by Forman Acton in his (excellent!) Numerical Methods that Work on the matter:

…the fact that this sequence of operations takes (much more) labor on the part of the computer as a direct solution of the problem by (Gaussian elimination) has never penetrated (the student's) consciousness. The glibness of the formal mathematical notation has obscured the realities of the arithmetic process. The cure is simple enough—the student should be asked to solve a 4-by-4 system, by hand, both ways. But this sort of realism is currently unfashionable—arithmetic labor being deemed only suitable for machines.

$\endgroup$
1
  • 1
    $\begingroup$ Oh, that is a great quote, thank you! $\endgroup$
    – Vivi
    Aug 8, 2010 at 11:07
9
$\begingroup$

Aside from its incredible utility in practical computations, echelon form is also a special case of a general construction called Bruhat decomposition which is important in the theory of Lie groups and algebraic groups.

$\endgroup$
1
  • 1
    $\begingroup$ A lot of the algorithmic procedures in linear algebra (e.g., Gram-Schmidt, QR decomposition) have a conceptual meaning in that setting. $\endgroup$
    – KCd
    Aug 8, 2010 at 6:25
6
$\begingroup$
  1. I think the only real utility of Cramer's rule -besides resolving 2x2 systems by hand- is that, for a general system of linear equations $AX = B$ with $\det A \neq 0$, it shows blatantly http://en.wikipedia.org/wiki/Cramer%27s_rule the continuous dependence of the solution with respect both $A$ and $B$.
  2. But, for the same reason, Cramer's rule is very dangerous because that $\det A$ appearing in the denominator: using it with a computer for small values of $\det A$ makes errors grow quickly.
  3. Nevertheless, I must confess that I feel somewhat unconfortable telling these kind of things to my students, since they could (and sometimes do) easely argue: (a) Are we going to actually solve some, say, 5x5 system of linear equations by hand? (b) Who cares what the computer really does in order to solve the system? -The only thing I need is the solution.

For these embarrassing objections, I have the following problem: try to solve some simultaneuous systems of linear equations. That is to say, for instance, two systems $AX = B_1$ and $AX = B_2$, with the same $A$. Of course, you can apply Cramer's rule two times, but the reducing row echelon algorithm allows you to solve it with one go, since the operations for reducing the system depend only on $A$. In manual computations, you can take advantage of this putting both matrices $B_1$ and $B_2$ together like this:

$$ (A \vert B_1 B_2) $$

Of course, this can be exploited further for any number of simultaneous systems $AX = B_1, \dots , AX=B_n$:

$$ (A \vert B_1 B_2 \dots B_n) \ . $$

For instance, inverting a matrix is a problem of solving a simultaneous system of linear equations:

$$ AX = I \quad \Longleftrightarrow \quad (A \vert e_1 \dots e_n) \ , $$

where $I$ is the identity matrix and $e_1, \dots , e_n$ is the standard basis of $\mathbb{R}^n$.

$\endgroup$
3
  • 7
    $\begingroup$ To recall a funny quote: "Good numerical analysts are conditioned to cringe upon hearing about determinants." $\endgroup$
    – J. M. ain't a mathematician
    Aug 8, 2010 at 10:17
  • 2
    $\begingroup$ AX can only equal one thing, not both B_1 and B_2. You should write AX_1 = B_1 and AX_2 = B_2. Likewise in the system of n equations you should write AX_i = B_i. $\endgroup$
    – KCd
    Aug 8, 2010 at 20:02
  • 1
    $\begingroup$ @KCd But such (ab)use is quite common, e.g. $\,ax=\pm b\,\Rightarrow\, x = \pm b/a,\,$ and $\,(ax-b_1)(ax-b_2)=0\,\Rightarrow\,x = b_1/a,\,$ or $\,b_2/a,\,$ etc. $\endgroup$
    – Bill Dubuque
    Mar 9, 2015 at 4:41
0
$\begingroup$

I will add a consideration that is quite unrelated to the answers that you got: besides the computational advantages, a matrix in reduced row echelon form could become very sparse, reducing drastically the amount of memory that is necessary to store the linear system.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .