7
$\begingroup$

For $n \in \mathbb{N}$, let $M_{n}$ denote the $n \times n$ integer matrix whereby the $(i, j)$-entry of $M_{n}$ is equal to $\sum_{k=1}^{j} \left\lfloor \frac{i}{k} \right\rfloor$, for all indices $i$ and $j$. For example, we have that: $$ M_{5} = \left( \begin{array}{ccccc} 1 & 1 & 1 & 1 & 1 \\ 2 & 3 & 3 & 3 & 3 \\ 3 & 4 & 5 & 5 & 5 \\ 4 & 6 & 7 & 8 & 8 \\ 5 & 7 & 8 & 9 & 10 \\ \end{array} \right).$$

Since there are many important number-theoretic properties related to summations of the form $\sum_{k=1}^{n} \left\lfloor \frac{n}{k} \right\rfloor$, it seems natural to consider generalizations and variants of such sums; this leads us to consider matrices of the form $M_{n} = \left[ \sum_{k=1}^{j} \left\lfloor \frac{i}{k} \right\rfloor \right]_{n \times n}$. Using elementary row operations inductively, it is easily seen that $M_{n}$ is invertible, and that the entries in $M_{n}^{-1}$ are in $\mathbb{Z}$. However, it is unclear as to how to construct an explicit formula for the entries of $M_{n}^{-1}$.

It appears that the initial column in $M_{n}^{-1}$ may be evaluated in terms of the Möbius function, as indicated in the following proposition, which is given as a conjecture in the On-Line Encyclopedia of Integer Sequences entry labelled as A092155.

Proposition 1: For $n \in \mathbb{N}_{\geq 2}$, the first $n-1$ entries in the first column of $\left(-M_{n}\right)^{-1}$ are the same as the first $n-1$ entries in the sequence A092155 given by the first differences of $$\left(\mu(n)- \mu\left(\frac{n}{2}\right) : n \in \mathbb{N} \right),$$ letting $\mu$ denote the Möbius function, adopting the convention whereby $\mu(q)$ vanishes for $q$ in $\mathbb{Q} \setminus \mathbb{Z}.$

Why does does the above property hold for all $n \in \mathbb{N}_{\geq 2}$? This is an intriguing question, in part because the sequence A092673 given by expressions of the form $\mu(n)- \mu\left(\frac{n}{2}\right)$ is known to have interesting connections with other number-theoretic sequences such as the ruler function.

To illustrate the conjecture noted above concerning A092155, we begin by computing the inverse of $-M_{5}$:

$$\left( -M_{5} \right)^{-1} = \left( \begin{array}{ccccc} -3 & 1 & 0 & 0 & 0 \\ 1 & -2 & 1 & 0 & 0 \\ 2 & 0 & -2 & 1 & 0 \\ -2 & 1 & 1 & -2 & 1 \\ 1 & 0 & 0 & 1 & -1 \\ \end{array} \right).$$ We thus observe that the first four entries along the first column of the above matrix are the same as the first four entries in A092155, namely: $-3$, $1$, $2$, and $-2$. Computing the inverse of $$-M_{10} = \left( \begin{array}{cccccccccc} -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 \\ -2 & -3 & -3 & -3 & -3 & -3 & -3 & -3 & -3 & -3 \\ -3 & -4 & -5 & -5 & -5 & -5 & -5 & -5 & -5 & -5 \\ -4 & -6 & -7 & -8 & -8 & -8 & -8 & -8 & -8 & -8 \\ -5 & -7 & -8 & -9 & -10 & -10 & -10 & -10 & -10 & -10 \\ -6 & -9 & -11 & -12 & -13 & -14 & -14 & -14 & -14 & -14 \\ -7 & -10 & -12 & -13 & -14 & -15 & -16 & -16 & -16 & -16 \\ -8 & -12 & -14 & -16 & -17 & -18 & -19 & -20 & -20 & -20 \\ -9 & -13 & -16 & -18 & -19 & -20 & -21 & -22 & -23 & -23 \\ -10 & -15 & -18 & -20 & -22 & -23 & -24 & -25 & -26 & -27 \\ \end{array} \right),$$ we obtain the matrix $$\left(-M_{10}\right)^{-1} = \left( \begin{array}{cccccccccc} -3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & -2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & -2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ -2 & 1 & 1 & -2 & 1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & -1 & 1 & -2 & 1 & 0 & 0 & 0 & 0 \\ -3 & 0 & 1 & 0 & 1 & -2 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & -1 & 0 & 1 & -2 & 1 & 0 & 0 \\ 0 & 1 & -2 & 1 & 0 & 0 & 1 & -2 & 1 & 0 \\ 2 & -2 & 1 & 1 & -1 & 0 & 0 & 1 & -2 & 1 \\ -2 & 1 & 0 & -1 & 1 & 0 & 0 & 0 & 1 & -1 \\ \end{array} \right),$$ and we find that the first nine entries $$ -3, 1, 2, -2, 3, -3, 1, 0, 2$$ are the same as the first nine entries of A092155.

Why are the entries of $M_{n}^{-1}$ above the super-diagonal all equal to $0$? It is not obvious why this would be true in general. What is the main diagonal of $M_{n}^{-1}$ of the form $3, 2, 2, ..., 2, 1$? It is not clear how this can be proven to be true for $\mathbb{N}_{\geq 3}$. A conjectured formula for the lower-left entry for $M_{n}^{-1}$ is given in A092673.

Proposition 2: The $(n, 1)$-entry of $M_{n}^{-1}$ is $\mu(n) - \mu\left(\frac{n}{2}\right)$ for $n \in \mathbb{N}$.

How can we prove the above proposition, using known results concerning the Möbius function?

It should be noted that there is a known formula for $\mu(n) - \mu\left(\frac{n}{2}\right)$ involving a summation containing the floor function, but it is not clear how this known identity can be used to attack the above propositions. In 2004, Jon Perry noted the following result on A092673. Letting $x$ be an indeterminate and writing $s_{1} = x$, and letting $$s_{i} = \binom{i+1}{2} - \sum_{j=1}^{i-1} s_{j} \left\lfloor\frac{i}{j}\right\rfloor$$ for indices $i$ in $\mathbb{N}_{\geq 2}$, we have that the coefficient of $x$ in $s_{n}$ is equal to $\mu(n) - \mu\left(\frac{n}{2}\right)$. How is this result related to the above propositions?

We conclude with the following questions.

Question 1: What is $M_{n}^{-1}$?

Question 2: How can we find an explicit number-theoretic formula for a given entry in $M_{n}^{-1}$?

Question 3: Have matrices of the form $M_{n}^{-1}$ been studied previously?

Thank you,

John M. Campbell

$\endgroup$
6
+100
$\begingroup$

Lemma

Let $j\leq i$. Then we have $$ \sum_{j'\leq i}\mu\left(\frac{j'}j\right) \left\lfloor \frac i{j'}\right\rfloor = 1. $$

Proof) We use the idea in this answer Prove $\sum_{d \leq x} \mu(d)\left\lfloor \frac xd \right\rfloor = 1 $.

We have $\sum\limits_{d|k/j} \mu(d)=\epsilon_j(k)$ where $\epsilon_j(k)=1$ if $k=j$, and it is $0$ otherwise. Then the sum $$ \sum_{k\leq x} \sum_{d|k/j} \mu(d) =\sum_{k\leq x} \epsilon_j(k) $$ is $1$ if $x\geq j$, and $0$ otherwise.

Moreover, changing the order of the summation, we have $$ \sum_{d\leq x/j} \mu(d) \sum_{dj|k, k\leq x} 1 = \sum_{d\leq x/j} \mu(d) \left\lfloor \frac x{dj} \right\rfloor = \sum_{j'\leq x} \mu\left(\frac {j'}j\right)\left\lfloor \frac x{j'}\right\rfloor. $$

Back to the problem, we may reduce $M_n$ by column operations $C_n - C_{n-1}, \ldots , C_2-C_1$. This gives $$ M_n E = \left[ \left\lfloor \frac ij\right\rfloor \right]_{(i,j)\in n\times n} $$ where $E$ is the $n\times n$ elementary matrix with $1$ on the main diagonal entries, and $-1$ on immediately above the main diagonal entries.

By Lemma 1, we have $$ M_n E \left[ \mu\left(\frac{j'}j \right) \right]_{(j',j)\in n\times n} = L $$ where $L$ is the $n\times n$ matrix with $1$ on the main diagonal and lower diagonal entries.

Now, we multiply the transpose of $E$ on the right of $L$, then the matrix finally becomes an identity matrix, i.e. $$ M_n E \left[ \mu\left(\frac{j'}j \right) \right]_{(j',j)\in n\times n} E^T = I_n. $$

This will be enough for the formula for $M_n^{-1}$, which now follows that $$ M_n^{-1} = E \left[ \mu\left(\frac{j'}j \right) \right]_{(j',j)\in n\times n} E^T. $$ From this, your propositions will follow.

$\endgroup$
  • $\begingroup$ Short and clear, very nice. $\endgroup$ – user90369 Mar 7 '18 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.