I am trying to do the following problem:
Let $p, m, n$ be positive integers. Determine the number of m by n matrices with entries from the set ${1,2,...,p}$ which have the property that the sum of the elements in each row and each column is not divisible by $p$.
I attempted to do it as follows:
We denote by $M$ the set of $m$ by $n$ matrices with entries from the set ${1,2,...,p}$. Let $A_i$ be the subset of $M$ formed by the matrices in which the sum of elements in the ith row is divisible by $p$ and $B_j$ the subset of M consisting of matrices in which the sum of elements in the jth column is divisible by p. The desired number is:
$N=|M|-\big| (\bigcup\limits_{i=1}^m A_i) \cup(\bigcup\limits_{i=1}^n B_i) \big|$ and this is about where I got stuck. I am fairly certain that this question can be solved with PIE, however I don't know how to do it. Could you please help me solve this question with PIE?
To count $\big| (\bigcup\limits_{i=1}^m A_i) \cup(\bigcup\limits_{i=1}^n B_i) \big|$, you would first add up $|A_1|+\dots+|A_m|+|B_1+\dots+|B_n|$, then you would subtract all pairwise of intersections, like $|A_i\cap A_j|$, $|B_i\cap B_j|$, and $|A_i\cap B_j|$.
To find $A_1$, note that most of the entries of the matrix can be chosen totally freely. The only time the constraint comes in is when choosing the last entry of the first row; you will have exactly one choice for this entry. Therefore, $|A_1|=p^{mn-1}$. Same for all other $|A_i|$, and $|B_j|$.
To find $|A_i\cap A_j|$, there are now two rows constrained to have sum $0\pmod p$. This means that there will be two entries whose choices are forced, so $|A_i\cap A_j|=p^{mn-2}$, as all other entries are free. As it turns out, same goes for $|A_i\cap B_j|$.
In fact, this nice pattern holds for almost the entire principle of inclusion-exclusion. The triple intersections are counted by $p^{mn-3}$, the quadruples are counted by $p^{mn-4}$, etc, regardless of the mix of row and column constraints. The only exception is the very last intersection of all the sets, $|A_1\cap \dots A_n\cap B_1\cap \dots \cap B_n|$. Even there are $m+n$ constraints, the constraints are not all "independent": knowing that the row sums are all zero and that all but one of the columns sums are zero implies the last column is zero automatically. Therefore, this last intersection is counted by $p^{mn-m-n+1}$.
All that remains is too put this all together. You will find that the result almost looks like binomial theorem, and with some twiddling, you can get a closed form for the answer with no summations.