# A $3n-2$ Conjecture for the Redheffer Matrix.

Question: Let $A(n)$ be a finite $n \times n$ square matrix with entries $a_{ij}=1$ if $i$ divides $j$ or $j=1$; otherwise equals zero. I denote the characteristic polynomial of $A(n)$ by $\chi_{A(n)}(X)$ and denote the eigenvalues (roots) of $\chi_{A(n)}(X)$ by $\lambda_k$ with $1 \leq k \leq n$. Is it true that for every $n$

$$\text{tr}(A(n)^2)= 3n-2$$

from which it should follow that

$$\lambda_1^2+\ldots+\lambda_k^2=3n-2$$

?

Let $A(n)$ be a finite $n \times n$ square matrix with entries $a_{ij}=1$ if $i$ divides $j$ or $j=1$; otherwise equals zero. $A(n)$ is known as the Redheffer matrix and is also sometimes called the "divisor matrix". Can we show that $\text{tr}(A(n)^2)=3n-2$ for every $n>1$. For example:

$$A(5)= \text{ }\begin{pmatrix} 1&1&1&1&1\\ 1&1&0&1&0\\ 1&0&1&0&0\\ 1&0&0&1&0\\ 1&0&0&0&1\\ \end{pmatrix}$$

and

$$A(5)^2= \text{ }\begin{pmatrix} 5&2&1&2&2\\ 3&2&1&3&1\\ 2&1&2&1&1\\ 2&1&1&2&1\\ 2&1&1&1&2\\ \end{pmatrix}$$

and by inspection $\text{tr}(A(n))=5+2+2+2+2=13=3\times 5-2$. The following table shows data for the matrix $A(n)^2$ for $1\leq n \leq 14$.

\begin{array}{| l | l | l | l |l|} \hline n & \det(A(n)) & \text{tr}(A(n)^2) & \text{Sum of entries in first column of } A(n)^2\\ \hline 2 & 0 & 4 & 4 \\ 3 & -1 & 7 & 7 \\ 4 & -1 & 10 & 11 \\ 5 & -2 & 13 & 14 \\ 6 & -1 & 16 & 19 \\ 7 & -2 & 19 & 22 \\ 8 & -2 & 22 & 27 \\ 9 & -2 & 25 & 31 \\ 10 & -1 & 28 & 36 \\ 11 & -2 & 31 & 39 \\ 12 & -2 & 34 & 46 \\ 13 & -3 & 37 & 49 \\ 14 & -2 & 40 & 54 \\ \hline \end{array}

Going columns wise starting with the determinant we have the following sequences: A002321, A016777 and A161886. Using a suitable offset we can rewrite A016777 as $3n-2$, it's essentially the same sequence. I have searched GOOGLE and cannot seem to find anything with respect to the trace of powers of the Redheffer matrix.

The $k^{th}$ diagonal entry of $A(n)^2$ is $\sum a_{ik}\times a_{ki}$ so if $k>1$ then the only non-zero entries in the sum occur when $i=1,k$. Thus the entry is $n$ if $k=1$ and $2$ otherwise so the trace is $$Tr(A(n)^2)=n+2\times(n-1)$$ from which your claim follows at once.