Saturday 25 August 2018

analysis - Monotone Function on n-tuples




I have a function $f: M_k \to R$, where $M_k \subset \{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 $M_k$, that is:



$\forall (x_1, \dots, x_n),(y_1, \dots, y_n) \in M_k:\\ (x_1, \dots, x_n) <(y_1, \dots, y_n) \Rightarrow f((x_1, \dots, x_n)) < f((y_1, \dots, y_n))$



Here, $(x_1, \dots, x_n) < (y_1, \dots, y_n)$ holds iff $x_i \leq y_i \; \forall 1 \leq i \leq n$ and $\exists j: x_j < y_j$.



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




Any tuple with $x_i < y_i$ must have another element with $x_j > y_j$, because each tuple has exactly $k$ entries that are 1?



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



Thanks in advance!


Answer



Claim: Given two distinct $n$-tuples, $\mathbf{x}=(x_1,\dots,x_n)$ and $\mathbf{y}=(y_1,\dots,y_n),$ with exactly $k$ entries equal to $1$ and the rest $0,$ where $1\le k< 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 $(x_1,\dots,x_n)\not<(y_1,\dots,y_n).$




Proof: If there does not exist a $j$ such that $x_jy_{\ell},$ making the condition $(\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 $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...