Saturday, 25 August 2018

analysis - Monotone Function on n-tuples




I have a function f:MkR, where Mk{0,1}n is the set of all n-tuples with exactly k entries that are 1 while the rest is 0.



I wish to show that f is strong monotonically increasing in Mk, that is:



(x1,,xn),(y1,,yn)Mk:(x1,,xn)<(y1,,yn)f((x1,,xn))<f((y1,,yn))



Here, (x1,,xn)<(y1,,yn) holds iff xiyi1in and j:xj<yj.



My problem is that this seems to be undefined since no two distinct tuples can fulfill this.




Any tuple with xi<yi must have another element with xj>yj, because each tuple has exactly k entries that are 1?



Is strong monotonicity even defined in this case or is each function on Mk strongly monotone per default?



Thanks in advance!


Answer



Claim: Given two distinct n-tuples, x=(x1,,xn) and y=(y1,,yn), with exactly k entries equal to 1 and the rest 0, where 1k<n, and given the definition
$$(u_1,\dots,u_n)<(v_1,\dots,v_n) \iff [(\forall\,i)(1\le i\le n)(u_i\le v_i)\;\land\;(\exists\,j)(u_jit follows that (x1,,xn)(y1,,yn).




Proof: If there does not exist a j such that $x_jy_{\ell},makingthecondition(\forall\,i)(1\le i\le n)(x_i\le y_i)false.Hence,\mathbf{x}\not<\mathbf{y}.$


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...