China Mathematical Olympiad

We may combine the operations on the same row or column, thus the final result of a series of operations can be realized as subtracting integer $x_i$ from each number of $i$-th row and subtracting integer $y_j$ from each number of $j$-th column. Thus, the matrix $A$ is good if and only if there exist integers $x_i,y_j$, such that $a_{ij}=x_i+y_j$ for all $1\le i,j\le p$.

Since the entries of $A$ are distinct, $x_1,x_2,\dots ,x_p$ are pairwise distinct, and so are $y_1,y_2,\dots ,y_p$. We may consider only the case that $x_1<x_2<\cdots <x_p$ since swapping the value of $x_i$ and $x_j$ results in swapping the $i$-th row and $j$-th row, which is again a good matrix. Similarly, we may consider only the case that $y_1<y_2<\cdots <y_p$, thus the matrix is increasing from left to right, also from top to bottom.

From the assumptions above, we have $a_{11}=1$, $a_{12}$ or $a_{21}$ equals $2$. We may consider only the case that $a_{12}=2$ since the transpose of the matrix is again good. Now we argue by contradiction that the first row is $1,2,\dots ,p$. Assume on the contrary that $1,2,\dots ,k$ is on the first row, but $k+1$ is not, $2\le k<p$, therefore $a_{21}=k+1$. We call $k$ consecutive integers a “block”, and we shall prove that the first row consists of several blocks, that is, the first $k$ numbers is a block, the next $k$ numbers is again a block, and so on.

If it is not so, assume the first $n$ groups of $k$ numbers are “blocks”, but the next $k$ numbers is not a “block” (or there are no $k$ numbers remaining). It follows that for $j=1,2,\dots ,n$,

$y_{(j-1)k+1},y_{(j-1)k+2},\dots ,y_{jk}$ is a "block", the first $nk$ columns of the matrix can be divided into $pn\times k$ submatrices $a_{i,(j-1)k+1},a_{i,(j-1)k+2},\dots ,a_{i,jk}$, $i=1,2,\dots ,p$, $j=1,2,\dots ,n$, each submatrix is a "block". Now assume $a_{1,nk+1}=a$, let $b$ be the smallest positive integer such that $a+b$ is not on the first row, then $b\le k-1$. Since $a_{2,nk+1}-a_{1,nk+1}=x_2-x_1=a_{21}-a_{11}=k$, we have $a_{2,nk+1}=a+k$, therefore $a+b$ lies in the first $nk$ columns. Therefore, $a+b$ is contained in one of the $1\times k$ submatrices mentioned above, which is a "block", however $a,a+k$ are not in this "block", which is a contradiction.

We showed that the first row is formed by blocks, in particular $k\mid p$, however, $1<k<p$, and $p$ is a prime, which is impossible. So we conclude that the first row is $1,2,\dots ,p$, the $k$-th row must be $(k-1)p+1,(k-1)p+2,\dots ,kp$. Thus up to interchanging rows, columns and transpose, the good matrix is unique, the answer is therefore $2(p!{)}^2$.