# How to solve this system of linear equations

$$M = \left(\begin{smallmatrix} a_1 & a_2 & a_3 & a_4\\ b_1 & b_2 & b_3 & b_4\\ a_1 & c_2 & b_2 & c_4\\ a_4 & d_2 & b_3 & c_4\\ b_1 & c_2 & a_2 & e_4\\ b_4 & d_2 & a_3 & e_4\end{smallmatrix}\right)$$ All of the equations equal to 26; augmented, the matrix would then have have “26” to the right of each row.

This is basically the “Star of David” that another user posted:

http://i.stack.imgur.com/mVHwZ.jpg

but I don’t think anyone has solved it like this.

#### Solutions Collecting From Web of "How to solve this system of linear equations"

You have forgotten the very important condition that all integers between 1 and 12 must be used exactly once.

Though the equations themselves are linear and contain only 0 and 1 as coefficients, the constraint is very tough. I don’t think you could find an easy solution without integer programming, which is, like you may have known, NP-Hard and thus we have by now only exponential solutions, which are not better than brute force for such a small problem.

As I see, there are $960$ solutions ($80$ different solutions, ignoring rotation and mirror-transformation).

For example, $2$ of them:

Way of solving: “try-and-check”.

A).
Consider any values $a,h$.
For example, $a=5,h=6$.

Then possible values for $i,c$ are:
– $3,12$;
– $4,11$;
– $7,8$;
– $8,7$;
– $11,4$;
– $12,3$.

For these values you’ll get system of $5$ equations for $8$ variables. Reduction of system.
Sometimes such system will have no solutions.

B).
Consider $3$ any values for cells $a,c,e$.
Choose values for $b,d,f$, such that $a+c+e=b+d+f$.

When we’ll have values for $a,b,c,d,e,f$, we’ll get system of $6$ equations for $6$ variables ($g,h,i,j,k,l$).

But such system can have no solutions.

If you’ll use brute computer search, then there is not so much permutations of $12$ numbers: $12! = 479~001~600$ (a few seconds of computer work).