Denote by S the set of all real symmetric 2025×2025 matrices of rank 1 whose entries take values −1 or +1. Let A,B∈S be matrices chosen independently uniformly at random. Find the probability that A and B commute, i.e. AB=BA.
Original from the official PDF
This transcription was compared symbol by symbol with the original, but not yet by a person.
Time on this problem
Work for at least 45 minutes before opening the solution.
Official solution
(proposed by Marian Panţiruc, "Gheorghe Asachi" Technical University of Iaşi, Romania)
Solution. Let n=2025. First, we give a charaterisation of matrices in S.
Suppose that A=(aij)i,j=1n∈S. Since rkA=1, for every 1<i,j≤n, we have
If a11=1 then this means aij=ai1aj1. In this case, let u=a11a21⋮an1=1a21⋮an1; then we have A=(ai1aj1)=uu⊤. Otherwise, if a11=−1, we have aij=−ai1aj1. In that case, let u=−a11−a21⋮−an1=1−a21⋮−an1; then A=−(ai1aj1)=−uu⊤.
Hence, all matrices in S can uniquely be written as ±uu⊤ with a vector u=1u2⋮un such that u2,…,un∈{±1}. (Note that rk(uu⊤)=1 is satisfied.) In particular, we have ∣S∣=2n, because the sign and the coordinates u2,…,un can be chosen independently.
Since n=2025 is odd, it follows that ⟨u,v⟩=0. The first columns of the matrices uv⊤=(uivj)i,j=1n and vu⊤=(viuj)i,j=1n are u and v, respectively. Hence, AB=BA if and only if u=v; in other words, if A=±B.
For each A∈S, there are precisely two suitable matrices B∈S, so the probability that A,B commute is ∣S∣2=2n−11.
Transcribed from the official solutions, pages 3–4. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.