# Maximum of sum is at most the sum of maxima

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.

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

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)$
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.