What is a good way to implement Gaussian elimination when the operators are custom operators, rather then standard arithmetic ones?

Here are the operators:

Addition:

0 + 0 = 0
0 + 1 = 1
1 + 1 = 0

Subtraction:

0 - 0 = 0
0 - 1 = 1
1 - 1 = 0

Multiplication:

0 * 0 = 0
0 * 1 = 0
1 * 1 = 1

Division:

0 / 0 = illegal
0 / 1 = 0
1 / 1 = 1

Here is a sample set of equations as augmented matrix, with the RHS in the right-most column:

1, 1, 0, 1, 0, 0, 0, 0, 0, 1
0, 1, 0, 1, 1, 0, 0, 0, 0, 1
0, 1, 1, 0, 0, 1, 0, 0, 0, 1
1, 0, 0, 1, 0, 0, 0, 0, 0, 1
0, 1, 0, 1, 1, 0, 0, 0, 0, 1
0, 0, 0, 0, 0, 1, 0, 0, 0, 1
0, 0, 0, 1, 0, 0, 1, 0, 0, 1
0, 0, 0, 1, 1, 0, 1, 1, 0, 1
0, 0, 0, 0, 0, 1, 0, 0, 1, 1

The solution for this set is:

x1 = 1
x2 = 0
x3 = 0
x4 = 0
x5 = 1
x6 = 1
x7 = 1
x8 = 1
x9 = 0

Gaussian elimination failed for me as I tried it on this set.

The equations will have 9, 16, 25 or 36 terms. It would be great if the algorithm is easily extendable to larger squares, up to 100. I'm looking for an algorithm, in pseudo code or JavaScript preferably.

What is a good way to implement Gaussian elimination when the operators are custom operators, rather then standard arithmetic ones?

Here are the operators:

Addition:

0 + 0 = 0
0 + 1 = 1
1 + 1 = 0

Subtraction:

0 - 0 = 0
0 - 1 = 1
1 - 1 = 0

Multiplication:

0 * 0 = 0
0 * 1 = 0
1 * 1 = 1

Division:

0 / 0 = illegal
0 / 1 = 0
1 / 1 = 1

Here is a sample set of equations as augmented matrix, with the RHS in the right-most column:

1, 1, 0, 1, 0, 0, 0, 0, 0, 1
0, 1, 0, 1, 1, 0, 0, 0, 0, 1
0, 1, 1, 0, 0, 1, 0, 0, 0, 1
1, 0, 0, 1, 0, 0, 0, 0, 0, 1
0, 1, 0, 1, 1, 0, 0, 0, 0, 1
0, 0, 0, 0, 0, 1, 0, 0, 0, 1
0, 0, 0, 1, 0, 0, 1, 0, 0, 1
0, 0, 0, 1, 1, 0, 1, 1, 0, 1
0, 0, 0, 0, 0, 1, 0, 0, 1, 1

The solution for this set is:

x1 = 1
x2 = 0
x3 = 0
x4 = 0
x5 = 1
x6 = 1
x7 = 1
x8 = 1
x9 = 0

Gaussian elimination failed for me as I tried it on this set.

The equations will have 9, 16, 25 or 36 terms. It would be great if the algorithm is easily extendable to larger squares, up to 100. I'm looking for an algorithm, in pseudo code or JavaScript preferably.

• javascript
• algorithm
• math

• Please note that due to the new operators some equation sets bee unsolvable, as their results would be fractions. I am particularly interested in the question of solvability. – Killroy Commented Aug 1, 2009 at 9:04

2 Answers 2

Gaussian Elimination Algorithm in pseudocode can be found here.

It doesn't matter if you are using 'normal' numbers or if you are in Z₂ ring, the algorithm remains the same.

What you could do is implement a structure to hold the values you are operating over and overload all necessary operators. Then all you need to do will be to rewrite pseudocode to the language you want to use it in.

Unfortunately since you have mentioned JavaScript you cannot override operators in that language so this will bee a bit more plex. I guess you could define functions that will perform operators job and use them instead of standard operators.

function add(v1, v2) {
    if ((v1 != 0 && v1 != 1) || (v2 != 0 && v2 != 1)) {
        alert('Invalid params');
        return;
    }

    return (v1 + v2) % 2;
}

function subtract(v1, v2) {
    if ((v1 != 0 && v1 != 1) || (v2 != 0 && v2 != 1)) {
        alert('Invalid params');
        return;
    }

    return Math.abs((v1 - v2) % 2);
}

function multiply(v1, v2) {
    if ((v1 != 0 && v1 != 1) || (v2 != 0 && v2 != 1)) {
        alert('Invalid params');
        return;
    }

    return v1 * v2;
}

function divide(v1, v2) {
    if ((v1 != 0 && v1 != 1) || (v2 != 0 && v2 != 1)) {
        alert('Invalid params');
        return;
    } else if (v2 == 0) {
        alert('Divider cannot be zero');
        return;
    }

    return v1 / v2;
}

What you describe are not really custom operators. Rather, it's Z₂ with standard addition and multiplication modulo 2.

This is a field; so you do not have any "fraction" problems.

The Gaussian elimination algorithm is not restricted to the field of real numbers; it works as well on Z₂.