[Community Question] Linear-algebra: System of Linear Equations with the solution(s) being permutations of a given set

One of our user asked:

Consider the system of equations

$$x_1 + x_2 + x_5 + x_6 = 26 \\x_2 + x_3 + x_7 + x_8 = 26 \\x_3 + x_1 + x_9 + x_4 = 26 \\x_4 + x_5 + x_{10} + x_{12} = 26 \\x_6 + x_7 + x_{10} + x_{11} = 26 \\x_8 + x_9 + x_{11} + x_{12} = 26$$

We need to find a solution such that $x_i = \sigma(i)$ for some permutation $\sigma$ of the set $\{k : k \le 12, k \in \Bbb N \}$.

The need to solve this system arose for an exercise from Pearls in Graph Theory by Hartfield and Ringel. I know that using a system like this may not be an efficient way for the graph problem, but for now I would like some insight on the equations by themselves without explicitly relying on the graph problem.

I only know that such solution(s) exist because the question asked for one and I would not be able to justify its existence without finding a solution.

Here's what I have tried so far:

• Some things can be obtained from the symmetry (I'm not sure if this is the right word) like $$x_1 + x_2 + x_3 = x_{10} + x_{11} + x_{12}$$ and since all the variables are equivalent, we can freely fix one of the variables. For convenience, let this simply be $x_1 = 1$. This is clear when the equations are put in context of the original graph question, but not so much to me if only the equations and constraints in the question are known.

• Also we can obtain a new solution from a solution by performing some swaps. For example, exchanging $x_1$ with $x_2$, $x_5$ with $x_6$, $x_4$ with $x_7$, $x_{11}$ with $x_{12}$, and $x_8$ with $x_9$. Again this is clearly evident when rotations and reflections of the graph in the original problem are considered, but I would like another angle of looking at these solutions that can be generated from one such solution.

• I could not really get anywhere with the above facts, so I just started afresh with Gaussian Elimination since I just learnt about it recently, but stopped midway since I couldn't think of how to use the fact that the solution must be a permutation directly with the matrix. Some online tool gave me a solution with only $6$'s and $7$'s for just the equations but I couldn't see how that may be useful.

• I then used a simple python script to just brute-force its way through all permutations and find which satisfy the equations. This confirmed one thing for me that even after fixing $x_1 = 1$, we are free to choose $x_2$ or some other $x_i$ though not for all.

• Next I started to solve after fixing $x_1 = 1$ and $x_2 = 2$. We get that $x_5$ and $x_6$ must be $11$ and $12$ in some order. I then arbitrarily chose $x_5 = 12$ and $x_6 = 11$ for which I had no justification other than the above script showing that either order was acceptable. Proceeding in this fashion with some trial-and-error and backtracking I finally arrived at $(1, 2, 9, 6, 12, 11, 8, 7, 10, 3, 4, 5)$.

I am primarily looking for efficient ways of solving this system of equations.

Secondly I would like explanations or some reference where I may better understand all the little aspects above that weren't very clear from an algebraic point of view such as the existence of solution(s) in general, existence of free variables, etc.