Combinatorics problem on k sets and partionning a set of numbers, understanding of the proof
$begingroup$
The question I'm struggling with is given here :
Remove any number and the remaining numbers can be partitioned into two subsets of equal sum; prove all numbers are equal.
The problem is the following :
Supposed I have a list of n real numbers, where n is odd. The list is
constructed such that I can remove any arbitrary number from the list,
and the remaining numbers can be partitioned into two equal-sized
subsets with equal sums. Prove that all numbers in the list are equal.
Here is my problem. I understand neither the paper given here : http://www.math.cmu.edu/~lohp/docs/math/mop2012/combinatorics-black-soln.pdf
nor the answer of @Mike Earnest.
I don't understand those points :
- why would be $Mx=0$ ?
- and $M{bf1}=0$?
- Are you looking in the field given by $text{mod } 2$ ?
- And finally, why since $x$ is a multiple of $1$, does that mean that all weights are equal?
Thanks for the help! I don't know if asking about another answer is allowed on this media, I hope it is not prohibited :)
linear-algebra combinatorics graph-theory proof-explanation
edited Jan 22 at 3:55
bof
52.1k558121
asked Jan 21 at 13:29
Marine GalantinMarine Galantin
860316
$endgroup$
|
show 1 more comment
$begingroup$
The question I'm struggling with is given here :
Remove any number and the remaining numbers can be partitioned into two subsets of equal sum; prove all numbers are equal.
The problem is the following :
Supposed I have a list of n real numbers, where n is odd. The list is
constructed such that I can remove any arbitrary number from the list,
and the remaining numbers can be partitioned into two equal-sized
subsets with equal sums. Prove that all numbers in the list are equal.
Here is my problem. I understand neither the paper given here : http://www.math.cmu.edu/~lohp/docs/math/mop2012/combinatorics-black-soln.pdf
nor the answer of @Mike Earnest.
I don't understand those points :
- why would be $Mx=0$ ?
- and $M{bf1}=0$?
- Are you looking in the field given by $text{mod } 2$ ?
- And finally, why since $x$ is a multiple of $1$, does that mean that all weights are equal?
Thanks for the help! I don't know if asking about another answer is allowed on this media, I hope it is not prohibited :)
linear-algebra combinatorics graph-theory proof-explanation
edited Jan 22 at 3:55
bof
52.1k558121
asked Jan 21 at 13:29
Marine GalantinMarine Galantin
860316
$endgroup$
$begingroup$
$Mx$ being 0 expresses the fact that the two subsets have the same sum. $M1$ being 0 expresses the fact that the two subsets have the same size.
$endgroup$
– Simon
Jan 21 at 13:45
$begingroup$
The same question was asked here with several answers. Personally I thought my answer was the clearest, though it didn't get any votes.
$endgroup$
– bof
Jan 22 at 3:52
$begingroup$
What does the "$k$ sets" in your question title refer to? What is $k$?
$endgroup$
– bof
Jan 22 at 4:39
$begingroup$
@bof math.stackexchange.com/questions/3080450/… It means a set of size $k$
$endgroup$
– Marine Galantin
Jan 22 at 22:57
$begingroup$
Interesting. I'd expect "$k$ sets" to mean that $k$ is the number of sets, and I'd expect "$k$-sets" to mean sets of size $k$. Still wondering what $k$-sets you're referring to; there is no $k$ anywhere else on the page. Wild guess: is $k=(n-1)/2$??
$endgroup$
– bof
Jan 22 at 23:26
|
show 1 more comment
$begingroup$
The question I'm struggling with is given here :
Remove any number and the remaining numbers can be partitioned into two subsets of equal sum; prove all numbers are equal.
The problem is the following :
Supposed I have a list of n real numbers, where n is odd. The list is
constructed such that I can remove any arbitrary number from the list,
and the remaining numbers can be partitioned into two equal-sized
subsets with equal sums. Prove that all numbers in the list are equal.
Here is my problem. I understand neither the paper given here : http://www.math.cmu.edu/~lohp/docs/math/mop2012/combinatorics-black-soln.pdf
nor the answer of @Mike Earnest.
I don't understand those points :
- why would be $Mx=0$ ?
- and $M{bf1}=0$?
- Are you looking in the field given by $text{mod } 2$ ?
- And finally, why since $x$ is a multiple of $1$, does that mean that all weights are equal?
Thanks for the help! I don't know if asking about another answer is allowed on this media, I hope it is not prohibited :)
linear-algebra combinatorics graph-theory proof-explanation
edited Jan 22 at 3:55
bof
52.1k558121
asked Jan 21 at 13:29
Marine GalantinMarine Galantin
860316
$endgroup$
The question I'm struggling with is given here :
Remove any number and the remaining numbers can be partitioned into two subsets of equal sum; prove all numbers are equal.
The problem is the following :
Supposed I have a list of n real numbers, where n is odd. The list is
constructed such that I can remove any arbitrary number from the list,
and the remaining numbers can be partitioned into two equal-sized
subsets with equal sums. Prove that all numbers in the list are equal.
Here is my problem. I understand neither the paper given here : http://www.math.cmu.edu/~lohp/docs/math/mop2012/combinatorics-black-soln.pdf
nor the answer of @Mike Earnest.
I don't understand those points :
- why would be $Mx=0$ ?
- and $M{bf1}=0$?
- Are you looking in the field given by $text{mod } 2$ ?
- And finally, why since $x$ is a multiple of $1$, does that mean that all weights are equal?
Thanks for the help! I don't know if asking about another answer is allowed on this media, I hope it is not prohibited :)
linear-algebra combinatorics graph-theory proof-explanation
linear-algebra combinatorics graph-theory proof-explanation
edited Jan 22 at 3:55
bof
52.1k558121
asked Jan 21 at 13:29
Marine GalantinMarine Galantin
860316
edited Jan 22 at 3:55
bof
52.1k558121
asked Jan 21 at 13:29
Marine GalantinMarine Galantin
860316
edited Jan 22 at 3:55
bof
52.1k558121
edited Jan 22 at 3:55
bof
52.1k558121
edited Jan 22 at 3:55
bof
52.1k558121
52.1k558121
asked Jan 21 at 13:29
Marine GalantinMarine Galantin
860316
asked Jan 21 at 13:29
Marine GalantinMarine Galantin
860316
asked Jan 21 at 13:29
Marine GalantinMarine Galantin
860316
860316
$begingroup$
$Mx$ being 0 expresses the fact that the two subsets have the same sum. $M1$ being 0 expresses the fact that the two subsets have the same size.
$endgroup$
– Simon
Jan 21 at 13:45
$begingroup$
The same question was asked here with several answers. Personally I thought my answer was the clearest, though it didn't get any votes.
$endgroup$
– bof
Jan 22 at 3:52
$begingroup$
What does the "$k$ sets" in your question title refer to? What is $k$?
$endgroup$
– bof
Jan 22 at 4:39
$begingroup$
@bof math.stackexchange.com/questions/3080450/… It means a set of size $k$
$endgroup$
– Marine Galantin
Jan 22 at 22:57
$begingroup$
Interesting. I'd expect "$k$ sets" to mean that $k$ is the number of sets, and I'd expect "$k$-sets" to mean sets of size $k$. Still wondering what $k$-sets you're referring to; there is no $k$ anywhere else on the page. Wild guess: is $k=(n-1)/2$??
$endgroup$
– bof
Jan 22 at 23:26
|
show 1 more comment
$begingroup$
$Mx$ being 0 expresses the fact that the two subsets have the same sum. $M1$ being 0 expresses the fact that the two subsets have the same size.
$endgroup$
– Simon
Jan 21 at 13:45
$begingroup$
The same question was asked here with several answers. Personally I thought my answer was the clearest, though it didn't get any votes.
$endgroup$
– bof
Jan 22 at 3:52
$begingroup$
What does the "$k$ sets" in your question title refer to? What is $k$?
$endgroup$
– bof
Jan 22 at 4:39
$begingroup$
@bof math.stackexchange.com/questions/3080450/… It means a set of size $k$
$endgroup$
– Marine Galantin
Jan 22 at 22:57
$begingroup$
Interesting. I'd expect "$k$ sets" to mean that $k$ is the number of sets, and I'd expect "$k$-sets" to mean sets of size $k$. Still wondering what $k$-sets you're referring to; there is no $k$ anywhere else on the page. Wild guess: is $k=(n-1)/2$??
$endgroup$
– bof
Jan 22 at 23:26
$begingroup$
$Mx$ being 0 expresses the fact that the two subsets have the same sum. $M1$ being 0 expresses the fact that the two subsets have the same size.
$endgroup$
– Simon
Jan 21 at 13:45
$begingroup$
$Mx$ being 0 expresses the fact that the two subsets have the same sum. $M1$ being 0 expresses the fact that the two subsets have the same size.
$endgroup$
– Simon
Jan 21 at 13:45
$begingroup$
The same question was asked here with several answers. Personally I thought my answer was the clearest, though it didn't get any votes.
$endgroup$
– bof
Jan 22 at 3:52
$begingroup$
The same question was asked here with several answers. Personally I thought my answer was the clearest, though it didn't get any votes.
$endgroup$
– bof
Jan 22 at 3:52
$begingroup$
What does the "$k$ sets" in your question title refer to? What is $k$?
$endgroup$
– bof
Jan 22 at 4:39
$begingroup$
What does the "$k$ sets" in your question title refer to? What is $k$?
$endgroup$
– bof
Jan 22 at 4:39
$begingroup$
@bof math.stackexchange.com/questions/3080450/… It means a set of size $k$
$endgroup$
– Marine Galantin
Jan 22 at 22:57
$begingroup$
@bof math.stackexchange.com/questions/3080450/… It means a set of size $k$
$endgroup$
– Marine Galantin
Jan 22 at 22:57
$begingroup$
Interesting. I'd expect "$k$ sets" to mean that $k$ is the number of sets, and I'd expect "$k$-sets" to mean sets of size $k$. Still wondering what $k$-sets you're referring to; there is no $k$ anywhere else on the page. Wild guess: is $k=(n-1)/2$??
$endgroup$
– bof
Jan 22 at 23:26
$begingroup$
Interesting. I'd expect "$k$ sets" to mean that $k$ is the number of sets, and I'd expect "$k$-sets" to mean sets of size $k$. Still wondering what $k$-sets you're referring to; there is no $k$ anywhere else on the page. Wild guess: is $k=(n-1)/2$??
$endgroup$
– bof
Jan 22 at 23:26
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
As in the linked answer, for each $i$ let $P_i$ and $Q_i$ be disjoint sets whose union equals ${1,ldots,n}backslash{i}$, and $M$ the matrix described there.
Let's write out what matrix equations $M{bf x}=0$ and $M{bf1}=0$ mean; the $i$-th coordinate of $M{bf x}$ is given by
$$M_i{bf x}=sum_{j=1}^nM_{ij}x_j=sum_{jin P_i}x_j-sum_{jin Q_i}x_j,$$
which equals $0$ precisely when the subset sums of $P_i$ and $Q_i$ are equal. So $M{bf x}=0$ is equivalent to the subset sums of $P_i$ and $Q_i$ being equal for each $i$. Similarly, the $i$-th coordinate of $M{bf1}$ is given by
$$M_i{bf1}=sum_{j=1}^nM_{ij}=sum_{jin P_i}1-sum_{jin Q_i}1=|P_i|-|Q_i|,$$
which equals $0$ precisely when the subsets $P_i$ and $Q_i$ are the same size.
So $M{bf1}=0$ is equivalent to $|P_i|=|Q_i|$ for each $i$.
This shows that the problem translates to linear algebra as follows:
Given a vector $x=(x_1,ldots,x_n)inBbb{R}^n$ where $n$ is odd. Show that if there exists an $ntimes n$-matrix $M$, with entries from ${-1,0,1}$ and $M_{ij}=0$ if and only if $i=j$, satisfying $M{bf 1}=0$ and $M{bf x}=0$, then $x$ is a scalar multiple of ${bf 1}$.
The last statement, that $x$ is a multiple of ${bf1}$, is the same as saying that all the $x_i$ are equal; after all, if $x_1=x_2=ldots=x_n$ then ${bf x}=x_1cdot{bf1}$.
To prove this, the linked answer shows that $dimker M=1$. Because ${bf x}$ and ${bf1}$ are both contained in $ker M$, it follows that ${bf x}$ is a scalar multiple of ${bf1}$.
answered Jan 21 at 15:03
ServaesServaes
25.8k33996
$endgroup$
1
$begingroup$
I would love to get some additional graph Theory... couldn't we say that $M$ is the adjacency matrix of an orientation of the complete graph, i.e. of a tournament? Now, do we know the multiplicity of the $0$ eigenvalue of such matrix? we would be done wouldn't we?
$endgroup$
– Thomas Lesgourgues
Jan 21 at 15:59
1
$begingroup$
Indeed $M$ is the adjacency graph of an orientation of $K_{n+1}$. The dimension of the kernel of the Laplacian $L=M^{top}M$ is equal to the number of connected components of $K_{n+1}$, which is of course $1$, so indeed this finishes the proof quite nicely.
$endgroup$
– Servaes
Jan 21 at 16:15
$begingroup$
really nice observation and commentary. Thank you very much !
$endgroup$
– Marine Galantin
Jan 21 at 21:41
add a comment |
Your Answer
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%2f3081884%2fcombinatorics-problem-on-k-sets-and-partionning-a-set-of-numbers-understanding%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
As in the linked answer, for each $i$ let $P_i$ and $Q_i$ be disjoint sets whose union equals ${1,ldots,n}backslash{i}$, and $M$ the matrix described there.
Let's write out what matrix equations $M{bf x}=0$ and $M{bf1}=0$ mean; the $i$-th coordinate of $M{bf x}$ is given by
$$M_i{bf x}=sum_{j=1}^nM_{ij}x_j=sum_{jin P_i}x_j-sum_{jin Q_i}x_j,$$
which equals $0$ precisely when the subset sums of $P_i$ and $Q_i$ are equal. So $M{bf x}=0$ is equivalent to the subset sums of $P_i$ and $Q_i$ being equal for each $i$. Similarly, the $i$-th coordinate of $M{bf1}$ is given by
$$M_i{bf1}=sum_{j=1}^nM_{ij}=sum_{jin P_i}1-sum_{jin Q_i}1=|P_i|-|Q_i|,$$
which equals $0$ precisely when the subsets $P_i$ and $Q_i$ are the same size.
So $M{bf1}=0$ is equivalent to $|P_i|=|Q_i|$ for each $i$.
This shows that the problem translates to linear algebra as follows:
Given a vector $x=(x_1,ldots,x_n)inBbb{R}^n$ where $n$ is odd. Show that if there exists an $ntimes n$-matrix $M$, with entries from ${-1,0,1}$ and $M_{ij}=0$ if and only if $i=j$, satisfying $M{bf 1}=0$ and $M{bf x}=0$, then $x$ is a scalar multiple of ${bf 1}$.
The last statement, that $x$ is a multiple of ${bf1}$, is the same as saying that all the $x_i$ are equal; after all, if $x_1=x_2=ldots=x_n$ then ${bf x}=x_1cdot{bf1}$.
To prove this, the linked answer shows that $dimker M=1$. Because ${bf x}$ and ${bf1}$ are both contained in $ker M$, it follows that ${bf x}$ is a scalar multiple of ${bf1}$.
answered Jan 21 at 15:03
ServaesServaes
25.8k33996
$endgroup$
1
$begingroup$
I would love to get some additional graph Theory... couldn't we say that $M$ is the adjacency matrix of an orientation of the complete graph, i.e. of a tournament? Now, do we know the multiplicity of the $0$ eigenvalue of such matrix? we would be done wouldn't we?
$endgroup$
– Thomas Lesgourgues
Jan 21 at 15:59
1
$begingroup$
Indeed $M$ is the adjacency graph of an orientation of $K_{n+1}$. The dimension of the kernel of the Laplacian $L=M^{top}M$ is equal to the number of connected components of $K_{n+1}$, which is of course $1$, so indeed this finishes the proof quite nicely.
$endgroup$
– Servaes
Jan 21 at 16:15
$begingroup$
really nice observation and commentary. Thank you very much !
$endgroup$
– Marine Galantin
Jan 21 at 21:41
add a comment |
$begingroup$
As in the linked answer, for each $i$ let $P_i$ and $Q_i$ be disjoint sets whose union equals ${1,ldots,n}backslash{i}$, and $M$ the matrix described there.
Let's write out what matrix equations $M{bf x}=0$ and $M{bf1}=0$ mean; the $i$-th coordinate of $M{bf x}$ is given by
$$M_i{bf x}=sum_{j=1}^nM_{ij}x_j=sum_{jin P_i}x_j-sum_{jin Q_i}x_j,$$
which equals $0$ precisely when the subset sums of $P_i$ and $Q_i$ are equal. So $M{bf x}=0$ is equivalent to the subset sums of $P_i$ and $Q_i$ being equal for each $i$. Similarly, the $i$-th coordinate of $M{bf1}$ is given by
$$M_i{bf1}=sum_{j=1}^nM_{ij}=sum_{jin P_i}1-sum_{jin Q_i}1=|P_i|-|Q_i|,$$
which equals $0$ precisely when the subsets $P_i$ and $Q_i$ are the same size.
So $M{bf1}=0$ is equivalent to $|P_i|=|Q_i|$ for each $i$.
This shows that the problem translates to linear algebra as follows:
Given a vector $x=(x_1,ldots,x_n)inBbb{R}^n$ where $n$ is odd. Show that if there exists an $ntimes n$-matrix $M$, with entries from ${-1,0,1}$ and $M_{ij}=0$ if and only if $i=j$, satisfying $M{bf 1}=0$ and $M{bf x}=0$, then $x$ is a scalar multiple of ${bf 1}$.
The last statement, that $x$ is a multiple of ${bf1}$, is the same as saying that all the $x_i$ are equal; after all, if $x_1=x_2=ldots=x_n$ then ${bf x}=x_1cdot{bf1}$.
To prove this, the linked answer shows that $dimker M=1$. Because ${bf x}$ and ${bf1}$ are both contained in $ker M$, it follows that ${bf x}$ is a scalar multiple of ${bf1}$.
answered Jan 21 at 15:03
ServaesServaes
25.8k33996
$endgroup$
1
$begingroup$
I would love to get some additional graph Theory... couldn't we say that $M$ is the adjacency matrix of an orientation of the complete graph, i.e. of a tournament? Now, do we know the multiplicity of the $0$ eigenvalue of such matrix? we would be done wouldn't we?
$endgroup$
– Thomas Lesgourgues
Jan 21 at 15:59
1
$begingroup$
Indeed $M$ is the adjacency graph of an orientation of $K_{n+1}$. The dimension of the kernel of the Laplacian $L=M^{top}M$ is equal to the number of connected components of $K_{n+1}$, which is of course $1$, so indeed this finishes the proof quite nicely.
$endgroup$
– Servaes
Jan 21 at 16:15
$begingroup$
really nice observation and commentary. Thank you very much !
$endgroup$
– Marine Galantin
Jan 21 at 21:41
add a comment |
$begingroup$
As in the linked answer, for each $i$ let $P_i$ and $Q_i$ be disjoint sets whose union equals ${1,ldots,n}backslash{i}$, and $M$ the matrix described there.
Let's write out what matrix equations $M{bf x}=0$ and $M{bf1}=0$ mean; the $i$-th coordinate of $M{bf x}$ is given by
$$M_i{bf x}=sum_{j=1}^nM_{ij}x_j=sum_{jin P_i}x_j-sum_{jin Q_i}x_j,$$
which equals $0$ precisely when the subset sums of $P_i$ and $Q_i$ are equal. So $M{bf x}=0$ is equivalent to the subset sums of $P_i$ and $Q_i$ being equal for each $i$. Similarly, the $i$-th coordinate of $M{bf1}$ is given by
$$M_i{bf1}=sum_{j=1}^nM_{ij}=sum_{jin P_i}1-sum_{jin Q_i}1=|P_i|-|Q_i|,$$
which equals $0$ precisely when the subsets $P_i$ and $Q_i$ are the same size.
So $M{bf1}=0$ is equivalent to $|P_i|=|Q_i|$ for each $i$.
This shows that the problem translates to linear algebra as follows:
Given a vector $x=(x_1,ldots,x_n)inBbb{R}^n$ where $n$ is odd. Show that if there exists an $ntimes n$-matrix $M$, with entries from ${-1,0,1}$ and $M_{ij}=0$ if and only if $i=j$, satisfying $M{bf 1}=0$ and $M{bf x}=0$, then $x$ is a scalar multiple of ${bf 1}$.
The last statement, that $x$ is a multiple of ${bf1}$, is the same as saying that all the $x_i$ are equal; after all, if $x_1=x_2=ldots=x_n$ then ${bf x}=x_1cdot{bf1}$.
To prove this, the linked answer shows that $dimker M=1$. Because ${bf x}$ and ${bf1}$ are both contained in $ker M$, it follows that ${bf x}$ is a scalar multiple of ${bf1}$.
answered Jan 21 at 15:03
ServaesServaes
25.8k33996
$endgroup$
As in the linked answer, for each $i$ let $P_i$ and $Q_i$ be disjoint sets whose union equals ${1,ldots,n}backslash{i}$, and $M$ the matrix described there.
Let's write out what matrix equations $M{bf x}=0$ and $M{bf1}=0$ mean; the $i$-th coordinate of $M{bf x}$ is given by
$$M_i{bf x}=sum_{j=1}^nM_{ij}x_j=sum_{jin P_i}x_j-sum_{jin Q_i}x_j,$$
which equals $0$ precisely when the subset sums of $P_i$ and $Q_i$ are equal. So $M{bf x}=0$ is equivalent to the subset sums of $P_i$ and $Q_i$ being equal for each $i$. Similarly, the $i$-th coordinate of $M{bf1}$ is given by
$$M_i{bf1}=sum_{j=1}^nM_{ij}=sum_{jin P_i}1-sum_{jin Q_i}1=|P_i|-|Q_i|,$$
which equals $0$ precisely when the subsets $P_i$ and $Q_i$ are the same size.
So $M{bf1}=0$ is equivalent to $|P_i|=|Q_i|$ for each $i$.
This shows that the problem translates to linear algebra as follows:
Given a vector $x=(x_1,ldots,x_n)inBbb{R}^n$ where $n$ is odd. Show that if there exists an $ntimes n$-matrix $M$, with entries from ${-1,0,1}$ and $M_{ij}=0$ if and only if $i=j$, satisfying $M{bf 1}=0$ and $M{bf x}=0$, then $x$ is a scalar multiple of ${bf 1}$.
The last statement, that $x$ is a multiple of ${bf1}$, is the same as saying that all the $x_i$ are equal; after all, if $x_1=x_2=ldots=x_n$ then ${bf x}=x_1cdot{bf1}$.
To prove this, the linked answer shows that $dimker M=1$. Because ${bf x}$ and ${bf1}$ are both contained in $ker M$, it follows that ${bf x}$ is a scalar multiple of ${bf1}$.
answered Jan 21 at 15:03
ServaesServaes
25.8k33996
answered Jan 21 at 15:03
ServaesServaes
25.8k33996
answered Jan 21 at 15:03
ServaesServaes
25.8k33996
answered Jan 21 at 15:03
ServaesServaes
25.8k33996
25.8k33996
1
$begingroup$
I would love to get some additional graph Theory... couldn't we say that $M$ is the adjacency matrix of an orientation of the complete graph, i.e. of a tournament? Now, do we know the multiplicity of the $0$ eigenvalue of such matrix? we would be done wouldn't we?
$endgroup$
– Thomas Lesgourgues
Jan 21 at 15:59
1
$begingroup$
Indeed $M$ is the adjacency graph of an orientation of $K_{n+1}$. The dimension of the kernel of the Laplacian $L=M^{top}M$ is equal to the number of connected components of $K_{n+1}$, which is of course $1$, so indeed this finishes the proof quite nicely.
$endgroup$
– Servaes
Jan 21 at 16:15
$begingroup$
really nice observation and commentary. Thank you very much !
$endgroup$
– Marine Galantin
Jan 21 at 21:41
add a comment |
1
$begingroup$
I would love to get some additional graph Theory... couldn't we say that $M$ is the adjacency matrix of an orientation of the complete graph, i.e. of a tournament? Now, do we know the multiplicity of the $0$ eigenvalue of such matrix? we would be done wouldn't we?
$endgroup$
– Thomas Lesgourgues
Jan 21 at 15:59
1
$begingroup$
Indeed $M$ is the adjacency graph of an orientation of $K_{n+1}$. The dimension of the kernel of the Laplacian $L=M^{top}M$ is equal to the number of connected components of $K_{n+1}$, which is of course $1$, so indeed this finishes the proof quite nicely.
$endgroup$
– Servaes
Jan 21 at 16:15
$begingroup$
really nice observation and commentary. Thank you very much !
$endgroup$
– Marine Galantin
Jan 21 at 21:41
1
1
$begingroup$
I would love to get some additional graph Theory... couldn't we say that $M$ is the adjacency matrix of an orientation of the complete graph, i.e. of a tournament? Now, do we know the multiplicity of the $0$ eigenvalue of such matrix? we would be done wouldn't we?
$endgroup$
– Thomas Lesgourgues
Jan 21 at 15:59
$begingroup$
I would love to get some additional graph Theory... couldn't we say that $M$ is the adjacency matrix of an orientation of the complete graph, i.e. of a tournament? Now, do we know the multiplicity of the $0$ eigenvalue of such matrix? we would be done wouldn't we?
$endgroup$
– Thomas Lesgourgues
Jan 21 at 15:59
1
1
$begingroup$
Indeed $M$ is the adjacency graph of an orientation of $K_{n+1}$. The dimension of the kernel of the Laplacian $L=M^{top}M$ is equal to the number of connected components of $K_{n+1}$, which is of course $1$, so indeed this finishes the proof quite nicely.
$endgroup$
– Servaes
Jan 21 at 16:15
$begingroup$
Indeed $M$ is the adjacency graph of an orientation of $K_{n+1}$. The dimension of the kernel of the Laplacian $L=M^{top}M$ is equal to the number of connected components of $K_{n+1}$, which is of course $1$, so indeed this finishes the proof quite nicely.
$endgroup$
– Servaes
Jan 21 at 16:15
$begingroup$
really nice observation and commentary. Thank you very much !
$endgroup$
– Marine Galantin
Jan 21 at 21:41
$begingroup$
really nice observation and commentary. Thank you very much !
$endgroup$
– Marine Galantin
Jan 21 at 21:41
add a comment |
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%2f3081884%2fcombinatorics-problem-on-k-sets-and-partionning-a-set-of-numbers-understanding%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
$begingroup$
$Mx$ being 0 expresses the fact that the two subsets have the same sum. $M1$ being 0 expresses the fact that the two subsets have the same size.
$endgroup$
– Simon
Jan 21 at 13:45
$begingroup$
The same question was asked here with several answers. Personally I thought my answer was the clearest, though it didn't get any votes.
$endgroup$
– bof
Jan 22 at 3:52
$begingroup$
What does the "$k$ sets" in your question title refer to? What is $k$?
$endgroup$
– bof
Jan 22 at 4:39
$begingroup$
@bof math.stackexchange.com/questions/3080450/… It means a set of size $k$
$endgroup$
– Marine Galantin
Jan 22 at 22:57
$begingroup$
Interesting. I'd expect "$k$ sets" to mean that $k$ is the number of sets, and I'd expect "$k$-sets" to mean sets of size $k$. Still wondering what $k$-sets you're referring to; there is no $k$ anywhere else on the page. Wild guess: is $k=(n-1)/2$??
$endgroup$
– bof
Jan 22 at 23:26