Combinatorics problem on k sets and partionning a set of numbers, understanding of the proof












3












$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







share|cite|improve this question











$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
















3












$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







share|cite|improve this question











$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














3












3








3


1



$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







share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 22 at 3:55









bof

52.1k558121




52.1k558121










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


















  • $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










1 Answer
1






active

oldest

votes


















2












$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}$.






share|cite|improve this answer









$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











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
});


}
});














draft saved

draft discarded


















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









2












$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}$.






share|cite|improve this answer









$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
















2












$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}$.






share|cite|improve this answer









$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














2












2








2





$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}$.






share|cite|improve this answer









$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}$.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










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














  • 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


















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







-

Popular posts from this blog

Mario Kart Wii

Image
Please consider supporting The Cutting Room Floor on Patreon. Thanks for all your support! Mario Kart Wii From The Cutting Room Floor Jump to: navigation, search Mario Kart Wii Developer : Nintendo Publisher : Nintendo Platform : Wii Released in JP : April 10, 2008 Released in US : April 27, 2008 Released in EU : April 11, 2008 Released in AU : April 24, 2008 Released in KR : April 30, 2009 This game has unused animations. This game has unused areas. This game has unused code. This game has unused objects. This game has unused modes / minigames. This game has unused graphics. This game has unused models. This game has unused items. This game has unused music. This game has regional differences. This game has a notes page This game has a prerelease article Mario Kart Wii is the sixth game in the series (not counting Arcade editions), which intro...
Read more

The Binding of Isaac: Rebirth/Afterbirth

Image
Please consider supporting The Cutting Room Floor on Patreon. Thanks for all your support! The Binding of Isaac: Rebirth/Afterbirth From The Cutting Room Floor < The Binding of Isaac: Rebirth Jump to: navigation, search This is a sub-page of The Binding of Isaac: Rebirth . Afterbirth is the first expansion pack for Rebirth and features a variety of improvements. Contents 1 Unused Graphics 1.1 Old Man Keeper 1.2 Skinless Hush 1.3 Miscellaneous Unused Hush Sprites 1.4 Generosity achievement 1.5 Afterbirth+ Room Editor 1.6 Bearded Ultra Greed 1.7 Early Ultra Greed 1.8 Unused Brownie Expression 1.9 Frail's Spinning Head 1.10 Mom's Dead Hand Alt 2 Unused Audio 2.1 Unused Dead Womb Layer 2.2 Unused Hush Battle Outro 2.3 The Stain Grunt Unused Graphics Old Man Keeper Image file: gfxuimain me...
Read more

What does “Dominus providebit” mean?

Image
5 Does "Dominus providebit" mean "The Lord will provide" or "The Lord provides"? I once had a bit of an argument with a guy who studied Latin over that. It's an inscription that appears on the rim of some old Swiss coins that I have. meaning latin-to-english-translation grammar-identification share | improve this question edited Jan 18 at 15:27 V2Blast 105 4 asked Jan 17 at 22:49 Donald K. Donald K. 26 1 ...
Read more