International Mathematics Competition
for University Students
2025

IMC2025: Day 1, Problem 3

Problem 3. Denote by \(\displaystyle \mathcal{S}\) the set of all real symmetric \(\displaystyle 2025\times 2025\) matrices of rank \(\displaystyle 1\) whose entries take values \(\displaystyle -1\) or \(\displaystyle +1\). Let \(\displaystyle A,B\in\mathcal{S}\) be matrices chosen independently uniformly at random. Find the probability that \(\displaystyle A\) and \(\displaystyle B\) commute, i.e. \(\displaystyle AB=BA.\)

Marian Panţiruc, "Gheorghe Asachi" Technical University of Iaşi, Romania

Solution. Let \(\displaystyle n=2025\). First, we give a charaterisation of matrices in \(\displaystyle \mathcal{S}\).

Suppose that \(\displaystyle A=(a_{ij})_{i,j=1}^n\in\mathcal{S}\). Since \(\displaystyle \mathrm{rk}\,A=1\), for every \(\displaystyle 1<i,j\le n\), we have

\(\displaystyle \det\begin{pmatrix}a_{11}&a_{1j}\\a_{i1}&a_{ij}\end{pmatrix}=a_{11}a_{ij}-a_{i1}a_{1j}=a_{11}a_{ij}-a_{i1}a_{j1}=0. \)

If \(\displaystyle a_{11}=1\) then this means \(\displaystyle a_{ij}=a_{i1}a_{j1}\). In this case, let \(\displaystyle u=\begin{pmatrix}a_{11}\\a_{21}\\\vdots\\a_{n1}\end{pmatrix}=\begin{pmatrix}1\\a_{21}\\\vdots\\a_{n1}\end{pmatrix}\); then we have \(\displaystyle A=\big(a_{i1}a_{j1}\big)=uu^\top\). Otherwise, if \(\displaystyle a_{11}=-1\), we have \(\displaystyle a_{ij}=-a_{i1}a_{j1}\). In that case, let \(\displaystyle u=\begin{pmatrix}-a_{11}\\-a_{21}\\\vdots\\-a_{n1}\end{pmatrix}=\begin{pmatrix}1\\-a_{21}\\\vdots\\-a_{n1}\end{pmatrix}\); then \(\displaystyle A=-\big(a_{i1}a_{j1}\big)=-uu^\top\).

Hence, all matrices in \(\displaystyle \mathcal{S}\) can uniquely be written as \(\displaystyle \pm uu^\top\) with a vector \(\displaystyle u=\begin{pmatrix}1\\u_2\\\vdots\\u_n\end{pmatrix}\) such that \(\displaystyle u_2,\ldots,u_n\in\{\pm1\}\). (Note that \(\displaystyle \rk(uu^\top)=1\) is satisfied.) In particular, we have \(\displaystyle |\mathcal{S}|=2^n\), because the sign and the coordinates \(\displaystyle u_2,\ldots,u_n\) can be chosen independently.

Now, if \(\displaystyle A=\pm uu^{T}\) and \(\displaystyle B=\pm vv^{T}\) are elements of \(\displaystyle \mathcal{S}\), then

\(\displaystyle AB = \pm(uu^\top)(vv^\top) = \pm u(u^\top v)v^\top = \pm u\cdot\langle u,v\rangle\cdot v^\top = \pm \langle u,v\rangle \cdot \big(u_iv_j\big)_{i,j=1}^n \)

and similarly

\(\displaystyle BA = \pm \langle u,v\rangle \cdot \big(v_iu_j\big)_{i,j=1}^n. \)

Since \(\displaystyle n=2025\) is odd, it follows that \(\displaystyle \left\langle u,v\right\rangle \neq 0\). The first columns of the matrices \(\displaystyle uv^\top = \big(u_iv_j\big)_{i,j=1}^n\) and \(\displaystyle vu^\top = \big(v_iu_j\big)_{i,j=1}^n\) are \(\displaystyle u\) and \(\displaystyle v\), respectively. Hence, \(\displaystyle AB=BA\) if and only if \(\displaystyle u=v\); in other words, if \(\displaystyle A=\pm B\).

For each \(\displaystyle A\in\mathcal{S}\), there are precisely two suitable matrices \(\displaystyle B\in\mathcal{S}\), so the probability that \(\displaystyle A,B\) commute is \(\displaystyle \dfrac{2}{|\mathcal{S}|}=\dfrac1{2^{n-1}}\).