7
$\begingroup$

Let $d_1$, $d_2$, ..., $d_n$ be positive integers. Let $B$ be the $n \times n$ matrix $$\begin{pmatrix} d_1 & 1 & 1 & \cdots & 1 \\ 1 & d_2 & 1 & \cdots & 1 \\ 1 & 1 & d_3 & \cdots & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & \cdots & d_n \end{pmatrix}.$$ When does $B$ have a square root in $\mathrm{Mat}_n(\mathbb{Z})$?

Motivation: The Friendship Theorem states that the only graph in which every pair of vertices is joined by a path of length $2$ is the "Friendship Graph", which you can see at the linked article. If $A$ is the adjacency matrix of such a graph, with degree sequence $(d_1, d_2, \ldots, d_n)$, then $A^2=B$. So this contributes the solution $(d_1, d_2, \ldots, d_n) = (2,2,2,\ldots,2,2m)$, with $n=2m+1$.

I was preparing notes on the friendship theorem and got distracted by trying to figure out when this matrix has an integer square root at all. It seemed like it might make a nice challenge for here.

$\endgroup$

1 Answer 1

4
$\begingroup$

$$\pmatrix{r&s\cr t&u\cr}\pmatrix{r&s\cr t&u\cr}=\pmatrix{d_1&1\cr1&d_2\cr}$$ $rs+su=1=(r+u)s$, $tr+ut=1=(r+u)t$, $s=t=r+u=\pm1$. $$\pmatrix{r&1\cr1&1-r\cr}^2=\pmatrix{r^2+1&1\cr1&(r-1)^2+1\cr}$$ $$\pmatrix{r&-1\cr-1&-1-r\cr}^2=\pmatrix{r^2+1&1\cr1&(r+1)^2+1\cr}$$ So for $n=2$, the answer is, $d_1-1$ and $d_2-1$ are squares of consecutive integers.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .