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) + \dots + \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:
$$\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. \tag{1}$$
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 + \dots + b_k$. Then there exist nonnegative real numbers $a_1, a_2, \dots, a_k$ such that $a_1 + a_2 + \dots + 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
$$\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)) \\ \geq p_1 - \min(p_1, q_1) = p_1 - q_1.$$
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$

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$