Solve a System of Linear Equations

Write a program to solve a series of linear equations as short as possible. It must solve arbitrary number of equations problems. They can inputted however you like, coefficients of augmented matrix is probably the easiest. The program doesn't have to handle non-integer coefficients or solutions. No degenerate or invalid cases will be tested. The program must output the value of each variable or reduced row echelon form.

No equation solving libraries, matrix functions, or any way to automatically solve is allowed. You can simulate matrices with arrays or lists.

Example input (or equivalent):

m={{2,1,-1,8},{-3,-1,2,-11},{-2,1,2,-3}}

This represents 2x+y-z=8, -3x-y+2z=-11, -2x+y+2z=-3

Example output (or equivalent):

{2,3,-1}

This represents x=2, y=3, z=-1

• Can the coefficients of the variables and the constant terms be separated into two arrays in the input? Mar 1 '14 at 21:58
• @ace yes, that's fine
– qwr
Mar 1 '14 at 22:08
• What exactly are you saying by degenerated cases? I guess that you are refering to all of those cases: 1) Malformed input; 2) Things like 0x=0 or 0x=5; 4) Cases where the number of equations is different than the number of variables; 5) Contradictory cases like x+5y=7, x+5y=8; 6) Cases without linear independency, like x+3y=6, 2x+6y=12. Am I right? Mar 1 '14 at 22:40
• @Victor Yes, any input that has any ambiguity at all or isn't solvable.
– qwr
Mar 1 '14 at 22:53
• What about cases which aren't degenerate but are ill-conditioned? (Or, in other words, what kind of pivoting is required?) Mar 1 '14 at 23:43

APL, 1 char

I know it doesn't fit the (revised) requirements, but it's too good not to post:

Symbol "domino" (division ÷ inside a rectangle) performs matrix division, therefore it can solve any system of linear equations. You just have to put it between the constant term vector and the matrix with the other terms:

8 ¯11 ¯3 ⌹ ⊃(2 1 ¯1)(¯3 ¯1 2)(¯2 1 2)
2 3 ¯1

(if you want to try it on TryApl, is )

Javascript (284 181) - Gauss Elimination method

function f(A){l=A.length;d=1;for(i=0;i+1;i+=d){v=A[i][i];for(k=0;k<l+1;k++)A[i][k]/=v;for(j=i+d;A[j];j+=d)for(k=0,w=A[j][i];k<l+1;k++)A[j][k]-=w*A[i][k];if(i==l-d)d=-1,i=l}return A}

Test

f([[2,1,-1,8],[-3,-1,2,-11],[-2,1,2,-3]]);

=> [[1,0,0,2],[0,1,0,3],[-0,-0,1,-1]]

The returned array combine the identity matrix and the solution.

• You can save couple more characters. Mar 2 '14 at 1:16
• Instead of l=A.length;for(i=0;i<l;i++) use for(i=0;i<l=A.length;i++). Mar 2 '14 at 1:22
• Instead of for(i=l-1;i>=0;i--) use for(i=l;--i;). Mar 2 '14 at 1:25
• You can also move w=A[j][i] into for() and skip {} around. Mar 2 '14 at 5:24
• Thanks everyone, I managed to merge forward and backward steps in one single step, saving a hundred chars and some of your tips are not valid anymore. (except @MarcinJuraszek tip) Mar 2 '14 at 9:07

Python 169 166

Implementation

def s(a):
if a:b=a;r=s([[x-1.*y*b/rfor x,y in zip(b[1:],r[1:])]for r in a[1:]]);return[round((b[-1]-sum(x*y for x,y in zip(b[1:-1],r)))/b)]+r
return[]

Demo

>>> arr=[[2, 1, -1, 8], [-3, -1, 2, -11], [-2, 1, 2, -3]]
>>> s(arr)
[2.0, 3.0, -1.0]

Note

If you are OK with the float approximation, then you can remove the round function call and further golf to 159 characters

This answer no longer fits the question after the rule change as it uses a matrix function.*

Sage, 32

~matrix(input())*vector(input())

Sample input:

[[2, 1, -1], [-3, -1, 2], [-2, 1, 2]]
[8, -11, -3]

Sample output:

(2, 3, -1)

*Arguably, matrix() is a typecast, not a function (running import types; isinstance(matrix, types.FunctionType) gives False). Also, the ~ and * are operators, not functions.

• I've updated the rules. The code must handle different number of equations and you now can't use matrix functions.
– qwr
Mar 1 '14 at 22:01

Java - 522434228 213 chars

Solves by systematically checking all possible integer n-tuples by direct multiplication until one is found that works.

Function takes augmented matrix, A, trial solution vector, x, and dimension, n, as input - outputs solution vector, x. Note that the vector x is actually one larger than the dimension to help step through possible solutions. (If I declared variables A,x,n,j,k,s as instance variables, the function would be 31 chars shorter - for a total of 182, but that feels like bending the rules too far.)

int[]Z(int[][]A,int[]x,int n){int j,k,s;for(;;){for(j=0;j<n;j++){for(k=s=0;k<n;s+=A[j][k]*x[k++]);if(s!=A[j][n])j+=n;}if(j==n)return x;for(j=0;j<=n;j++)if(x[j]!=x[n]||j==n){x[j]++;for(k=0;k<j;x[k++]=-x[n]);j=n;}}}

Program for testing (somewhat ungolfed):

import java.util.*;
class MatrixSolver{
public MatrixSolver() {
Scanner p=new Scanner(System.in); //initialize everything from stdin
int j,k,n=p.nextInt(),A[][]=new int[n][n+1],x[]=new int[n+1];
for(j=0;j<n;j++)for(k=0;k<=n;A[j][k++]=p.nextInt());
x=Z(A,x,n); //call the magic function
for(j=0;j<n;j++) System.out.print(x[j]+" "); //print the output
}
public static void main(String[]args){
new MatrixSolver();
}

int[]Z(int[][]A,int[]x,int n){
int j,k,s;
for(;;){
for(j=0;j<n;j++){ //multiply each row of matrix by trial solution and check to see if it is correct
for(k=s=0;k<n;s+=A[j][k]*x[k++]);
if(s!=A[j][n])j+=n;
}
if(j==n)return x; //if it is correct return the trial solution
for(j=0;j<=n;j++)if(x[j]!=x[n]||j==n){//calculate the next trial solution
x[j]++;
for(k=0;k<j;x[k++]=-x[n]);
j=n;
}
}
}
}

Program takes input from stdin as space separated integers as follows: first, the dimension of the problem, second, the entries of the augmented matrix by row.

Sample run:

\$java -jar MatrixSolver.jar
3 2 1 -1 8 -3 -1 2 -11 -2 1 2 -3
2 3 -1

I shaved several characters by following Victor's advice about loops and "public", storing the RHS in the augmented matrix instead of separately, and adding an extra entry to my trial solution to simplify the generation of each new trial solution. The OP also said that a function is enough - no need to count the entire program.

• while(true){f=0;for(j=0;j<n;j++) can be replaced by while(true){for(f=j=0;j<n;j++). Further your class don't need to be public. For-loops with only one instruction in the body don't need the curly-braces. Mar 2 '14 at 6:03
• I think that for(j=0;j<n;j++){for(k=0;k<n;k++){A[j][k]=p.nextInt();}b[j]=p.nextInt();} can be replaced by for(j=0;j<n;b[j++]=p.nextInt())for(k=0;k<n;)A[j][k++]=p.nextInt(); Mar 2 '14 at 6:06
• @Victor Thanks, I made those, and other, changes. Mar 2 '14 at 7:37
• while(true) can be changed to for(;;) Mar 2 '14 at 9:05
• @ace thanks - changed that and a couple other things and shaved 15 chars. Mar 2 '14 at 23:39

JavaScript (ES6),  152  151 bytes

Implementation of Cramer's rule.

Takes input as (m)(v), where $$\m\$$ is the matrix of variable coefficients and $$\v\$$ is the vector of constant terms.

m=>v=>m.map((_,i)=>(D=m=>m+m?m.reduce((s,[v],i)=>s+(i&1?-v:v)*D(m.map(([,...r])=>r).filter(_=>i--)),0):1)(m.map((r,y)=>r.map((k,x)=>x-i?k:v[y])))/D(m))

Try it online!