5
$\begingroup$

I'd like to show the following:

$$\max_x \sum_y f(x,y) \le \sum_y \max_x f(x,y)$$

I've also been asked to show the conditions under which the two are equal.

I believe that I'm getting confused by the multiple dimensions. Intuitively, if you take the max over $x$ of $f(x,y)$ and sum over $y$, I know that this will more than likely be greater than the prior, but I'm really stumped on this.

$\endgroup$
  • $\begingroup$ Am I missing something or are the RHS and LHS equal by accident? $\endgroup$ – JMCF125 Apr 4 '14 at 22:08
4
$\begingroup$

Let $x\prime$ be the $x$ which maximizes the LHS. Then, for every term on the RHS you have: $f(x\prime, y) \leq \max_x f(x,y)$

$\endgroup$
6
$\begingroup$

Here's a methodical way to solve the problem.

First, you're trying to show $$ \max_x \text{something} \le \text{something else} $$ This is equivalent to $$ \text{for all $x$,}\quad \text{something}\le\text{something else} $$ So let $x$ be arbitrary and let's show $$ \sum_y f(x,y) \le \sum_y \max_x f(x,y) $$ To avoid confusion, let me change the $x$ on the right, because it's not the same as the $x$ we just chose. $$ \sum_y f(x,y) \le \sum_y \max_z f(z,y) $$ Anyway, to show $\sum_y \text{something} \le \sum_y \text{something else}$, the simplest thing that could possibly work is to show $\text{something}\le\text{something else}$ and then sum over $y$. So let's try that: we want to show $$ f(x,y) \le \max_z f(z,y) $$ And now... well, yes, this is true: the LHS is one of the values considered in the maximum on the RHS, so of course the RHS is larger.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.