Computing the inverse of some matrix

Question

Let $A(n) = (a_{i,j})_{1\le i,j \le n}$ be defined through: $a_{i,j} = 1, \text{ if } i \equiv 0 \mod (j)$, $0$ otherwise. What is the inverse of $A$? Is there an "easy" formula for the inverse? It seems that the inverse of the matrix has only entries $0,1,-1$.

Answer 1

1. Your matrices $A(n)$ are parts of the infinite matrix $A = (A_{i,j})_{i,j\geq 1}$ with entries given by

$$A_{i,j} = \mathbf{1}_{\{ j \mid i \}} = \begin{cases} 1, & \text{if } j \mid i \\ 0, &\text{otherwise.} \end{cases}$$

Then for each $n$, we would like to find the $n\times n$ matrix $B(n)$ for which $A(n)B(n) = I_d$ is true. Note that this relation is enough to guarantee that $B(n) = A(n)^{-1}$.

We accomplish this by constructing an infinite lower-triangular matrix $B = (B_{i,j})_{i,j\geq 1}$ for which the relation $AB = I$ holds. Once this is proved, the upper-leftmost $n\times n$-minor of $B$

$$B(n) = (B_{i,j})_{1\leq i,j\leq n}$$

will serve as the inverse matrix of $A(n)$.

2. That being said, we want to solve the system of equations

$$ \forall i,j \ : \quad \sum_{d = 1}^{\infty} A_{i,d}B_{d,j} = \delta_{i,j}. $$

Plugging $A_{i,d} = \mathbf{1}_{\{ d \mid i \}}$, this reduces to

$$ \sum_{d \mid i} B_{d,j} = \delta_{i,j}. \tag{2} $$

Such $B$ is easily determined by applying the Möbius inversion formula to the sequence $(B_{i,j})_{i\geq 1}$ for each fixed $j$:

$$ B_{i,j} = \sum_{d\mid i} \mu\left(\frac{i}{d}\right)\delta_{d,j} = \mu\left(\frac{i}{j}\right) \mathbf{1}_{\{j \mid i\}} = \begin{cases} \mu(i/j), & \text{if } j \mid i \\ 0, &\text{otherwise.} \end{cases} $$

The corresponding infinite matrix $B$ is lower triangular and solves $AB = I$ as desired. ////

Answer 2

Your matrix is http://oeis.org/A051731:

Triangle read by rows: T(n,k) = 1 if k divides n, T(n,k) = 0 otherwise.

and (according to the OEIS entry) the inverse matrix is http://oeis.org/A054525:

Triangle T(n,k): T(n,k) = mu(n/k) if k divides n, T(n,k)=0 otherwise (n >= 1, 1<=k<=n).

where mu is the Möbius function (which takes only the values $-1, 0, 1$, confirming your conjecture).

Answer 3

Let's look at $A_3$ :

$$A_3 = \begin{pmatrix}1&0&0 \\ 1&1&0 \\ 1&0&1 \end{pmatrix}$$

With various methods you can obtain $A_3^{-1}$ :

$$ A_3^{-1} = \begin{pmatrix} 1&0&0 \\ -1&1&0 \\ -1&0&1 \end{pmatrix}$$

Now there seems to be a trend here, with the $1$'s under the diagonal being turned into $-1$'s.

Let's look at $A_4$ :

$$A_4 = \begin{pmatrix}1&0&0&0 \\ 1&1&0&0 \\ 1&0&1&0 \\1&1&0&1 \end{pmatrix}$$

Now $A_4^{-1}$ :

$$A_4^{-1} = \begin{pmatrix} 1&0&0&0\\-1&1&0&0\\-1&0&1&0\\0&-1&0&1\end{pmatrix}$$

Now unfortunately, what we observe in $A_3$ doesn't hold true for $A_4$ so we need to lay out the equations :

Let's note $A_n = (a_{i,j})$ and $A_n^{-1}=(b_{i,j})$.

We have the following equations :

$$\forall i,j\in [1,n] : \sum_{k=1}^n a_{ik}\cdot b_{kj}=\delta_{ij} = \left\{\begin{matrix}0 &\text{if }i\ne j\\1&\text{if }i=j\end{matrix}\right.$$

(I don't have time to finish now, I'll come back later, feel free to try and use those equations, next step is using the $a_{ij}$ definition)

EDIT : Just saw Martin's answer, no way I would have solved this. I won't delete this answer as i think it highlights the general approach to such problems.