Redheffer matrix

In mathematics, a Redheffer matrix, often denoted $A_{n}$ as studied by Redheffer (1977), is a square (0,1) matrix whose entries a_ij are 1 if i divides j or if j = 1; otherwise, a_ij = 0. It is useful in some contexts to express Dirichlet convolution, or convolved divisors sums, in terms of matrix products involving the transpose of the $n^{th}$ Redheffer matrix.

Variants and definitions of component matrices

Since the invertibility of the Redheffer matrices are complicated by the initial column of ones in the matrix, it is often convenient to express $A_{n}:=C_{n}+D_{n}$ where $C_{n}:=[c_{ij}]$ is defined to be the (0,1) matrix whose entries are one if and only if $j=1$ and $i\neq 1$. The remaining one-valued entries in $A_{n}$ then correspond to the divisibility condition reflected by the matrix $D_{n}$, which plainly can be seen by an application of Mobius inversion is always invertible with inverse $D_{n}^{-1}=\left[\mu (j/i)M_{i}(j)\right]$. We then have a characterization of the singularity of $A_{n}$ expressed by $\det \left(A_{n}\right)=\det \left(D_{n}^{-1}C_{n}+I_{n}\right).$

If we define the function

$M_{j}(i):={\begin{cases}1,&{\text{ if j divides i; }}\\0,&{\text{otherwise, }}\end{cases}},$

then we can define the $n^{th}$ Redheffer (transpose) matrix to be the nxn square matrix $R_{n}=[M_{j}(i)]_{1\leq i,j\leq n}$ in usual matrix notation. We will continue to make use this notation throughout the next sections.

Examples

The matrix below is the 12 × 12 Redheffer matrix. In the split sum-of-matrices notation for $A_{12}:=C_{12}+D_{12}$, the entries below corresponding to the initial column of ones in $C_{n}$ are marked in blue.

$\left({\begin{matrix}1&1&1&1&1&1&1&1&1&1&1&1\\{\color {blue}\mathbf {1} }&1&0&1&0&1&0&1&0&1&0&1\\{\color {blue}\mathbf {1} }&0&1&0&0&1&0&0&1&0&0&1\\{\color {blue}\mathbf {1} }&0&0&1&0&0&0&1&0&0&0&1\\{\color {blue}\mathbf {1} }&0&0&0&1&0&0&0&0&1&0&0\\{\color {blue}\mathbf {1} }&0&0&0&0&1&0&0&0&0&0&1\\{\color {blue}\mathbf {1} }&0&0&0&0&0&1&0&0&0&0&0\\{\color {blue}\mathbf {1} }&0&0&0&0&0&0&1&0&0&0&0\\{\color {blue}\mathbf {1} }&0&0&0&0&0&0&0&1&0&0&0\\{\color {blue}\mathbf {1} }&0&0&0&0&0&0&0&0&1&0&0\\{\color {blue}\mathbf {1} }&0&0&0&0&0&0&0&0&0&1&0\\{\color {blue}\mathbf {1} }&0&0&0&0&0&0&0&0&0&0&1\end{matrix}}\right)$

A corresponding application of the Mobius inversion formula shows that the $n^{th}$ Redheffer transpose matrix is always invertible, with inverse entries given by

$R_{n}^{-1}=\left[M_{j}(i)\cdot \mu \left({\frac {i}{j}}\right)\right]_{1\leq i,j\leq n},$

where $\mu (n)$ denotes the Moebius function. In this case, we have that the $12\times 12$ inverse Redheffer transpose matrix is given by

$R_{12}^{-1}=\left({\begin{matrix}1&0&0&0&0&0&0&0&0&0&0&0\\-1&1&0&0&0&0&0&0&0&0&0&0\\-1&0&1&0&0&0&0&0&0&0&0&0\\0&-1&0&1&0&0&0&0&0&0&0&0\\-1&0&0&0&1&0&0&0&0&0&0&0\\1&-1&-1&0&0&1&0&0&0&0&0&0\\-1&0&0&0&0&0&1&0&0&0&0&0\\0&0&0&-1&0&0&0&1&0&0&0&0\\0&0&-1&0&0&0&0&0&1&0&0&0\\1&-1&0&0&-1&0&0&0&0&1&0&0\\-1&0&0&0&0&0&0&0&0&0&1&0\\0&1&0&-1&0&-1&0&0&0&0&0&1\\\end{matrix}}\right)$

Key properties

Singularity and relations to the Mertens function

The determinant of the nxn square Redheffer matrix is given by the Mertens function M(n). In particular, the matrix $A_{n}$ is not invertible precisely when the Mertens function is zero (or is close to changing signs). This results in an interesting characterization that the Mertens function can only change signs infinitely often if the Redheffer matrix $A_{n}$ is singular at infinitely many natural numbers, which is widely believed to be the case with respect to the oscillatory behavior of $M(x)$. The determinants of the Redheffer matrices are immediately tied to the Riemann Hypothesis (RH) through this intimate relation with the Mertens function as the RH is equivalent to showing that $M(x)=O\left(x^{1/2+\varepsilon }\right)$ for all (sufficiently small) $\varepsilon >0$.

Spectral radius and eigenspaces

• If we denote the spectral radius of $A_{n}$ by $\rho _{n}$, i.e., the dominant maximum modulus eigenvalue in the spectrum of $A_{n}$, then

$\lim _{n\rightarrow \infty }{\frac {\rho _{n}}{\sqrt {n}}}=1,$

which bounds the asymptotic behavior of the spectrum of $A_{n}$ when n is large. It can also be shown that $1+{\sqrt {n-1}}\leq \rho _{n}<{\sqrt {n}}+O(\log n)$, and by a careful analysis (see the characteristic polynomial expansions below) that $\rho _{n}={\sqrt {n}}+\log {\sqrt {n}}+O(1)$.

• The matrix $A_{n}$ has eigenvalue one with multiplicity $n-\left\lfloor \log _{2}(n)\right\rfloor -1$.
• The dimension of the eigenspace $E_{\lambda }(A_{n})$ corresponding to the eigenvalue $\lambda :=1$ is known to be $\left\lfloor {\frac {n}{2}}\right\rfloor -1$. In particular, this implies that $A_{n}$ is not diagonalizable whenever $n\geq 5$.
• For all other eigenvalues $\lambda \neq 1$ of $A_{n}$, then dimension of the corresponding eigenspaces $E_{\lambda }(A_{n})$ are one.

Characterizing eigenvectors

We have that $[a_{1},a_{2},\ldots ,a_{n}]$ is an eigenvector of $A_{n}^{T}$ corresponding to some eigenvalue $\lambda \in \sigma (A_{n})$ in the spectrum of $A_{n}$ if and only if for $n\geq 2$ the following two conditions hold:

$\lambda a_{n}=\sum _{d|n}a_{d}\quad {\text{ and }}\quad \lambda a_{1}=\sum _{k=1}^{n}a_{k}.$

If we restrict ourselves to the so-called non-trivial cases where $\lambda \neq 1$, then given any initial eigenvector component $a_{1}$ we can recursively compute the remaining n-1 components according to the formula

$a_{j}={\frac {1}{\lambda -1}}\sum _{d|j \atop d<j}a_{d}.$

With this in mind, for $\lambda \neq 1$ we can define the sequences of

$v_{\lambda }(n):={\begin{cases}1,&n=1;\\{\frac {1}{\lambda -1}}\sum _{d|n \atop d\neq n}v_{\lambda }(d),&n\geq 2.\end{cases}}$

There are a couple of curious implications related to the definitions of these sequences. First, we have that $\lambda \in \sigma (A_{n})$ if and only if

$\sum _{k=1}^{n}v_{\lambda }(k)=\lambda .$

Secondly, we have an established formula for the Dirichlet series, or Dirichlet generating function, over these sequences for fixed $\lambda \neq 1$ which holds for all $\Re (s)>1$ given by

$\sum _{n\geq 1}{\frac {v_{\lambda }(n)}{n^{s}}}={\frac {\lambda -1}{\lambda -\zeta (s)}},$

where $\zeta (s)$ of course as usual denotes the Riemann zeta function.

Bounds and properties of non-trivial eigenvalues

A graph theoretic intepretation to evaluating the zeros of the characteristic polynomial of $A_{n}$ and bounding its coefficients is given in Section 5.1 of . Estimates of the sizes of the Jordan blocks of $A_{n}$ corresponding to the eigenvalue one are given in . A brief overview of the properties of a modified approach to factorizing the characteristic polynomial, $p_{A_{n}}(x)$, of these matrices is defined here without the full scope of the somewhat technical proofs justifying the bounds from the references cited above. Namely, let the shorthand $s:=\lfloor \log _{2}(n)\rfloor$ and define a sequence of auxiliary polynomial expansions according to the formula

$f_{n}(t):={\frac {p_{A_{n}}(t+1)}{t^{n-s-1}}}=t^{s+1}-\sum _{k=1}^{s}v_{nk}t^{s-k}.$

Then we know that $f_{n}(t)$ has two real roots, denoted by $t_{n}^{\pm }$, which satisfy

$t_{n}^{\pm }=\pm {\sqrt {n}}+\log {\sqrt {n}}+\gamma -{\frac {3}{2}}+O\left({\frac {\log ^{2}(n)}{\sqrt {n}}}\right),$

where $\gamma \approx 0.577216$ is Euler's classical gamma constant, and where the remaining coefficients of these polynomials are bounded by

$|v_{nk}|\leq {\frac {n\cdot \log ^{k-1}(n)}{(k-1)!}}.$

A plot of the much more size-constrained nature of the eigenvalues of $f_{n}(t)$ which are not characterized by these two dominant zeros of the polynomial seems to be remarkable as evidenced by the only 20 remaining complex zeros shown below. The next image is reproduced from a freely available article cited above when $n\sim 10^{6}$ is available here for reference.

References

• Redheffer, Ray (1977), "Eine explizit lösbare Optimierungsaufgabe", Numerische Methoden bei Optimierungsaufgaben, Band 3 (Tagung, Math. Forschungsinst., Oberwolfach, 1976), Basel, Boston, Berlin: Birkhäuser, pp. 213–216, MR 0468170

External links

• Weisstein, Eric W. "Redheffer matrix". MathWorld.