Let n≥2 be an integer, and let O be the n×n matrix whose entries are all equal to 0. Two distinct entries of the matrix are chosen uniformly at random, and those two entries are changed from 0 to 1. Call the resulting matrix A.
Determine the probability that A2 = O, as a function of n.
There are n^2*(n^2-1)/2 total possible matrices A.
If either of the 1s are on the main diagonal of A then A^2 will have a 1 in that position as well. Then for all these possible A, A^2 is not the zero matrix. So the 1s cannot be on the diagonal.
Then there are (n^2-n)*(n^2-n-1)/2 possible matrices A without 1s on the diagonal.
The other way to get a 1 in A^2 is for the column of one of the 1s match up with the row of the other 1. So if one 1 is at entry (j,k) {j!=k} then the other 1 cannot occur in row k or column j.
There are then 2n-3 additional locations the second 1 cannot occur.
Then this reduces the possible matrices A down to (n^2-n)*(n^2-3n+2)/2.
Then the probability that A^2 is the zero matrix is the ratio [(n^2-n)*(n^2-3n+2)/2]/[n^2*(n^2-1)/2] = (n^2-3n+2)/(n^2+n).
Analytic Solution
