# Solving matrix equations (or systems of linear equations) over $\mathbb Z$

Here is an extract from Artin's "Algebra":

Proposition 14.4.9 Let $A$ be an $m \times n$ matrix, and let $P$ and $Q$ be invertible integer matrices such that $A' = Q^{-1}AP$ has the diagonal form described in Theorem 14.4.6.

(a) The integer solutions of the homogeneous equation $A'X' = 0$ are the integer vectors $X'$ whose first $k$ coordinates are zero.

(b) The integer solutions of the homogeneous equation $AX = 0$ are those of the form $X = PX'$, where $A'X' = 0$.

(c) The image $W'$ of multiplication by $A'$ consists of the integer combinations of the vectors $d_1 e_1, \ldots, d_k e_k$.

(d) The image $W$ of multiplication by $A$ consists of the vectors $Y = QY'$, where $Y'$ is in $W'$.

(b),(d) We regard $Q$ and $P$ as matrices of changes of basis in $\mathbb{Z}^n$ and $\mathbb{Z}^m$, respectively. The vertical arrows in the diagram 14.4.7 [below] are bijective, so $P$ carries the kernel of $A'$ bijectively to the kernel of $A$, and $Q$ carries the image of $A'$ bijectively to the image of $A$. $\tag*{$\blacksquare$}$ $\require{AMScd}$ \begin{CD} \mathbb{Z}^n @>A'>> \mathbb{Z}^m\\ @V P V V @VV Q V\\ \mathbb{Z}^n @>>A> \mathbb{Z}^m \end{CD}

I don't understand the proof of $(b),(d)$. Specifically,

1. Why can $Q$ (resp. $P$) be regarded as matrices of changes of basis in $\mathbb Z^n$ (resp. $\mathbb Z^m$)? Shouldn't $P$ and $Q$ be switched in this sentence? I mean $P$ looks like a change of basis matrix of $\mathbb Z^n$ (and $Q$ for $\mathbb Z^m)$.
2. How exactly does the bijectivity of $P$ and $Q$ imply that $P$ and $Q$ carry the kernel and image of $A'$ bijectively to those of $A$?

To 1. You are right, $Q$ is a change of basis in $\mathbb{Z}^m$ and $P$ a change of basis in $\mathbb{Z}^n$, as depicted in the diagram.
To 2. This means that $P(\mathrm{ker}(A'))=\mathrm{ker}(A)$, for "$\subset$": Let $v\in\mathrm{ker}(A')$, i.e. $A'v=0$. But then also $APv=QA'v=Q0=0$, so $Pv\in\mathrm{ker}(A)$. For "$\supset$": Let $w\in\mathrm{ker}(A)$, i.e. $Aw=0$. Then $QA'P^{-1}w=Aw=0$, so $P^{-1}w\in\mathrm{ker}(QA')=\mathrm{ker}(A')$. This means $w=PP^{-1}w\in P(\mathrm{ker}(A'))$. So $P$ gives a bijection $$P\vert_{\mathrm{ker}(A')}\colon \mathrm{ker}(A')\rightarrow \mathrm{ker}(A)$$ (with inverse $P^{-1}\vert_{\mathrm{ker}(A)}$).
The same way, $Q(\mathrm{im}(A'))=\mathrm{im}(A)$, so $Q\vert_{\mathrm{im}(A')}$ is a bijection $\mathrm{im}(A')\rightarrow \mathrm{im}(A)$.
• Probably this is obvious, but how exactly do you show that $P^{-1}w\in \ker A'$ implies $w=PP^{-1}\in P(\ker A')$? I.e., why does taking $P$ of both sides of $P^{-1}w\in \ker A$ preserve the "$\in$" sign?
• Well, $P(\mathrm{ker}A')$ is defined as the set $$P(\mathrm{ker}A')=\{Pa\vert a\in\mathrm{ker}A'\},$$ and $w=P\underset{\in\mathrm{ker}A'}{(\underbrace{P^{-1}w})}$ is an element of this form. Mar 30 '18 at 21:26