Maximum of sum is at most the sum of maxima

Question

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.

Answer 1

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

Answer 2

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.