Gaussian exception using custom operators

Question

What is a good way to implement a Gaussian exception when the operators are user operators and not standard arithmetic?

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 

Section:

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

Here is an example system of equations as an extended matrix with RHS in the right 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 kit is:

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

The Gauss exception failed for me as I tried this on this set.

Equations will have 9, 16, 25, or 36 members. It would be great if the algorithm could easily expand to large squares, to 100. I am looking for an algorithm, preferably in pseudo-code or JavaScript.

Answer 1

An algorithm for eliminating the Gaussian algorithm in pseudo-code can be found here .

It doesn’t matter if you use “normal” numbers or if you are in the Z ₂ ring, the algorithm remains the same.

What you can do is implement a structure to store the values ​​you use and overload all the necessary operators. Then all you have to do is rewrite the pseudo-code into the language in which you want to use it.

Unfortunately, since you mentioned JavaScript, you cannot override operators in this language to make this a bit more complicated. I think you could define functions that will perform the work of operators 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; } 

Answer 2

What you are describing is not an ordinary operator. Rather, it is Z ₂ with standard additions and multiplication modulo 2.

This is a field ; therefore, you have no problem with the "faction".

The Gauss elimination algorithm is not limited to the field of real numbers; It also works on Z ₂ .