Iranian Mathematical Olympiad

We use the notation $A$ for matrices and $A_{ij}$ for the entry of row $i$ and column $j$.

First, observe that $A_{ii}\le p_i$, since the sum of the $i$th row is $p_i$ and the entries are nonnegative. Similarly, $A_{ii}\le q_i$. Thus, $A_{ii}\le \min (p_i,q_i)$ and it follows that $\text{trace}(A)\le \min (p_1,q_1)+\min (p_2,q_2)+\cdots +\min (p_n,q_n)$. It remains to prove there is a matrix with the property that $A_{ii}=\min (p_i,q_i)$ for every $1\le i\le n$.

We proceed by induction on $n$. The case $n=1$ is obvious, since $p_1=q_1$. Assume the assertion holds for $n=1,2,\dots ,k$ and consider the case $n=k+1$. We can suppose $q_1\le p_1$ without loss of generality. Let $A_{11}=q_1$ and $A_{i1}=0$ for $2\le i\le n$. We claim that there exist nonnegative real numbers ${\beta }_i:=A_{1i}$ for $2\le i\le n$ such that these conditions hold: $$\begin{gathered} \sum _{i=2}^n{\beta }_i=p_1-q_1, \\ {\beta }_i\le q_i-\min (p_i,q_i)\text{ for every }2\le i\le n.\text{\hspace{1em}(1)} \end{gathered}$$ To verify our claim, first we prove a lemma.

Lemma. Let $a,b_1,b_2,\dots ,b_k$ be nonnegative real numbers such that $a\le b_1+b_2+\cdots +b_k$. Then there exist nonnegative real numbers $a_1,a_2,\dots ,a_k$ such that $a_1+a_2+\cdots +a_k=a$ and $a_i\le b_i$ for every $1\le i\le k$.

---

Proof of lemma. We use induction on $k$. For $k=1$ the lemma is obvious. If $b_k>a$, we can set $a_1=a_2=\cdots =a_{k-1}=0$ and $a_k=a$, so suppose that $b_k\le a$. Let $a_k:=b_k$. Now, we must have $a_1+a_2+\cdots +a_{k-1}=a-b_k$. but $a-b_k\le b_1+b_2+\cdots +b_k-b_k=b_1+b_2+\cdots +b_{k-1}$ and the assertion follows by the induction hypothesis. $\square$

We have $$\begin{gathered} \sum _{i=2}^n(q_i-\min (p_i,q_i))=\sum _{i=1}^n(q_i-\min (p_i,q_i))=\sum _{i=1}^n(p_i-\min (p_i,q_i)) \\ \ge p_1-\min (p_1,q_1)=p_1-q_1. \end{gathered}$$ Hence, by the lemma we can find nonnegative real numbers ${\beta }_2,{\beta }_3,\dots ,{\beta }_n$ such that equation 1 holds. Let $A_{1i}={\beta }_i$ for $2\le i\le n$. The remaining entries of $A$ should satisfy

$A_{i2}+A_{i3}+\cdots +A_{in}=p_i$ for $2\le i\le n$, $A_{2i}+A_{3i}+\cdots +A_{ni}=q_i-{\beta }_i$ for $1\le i\le n$.

We have $q_i-{\beta }_i\ge \min (p_i,q_i)$ by equation 1, so $\min (p_i,q_i-{\beta }_i)=\min (p_i,q_i)$. Hence, the rest of the matrix can be filled using the induction hypothesis. $\square$

---

Alternative solution.

We can change the order of $p_1,p_2,\dots ,p_n$ and $q_1,q_2,\dots ,q_n$ arbitrarily by changing corresponding rows and columns of the matrix. So we can suppose $p_1\le q_1,p_2\le q_2,\dots ,p_k\le q_k$ and $p_{k+1}\ge q_{k+1},\dots ,p_n\ge q_n$. Let $A_{ii}=\min (p_i,q_i)$ for $1\le i\le n$. Also let $A_{ij}=0$ if $i\ne j$ and either $i\le k$ or $j>k$. The remaining entries $\{A_{ij}:i>k,j\le k\}$ should satisfy:

$A_{i1}+A_{i2}+\cdots +A_{ik}=p_i-q_i$ for $i>k$, $A_{(k+1)i}+\cdots +A_{ni}=q_i-p_i$ for $i\le k$.

i.e. we should find a matrix with nonnegative entries for the given row sums and column sums. We can construct such a matrix using induction on the number of rows as follows.

By the lemma above, we can find $A_{n1},A_{n2},\dots ,A_{nk}$ such that their sum is $p_n-q_n$ and $A_{ni}\le q_i-p_i$ for each $i\le k$. Then, we delete the $n$'th row and replace $q_i-p_i$ by $q_i-p_i-A_{ni}$ for each $i\le k$. We can proceed by using induction and the desired matrix will be constructed. $\square$