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]^\mathrm{T}$ and $b=[1 1 ... 0 1]^\mathrm{T}$). How can I demonstrate that $$\mathrm{sum}\,(a)-2(a^\mathrm{T}b)+\mathrm{sum}\,(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^\mathrm{T}a-2(a^\mathrm{T}b)+b^\mathrm{T}b\geq 1?$$which reminds of the polynomial identity: $$(x-y)^2=x^2-2xy+y^2$$
Thank you for your help!
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 $a\ne 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 $a\ne b$, so $(a-b)^t(a-b)>0$, so $(a-b)^t(a-b)\ge1$ and we're done.