The Redheffer Matrix and Its Determinant: det(Aₙ) = M(n)

What you have written down is one of the most elegant "hidden in plain sight" reformulations of the Riemann Hypothesis: the Redheffer matrix. Below is a full treatment — history, the theorem, proof structure, spectral theory, literature with links, and working Python code.

1. The Object

The Redheffer matrix Aₙ is the n × n matrix of 0s and 1s defined by:

$$ (A_n)_{ij} = \begin{cases} 1 & \text{if } j = 1 \text{ (first column)}, \\ 1 & \text{if } i \mid j \ (i \text{ divides } j), \\ 0 & \text{otherwise.} \end{cases} $$

Example, n = 5:

A₅ = ⎡1 1 1 1 1⎤   (row 1: 1 divides everything)
     ⎢1 1 0 1 0⎥   (row 2: first column + multiples of 2)
     ⎢1 0 1 0 0⎥
     ⎢1 0 0 1 0⎥
     ⎣1 0 0 0 1⎦

Theorem (Redheffer, 1977). $$ \det A_n = M(n) := \sum_{k=1}^{n} \mu(k), $$ where μ is the Möbius function and M(n) is the Mertens function.

2. History

• Raymond M. Redheffer (1921–2005), a professor at UCLA (also known for the Redheffer star product in scattering theory), introduced the matrix in:

R. M. Redheffer, "Eine explizit lösbare Optimierungsaufgabe", in Numerische Methoden bei Optimierungsaufgaben, Band 3, Internationale Schriftenreihe zur Numerischen Mathematik (ISNM) vol. 36, Birkhäuser, Basel, 1977, pp. 213–216.

The title translates as "An explicitly solvable optimization problem." Redheffer presented it almost as a curiosity — a 0-1 matrix whose determinant encodes deep arithmetic.

• The reason it matters: Littlewood (1912) had shown that the Riemann Hypothesis is equivalent to the growth estimate

$$ M(n) = O(n^{1/2 + \varepsilon}) \quad \text{for every } \varepsilon > 0. $$

(This is the "#26" in your notes — the classical Mertens-function equivalence of RH.)

• Combining the two facts gives the striking reformulation:

RH is true ⟺ det Aₙ = O(n^{1/2+ε}) for every ε > 0.

That is, the Riemann Hypothesis is exactly a statement about how fast the determinant of an explicit family of 0-1 matrices can grow.

• Historical footnote: Mertens conjectured (1897) the stronger bound |M(n)| < √n, i.e. |det Aₙ| < √n. This was famously disproved by Odlyzko and te Riele in 1985 using lattice reduction (LLL) and high-precision zeros of ζ(s) — one of the great computational number theory results. RH itself only requires the weaker O(n^{1/2+ε}) bound, which remains open.

3. Proof Sketch (the decomposition in your Step 1)

Write Aₙ = Bₙ + E, where:

• Bₙ is the divisibility matrix: (Bₙ)ᵢⱼ = 1 iff i | j. Sorted by size, Bₙ is upper triangular with 1s on the diagonal (unipotent), so det Bₙ = 1.
• E is rank one: E = u e₁ᵀ, where u = (0, 1, 1, …, 1)ᵀ. It just adds 1s in the first column, rows 2..n.

Key fact from the incidence algebra of the divisibility poset (Möbius inversion, Rota 1964): the inverse of Bₙ is explicit:

$$ (B_n^{-1})_{ij} = \begin{cases} \mu(j/i) & \text{if } i \mid j \\ 0 & \text{otherwise.} \end{cases} $$

Now use the matrix determinant lemma, det(B + uvᵀ) = det(B)(1 + vᵀB⁻¹u):

$$ \det A_n = \det(B_n)\,\bigl(1 + e_1^{\mathsf T} B_n^{-1} u\bigr) = 1 + \sum_{j=2}^{n} \mu(j) = \sum_{j=1}^n \mu(j) = M(n). \qquad \blacksquare $$

The "inclusion–exclusion telescoping" in your notes is exactly Möbius inversion on the divisor lattice; the rank-one column is what turns unipotent triviality (det = 1) into the Mertens sum.

4. Spectral Theory (the "eigenvalues ≈ ±√n" remark)

The eigenvalues of Aₙ have been studied intensively, in the hope of a spectral attack on RH:

• Barrett, Forcade, Pollington (1988) proved that Aₙ has the eigenvalue 1 with multiplicity at least n − ⌊log₂ n⌋ − 1. So almost all of the spectrum is trivial; the arithmetic lives in only ~log₂ n "nontrivial" eigenvalues.

• Barrett & Jarvis (1992) and Vaughan (1993, 1996) showed:

• There are two dominant real eigenvalues λ± ≈ ±√n; more precisely λ₊ = √n + ½ log n + O(1), λ₋ = −√n + ½ log n + O(1).
• The remaining nontrivial eigenvalues satisfy |λ| ≪ (log n)^{2/5} (Vaughan), and it is conjectured they are ≪ log log n. Vaughan also connected their distribution to zeros of Dirichlet series.

Since det Aₙ = product of eigenvalues and the two dominant ones contribute ≈ −n, all the subtlety of M(n) — and hence of RH — is compressed into the small cluster of ~log₂ n nontrivial eigenvalues near the origin. This is why the reformulation is "occasionally useful for spectral reformulations": it's a concrete, finite, combinatorial family of operators whose spectral behaviour encodes RH, in the spirit of the Hilbert–Pólya philosophy.

5. Key References (with links)

1. R. M. Redheffer, Eine explizit lösbare Optimierungsaufgabe, ISNM 36, Birkhäuser (1977). (Print only; no stable free link — cite via Springer/Birkhäuser: https://doi.org/10.1007/978-3-0348-5936-3)

2. W. W. Barrett, R. W. Forcade, A. D. Pollington, On the spectral radius of a (0,1) matrix related to Mertens' function, Linear Algebra Appl. 107 (1988), 151–159. https://doi.org/10.1016/0024-3795(88)90246-6 (open access PDF via Elsevier/CORE)

3. W. W. Barrett & T. J. Jarvis, Spectral properties of a matrix of Redheffer, Linear Algebra Appl. 162–164 (1992), 673–683. https://doi.org/10.1016/0024-3795(92)90401-U

4. R. C. Vaughan, On the eigenvalues of Redheffer's matrix, I, in Number Theory with an Emphasis on the Markoff Spectrum, Dekker (1993); …II, J. Austral. Math. Soc. Ser. A 60 (1996), 260–273. https://doi.org/10.1017/S1446788700037666

5. A. M. Odlyzko & H. J. J. te Riele, Disproof of the Mertens conjecture, J. reine angew. Math. 357 (1985), 138–160. Free PDF from Odlyzko's site: http://www.dtc.umn.edu/~odlyzko/doc/arch/mertens.disproof.pdf

6. E. C. Titchmarsh, The Theory of the Riemann Zeta-Function (2nd ed., Oxford, 1986) — Chapter XIV for the M(n) ⟺ RH equivalence (Littlewood's theorem).

7. Survey-style treatment: Borwein, Choi, Rooney, Weirathmueller, The Riemann Hypothesis: A Resource for the Afficionado and Virtuoso Alike, Springer (2008) — discusses the Redheffer/Mertens equivalence among the catalog of RH equivalents.

(Links can rot; the DOIs are the stable identifiers to cite in your paper.)

6. Computational Examples in Python

6.1 Build Aₙ, verify det Aₙ = M(n) exactly

import numpy as np
from sympy import Matrix, mobius

def redheffer(n):
    """n x n Redheffer matrix (0/1 integer entries)."""
    A = np.zeros((n, n), dtype=int)
    A[:, 0] = 1                      # first column all ones
    for i in range(1, n + 1):
        A[i - 1, i - 1::i] = 1       # i divides j  ->  A[i-1, j-1] = 1
    return A

def mertens(n):
    """Mertens function M(n) via a sieve for the Möbius function."""
    mu = np.ones(n + 1, dtype=int)
    mu[0] = 0
    primes_mark = np.ones(n + 1, dtype=bool)
    for p in range(2, n + 1):
        if primes_mark[p]:                       # p is prime
            primes_mark[2*p::p] = False
            mu[p::p] *= -1                       # one factor of p
            mu[p*p::p*p] = 0                     # p^2 divides -> mu = 0
    return int(mu[1:n + 1].sum())

for n in [1, 2, 5, 10, 20, 50, 100]:
    A = redheffer(n)
    det_exact = int(Matrix(A).det())   # exact integer determinant
    print(f"n={n:4d}  det(A_n)={det_exact:4d}  M(n)={mertens(n):4d}  "
          f"match={det_exact == mertens(n)}")

Output:

n=   1  det(A_n)=   1  M(n)=   1  match=True
n=   2  det(A_n)=   0  M(n)=   0  match=True
n=   5  det(A_n)=  -2  M(n)=  -2  match=True
n=  10  det(A_n)=  -1  M(n)=  -1  match=True
n=  20  det(A_n)=  -3  M(n)=  -3  match=True
n=  50  det(A_n)=  -3  M(n)=  -3  match=True
n= 100  det(A_n)=   1  M(n)=   1  match=True

6.2 Verify the rank-one / unipotent decomposition proof numerically

from sympy import Matrix, mobius, eye, zeros

def divisibility_matrix(n):
    B = zeros(n, n)
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            B[i - 1, j - 1] = 1
    return B

n = 12
B = divisibility_matrix(n)

# Möbius-inverse of B: (B^{-1})_{ij} = mu(j/i) if i | j
Binv = zeros(n, n)
for i in range(1, n + 1):
    for j in range(i, n + 1, i):
        Binv[i - 1, j - 1] = mobius(j // i)

assert B * Binv == eye(n)            # incidence-algebra Möbius inversion

u  = Matrix([0] + [1]*(n - 1))        # rank-one perturbation column
e1 = Matrix([1] + [0]*(n - 1))
A  = B + u * e1.T                     # A_n = B_n + u e1^T (Redheffer)

# Matrix determinant lemma: det A = det B * (1 + e1^T B^{-1} u)
lemma_value = (1 + (e1.T * Binv * u)[0, 0])
print("det via lemma:", lemma_value, "  det direct:", A.det())
# Both equal M(12) = -2

6.3 Dominant eigenvalues ≈ ±√n and eigenvalue-1 multiplicity

import numpy as np

for n in [100, 400, 1600, 6400]:
    A = redheffer(n).astype(float)
    ev = np.linalg.eigvals(A)
    ev_sorted = sorted(ev, key=lambda z: -abs(z))
    lam_plus, lam_minus = ev_sorted[0].real, ev_sorted[1].real
    mult_one = np.sum(np.isclose(ev, 1.0, atol=1e-6))
    print(f"n={n:5d}  λ+={lam_plus:9.4f} (√n={np.sqrt(n):7.3f})  "
          f"λ-={lam_minus:9.4f}  #(λ≈1) ≥ n-⌊log₂n⌋-1 = {n - int(np.log2(n)) - 1} "
          f"(found {mult_one})")

You will see λ₊ ≈ √n + ½ ln n and λ₋ ≈ −√n + ½ ln n, and the huge cluster of eigenvalues at 1, exactly as Barrett–Forcade–Pollington and Vaughan proved.

6.4 The RH-relevant growth test: M(n)/√n

import matplotlib.pyplot as plt
import numpy as np

N = 200_000
# incremental Mertens via sieve
mu = np.ones(N + 1, dtype=np.int64); mu[0] = 0
is_p = np.ones(N + 1, dtype=bool)
for p in range(2, N + 1):
    if is_p[p]:
        is_p[2*p::p] = False
        mu[p::p] *= -1
        mu[p*p::p*p] = 0
M = np.cumsum(mu[1:])
x = np.arange(1, N + 1)

plt.figure(figsize=(10, 4))
plt.plot(x, M / np.sqrt(x), lw=0.4)
plt.axhline( 1, color='r', ls='--', label='±√n  (disproved Mertens bound)')
plt.axhline(-1, color='r', ls='--')
plt.title(r'$\det A_n/\sqrt{n} = M(n)/\sqrt{n}$ — RH ⟺ growth $O(n^{\varepsilon})$')
plt.legend(); plt.tight_layout(); plt.show()

The plot stays well inside ±1 in any feasible computation — yet Odlyzko–te Riele proved limsup M(n)/√n > 1.06 (the first crossing is astronomically large, currently only known to occur below ~10^(10^40)). This is a superb cautionary tale for your paper about the limits of numerical evidence in this subject.

7. Summary for Your Paper