# Lifting linear solutions mod $p$ to mod $p^2$

I've always known the famous Hensel's lemma in number theory which allows us to lift solutions of an equation $f(x) \equiv 0 \pmod p$ to solutions modulo $p^n$ under non-degeneracy.

What about the following problem : if I start with a linear system of equations of the form $Px \equiv 0 \pmod p$ where $P$ is an $n \times n$ matrix with integer coefficients and $x = \begin{bmatrix} x_1, \dots, x_n \end{bmatrix}^{\top}$. Is there any way I can lift a solution $x \pmod p$ to a solution $\hat x \pmod {p^m}$ such that $\hat x \equiv x \pmod p$? I'd be more than happy to have an answer for $p^2$ and $n=2$ or $n=3$, if that's possible ; I'm usually working with matrices whose lines have one $2$ and two $1$'s, with the rest all zeros, such as this one : $$\begin{bmatrix} 2 & 1 & 1 & 0 \\ 0 & 2 & 1 & 1 \\ 1 & 0 & 2 & 1 \\ 1 & 1 & 0 & 2 \\ \end{bmatrix}$$ (The reason for the symmetry is because this matrix arose from some nice knot in knot theory, but I don't think this context is relevant here.)

I could possibly be interested in a simple existence result, but I am way more interested in being able to count the number of solutions for a particular example, because that's what I need to do in my number-theoretic context ; an understanding of the shape of the solutions would be heaven. Either way, any kind of answer is appreciated as long as it gives some insight.

-

You have found $x_0$ with $Px\equiv b\pmod p$. Make the ansatz $x=x_0+px_1$. Then $Px\equiv b\pmod{p^2}$ is equivalent to $Px_1\equiv \frac{b-Px_0}{p}\pmod{p}$ (where the division on the right hand side is possible by assumption). So you have to solve a linear equation mod $p$ again (though with different right hand side).
Your specific example $P$ is not invertible (rank is $n-1$), so it may depend: either you have no or you have $p$ solutions above a given one.