# Show that there is a star for which there are less stars in its column than in its row.

In a table there are n columns and m rows, n > m. Some cells are marked by stars, and in each column there's at least one star. Show that there is a star for which there are less stars in its column than in its row.

-
What level of formalism is expected? What is the context? The result is completely obvious, so to submit an acceptable 'proof', knowing this would help. – gnometorule Feb 28 '13 at 13:41
The result doesn't seem that obvious to me. Can you show me an informal proof? – muzzlator Feb 28 '13 at 13:44
the same goes here. and as much as formalism that you can. – user64370 Feb 28 '13 at 15:25
@muzzlator: This sounded a bit glib, for which I apologize. I meant (and still think) that this I'd obvious when you look at it; but this doesn't mean a proof is (it is not). I have one though, and am typing this up. – gnometorule Feb 28 '13 at 16:35

First,

$\underline{Note}$: If the result holds for a matrix $A^{m, m +k}:=B$, it holds for $A^{m, m+k + 1}:=C$, for $k \ge 1$, the same matrix $B$ with a column added.

This is obvious: there is at least one row-column combination in $B$ where the result holds. Adding one or more stars in a new column cannot change this.

So, wlog, one can assume in what follows that the matrix is of form $$A \in M^{m, m+1}.$$ Note next that the sum of stars $r_i$ in row $i$ and the sum of stars $r^j$ in column $j$ must satisfy.  $$\sum_{i = 1}^m r_i = \sum_{j=1}^{m+1} r^j \quad (1),$$ and that, by construction, $$r^j \geq 1 \text{ for all j} \quad (2).$$ Now, assume to the contrary that the claim is wrong.  Then  $$r_i \leq r^i \text{ for all i} \quad (3)$$ But then:   \begin{align} \sum_{j=1}^{m+1} r^j & = r^{m+1} + \sum_{j=1}^m r^j \\ & \geq r^{m+1} + \sum_{i=1}^m r_i \quad \text{using (3)} \\ & \gt \sum_{i=1}^m r_i \quad \text{using (2), } \\ \end{align} which contradicts (1). So there is at least one $i$ for which (3) is false, which was to be shown.

Edit (03/04): See Macavity's comment below for how to complete the argument (thank you!).

-
I'm a bit confused about how this proof works, why is equation $(3)$ the claim? It doesn't say that the stars have to belong to the diagonal of the matrix which is almost what $(3)$ is saying? – muzzlator Mar 1 '13 at 3:14
@muzzlator: You're right, it's a bit careless. To be perfectly precise, you need to link a column with a specific row thar has an entry in the column. It gets less elegant, but it goes through in essence. – gnometorule Mar 1 '13 at 3:47
now i'm confuse.. – user64370 Mar 1 '13 at 7:18
@user64370: Thos shows there's a row that has more stars than its corresponding column, which I remembered was to be shown. But this is only exactly the same to what you ask if $a_{i,i}$ has a star, so needs a little extension. – gnometorule Mar 1 '13 at 14:09
@gnometorule In the interests of completing this argument, you could note that whether the matrix satisfies the condition or not is invariant to (1) removing all empty rows (2) re-ordering of columns (or rows). Thus it is sufficient to consider an $m$ by $(m+1)$ matrix with non-empty rows (and columns); and by reordering columns, one can always have an equivalent matrix with stars in all $a_{i, i}$. Your argument then applies. – Macavity Mar 4 '13 at 4:49

While completing @gnometorule's argument was easier, I thought the following approach is also worth mentioning:

Let $S(i, j)$ denote a function which gives $1$ if there is a star in cell from column $i$ and row $j$, and $0$ otherwise. Then we have,

$\sum_{i, j} S(i, j) = X$, the total number of stars.

Also if $C_i$ denotes the number of stars in column $i$ and $R_j$ denotes the number of stars in row $j$, we have
$\sum_{i=1}^n C_i = \sum_{j=1}^m R_j = X$

Further, it can be noted that $\sum_j S(i,j) = C_i$ and $\sum_i S(i,j) = R_j$

If all starred cells $(i, j)$ are such that $C_i \ge R_j$, then summing over all cells we have:
$\sum_{i, j} (C_i - R_j) S(i, j) \ge 0$

$\implies \sum_{i, j} C_i S(i, j) \ge \sum_{i, j} R_j S(i, j)$

$\implies \sum_{i} C_i C_i \ge \sum_{j} R_j R_j$

$\implies \sum_{i=1}^n C_i^2 \ge \sum_{j=1}^m R_j^2$

Now, I believe the above inequality is not possible for such column and row sums, i.e. if:
$0 < C_i \le m$ and $0 \le R_j \le n$ with $n > m$, but have not been able to prove it.

-