Dgdrxrt

Disable hyphenation for an entire paragraph

What are the pros and cons of Aerospike nosecones?

What makes black pepper strong or mild?

What does the "x" in "x86" represent?

If Jon Snow became King of the Seven Kingdoms what would his regnal number be?

I am not a queen, who am I?

How discoverable are IPv6 addresses and AAAA names by potential attackers?

Is high blood pressure ever a symptom attributable solely to dehydration?

Did Kevin spill real chili?

Sorting numerically

Why is "Captain Marvel" translated as male in Portugal?

Check which numbers satisfy the condition [A*B*C = A! + B! + C!]

When to stop saving and start investing?

Antler Helmet: Can it work?

Why does Python start at index 1 when iterating an array backwards?

Is there a Spanish version of "dot your i's and cross your t's" that includes the letter 'ñ'?

Why is high voltage dangerous?

Is there a service that would inform me whenever a new direct route is scheduled from a given airport?

When is phishing education going too far?

How to draw this diagram using TikZ package?

How do I mention the quality of my school without bragging

Is above average number of years spent on PhD considered a red flag in future academia or industry positions?

Is it true to say that an hosting provider's DNS server is what links the entire hosting environment to ICANN?

What causes the vertical darker bands in my photo?

Question on binary vectors

-1

$begingroup$

Assume $a$ and $b$ are two arbitrary vectors of the same length with binary entries that are not equal (say, $a=[1 0 ... 1 1]^mathrmT$ and $b=[1 1 ... 0 1]^mathrmT$). How can I demonstrate that $$mathrmsum,(a)-2(a^mathrmTb)+mathrmsum,(b)geq 1?$$ This equation is correct. I just need the mathematical proof.

Please be advised it also can written in a different notation. I hope it helps:
$$a^mathrmTa-2(a^mathrmTb)+b^mathrmTbgeq 1?$$which reminds of the polynomial identity: $$(x-y)^2=x^2-2xy+y^2$$

Thank you for your help!

vectors

share|cite|improve this question

edited Apr 1 at 0:49

Mahdi Rouholamini

asked Mar 31 at 23:27

Mahdi RouholaminiMahdi Rouholamini

223

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What do you mean by $a'$? Transpose?
  $endgroup$
  – David Peterson
  Mar 31 at 23:50
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes, it is transpose.
  $endgroup$
  – Mahdi Rouholamini
  Apr 1 at 0:10
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How do you know the equation is correct, if you don't have a proof?
  $endgroup$
  – Gerry Myerson
  Apr 1 at 0:29
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It is a homework. It says the equation is correct.
  $endgroup$
  – Mahdi Rouholamini
  Apr 1 at 0:33
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Do you have any idea how many homework problems are wrong? But this one is OK.
  $endgroup$
  – Gerry Myerson
  Apr 1 at 1:03
  

  
  
  
  

 | 
show 2 more comments

-1

$begingroup$

Assume $a$ and $b$ are two arbitrary vectors of the same length with binary entries that are not equal (say, $a=[1 0 ... 1 1]^mathrmT$ and $b=[1 1 ... 0 1]^mathrmT$). How can I demonstrate that $$mathrmsum,(a)-2(a^mathrmTb)+mathrmsum,(b)geq 1?$$ This equation is correct. I just need the mathematical proof.

Please be advised it also can written in a different notation. I hope it helps:
$$a^mathrmTa-2(a^mathrmTb)+b^mathrmTbgeq 1?$$which reminds of the polynomial identity: $$(x-y)^2=x^2-2xy+y^2$$

Thank you for your help!

vectors

share|cite|improve this question

edited Apr 1 at 0:49

Mahdi Rouholamini

asked Mar 31 at 23:27

Mahdi RouholaminiMahdi Rouholamini

223

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What do you mean by $a'$? Transpose?
  $endgroup$
  – David Peterson
  Mar 31 at 23:50
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes, it is transpose.
  $endgroup$
  – Mahdi Rouholamini
  Apr 1 at 0:10
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How do you know the equation is correct, if you don't have a proof?
  $endgroup$
  – Gerry Myerson
  Apr 1 at 0:29
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It is a homework. It says the equation is correct.
  $endgroup$
  – Mahdi Rouholamini
  Apr 1 at 0:33
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Do you have any idea how many homework problems are wrong? But this one is OK.
  $endgroup$
  – Gerry Myerson
  Apr 1 at 1:03
  

  
  
  
  

 | 
show 2 more comments

$begingroup$

Assume $a$ and $b$ are two arbitrary vectors of the same length with binary entries that are not equal (say, $a=[1 0 ... 1 1]^mathrmT$ and $b=[1 1 ... 0 1]^mathrmT$). How can I demonstrate that $$mathrmsum,(a)-2(a^mathrmTb)+mathrmsum,(b)geq 1?$$ This equation is correct. I just need the mathematical proof.

Please be advised it also can written in a different notation. I hope it helps:
$$a^mathrmTa-2(a^mathrmTb)+b^mathrmTbgeq 1?$$which reminds of the polynomial identity: $$(x-y)^2=x^2-2xy+y^2$$

Thank you for your help!

vectors

share|cite|improve this question

edited Apr 1 at 0:49

Mahdi Rouholamini

asked Mar 31 at 23:27

Mahdi RouholaminiMahdi Rouholamini

223

$endgroup$

share|cite|improve this question

edited Apr 1 at 0:49

Mahdi Rouholamini

asked Mar 31 at 23:27

Mahdi RouholaminiMahdi Rouholamini

223

share|cite|improve this question

edited Apr 1 at 0:49

Mahdi Rouholamini

asked Mar 31 at 23:27

Mahdi RouholaminiMahdi Rouholamini

223

asked Mar 31 at 23:27

Mahdi RouholaminiMahdi Rouholamini

223

asked Mar 31 at 23:27

Mahdi RouholaminiMahdi Rouholamini

223

1 Answer
1

active

oldest

votes

1

$begingroup$

Note that $a^tb$ is the number of coordinates where both $a$ and $b$ have a one. Then $rm sum(a)-a^tb$ is the number of coordinates where $a$ has a one and $b$ doesn't, $rm sum(b)-a^tb$ is the number of coordinates where $b$ has a one and $a$ doesn't, and, since $ane b$, at least one of those two numbers is positive (and neither one is negative). So their sum, which is $rm sum(a)-2a^tb+rm sum(b)$, is at least one.

EDIT: "Algebraic" approach:

$$a^ta-2a^tb+b^tb=(a^ta-a^tb)-(a^tb-b^tb)=a^t(a-b)-(a^t-b^t)b$$ $$=a^t(a-b)-b^t(a-b)=(a^t-b^t)(a-b)=(a-b)^t(a-b)$$

but $(a-b)^t(a-b)ge0$ with equality if and only if $a-b=0$. But we know $ane b$, so $(a-b)^t(a-b)>0$, so $(a-b)^t(a-b)ge1$ and we're done.

share|cite|improve this answer

edited Apr 1 at 1:47

answered Apr 1 at 0:35

Gerry MyersonGerry Myerson

148k8152306

$endgroup$

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



);

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

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3170016%2fquestion-on-binary-vectors%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

Note that $a^tb$ is the number of coordinates where both $a$ and $b$ have a one. Then $rm sum(a)-a^tb$ is the number of coordinates where $a$ has a one and $b$ doesn't, $rm sum(b)-a^tb$ is the number of coordinates where $b$ has a one and $a$ doesn't, and, since $ane b$, at least one of those two numbers is positive (and neither one is negative). So their sum, which is $rm sum(a)-2a^tb+rm sum(b)$, is at least one.

EDIT: "Algebraic" approach:

$$a^ta-2a^tb+b^tb=(a^ta-a^tb)-(a^tb-b^tb)=a^t(a-b)-(a^t-b^t)b$$ $$=a^t(a-b)-b^t(a-b)=(a^t-b^t)(a-b)=(a-b)^t(a-b)$$

but $(a-b)^t(a-b)ge0$ with equality if and only if $a-b=0$. But we know $ane b$, so $(a-b)^t(a-b)>0$, so $(a-b)^t(a-b)ge1$ and we're done.

share|cite|improve this answer

edited Apr 1 at 1:47

answered Apr 1 at 0:35

Gerry MyersonGerry Myerson

148k8152306

$endgroup$

add a comment | 

1

$begingroup$

Note that $a^tb$ is the number of coordinates where both $a$ and $b$ have a one. Then $rm sum(a)-a^tb$ is the number of coordinates where $a$ has a one and $b$ doesn't, $rm sum(b)-a^tb$ is the number of coordinates where $b$ has a one and $a$ doesn't, and, since $ane b$, at least one of those two numbers is positive (and neither one is negative). So their sum, which is $rm sum(a)-2a^tb+rm sum(b)$, is at least one.

EDIT: "Algebraic" approach:

$$a^ta-2a^tb+b^tb=(a^ta-a^tb)-(a^tb-b^tb)=a^t(a-b)-(a^t-b^t)b$$ $$=a^t(a-b)-b^t(a-b)=(a^t-b^t)(a-b)=(a-b)^t(a-b)$$

but $(a-b)^t(a-b)ge0$ with equality if and only if $a-b=0$. But we know $ane b$, so $(a-b)^t(a-b)>0$, so $(a-b)^t(a-b)ge1$ and we're done.

share|cite|improve this answer

edited Apr 1 at 1:47

answered Apr 1 at 0:35

Gerry MyersonGerry Myerson

148k8152306

$endgroup$

add a comment | 

$begingroup$

Note that $a^tb$ is the number of coordinates where both $a$ and $b$ have a one. Then $rm sum(a)-a^tb$ is the number of coordinates where $a$ has a one and $b$ doesn't, $rm sum(b)-a^tb$ is the number of coordinates where $b$ has a one and $a$ doesn't, and, since $ane b$, at least one of those two numbers is positive (and neither one is negative). So their sum, which is $rm sum(a)-2a^tb+rm sum(b)$, is at least one.

EDIT: "Algebraic" approach:

$$a^ta-2a^tb+b^tb=(a^ta-a^tb)-(a^tb-b^tb)=a^t(a-b)-(a^t-b^t)b$$ $$=a^t(a-b)-b^t(a-b)=(a^t-b^t)(a-b)=(a-b)^t(a-b)$$

but $(a-b)^t(a-b)ge0$ with equality if and only if $a-b=0$. But we know $ane b$, so $(a-b)^t(a-b)>0$, so $(a-b)^t(a-b)ge1$ and we're done.

share|cite|improve this answer

edited Apr 1 at 1:47

answered Apr 1 at 0:35

Gerry MyersonGerry Myerson

148k8152306

$endgroup$

share|cite|improve this answer

edited Apr 1 at 1:47

answered Apr 1 at 0:35

Gerry MyersonGerry Myerson

148k8152306

answered Apr 1 at 0:35

Gerry MyersonGerry Myerson

148k8152306

answered Apr 1 at 0:35

Gerry MyersonGerry Myerson

148k8152306