In mathematics, a Redheffer matrix, often denoted
An
nth
Since the invertibility of the Redheffer matrices are complicated by the initial column of ones in the matrix, it is often convenient to express
An:=Cn+Dn
Cn:=[cij]
j=1
i ≠ 1
An
Dn
-1 | |
D | |
n |
=\left[\mu(j/i)Mi(j)\right]
An
\det\left(An\right)=
-1 | |
\det\left(D | |
n |
Cn+In\right).
If we define the function
Mj(i):=\begin{cases}1,&ifjdividesi;\ 0,&otherwise,\end{cases},
then we can define the
nth
Rn=[Mj(i)]1
The matrix below is the 12 × 12 Redheffer matrix. In the split sum-of-matrices notation for
A12:=C12+D12
Cn
\left(\begin{matrix} 1&1&1&1&1&1&1&1&1&1&1&1\\ {\color{blue}1
A corresponding application of the Mobius inversion formula shows that the
nth
-1 | |
R | |
n |
=\left[Mj(i) ⋅ \mu\left(
i | |
j |
\right)\right]1,
where
\mu(n)
12 x 12
-1 | |
R | |
12 |
=\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)
The determinant of the n × n square Redheffer matrix is given by the Mertens function M(n). In particular, the matrix
An
An
The determinants of the Redheffer matrices are immediately tied to the Riemann Hypothesis through this relation with the Mertens function, since the Hypothesis is equivalent to showing that
M(x)=O\left(x1/2+\varepsilon\right)
\varepsilon>0
In a somewhat unconventional construction which reinterprets the (0,1) matrix entries to denote inclusion in some increasing sequence of indexing sets, we can see that these matrices are also related to factorizations of Lambert series. This observation is offered in so much as for a fixed arithmetic function f, the coefficients of the next Lambert series expansion over f provide a so-called inclusion mask for the indices over which we sum f to arrive at the series coefficients of these expansions. Notably, observe that
\sumd|nf(d)=
n | |
\sum | |
k=1 |
Mk(n) ⋅ f(k)=
n]\left(\sum | |
[q | |
n\geq1 |
f(n)qn | |
1-qn |
\right).
Now in the special case of these divisor sums, which we can see from the above expansion, are codified by boolean (zero-one) valued inclusion in the sets of divisors of a natural number n, it is possible to re-interpret the Lambert series generating functions which enumerate these sums via yet another matrix-based construction. Namely, Merca and Schmidt (2017-2018) proved invertible matrix factorizations expanding these generating functions in the form of [1]
\sumn
f(n)qn | |
1-qn |
=
1 | |
(q;q)infty |
\sumn
n | |
\left(\sum | |
k=1 |
sn,kf(k)\right)qn,
where
(q;q)infty
sn,k=[qn]
qk | |
1-qk |
(q;q)infty
\ell(n)=(f\ast1)(n)
f(n)=\sumd|n
n | |
\sum | |
k=1 |
p(d-k)\mu(n/d)\left[\sumj\ell(k-j)[qj](q;q)infty\right],
where p(n) denotes the partition function,
\mu(n)
(q;q)infty
An
Other than that the underlying so-termed mask matrix which specifies the inclusion of indices in the divisor sums at hand are invertible, utilizing this type of construction to expand other Redheffer-like matrices for other special number theoretic sums need not be limited to those forms classically studied here. For example, in 2018 Mousavi and Schmidt extend such matrix based factorization lemmas to the cases of Anderson-Apostol divisor sums (of which Ramanujan sums are a notable special case) and sums indexed over the integers that are relatively prime to each n (for example, as classically defines the tally denoted by the Euler phi function).[3] More to the point, the examples considered in the applications section below suggest a study of the properties of what can be considered generalized Redheffer matrices representing other special number theoretic sums.
An
\rhon
An
\limn
\rhon | |
\sqrt{n |
An
1+\sqrt{n-1}\leq\rhon<\sqrt{n}+O(logn)
\rhon=\sqrt{n}+log\sqrt{n}+O(1)
An
n-\left\lfloorlog2(n)\right\rfloor-1
Eλ(An)
λ:=1
\left\lfloor
n | |
2 |
\right\rfloor-1
An
n\geq5
λ ≠ 1
An
Eλ(An)
We have that
[a1,a2,\ldots,an]
T | |
A | |
n |
λ\in\sigma(An)
An
n\geq2
λan=\sumd|nad and λa1=
n | |
\sum | |
k=1 |
ak.
If we restrict ourselves to the so-called non-trivial cases where
λ ≠ 1
a1
aj=
1 | |
λ-1 |
\sumd|jad.
With this in mind, for
λ ≠ 1
vλ(n):=\begin{cases}1,&n=1;\
1 | |
λ-1 |
\sumd|nvλ(d),&n\geq2.\end{cases}
There are a couple of curious implications related to the definitions of these sequences. First, we have that
λ\in\sigma(An)
n | |
\sum | |
k=1 |
vλ(k)=λ.
Secondly, we have an established formula for the Dirichlet series, or Dirichlet generating function, over these sequences for fixed
λ ≠ 1
\Re(s)>1
\sumn
vλ(n) | |
ns |
=
λ-1 | |
λ-\zeta(s) |
,
where
\zeta(s)
A graph theoretic interpretation to evaluating the zeros of the characteristic polynomial of
An
An
p | |
An |
(x)
s:=\lfloorlog2(n)\rfloor
fn(t):=
| |||||||
tn-s-1 |
=ts+1-
s | |
\sum | |
k=1 |
vnkts-k.
Then we know that
fn(t)
\pm | |
t | |
n |
\pm | |
t | |
n |
=\pm\sqrt{n}+log\sqrt{n}+\gamma-
3 | |
2 |
+O\left(
log2(n) | |
\sqrt{n |
where
\gamma ≈ 0.577216
|vnk|\leq
n ⋅ logk-1(n) | |
(k-1)! |
.
A plot of the much more size-constrained nature of the eigenvalues of
fn(t)
n\sim106
We provide a few examples of the utility of the Redheffer matrices interpreted as a (0,1) matrix whose parity corresponds to inclusion in an increasing sequence of index sets. These examples should serve to freshen up some of the at times dated historical perspective of these matrices, and their being footnote-worthy by virtue of an inherent, and deep, relation of their determinants to the Mertens function and equivalent statements of the Riemann Hypothesis. This interpretation is a great deal more combinatorial in construction than typical treatments of the special Redheffer matrix determinants. Nonetheless, this combinatorial twist on enumerating special sequences of sums has been explored more recently in a number of papers and is a topic of active interest in pre-print archives. Before diving into the full construction of this spin on the Redheffer matrix variants
Rn
First, given any two non-identically-zero arithmetic functions f and g, we can provide explicit matrix representations which encode their Dirichlet convolution in rows indexed by natural numbers
n\geq1,1\leqn\leqx
Df,g(x):=\left[Md(n)f(d)g(n/d)\right]1=\begin{bmatrix}0&0& … &0&g(x)\ 0&0& … &g(x-1)&g(x)\ \ldots&\ldots&\ddots&\ddots& … \ g(1)&g(2)& … &g(x-1)&g(x)\end{bmatrix}\begin{bmatrix}0&0& … &0&f(1)\ 0&0& … &f(2)&f(1)\ \ldots&\ldots&\ddots&\ddots& … \ f(x)&f(x-1)& … &f(2)&f(1)\end{bmatrix}
T | |
R | |
x |
.
Then letting
eT:=[1,1,\ldots,1]
nth
eT ⋅ Df,g(x)
(f\astg)(n)=\sumd|nf(d)g(n/d),
for all
1\leqn\leqx
x\geq2
One task that is particularly onerous given an arbitrary function f is to determine its Dirichlet inverse exactly without resorting to a standard recursive definition of this function via yet another convolved divisor sum involving the same function f with its under-specified inverse to be determined:
f-1(n) =
-1 | |
f(1) |
\sumd\mid | f\left( | |
d<n |
n | |
d |
\right)f-1(d), n>1wheref-1(1):=1/f(1).
f-1(n)
(f-1\astf)(n)=\deltan,1
\omega(n)
Rn
There are several often cited articles from worthy journals that fight to establish expansions of number theoretic divisor sums, convolutions, and Dirichlet series (to name a few) through matrix representations. Besides non-trivial estimates on the corresponding spectrum and eigenspaces associated with truly notable and important applications of these representations—the underlying machinery in representing sums of these forms by matrix products is to effectively define a so-termed masking matrix whose zero-or-one valued entries denote inclusion in an increasing sequence of sets of the natural numbers
\{1,2,\ldots,n\}
l{A}n\subseteq[1,n]\capZ
f:N\longrightarrowC
Sl{A,f}(n)\mapstoSf(n):=\sumkn}f(k).
One of the classes of sums considered by Mousavi and Schmidt (2017) defines the relatively prime divisor sums by setting the index sets in the last definition to be
l{A}n\mapstol{G}n:=\{1\leqd\leqn:\gcd(d,n)=1\}.
This class of sums can be used to express important special arithmetic functions of number theoretic interest, including Euler's phi function (where classically we define
m:=0
\varphi(n)=\sumdn}dm,
and even the Mobius function through its representation as a discrete (finite) Fourier transform:
\mu(n)=\sum\stackrel{1\le{\gcd(k,n)=1}}
| ||||||
e |
.
Citations in the full paper provide other examples of this class of sums including applications to cyclotomic polynomials (and their logarithms). The referenced article by Mousavi and Schmidt (2017) develops a factorization-theorem-like treatment to expanding these sums which is an analog to the Lambert series factorization results given in the previous section above. The associated matrices and their inverses for this definition of the index sets
l{A}n
\varphi(n)
\mu(n)
x:=21
\left(\begin{smallmatrix} 1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 1&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 1&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 1&1&1&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 1&1&1&1&1&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 1&0&1&0&1&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 1&1&0&1&1&0&1&1&0&0&0&0&0&0&0&0&0&0&0&0\\ 1&0&1&0&0&0&1&0&1&0&0&0&0&0&0&0&0&0&0&0\\ 1&1&1&1&1&1&1&1&1&1&0&0&0&0&0&0&0&0&0&0\\ 1&0&0&0&1&0&1&0&0&0&1&0&0&0&0&0&0&0&0&0\\ 1&1&1&1&1&1&1&1&1&1&1&1&0&0&0&0&0&0&0&0\\ 1&0&1&0&1&0&0&0&1&0&1&0&1&0&0&0&0&0&0&0\\ 1&1&0&1&0&0&1&1&0&0&1&0&1&1&0&0&0&0&0&0\\ 1&0&1&0&1&0&1&0&1&0&1&0&1&0&1&0&0&0&0&0\\ 1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&0&0&0&0\\ 1&0&0&0&1&0&1&0&0&0&1&0&1&0&0&0&1&0&0&0\\ 1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&0&0\\ 1&0&1&0&0&0&1&0&1&0&1&0&1&0&0&0&1&0&1&0\\ 1&1&0&1&1&0&0&1&0&1&1&0&1&0&0&1&1&0&1&1\\ \end{smallmatrix}\right)-1=\left(\begin{smallmatrix} 1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ -1&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ -1&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 1&-1&-1&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ -1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 1&0&0&-1&-1&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 1&0&-1&0&-1&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0\\ -1&0&2&-1&0&0&-1&1&0&0&0&0&0&0&0&0&0&0&0&0\\ -1&0&0&0&1&0&-1&0&1&0&0&0&0&0&0&0&0&0&0&0\\ 1&0&-1&1&0&-1&1&-1&-1&1&0&0&0&0&0&0&0&0&0&0\\ -1&0&1&0&0&0&-1&0&0&0&1&0&0&0&0&0&0&0&0&0\\ 1&0&-1&0&0&0&1&0&0&-1&-1&1&0&0&0&0&0&0&0&0\\ 3&0&-2&0&-2&0&2&0&-1&0&-1&0&1&0&0&0&0&0&0&0\\ -3&0&1&0&3&0&-1&-1&1&0&0&0&-1&1&0&0&0&0&0&0\\ -1&0&1&0&1&0&-1&0&0&0&0&0&-1&0&1&0&0&0&0&0\\ 1&0&0&0&-2&0&0&1&0&0&1&-1&1&-1&-1&1&0&0&0&0\\ -3&0&2&0&2&0&-2&0&1&0&0&0&-1&0&0&0&1&0&0&0\\ 3&0&-2&0&-2&0&2&0&-1&0&0&0&1&0&0&-1&-1&1&0&0\\ 1&0&-1&0&0&0&1&0&-1&0&0&0&0&0&0&0&-1&0&1&0\\ -1&0&0&-1&1&1&0&-1&2&-1&-1&1&-1&1&1&-1&0&0&-1&1\\ \end{smallmatrix}\right)
Examples of invertible matrices which define other special sums with non-standard, however, clear applications should be catalogued and listed in this generalizations section for completeness. An existing summary of inversion relations, and in particular, exact criteria under which sums of these forms can be inverted and related is found in many references on orthogonal polynomials. Other good examples of this type of factorization treatment to inverting relations between sums over sufficiently invertible, or well enough behaved triangular sets of weight coefficients include the Mobius inversion formula, the binomial transform, and the Stirling transform, among others.