What are the facets of the Birkhoff Polytope when $n=2$?

Clash Royale CLAN TAG#URR8PPP

up vote
5
down vote

favorite

I've read in several sources that the number of facets of the Birkhoff polytope $mathcalB(n)$ is $n^2$.

Is this supposed to hold when $n=2$? Since $mathcalB(2)$ has dimension $1$, the facets would be the two $0$-dimensional vertices, which are the two permutation matrices below:
$$beginpmatrix
1 & 0 \ 0 &1
endpmatrix text and beginpmatrix
0 & 1 \ 1 &0
endpmatrix$$
However, the claim is that there should be $2^2 = 4$ facets. None of my sources have given any restriction on $n$. What am I missing?

discrete-mathematics polytopes

share|cite|improve this question

edited Jul 21 at 23:21

asked Jul 21 at 21:03

M47145

3,20131029

add a comment | 

up vote
5
down vote

favorite

I've read in several sources that the number of facets of the Birkhoff polytope $mathcalB(n)$ is $n^2$.

Is this supposed to hold when $n=2$? Since $mathcalB(2)$ has dimension $1$, the facets would be the two $0$-dimensional vertices, which are the two permutation matrices below:
$$beginpmatrix
1 & 0 \ 0 &1
endpmatrix text and beginpmatrix
0 & 1 \ 1 &0
endpmatrix$$
However, the claim is that there should be $2^2 = 4$ facets. None of my sources have given any restriction on $n$. What am I missing?

discrete-mathematics polytopes

share|cite|improve this question

edited Jul 21 at 23:21

asked Jul 21 at 21:03

M47145

3,20131029

add a comment | 

up vote
5
down vote

favorite

up vote
5
down vote

favorite

I've read in several sources that the number of facets of the Birkhoff polytope $mathcalB(n)$ is $n^2$.

Is this supposed to hold when $n=2$? Since $mathcalB(2)$ has dimension $1$, the facets would be the two $0$-dimensional vertices, which are the two permutation matrices below:
$$beginpmatrix
1 & 0 \ 0 &1
endpmatrix text and beginpmatrix
0 & 1 \ 1 &0
endpmatrix$$
However, the claim is that there should be $2^2 = 4$ facets. None of my sources have given any restriction on $n$. What am I missing?

discrete-mathematics polytopes

share|cite|improve this question

edited Jul 21 at 23:21

asked Jul 21 at 21:03

M47145

3,20131029

I've read in several sources that the number of facets of the Birkhoff polytope $mathcalB(n)$ is $n^2$.

Is this supposed to hold when $n=2$? Since $mathcalB(2)$ has dimension $1$, the facets would be the two $0$-dimensional vertices, which are the two permutation matrices below:
$$beginpmatrix
1 & 0 \ 0 &1
endpmatrix text and beginpmatrix
0 & 1 \ 1 &0
endpmatrix$$
However, the claim is that there should be $2^2 = 4$ facets. None of my sources have given any restriction on $n$. What am I missing?

discrete-mathematics polytopes

share|cite|improve this question

edited Jul 21 at 23:21

asked Jul 21 at 21:03

M47145

3,20131029

share|cite|improve this question

share|cite|improve this question

edited Jul 21 at 23:21

edited Jul 21 at 23:21

edited Jul 21 at 23:21

asked Jul 21 at 21:03

M47145

3,20131029

asked Jul 21 at 21:03

M47145

3,20131029

asked Jul 21 at 21:03

M47145

3,20131029

3,20131029

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
1
down vote



accepted

No, it doesn't apply to $n=2$; your sources (like this one) apparently failed to treat this special case.

The generally $n^2$ facets correspond to the non-negativity constraints for the $n^2$ entries of the matrix. But for $n=2$, the $4$ non-negativity constraints form two pairs of identical constraints if you restrict them to the space defined by the row and column sum constraints: The row and column sum constraints span a $3$-dimensional space and thus leave only a $1$-dimensional space of doubly stochastic matrixes of the form

$$
pmatrixx&1-x\1-x&x;,
$$

in which the non-negativity constraints are pairwise identical on the diagonal and off the diagonal.

So you're right; there are only two facets in this case, defined by $x=0$ and $x=1$, which corresponds to the two matrices you gave.

share|cite|improve this answer

edited Jul 22 at 5:06

answered Jul 22 at 0:37

joriki

164k10180328

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',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

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

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2858882%2fwhat-are-the-facets-of-the-birkhoff-polytope-when-n-2%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
1
down vote



accepted

No, it doesn't apply to $n=2$; your sources (like this one) apparently failed to treat this special case.

The generally $n^2$ facets correspond to the non-negativity constraints for the $n^2$ entries of the matrix. But for $n=2$, the $4$ non-negativity constraints form two pairs of identical constraints if you restrict them to the space defined by the row and column sum constraints: The row and column sum constraints span a $3$-dimensional space and thus leave only a $1$-dimensional space of doubly stochastic matrixes of the form

$$
pmatrixx&1-x\1-x&x;,
$$

in which the non-negativity constraints are pairwise identical on the diagonal and off the diagonal.

So you're right; there are only two facets in this case, defined by $x=0$ and $x=1$, which corresponds to the two matrices you gave.

share|cite|improve this answer

edited Jul 22 at 5:06

answered Jul 22 at 0:37

joriki

164k10180328

add a comment | 

up vote
1
down vote



accepted

No, it doesn't apply to $n=2$; your sources (like this one) apparently failed to treat this special case.

The generally $n^2$ facets correspond to the non-negativity constraints for the $n^2$ entries of the matrix. But for $n=2$, the $4$ non-negativity constraints form two pairs of identical constraints if you restrict them to the space defined by the row and column sum constraints: The row and column sum constraints span a $3$-dimensional space and thus leave only a $1$-dimensional space of doubly stochastic matrixes of the form

$$
pmatrixx&1-x\1-x&x;,
$$

in which the non-negativity constraints are pairwise identical on the diagonal and off the diagonal.

So you're right; there are only two facets in this case, defined by $x=0$ and $x=1$, which corresponds to the two matrices you gave.

share|cite|improve this answer

edited Jul 22 at 5:06

answered Jul 22 at 0:37

joriki

164k10180328

add a comment | 

up vote
1
down vote



accepted

up vote
1
down vote



accepted

No, it doesn't apply to $n=2$; your sources (like this one) apparently failed to treat this special case.

The generally $n^2$ facets correspond to the non-negativity constraints for the $n^2$ entries of the matrix. But for $n=2$, the $4$ non-negativity constraints form two pairs of identical constraints if you restrict them to the space defined by the row and column sum constraints: The row and column sum constraints span a $3$-dimensional space and thus leave only a $1$-dimensional space of doubly stochastic matrixes of the form

$$
pmatrixx&1-x\1-x&x;,
$$

in which the non-negativity constraints are pairwise identical on the diagonal and off the diagonal.

So you're right; there are only two facets in this case, defined by $x=0$ and $x=1$, which corresponds to the two matrices you gave.

share|cite|improve this answer

edited Jul 22 at 5:06

answered Jul 22 at 0:37

joriki

164k10180328

No, it doesn't apply to $n=2$; your sources (like this one) apparently failed to treat this special case.

The generally $n^2$ facets correspond to the non-negativity constraints for the $n^2$ entries of the matrix. But for $n=2$, the $4$ non-negativity constraints form two pairs of identical constraints if you restrict them to the space defined by the row and column sum constraints: The row and column sum constraints span a $3$-dimensional space and thus leave only a $1$-dimensional space of doubly stochastic matrixes of the form

$$
pmatrixx&1-x\1-x&x;,
$$

in which the non-negativity constraints are pairwise identical on the diagonal and off the diagonal.

So you're right; there are only two facets in this case, defined by $x=0$ and $x=1$, which corresponds to the two matrices you gave.

share|cite|improve this answer

edited Jul 22 at 5:06

answered Jul 22 at 0:37

joriki

164k10180328

share|cite|improve this answer

share|cite|improve this answer

edited Jul 22 at 5:06

edited Jul 22 at 5:06

edited Jul 22 at 5:06

answered Jul 22 at 0:37

joriki

164k10180328

answered Jul 22 at 0:37

joriki

164k10180328

answered Jul 22 at 0:37

joriki

164k10180328

164k10180328

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

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

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2858882%2fwhat-are-the-facets-of-the-birkhoff-polytope-when-n-2%23new-answer', 'question_page');

);

Post as a guest

Name Email

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

Name Email

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

Name Email

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

Name Email

Name Email

Name

Email

Name Email

Name

Email