Extracting non-duplicate cells in a particular matrix with repeated entries
Choose a permutation $\pi$ uniformly at random, and let $P = \{ a_{i, \pi(i)} \mid i\in [n]\}$.  The set $P$ contains exactly one element in each row and each column of given the matrix $A$.

Now consider any pair of entries in $A$ with the same value.  If those two entries lie in the same row or the same column, they cannot both be in $P$.  If those two entries are in different rows and columns of $A$, then the probability that both entries lie in $P$ is exactly $1/n(n-1)$.

There are $n^2/2$ different values in the matrix.  So the expected number of values with both entries in $P$ is at most $n^2/2n(n-1) = n/2(n-1)$.  If $n\ge 4$, this expected value is less than $1$, which implies that the probability of choosing no matching pairs must be positive.