Linear constraint equivalent to one-to-oneness
$begingroup$
Suppose that $A$ is a finite set with cardinality $n$. Let $phi$ be a one-to-one function from $A$ to ${1,2,dots,n}$. I am wondering if it is possible to write the one-to-oneness condition on $phi$ to an equivalent linear equality (or inequality) constraint on $phi$. Any help is greatly appreciated.
real-analysis calculus optimization
asked Jan 17 at 6:40
KumaraKumara
221118
$endgroup$
add a comment |
$begingroup$
Suppose that $A$ is a finite set with cardinality $n$. Let $phi$ be a one-to-one function from $A$ to ${1,2,dots,n}$. I am wondering if it is possible to write the one-to-oneness condition on $phi$ to an equivalent linear equality (or inequality) constraint on $phi$. Any help is greatly appreciated.
real-analysis calculus optimization
asked Jan 17 at 6:40
KumaraKumara
221118
$endgroup$
1
$begingroup$
Are binary variables acceptable?
$endgroup$
– LinAlg
Jan 20 at 22:26
add a comment |
$begingroup$
Suppose that $A$ is a finite set with cardinality $n$. Let $phi$ be a one-to-one function from $A$ to ${1,2,dots,n}$. I am wondering if it is possible to write the one-to-oneness condition on $phi$ to an equivalent linear equality (or inequality) constraint on $phi$. Any help is greatly appreciated.
real-analysis calculus optimization
asked Jan 17 at 6:40
KumaraKumara
221118
$endgroup$
Suppose that $A$ is a finite set with cardinality $n$. Let $phi$ be a one-to-one function from $A$ to ${1,2,dots,n}$. I am wondering if it is possible to write the one-to-oneness condition on $phi$ to an equivalent linear equality (or inequality) constraint on $phi$. Any help is greatly appreciated.
real-analysis calculus optimization
real-analysis calculus optimization
asked Jan 17 at 6:40
KumaraKumara
221118
asked Jan 17 at 6:40
KumaraKumara
221118
asked Jan 17 at 6:40
KumaraKumara
221118
asked Jan 17 at 6:40
KumaraKumara
221118
asked Jan 17 at 6:40
KumaraKumara
221118
221118
1
$begingroup$
Are binary variables acceptable?
$endgroup$
– LinAlg
Jan 20 at 22:26
add a comment |
1
$begingroup$
Are binary variables acceptable?
$endgroup$
– LinAlg
Jan 20 at 22:26
1
1
$begingroup$
Are binary variables acceptable?
$endgroup$
– LinAlg
Jan 20 at 22:26
$begingroup$
Are binary variables acceptable?
$endgroup$
– LinAlg
Jan 20 at 22:26
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
The answer to your question is NO. In fact it already fails for $n=2$. In this case, $A=lbrace a_1,a_2 rbrace $ and there are exactly two one-to-one functions $A to lbrace 1,2 rbrace $, namely $phi_1$ defined by $phi_1(a_1)=1,phi_1(a_2)=2$ and $phi_2$ defined by $phi_2(a_1)=2,phi_2(a_2)=1$.
Now, suppose a set of linear constraints is satisfied by both $phi_1$ and $phi_2$. Because the constraints are linear, they will still be satisfied by any linear combination of $phi_1$ and $phi_2$ with nonnegative coefficients. In particular, they will be satisfied by the mean $frac{phi_1+phi_2}{2}$ which is constant equal to $1$ and therefore not one-to-one.
Similarly, for arbitrary $n$ there are $n!$ different one-to-one functions $A to lbrace 1,2,ldots,n rbrace $ and their (scaled) mean, i.e. their sum divided by $n$, is constant equal to $1$.
answered Jan 20 at 6:17
Ewan DelanoyEwan Delanoy
42k443104
$endgroup$
add a comment |
$begingroup$
A bijection from A to S = { 1,2,.. n } usually it isn't linear.
How could it be if A, for example, were a set of open sets?
Even if A were a set of integers,
how could there be a linear bijection from { x$^2$ : x in S } to S?
answered Jan 17 at 7:43
William ElliotWilliam Elliot
9,1812820
$endgroup$
$begingroup$
I am not asking if $phi$ is linear; some linear constraint on $phi$. Something like $sum_x F(phi(x)) = k$ for some function $F$ and some constant $k$.
$endgroup$
– Kumara
Jan 17 at 9:19
$begingroup$
@Kumara. Yes. Let k = n and F is constant function 1 or k = 0 and F the constant function 0.
$endgroup$
– William Elliot
Jan 18 at 0:01
$begingroup$
Please understand the question properly. I am asking a condition on $phi$ $equivalent$ to one-to-oneness.
$endgroup$
– Kumara
Jan 18 at 4:10
add a comment |
Your Answer
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%2f3076660%2flinear-constraint-equivalent-to-one-to-oneness%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The answer to your question is NO. In fact it already fails for $n=2$. In this case, $A=lbrace a_1,a_2 rbrace $ and there are exactly two one-to-one functions $A to lbrace 1,2 rbrace $, namely $phi_1$ defined by $phi_1(a_1)=1,phi_1(a_2)=2$ and $phi_2$ defined by $phi_2(a_1)=2,phi_2(a_2)=1$.
Now, suppose a set of linear constraints is satisfied by both $phi_1$ and $phi_2$. Because the constraints are linear, they will still be satisfied by any linear combination of $phi_1$ and $phi_2$ with nonnegative coefficients. In particular, they will be satisfied by the mean $frac{phi_1+phi_2}{2}$ which is constant equal to $1$ and therefore not one-to-one.
Similarly, for arbitrary $n$ there are $n!$ different one-to-one functions $A to lbrace 1,2,ldots,n rbrace $ and their (scaled) mean, i.e. their sum divided by $n$, is constant equal to $1$.
answered Jan 20 at 6:17
Ewan DelanoyEwan Delanoy
42k443104
$endgroup$
add a comment |
$begingroup$
The answer to your question is NO. In fact it already fails for $n=2$. In this case, $A=lbrace a_1,a_2 rbrace $ and there are exactly two one-to-one functions $A to lbrace 1,2 rbrace $, namely $phi_1$ defined by $phi_1(a_1)=1,phi_1(a_2)=2$ and $phi_2$ defined by $phi_2(a_1)=2,phi_2(a_2)=1$.
Now, suppose a set of linear constraints is satisfied by both $phi_1$ and $phi_2$. Because the constraints are linear, they will still be satisfied by any linear combination of $phi_1$ and $phi_2$ with nonnegative coefficients. In particular, they will be satisfied by the mean $frac{phi_1+phi_2}{2}$ which is constant equal to $1$ and therefore not one-to-one.
Similarly, for arbitrary $n$ there are $n!$ different one-to-one functions $A to lbrace 1,2,ldots,n rbrace $ and their (scaled) mean, i.e. their sum divided by $n$, is constant equal to $1$.
answered Jan 20 at 6:17
Ewan DelanoyEwan Delanoy
42k443104
$endgroup$
add a comment |
$begingroup$
The answer to your question is NO. In fact it already fails for $n=2$. In this case, $A=lbrace a_1,a_2 rbrace $ and there are exactly two one-to-one functions $A to lbrace 1,2 rbrace $, namely $phi_1$ defined by $phi_1(a_1)=1,phi_1(a_2)=2$ and $phi_2$ defined by $phi_2(a_1)=2,phi_2(a_2)=1$.
Now, suppose a set of linear constraints is satisfied by both $phi_1$ and $phi_2$. Because the constraints are linear, they will still be satisfied by any linear combination of $phi_1$ and $phi_2$ with nonnegative coefficients. In particular, they will be satisfied by the mean $frac{phi_1+phi_2}{2}$ which is constant equal to $1$ and therefore not one-to-one.
Similarly, for arbitrary $n$ there are $n!$ different one-to-one functions $A to lbrace 1,2,ldots,n rbrace $ and their (scaled) mean, i.e. their sum divided by $n$, is constant equal to $1$.
answered Jan 20 at 6:17
Ewan DelanoyEwan Delanoy
42k443104
$endgroup$
The answer to your question is NO. In fact it already fails for $n=2$. In this case, $A=lbrace a_1,a_2 rbrace $ and there are exactly two one-to-one functions $A to lbrace 1,2 rbrace $, namely $phi_1$ defined by $phi_1(a_1)=1,phi_1(a_2)=2$ and $phi_2$ defined by $phi_2(a_1)=2,phi_2(a_2)=1$.
Now, suppose a set of linear constraints is satisfied by both $phi_1$ and $phi_2$. Because the constraints are linear, they will still be satisfied by any linear combination of $phi_1$ and $phi_2$ with nonnegative coefficients. In particular, they will be satisfied by the mean $frac{phi_1+phi_2}{2}$ which is constant equal to $1$ and therefore not one-to-one.
Similarly, for arbitrary $n$ there are $n!$ different one-to-one functions $A to lbrace 1,2,ldots,n rbrace $ and their (scaled) mean, i.e. their sum divided by $n$, is constant equal to $1$.
answered Jan 20 at 6:17
Ewan DelanoyEwan Delanoy
42k443104
answered Jan 20 at 6:17
Ewan DelanoyEwan Delanoy
42k443104
answered Jan 20 at 6:17
Ewan DelanoyEwan Delanoy
42k443104
answered Jan 20 at 6:17
Ewan DelanoyEwan Delanoy
42k443104
42k443104
add a comment |
add a comment |
$begingroup$
A bijection from A to S = { 1,2,.. n } usually it isn't linear.
How could it be if A, for example, were a set of open sets?
Even if A were a set of integers,
how could there be a linear bijection from { x$^2$ : x in S } to S?
answered Jan 17 at 7:43
William ElliotWilliam Elliot
9,1812820
$endgroup$
$begingroup$
I am not asking if $phi$ is linear; some linear constraint on $phi$. Something like $sum_x F(phi(x)) = k$ for some function $F$ and some constant $k$.
$endgroup$
– Kumara
Jan 17 at 9:19
$begingroup$
@Kumara. Yes. Let k = n and F is constant function 1 or k = 0 and F the constant function 0.
$endgroup$
– William Elliot
Jan 18 at 0:01
$begingroup$
Please understand the question properly. I am asking a condition on $phi$ $equivalent$ to one-to-oneness.
$endgroup$
– Kumara
Jan 18 at 4:10
add a comment |
$begingroup$
A bijection from A to S = { 1,2,.. n } usually it isn't linear.
How could it be if A, for example, were a set of open sets?
Even if A were a set of integers,
how could there be a linear bijection from { x$^2$ : x in S } to S?
answered Jan 17 at 7:43
William ElliotWilliam Elliot
9,1812820
$endgroup$
$begingroup$
I am not asking if $phi$ is linear; some linear constraint on $phi$. Something like $sum_x F(phi(x)) = k$ for some function $F$ and some constant $k$.
$endgroup$
– Kumara
Jan 17 at 9:19
$begingroup$
@Kumara. Yes. Let k = n and F is constant function 1 or k = 0 and F the constant function 0.
$endgroup$
– William Elliot
Jan 18 at 0:01
$begingroup$
Please understand the question properly. I am asking a condition on $phi$ $equivalent$ to one-to-oneness.
$endgroup$
– Kumara
Jan 18 at 4:10
add a comment |
$begingroup$
A bijection from A to S = { 1,2,.. n } usually it isn't linear.
How could it be if A, for example, were a set of open sets?
Even if A were a set of integers,
how could there be a linear bijection from { x$^2$ : x in S } to S?
answered Jan 17 at 7:43
William ElliotWilliam Elliot
9,1812820
$endgroup$
A bijection from A to S = { 1,2,.. n } usually it isn't linear.
How could it be if A, for example, were a set of open sets?
Even if A were a set of integers,
how could there be a linear bijection from { x$^2$ : x in S } to S?
answered Jan 17 at 7:43
William ElliotWilliam Elliot
9,1812820
answered Jan 17 at 7:43
William ElliotWilliam Elliot
9,1812820
answered Jan 17 at 7:43
William ElliotWilliam Elliot
9,1812820
answered Jan 17 at 7:43
William ElliotWilliam Elliot
9,1812820
9,1812820
$begingroup$
I am not asking if $phi$ is linear; some linear constraint on $phi$. Something like $sum_x F(phi(x)) = k$ for some function $F$ and some constant $k$.
$endgroup$
– Kumara
Jan 17 at 9:19
$begingroup$
@Kumara. Yes. Let k = n and F is constant function 1 or k = 0 and F the constant function 0.
$endgroup$
– William Elliot
Jan 18 at 0:01
$begingroup$
Please understand the question properly. I am asking a condition on $phi$ $equivalent$ to one-to-oneness.
$endgroup$
– Kumara
Jan 18 at 4:10
add a comment |
$begingroup$
I am not asking if $phi$ is linear; some linear constraint on $phi$. Something like $sum_x F(phi(x)) = k$ for some function $F$ and some constant $k$.
$endgroup$
– Kumara
Jan 17 at 9:19
$begingroup$
@Kumara. Yes. Let k = n and F is constant function 1 or k = 0 and F the constant function 0.
$endgroup$
– William Elliot
Jan 18 at 0:01
$begingroup$
Please understand the question properly. I am asking a condition on $phi$ $equivalent$ to one-to-oneness.
$endgroup$
– Kumara
Jan 18 at 4:10
$begingroup$
I am not asking if $phi$ is linear; some linear constraint on $phi$. Something like $sum_x F(phi(x)) = k$ for some function $F$ and some constant $k$.
$endgroup$
– Kumara
Jan 17 at 9:19
$begingroup$
I am not asking if $phi$ is linear; some linear constraint on $phi$. Something like $sum_x F(phi(x)) = k$ for some function $F$ and some constant $k$.
$endgroup$
– Kumara
Jan 17 at 9:19
$begingroup$
@Kumara. Yes. Let k = n and F is constant function 1 or k = 0 and F the constant function 0.
$endgroup$
– William Elliot
Jan 18 at 0:01
$begingroup$
@Kumara. Yes. Let k = n and F is constant function 1 or k = 0 and F the constant function 0.
$endgroup$
– William Elliot
Jan 18 at 0:01
$begingroup$
Please understand the question properly. I am asking a condition on $phi$ $equivalent$ to one-to-oneness.
$endgroup$
– Kumara
Jan 18 at 4:10
$begingroup$
Please understand the question properly. I am asking a condition on $phi$ $equivalent$ to one-to-oneness.
$endgroup$
– Kumara
Jan 18 at 4:10
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%2f3076660%2flinear-constraint-equivalent-to-one-to-oneness%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
1
$begingroup$
Are binary variables acceptable?
$endgroup$
– LinAlg
Jan 20 at 22:26