Möbius function matrix

Question

In http://en.wikipedia.org/wiki/M%C3%B6bius_function#Matrix_inverse, it is stated, that the values of the Möbius function appear in the inverse matrix of some lower triangular matrix. Does anyone know of a reference for that?

Answer 1

It's not too difficult to prove this yourself. Let's define the doubly infinite matices $A = (a_{nk})$ and $B = (b_{nk})$ with $n, k \in \mathbb N$ and $a_{nk} = 1$ iff $k | n$, $a_{nk} = 0$ otherwise, $b_{nk} = \mu(n/k)$ iff $k | n$, $b_{nk} = 0$ otherwise. We think of $n$ as the row index and of $k$ as the column index. Then $A$ is the matrix $T$ and $B$ is the matrix $T_{inv}$ from your Wikipedia link.

Let's put $C = AB$ with $C = (c_{nk})$. Now we fix $n$ and $k$ and calculate $c_{nk}$. We get $$c_{nk} = \sum_{j \in \mathbb N}a_{nj}b_{jk} = \sum_{j \in \mathbb N,\ j | n,\ k | j} \mu(j/k).$$

Now if $k$ doesn't divide $n$, the summation is over the empty set, and we have $c_{nk} = 0$.

If $k | n$, there are bijections between the sets $$X := \left\{ j \in \mathbb N\ |\ j | n,\ k | j \right\}\quad and \quad Y := \left\{ \ell \in \mathbb N\ |\ \ell | \frac{n}{k} \right\},$$ namely $X \rightarrow Y, j \mapsto j/k$ and $Y \rightarrow X,\ell \mapsto k\ell$. In other words, ($j|n$ and $k|j$) iff $\frac{j}{k}|\frac{n}{k}$. So, instead of summing over $X$, we can change variables and sum over $Y$ and get $$c_{nk} = \sum_{j \in X}\mu(j/k) = \sum_{\ell \in Y} \mu(\ell) = \delta_{\frac{n}{k}1}.$$

Here, $\delta$ is the Kronecker delta with $\delta_{pq} = 1$ iff $p = q$ and $\delta_{pq} = 0$ otherwise. The last equality $\sum_{\ell \in Y} \mu(\ell) = \delta_{\frac{n}{k}1}$ is a "well known fact" about the Moebius function.

So, in the case $k|n$, we have $c_{nk} = \delta_{\frac{n}{k}1} = \delta_{nk}.$

All in all, we have shown that $C$ is the identity matrix, or in other words that $B = A^{-1}$, as desired.