In an $n\times(n+1)$ nonnegative matrix, there is a positive pivot at which the row sum is greater than the column sum 
Let $A$ be a matrix of shape $n\times (n+1)$ with non-negative real entries, which has at least one positive entry in each column. Show that there is an $a_{ij} > 0$ such that the sum over the $i$-th row is higher than sum over the $j$-th column.

I found this exercise in a book about combinatorics and algebra. Thus, I tried methods known from linear algebra and combinatorics to solve this problem. My main approaches are:
I use induction on $n$ and assume the opposite in the induction step, i.e. that for all $a_{ij} > 0$ the sum over the $i$-th row is less than or equal to the sum over the $j$-th column. Now, I observed that if there is a $a_{ij} > 0$ such that the sum over the $i$-th row is equal to the sum over the $j$-th row, then the matrix gained by deleting the $i$-th row and $j$-th column does still fulfill the prerequests. Finally, by doing this step as often as possible, we obtain a matrix such that if $a_{ij} > 0$, then the sum over the $i$-th row is less than the sum over $j$-th column or in the other case, can conclude a contraction since the matrix has the shape $0 \times 1$. Then, I tried to conclude a contradiction also for the first case, which I can't do.
 A: By permuting the rows and columns of $A$, we may assume that the matrix has descending row sums $r_1\ge r_2\ge\cdots\ge r_n$ and descending column sums $c_1\ge c_2\ge\cdots\ge c_{n+1}$. Now consider the following condition:
$$
a_{ij}=0 \text{ whenever } r_i>c_j.\tag{1}
$$
Assume for the moment that it is true. There are two possibilities:

*

*$r_i\le c_{i+1}$ for every $i$. Then $\sum_{i=1}^nr_i\le\sum_{i=1}^nc_{i+1}=\sum_{j=2}^{n+1}c_j$. It follows that the first column of $A$ is zero, which is a contradiction to the assumption that each column of $A$ contains a positive entry.

*$r_k>c_{k+1}$ for some $k$. Among all such indices $k$, we pick the largest one. Then $r_1\ge\cdots\ge r_k>c_{k+1}\ge\cdots\ge c_n$ and condition $(1)$ implies that
$$
a_{ij}=0 \text{ for all } i\le k \text{ and } j\ge k+1.\tag{2}
$$
Hence $k<n$, or else the last column of $A$ will be zero, which is a contradiction. Since $k$ is the largest possible index such that $r_k>c_{k+1}$, we have $r_i\le c_{i+1}$ for all $i>k$. In turn,
$$
\sum_{j>k+1}c_j
=\sum_{i>k}c_{i+1}
\ge\sum_{i>k}r_i
\color{red}{\ge}\sum_{i>k}\sum_{j>k+1}a_{ij}
=\sum_{j>k+1}\sum_{i>k}a_{ij}
\stackrel{\text{by } (2)}{=}\sum_{j>k+1}\sum_{i=1}^na_{ij}
=\sum_{j>k+1}c_j.
$$
Thus equality holds in the second inequality above. That is,
$$
a_{ij}=0 \text{ for all } i>k \text{ and } j\le k+1.\tag{3}
$$
But then $(2)$ and $(3)$ imply that the $(k+1)$-th column of $A$ is zero, which is a contradiction.

Hence condition $(1)$ does not hold. Since $r_1\ge\frac{1}{n}\sum_{i,j}a_{ij}>\frac{1}{n+1}\sum_{i,j}a_{ij}\ge c_n$, the set $\{(i,j): r_i>c_j\}$ is non-empty. The falseness of $(1)$ thus implies that $a_{ij}>0$ and $r_i>c_j$ for some $(i,j)$.
A: @Mick: you're right. That's the exercise.
@user1551: Thanks a lot for the answer. Unfortunately, I observed that my approach was wrong. I cannot assume in general that if for any a_ij > 0 in A the sum over the i-th row is less than or equal to the sum over the j-th column, then this property still holds after deleting the k-th row and the l-th column with a_kl > 0 in the gained matrix. Due to my fault, your prove only works if the matrix A itself has already the property that for any a_ij > 0, the sum over the i-th row is less than the sum over the j-th column.
For the other case, i.e. there is an a_ij in A such that the sum over the i-th row is higher than the sum over the j-th column, I would delete this i-th row and the j-th column. Now, by the use of the induction hypothesis we can conclude the existence of a certain a_kl > 0 such that the sum over the k-th row is higher than the sum over the l-th column. Now, I cannot induce the statement from that point since the entry a_ij doesn't necessarily has the property in A. I thought of splitting the matrix A into a matrix n x n and a vector n. But I doubt that this is the right way.
