Mixing
System of Linear Equations with the solution(s) being permutations of a given set
$begingroup$
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 into 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.
linear-algebra algebra-precalculus permutations systems-of-equations diophantine-equations
asked Jan 29 at 15:15
GeekGeek
113
$endgroup$
add a comment |
$begingroup$
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 into 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.
linear-algebra algebra-precalculus permutations systems-of-equations diophantine-equations
asked Jan 29 at 15:15
GeekGeek
113
$endgroup$
add a comment |
$begingroup$
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 into 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.
linear-algebra algebra-precalculus permutations systems-of-equations diophantine-equations
asked Jan 29 at 15:15
GeekGeek
113
$endgroup$
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 into 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.
linear-algebra algebra-precalculus permutations systems-of-equations diophantine-equations
linear-algebra algebra-precalculus permutations systems-of-equations diophantine-equations
asked Jan 29 at 15:15
GeekGeek
113
asked Jan 29 at 15:15
GeekGeek
113
edited Jan 29 at 16:16
Geek
asked Jan 29 at 15:15
GeekGeek
113
asked Jan 29 at 15:15
GeekGeek
113
asked Jan 29 at 15:15
GeekGeek
113
113
add a comment |
add a comment |
0
active
oldest
votes
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3092296%2fsystem-of-linear-equations-with-the-solutions-being-permutations-of-a-given-se%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3092296%2fsystem-of-linear-equations-with-the-solutions-being-permutations-of-a-given-se%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
