Mixing
“Decomposability†of system of linear constraints
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
This question is with reference to this proof of the Birkhoff-von Neumann theorem.
Consider the polytope:
$mathcalB =xin [0,1]^N: Ax=v$
where $A$ is a matrix and $v$ is a vector, both with elements in $-1,0,1$ only. (In case of the linked proof $mathcalB$ is the Birkhoff polytope, $A$ is the set of bistochastic constraints and $v$ is a vector of $1$'s.)
The idea of the aforementioned proof is to show that if for any $x in mathcalB$, any of its elements is in $(0,1)$, then there exists a vector $mathcalI in -1,0,1^N, mathcalI neq 0$, (in case of the Birkhoff polytope $mathcalI in 0,1^N$) and $epsilon > 0$ such that $x+epsilonmathcalI, x-epsilonmathcalI subset mathcalB$. This is achieved by showing that in case of the Birkhoff polytope, the system of equalities is such that any graph constructed by taking one variable from each equality constraint is balanced. Hence the extreme points of the polytope $mathcalB$ are integral. The part about taking exactly one variable from each equality is important because we consider the "worst case" i.e. the case where all the other variables of each equation are in $0,1$.
Now let us apply this idea to a general polytope $mathcalB$, as defined previously. Following the above logic we see that the aforementioned condition -i.e. any graph constructed by taking one variable from each equality constraint being balanced - is a sufficient condition for the extreme points of $mathcalB$ to be integral. My question is, is it also a necessary condition for a general $mathcalB subseteq [0,1]^N$, constrained by only linear equality constraints, as defined earlier? If not, what conditions on $A$ and $v$ are needed (in addition to the condition already mentioned, i.e. the elements of $A$ and $v$ are in $-1,0,1$) for this condition to be both necessary and sufficient?
My attempt so far is just to follow the same argument as in the proof, backwards. That is, if there exists some unbalanced graph constructed taking one variable from each equality constraint at a time, that means there exists a cycle: say $a_1 - a_2 - cdots - a_K - a_1$ such that when $a_1,cdots, a_K in (0,1)$ and $a_1$ is increased by $epsilon$ - going by the intermediate equalities - $a_K$ decreases by $epsilon$. But there exists some other equality such that such a decrease in $a_K$ causes a decrease in $a_1$, not an increase. In other words, combining several equalities which constrain $mathcalB$, we can construct two equations as follows:
$a_1 + a_k = a_i_1+cdots+a_i_n-a_i_n+1-cdots-a_i_m$
$a_1 - a_k = a_j_1+cdots+a_j_k-a_j_k+1-cdots-a_k_l$
Hence we get:
$a_1 = frac12[a_j_1+cdots+a_j_M-a_j_M+1-cdots-a_j_L]$
Hence there exists some pattern of $0$'s and $1$'s among $a_j_1,cdots,a_j_M$ (e.g. $a_j_1=1, a_j_2=0,cdots,a_j_L=0$) such that $a_1$ is fractional. The part I'm not sure about is - does there always exist such a combination of $0$'s and $1$'s of other variables which is feasible (going by other equality constraints)?
Thank you for your help.
graph-theory polyhedra
edited Jul 26 at 9:44
Bill Wallis
1,7811821
asked Jul 24 at 17:21
Canine360
19614
add a comment |Â
up vote
0
down vote
favorite
This question is with reference to this proof of the Birkhoff-von Neumann theorem.
Consider the polytope:
$mathcalB =xin [0,1]^N: Ax=v$
where $A$ is a matrix and $v$ is a vector, both with elements in $-1,0,1$ only. (In case of the linked proof $mathcalB$ is the Birkhoff polytope, $A$ is the set of bistochastic constraints and $v$ is a vector of $1$'s.)
The idea of the aforementioned proof is to show that if for any $x in mathcalB$, any of its elements is in $(0,1)$, then there exists a vector $mathcalI in -1,0,1^N, mathcalI neq 0$, (in case of the Birkhoff polytope $mathcalI in 0,1^N$) and $epsilon > 0$ such that $x+epsilonmathcalI, x-epsilonmathcalI subset mathcalB$. This is achieved by showing that in case of the Birkhoff polytope, the system of equalities is such that any graph constructed by taking one variable from each equality constraint is balanced. Hence the extreme points of the polytope $mathcalB$ are integral. The part about taking exactly one variable from each equality is important because we consider the "worst case" i.e. the case where all the other variables of each equation are in $0,1$.
Now let us apply this idea to a general polytope $mathcalB$, as defined previously. Following the above logic we see that the aforementioned condition -i.e. any graph constructed by taking one variable from each equality constraint being balanced - is a sufficient condition for the extreme points of $mathcalB$ to be integral. My question is, is it also a necessary condition for a general $mathcalB subseteq [0,1]^N$, constrained by only linear equality constraints, as defined earlier? If not, what conditions on $A$ and $v$ are needed (in addition to the condition already mentioned, i.e. the elements of $A$ and $v$ are in $-1,0,1$) for this condition to be both necessary and sufficient?
My attempt so far is just to follow the same argument as in the proof, backwards. That is, if there exists some unbalanced graph constructed taking one variable from each equality constraint at a time, that means there exists a cycle: say $a_1 - a_2 - cdots - a_K - a_1$ such that when $a_1,cdots, a_K in (0,1)$ and $a_1$ is increased by $epsilon$ - going by the intermediate equalities - $a_K$ decreases by $epsilon$. But there exists some other equality such that such a decrease in $a_K$ causes a decrease in $a_1$, not an increase. In other words, combining several equalities which constrain $mathcalB$, we can construct two equations as follows:
$a_1 + a_k = a_i_1+cdots+a_i_n-a_i_n+1-cdots-a_i_m$
$a_1 - a_k = a_j_1+cdots+a_j_k-a_j_k+1-cdots-a_k_l$
Hence we get:
$a_1 = frac12[a_j_1+cdots+a_j_M-a_j_M+1-cdots-a_j_L]$
Hence there exists some pattern of $0$'s and $1$'s among $a_j_1,cdots,a_j_M$ (e.g. $a_j_1=1, a_j_2=0,cdots,a_j_L=0$) such that $a_1$ is fractional. The part I'm not sure about is - does there always exist such a combination of $0$'s and $1$'s of other variables which is feasible (going by other equality constraints)?
Thank you for your help.
graph-theory polyhedra
edited Jul 26 at 9:44
Bill Wallis
1,7811821
asked Jul 24 at 17:21
Canine360
19614
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
This question is with reference to this proof of the Birkhoff-von Neumann theorem.
Consider the polytope:
$mathcalB =xin [0,1]^N: Ax=v$
where $A$ is a matrix and $v$ is a vector, both with elements in $-1,0,1$ only. (In case of the linked proof $mathcalB$ is the Birkhoff polytope, $A$ is the set of bistochastic constraints and $v$ is a vector of $1$'s.)
The idea of the aforementioned proof is to show that if for any $x in mathcalB$, any of its elements is in $(0,1)$, then there exists a vector $mathcalI in -1,0,1^N, mathcalI neq 0$, (in case of the Birkhoff polytope $mathcalI in 0,1^N$) and $epsilon > 0$ such that $x+epsilonmathcalI, x-epsilonmathcalI subset mathcalB$. This is achieved by showing that in case of the Birkhoff polytope, the system of equalities is such that any graph constructed by taking one variable from each equality constraint is balanced. Hence the extreme points of the polytope $mathcalB$ are integral. The part about taking exactly one variable from each equality is important because we consider the "worst case" i.e. the case where all the other variables of each equation are in $0,1$.
Now let us apply this idea to a general polytope $mathcalB$, as defined previously. Following the above logic we see that the aforementioned condition -i.e. any graph constructed by taking one variable from each equality constraint being balanced - is a sufficient condition for the extreme points of $mathcalB$ to be integral. My question is, is it also a necessary condition for a general $mathcalB subseteq [0,1]^N$, constrained by only linear equality constraints, as defined earlier? If not, what conditions on $A$ and $v$ are needed (in addition to the condition already mentioned, i.e. the elements of $A$ and $v$ are in $-1,0,1$) for this condition to be both necessary and sufficient?
My attempt so far is just to follow the same argument as in the proof, backwards. That is, if there exists some unbalanced graph constructed taking one variable from each equality constraint at a time, that means there exists a cycle: say $a_1 - a_2 - cdots - a_K - a_1$ such that when $a_1,cdots, a_K in (0,1)$ and $a_1$ is increased by $epsilon$ - going by the intermediate equalities - $a_K$ decreases by $epsilon$. But there exists some other equality such that such a decrease in $a_K$ causes a decrease in $a_1$, not an increase. In other words, combining several equalities which constrain $mathcalB$, we can construct two equations as follows:
$a_1 + a_k = a_i_1+cdots+a_i_n-a_i_n+1-cdots-a_i_m$
$a_1 - a_k = a_j_1+cdots+a_j_k-a_j_k+1-cdots-a_k_l$
Hence we get:
$a_1 = frac12[a_j_1+cdots+a_j_M-a_j_M+1-cdots-a_j_L]$
Hence there exists some pattern of $0$'s and $1$'s among $a_j_1,cdots,a_j_M$ (e.g. $a_j_1=1, a_j_2=0,cdots,a_j_L=0$) such that $a_1$ is fractional. The part I'm not sure about is - does there always exist such a combination of $0$'s and $1$'s of other variables which is feasible (going by other equality constraints)?
Thank you for your help.
graph-theory polyhedra
edited Jul 26 at 9:44
Bill Wallis
1,7811821
asked Jul 24 at 17:21
Canine360
19614
This question is with reference to this proof of the Birkhoff-von Neumann theorem.
Consider the polytope:
$mathcalB =xin [0,1]^N: Ax=v$
where $A$ is a matrix and $v$ is a vector, both with elements in $-1,0,1$ only. (In case of the linked proof $mathcalB$ is the Birkhoff polytope, $A$ is the set of bistochastic constraints and $v$ is a vector of $1$'s.)
The idea of the aforementioned proof is to show that if for any $x in mathcalB$, any of its elements is in $(0,1)$, then there exists a vector $mathcalI in -1,0,1^N, mathcalI neq 0$, (in case of the Birkhoff polytope $mathcalI in 0,1^N$) and $epsilon > 0$ such that $x+epsilonmathcalI, x-epsilonmathcalI subset mathcalB$. This is achieved by showing that in case of the Birkhoff polytope, the system of equalities is such that any graph constructed by taking one variable from each equality constraint is balanced. Hence the extreme points of the polytope $mathcalB$ are integral. The part about taking exactly one variable from each equality is important because we consider the "worst case" i.e. the case where all the other variables of each equation are in $0,1$.
Now let us apply this idea to a general polytope $mathcalB$, as defined previously. Following the above logic we see that the aforementioned condition -i.e. any graph constructed by taking one variable from each equality constraint being balanced - is a sufficient condition for the extreme points of $mathcalB$ to be integral. My question is, is it also a necessary condition for a general $mathcalB subseteq [0,1]^N$, constrained by only linear equality constraints, as defined earlier? If not, what conditions on $A$ and $v$ are needed (in addition to the condition already mentioned, i.e. the elements of $A$ and $v$ are in $-1,0,1$) for this condition to be both necessary and sufficient?
My attempt so far is just to follow the same argument as in the proof, backwards. That is, if there exists some unbalanced graph constructed taking one variable from each equality constraint at a time, that means there exists a cycle: say $a_1 - a_2 - cdots - a_K - a_1$ such that when $a_1,cdots, a_K in (0,1)$ and $a_1$ is increased by $epsilon$ - going by the intermediate equalities - $a_K$ decreases by $epsilon$. But there exists some other equality such that such a decrease in $a_K$ causes a decrease in $a_1$, not an increase. In other words, combining several equalities which constrain $mathcalB$, we can construct two equations as follows:
$a_1 + a_k = a_i_1+cdots+a_i_n-a_i_n+1-cdots-a_i_m$
$a_1 - a_k = a_j_1+cdots+a_j_k-a_j_k+1-cdots-a_k_l$
Hence we get:
$a_1 = frac12[a_j_1+cdots+a_j_M-a_j_M+1-cdots-a_j_L]$
Hence there exists some pattern of $0$'s and $1$'s among $a_j_1,cdots,a_j_M$ (e.g. $a_j_1=1, a_j_2=0,cdots,a_j_L=0$) such that $a_1$ is fractional. The part I'm not sure about is - does there always exist such a combination of $0$'s and $1$'s of other variables which is feasible (going by other equality constraints)?
Thank you for your help.
graph-theory polyhedra
edited Jul 26 at 9:44
Bill Wallis
1,7811821
asked Jul 24 at 17:21
Canine360
19614
edited Jul 26 at 9:44
Bill Wallis
1,7811821
edited Jul 26 at 9:44
Bill Wallis
1,7811821
edited Jul 26 at 9:44
Bill Wallis
1,7811821
1,7811821
asked Jul 24 at 17:21
Canine360
19614
asked Jul 24 at 17:21
Canine360
19614
asked Jul 24 at 17:21
Canine360
19614
19614
add a comment |Â
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2861575%2fdecomposability-of-system-of-linear-constraints%23new-answer', 'question_page');
);
Post as a guest
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
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
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