[Math] How to solve systems of linear equations of multiple variables (more than 3 to 100s)

linear algebralinear programming

This was a question asked during an interview for programming job. And the bottom line was to write an alogrithm to solve such equations. As much as it numbed my neurons – it really provoked me. I had searched around for few days now. My maths knowledge is limited to freshman year. I am not sure if I am missing out sth from my limited maths knowledge. This whole multi variable concept looks like prediction system…or a rule based system.

Are there formal methods (with fancy names) available to solve linear equations of multi variables? Like new maths methods/theory I may have to learn. In what context are multi variable linear euqations used in real life? Perhaps this could be trivia to you maths experts – pardon me if so.

Best Answer

Row reduction is one of the classic methods and you can write software which will handle it. Although you would need a matrix library, which shouldn't be difficult to find.

An introductory text on linear algebra would be useful in understanding the techniques. As daOnlyBG mentioned, that's a large part of what linear algebra is about. I would write out a list of examples, but I am still not great with LaTex. Here's an explanation that seems reasonable.

Gauss-Jordan elimination is a straight forward algorithm which can be implemented in code. Pseudocode from Wikipedia

 for k = 1 ... min(m,n):
   Find the k-th pivot:
   i_max  := argmax (i = k ... m, abs(A[i, k]))
   if A[i_max, k] = 0
     error "Matrix is singular!"
   swap rows(k, i_max)
   Do for all rows below pivot:
   for i = k + 1 ... m:
     Do for all remaining elements in current row:
     for j = k + 1 ... n:
       A[i, j]  := A[i, j] - A[k, j] * (A[i, k] / A[k, k])
     Fill lower triangular matrix with zeros:
     A[i, k]  := 0
Related Question