Key Concepts and Formulas

• Prime Numbers: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
• Permutations with Repetition: The number of ways to arrange $n$ objects where $n_1$ are alike, $n_2$ are alike, ..., $n_k$ are alike is given by $\frac{n!}{n_1! n_2! ... n_k!}$, where $n_1 + n_2 + ... + n_k = n$.
• Combinations with Repetition (Stars and Bars): The number of ways to choose $k$ objects from $n$ types of objects with repetition allowed is given by $\binom{n+k-1}{k}$. However, in this problem, each entry $a_{ij}$ is restricted to the interval $[0,4]$.

Step-by-Step Solution

Step 1: Identify possible prime number sums

The sum of all entries of matrix A is a prime number $p \in (2, 13)$. Therefore, the possible values for $p$ are 3, 5, 7, and 11. We need to find the number of matrices for each of these sums.

Step 2: Analyze the case where the sum is 3

We want to find the number of non-negative integer solutions to $a_{11} + a_{12} + a_{21} + a_{22} = 3$, where $0 \le a_{ij} \le 4$. Since the maximum value for any $a_{ij}$ is 4, the condition $a_{ij} \le 4$ is automatically satisfied when the sum is 3. Using stars and bars, the number of solutions is $\binom{3+4-1}{4-1} = \binom{6}{3} = \frac{6 \cdot 5 \cdot 4}{3 \cdot 2 \cdot 1} = 20$.

Step 3: Analyze the case where the sum is 5

We want to find the number of non-negative integer solutions to $a_{11} + a_{12} + a_{21} + a_{22} = 5$, where $0 \le a_{ij} \le 4$. Since the maximum value for any $a_{ij}$ is 4, we must subtract cases where any $a_{ij} \ge 5$. However, since the sum is 5, only one of the variables can be greater than or equal to 5 at a time.

First, without considering the upper bound, the number of solutions is $\binom{5+4-1}{4-1} = \binom{8}{3} = \frac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = 56$.

Now we subtract the cases where any $a_{ij} \ge 5$. If $a_{11} \ge 5$, let $a_{11} = a_{11}' + 5$, where $a_{11}' \ge 0$. Then $a_{11}' + 5 + a_{12} + a_{21} + a_{22} = 5$, so $a_{11}' + a_{12} + a_{21} + a_{22} = 0$. There is only 1 solution to this equation. Since any of the four variables could be greater than or equal to 5, we have to subtract $4 \cdot 1 = 4$ from the total.

Therefore, the number of solutions is $56 - 4 = 52$.

Step 4: Analyze the case where the sum is 7

We want to find the number of non-negative integer solutions to $a_{11} + a_{12} + a_{21} + a_{22} = 7$, where $0 \le a_{ij} \le 4$.

First, without considering the upper bound, the number of solutions is $\binom{7+4-1}{4-1} = \binom{10}{3} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120$.

Now we subtract the cases where any $a_{ij} \ge 5$. If $a_{11} \ge 5$, let $a_{11} = a_{11}' + 5$, where $a_{11}' \ge 0$. Then $a_{11}' + 5 + a_{12} + a_{21} + a_{22} = 7$, so $a_{11}' + a_{12} + a_{21} + a_{22} = 2$. The number of solutions to this equation is $\binom{2+4-1}{4-1} = \binom{5}{3} = 10$. Since any of the four variables could be greater than or equal to 5, we have to subtract $4 \cdot 10 = 40$ from the total.

Therefore, the number of solutions is $120 - 40 = 80$.

Step 5: Analyze the case where the sum is 11

We want to find the number of non-negative integer solutions to $a_{11} + a_{12} + a_{21} + a_{22} = 11$, where $0 \le a_{ij} \le 4$.

First, without considering the upper bound, the number of solutions is $\binom{11+4-1}{4-1} = \binom{14}{3} = \frac{14 \cdot 13 \cdot 12}{3 \cdot 2 \cdot 1} = 364$.

Now we subtract the cases where any $a_{ij} \ge 5$. If $a_{11} \ge 5$, let $a_{11} = a_{11}' + 5$, where $a_{11}' \ge 0$. Then $a_{11}' + 5 + a_{12} + a_{21} + a_{22} = 11$, so $a_{11}' + a_{12} + a_{21} + a_{22} = 6$. The number of solutions to this equation is $\binom{6+4-1}{4-1} = \binom{9}{3} = \frac{9 \cdot 8 \cdot 7}{3 \cdot 2 \cdot 1} = 84$. Since any of the four variables could be greater than or equal to 5, we have to subtract $4 \cdot 84 = 336$ from the total.

Next, we consider the cases where two variables are greater than or equal to 5. If $a_{11} \ge 5$ and $a_{12} \ge 5$, let $a_{11} = a_{11}' + 5$ and $a_{12} = a_{12}' + 5$, where $a_{11}', a_{12}' \ge 0$. Then $a_{11}' + 5 + a_{12}' + 5 + a_{21} + a_{22} = 11$, so $a_{11}' + a_{12}' + a_{21} + a_{22} = 1$. The number of solutions to this equation is $\binom{1+4-1}{4-1} = \binom{4}{3} = 4$. There are $\binom{4}{2} = 6$ ways to choose two variables to be greater than or equal to 5, so we have to add back $6 \cdot 4 = 24$.

Therefore, the number of solutions is $364 - 336 + 24 = 52$.

Step 6: Calculate the total number of matrices

The total number of matrices is $20 + 52 + 80 + 52 = 204$.

Common Mistakes & Tips

• Remember to account for the upper bound restriction on the values of $a_{ij}$.
• Stars and Bars is a useful technique, but requires careful consideration of restrictions.
• Inclusion-Exclusion principle is critical when dealing with constraints.

Summary

We found the number of matrices A such that the sum of all entries is a prime number $p \in (2, 13)$ by considering each possible prime number (3, 5, 7, 11) separately. For each prime, we used stars and bars and the inclusion-exclusion principle to account for the upper bound constraint on the entries of the matrix. Summing the results for each prime, we get the final answer.

Final Answer

The final answer is \boxed{204}.