Computing the inverse of some matrix 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$.
 A: 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. ////
A: 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).
A: 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.
