4
$\begingroup$

Consider the matrix $A_n$ defined for positive integers $n$ by setting the $(i,j)$th entry to $1$ if $j$ divides $i$, and $0$ otherwise, for $1\leq i,j\leq n$. For example, $$A_6=\begin{bmatrix}1&0&0&0&0&0\\1&1&0&0&0&0\\1&0&1&0&0&0\\1&1&0&1&0&0\\1&0&0&0&1&0\\1&1&1&0&0&1\end{bmatrix}.$$ This matrix has the interesting property that $\det A_n=1$ for all $n$ (since it is a lower triangular matrix), and that its inverse can be described explicitly as having $(i,j)$th entry equal to $\mu(j/i)$ if $i\mid j$, and $0$ otherwise, where $\mu$ is the möbius function. This fact is easily seen to be equivalent to möbius inversion.

Q. Does this matrix have a name? This seems like a basic enough matrix that its properties could (should?) be well-studied, but I don't know what key words to search to find out more, if it has a special name at all.

$\endgroup$
4

1 Answer 1

4
$\begingroup$

This matrix is the adjacency matrix of the poset $P$ of integers between $1$ and $n$ (inclusive) under division, regarded as a directed graph. It sits inside the incidence algebra, as Sungjin mentions in the comments, which you can think of as the subalgebra of the matrix algebra $\text{End}(k[P])$ generated by the edges of the directed graph, and in incidence algebra terminology it's called the zeta function of the poset, and its inverse is called the Mobius function of the poset. We have a generalization of Mobius inversion that relates multiplying by the zeta function and multiplying by the Mobius function that specializes to ordinary Mobius inversion as well as inclusion-exclusion and other fun stuff.

(The definition of the incidence algebra I gave above is only equivalent to the usual definition for finite posets. In the infinite case there are at least two different algebras you could write down, and the usual one requires that the poset be locally finite. The one I wrote down makes no such requirement but it has fewer elements.)

Somewhat more generally, you can define the category algebra of a (small) category $C$ to be the free $k$-module on the morphisms of $C$, with composition given by either the composition in $C$ if defined or zero otherwise. This construction generalizes the incidence algebra (thinking of posets as categories) but also the construction of group algebras. (Again, in the finite case, and again in the infinite case there are at least two different algebras you could write down.) If $C$ has finitely many morphisms you can again consider a zeta function given by the sum of all the morphisms, and if this element has an inverse it's called the Mobius function of $C$. See, for example, Tom Leinster's Notions of Mobius inversion.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .