Solve a System of Linear Equations

Question

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

Answer 1

Python 169 166

Implementation

def s(a):
 if a:b=a[0];r=s([[x-1.*y*b[0]/r[0]for 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[0])]+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

Answer 2

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 ↑)

Answer 3

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.

Answer 4

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.}

Answer 5

Java - 522 434 228 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.

Answer 6

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!