Let $n \geq 2$ be an integer, and let $O$ be the $n \times 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 $A^{2}=O$, as a function of $n$.
Solution 1.
Suppose the $(i, j)$ - and the $(p, q)$-entries are turned from 0 to 1 to form the matrix $A$. Note that $A^{2}=O$ if and only if the dot product of any row of $A$ with any column of $A$ is equal to 0 . This is equivalent to $\{i, p\} \cap\{j, q\}=\emptyset$.

Hence, if the two entries to be turned from 0 to 1 are picked one by one, the first one must be an entry not on the main diagonal. There are $n^{2}-n$ ways to choose this out of $n^{2}$ possibilities. If the first one is the $(i, j)$-entry with $i \neq j$, then the second entry must, in addition to not being on the main diagonal, not be in the $i$-th column or the $j$-th row. Hence, out of the remaining $n^{2}-1$ possibilities, only $\left(n^{2}-1\right)-n-(2 n-3)=n^{2}-3 n+2$ will work; here, the 'minus $n$ ' is for the diagonal entries, while the 'minus $2 n-3$ ' is for off-diagonal entries in row $j$ union those in column $i$. It follows that the answer is
$$
\frac{n^{2}-n}{n^{2}} \times \frac{n^{2}-3 n+2}{n^{2}-1}=\frac{(n-1)(n-2)}{n(n+1)} .
$$

Solution 2.
Notice that
$$
\frac{n^{2}-n}{n^{2}} \times \frac{n^{2}-3 n+2}{n^{2}-1}=\frac{(n-1)^{2}\left(n^{2}-2 n\right)}{n^{2}\left(n^{2}-1\right)}=\frac{\binom{n-1)^{2}}{2}}{\binom{n^{2}}{2}} .
$$

We give a bijective proof of the answer in this form.
Let $\mathcal{A}_{n}$ be the set of all $n \times n$ matrices that can be obtained from $O$ by changing two distinct entries from 0 to 1 , and let
$$
\mathcal{B}_{n}=\left\{B \in \mathcal{A}_{n}: B^{2}=O\right\} .
$$

Clearly $\left|\mathcal{A}_{n}\right|=\binom{n^{2}}{2}$. We exhibit a bijection from $\mathcal{A}_{n-1}$ to $\mathcal{B}_{n}$, showing that $\left|\mathcal{B}_{n}\right|=\binom{(n-1)^{2}}{2}$.
Let $A \in \mathcal{A}_{n-1}$, and suppose that the nonzero entries of $A$ are the $(i, j)$ - and $(p, q)$-entries. We define $\phi(A) \in \mathcal{A}_{n}$ according to the series of mutually exclusive cases in Table 1 . In all cases it can be seen that the resulting nonzero entries $(k, \ell),(r, s)$ of $\phi(A)$ satisfy $\{k, r\} \cap\{\ell, s\}=\emptyset$, so $\phi$ maps $\mathcal{A}_{n-1}$ into $\mathcal{B}_{n}$. We verify that it's one-to-one and onto.
\begin{tabular}{llcc}
\hline \hline Description of $A \in \mathcal{A}_{n-1}$ & Strict conditions & Entries in $A$ & Entries in $\phi(A)$ \\
\hline One diagonal entry & $i=j$ or $p=q$ & $(i, i),(p, q)$ & $(n, i),(p, q)$ \\
One row/column shared & $i=q$ or $p=j$ & $(i, j),(j, q)$ & $(i, n),(j, q)$ \\
Two diagonal entries & $i=j$ and $p=q$ & $(i, i),(p, p)$ & $(i, n),(p, n)$ \\
Symmetric entries & $i=q$ and $p=j$ & $(i, j),(j, i)$ & $(n, j),(n, i)$ \\
One diagonal and one row shared & $i=j$ and $p=i$ & $(i, i),(i, q)$ & $(i, n),(i, q)$ \\
One diagonal and one column shared & $i=j$ and $q=j$ & $(i, i),(p, i)$ & $(n, i),(p, i)$ \\
No diagonals, no row/column shared & $\{i, p\} \cap\{j, q\}=\emptyset$ & $(i, j),(p, q)$ & $(i, j),(p, q)$ \\
\hline \hline
\end{tabular}

Table 1: Cases used to define the bijection $\mathcal{A}_{n-1} \rightarrow \mathcal{B}_{n}$. In each row, there are no equalities between the indices $i, j, p, q$ other than those that follow from the equations listed under "strict conditions". Each "or" should be understood as an exclusive or.

To see that $\phi$ is one-to-one, we check that the positions of the nonzero entries of $\phi(A)$ completely determine which row of the table $A$ belongs to, and that the map defined in each row of the table is one-to-one.

To see that $\phi$ is onto we carry out a similar case by case check. Let $B \in \mathcal{B}_{n}$. If the nonzero entries of $B$ belong to the upper left $(n-1) \times(n-1)$ submatrix $B_{n-1}$ of $B$ then $B=\phi\left(B_{n-1}\right)$. So it remains to check that $B$ belongs to the image of $\phi$ if one or both of the nonzero entries of $B$ lie in the $n$th row or column. This is done by examining the final column of the table and verifying that all possible cases are covered.