Let $\phi\colon F\to G$ be a homomorphism of finitely generated abelian groups. If $F$ is free, then $\ker(\phi)$ is also free and thus admits a basis.
Question: Is there a general procedure to find a basis for $\ker(\phi)$?
As an example, consider the homomorphism $\phi\colon\mathbb Z^3\to (\mathbb Z/2)^2$ given by the matrix
$$
\begin{pmatrix}
1&1&0\\0&1&1
\end{pmatrix}.
$$
After playing around, I guess that the elements $\begin{pmatrix}0\\2\\0\end{pmatrix}$, $\begin{pmatrix}1\\1\\0\end{pmatrix}$ and $\begin{pmatrix}0\\1\\1\end{pmatrix}$ form a basis. Is this true? How could I see this in a systematic way?
Best Answer
One way is to proceed recursively, by considering subgroups of $\mathbb{Z}^k$ as $k$ increases.
For $k=1$, you are considering subgroups of $\mathbb{Z}$, which are straightforward: they are generated by the least positive element in the subgroup (if there is one; otherwise, they are the zero subgroup).
Now, for subgroups of $\mathbb{Z}^{k+1}$, given a subgroup $H$, consider $$\begin{align*} H_1 &= \{ a\in H \mid a = (a_1,\ldots,a_k,0)\text{ for some }a_i\in\mathbb{Z}\};\\ H_2 &= \{ (0,0,\ldots,0,a_{k+1})\mid (a_1,\ldots,a_k,a_{k+1})\in H\text{ for some }a_i\in\mathbb{Z}\}. \end{align*}$$ They are both subgroups; $H_2$ is isomorphic to a subgroup of $\mathbb{Z}$, and $H_1$ is isomorphic to a subgroup of $\mathbb{Z}^{k}$. Assuming you already know how to find bases for subgroups of $\mathbb{Z}^k$, let $\beta$ be a basis for $H_1$; if $H_1$ is trivial, $\beta=\emptyset$. Since $H_2$ is isomorphic to a subgroup of $\mathbb{Z}$, there exists $a\geq 0$ such that $H_2 = \langle(0,0,\ldots,0,a)\rangle$. If $a=0$, then $H=H_1$ and we are done, with basis $\beta$. If $a\neq 0$, find $h\in H$, $h=(a_1,\ldots,a_{k},a)$.
Then $\beta\cup\{h\}$ is a basis for $H$. Indeed, if $(b_1,\ldots,b_k,b_{k+1})\in H$, then $(0,0,\ldots,0,b_{k+1})\in H_2$, so there exists $\alpha\in\mathbb{Z}$ such that $(b_1,\ldots,b_k,b_{k+1})-\alpha h\in H_1$, and therefore we can express $(b_1,\ldots,b_{k},b_{k+1})-\alpha h$ in terms of $\beta$. So $\beta\cup\{h\}$ generates. To show it is linearly independent, suppose $$\alpha_1 v_1+\cdots+\alpha_k v_k + \alpha h = \mathbf{0}$$ with $v_i\in\beta$. This requires $\alpha=0$ by looking at the last coordinate, and so since $\beta$ is linearly independent, $\alpha_1+\cdots+\alpha_k = 0$ as well.
To see this in action for your example, you are looking for the kernel of the matrix. The kernel of the matrix, call it $K$, consists of all elements $(a,b,c)\in\mathbb{Z}^3$ such that $a\equiv b\pmod{2}$ and $b\equiv c\pmod{2}$ (reading off the matrix); that is, all vectors in which all three components are odd, or all three components are even.
The set of all vectors of the form $(a,b,0)$ that are in $K$ are the vectors that have $a$ and $b$ both even. The set of integers that can be the last coordinate of a vector in $K$ is all of $\mathbb{Z}$. So $$\begin{align*} K_1 &= \{(a,b,0)\in \mathbb{Z}^3 \mid a\equiv b\equiv 0\pmod{2}\},\\ K_2 &=\{0\}\times\{0\}\times \mathbb{Z} \end{align*} $$ $K_2$ is generated by $(0,0,1)$, so we pick a vector from $K$ that has last coordinate equal to $1$. One such is $k=(1,1,1)$.
So now we want to find a basis for $K_1$. Note that since we need all components to be congruent, and the last is congruent to $0$ modulo $2$, then in fact $$K_1 = \{ (a,b,0)\in\mathbb{Z}^3\mid a,b\in 2\mathbb{Z}\}.$$
At this point it is easy to find a basis (e.g., $(2,0,0)$ and $(0,2,0)$), but let's continue the process. Look at the subgroup $H$ of $\mathbb{Z}^2$ isomorphic to $K_1$, $$H = \{ (a,b)\in\mathbb{Z}^2 \mid a,b\in2\mathbb{Z}\}.$$ We have $$\begin{align*} H_1 &= \{ (a,0)\in \mathbb{Z}^2\mid a\in 2\mathbb{Z}\},\\ H_2 &= \{(0,b)\in H\}. \end{align*}$$ The elements of $\mathbb{Z}$ that can be second coordinates of vectors in $H$ are $2\mathbb{Z}$. The ideal is generated by $2$, so we find a vector $h\in H$ with second coordinate equal to $2$. One such vector is $h=(0,2)$ (which corresponds to $(0,2,0)$ in $K$).
And then we want a basis for $H_1$. A basis is clearly given by $h_1=(2,0)$ (which corresponds to $(2,0,0)$ in $K$). This gives $\{(2,0), (0,2)\}$ as a basis for $H$.
Going back to $K$, we have that $\beta=\{(2,0,0), (0,2,0)\}$, and $k=(1,1,1)$.
So a basis for $K$ is $\bigl\{(2,0,0), (0,2,0), (1,1,1)\bigr\}$.
The process above is in fact the proof that a submodule of a finitely generated free module over any PID is free, applied to the case of $\mathbb{Z}$. There are other methods, of course.
Added. Smith Normal Form, mentioned by lhf, is a way of doing the above without first trying to figure out the kernel; it requires you to keep track of the operations in question.
Here, you would start as with usual Gauss-Jordan reduction, but without multiplying a row by anything other than $1$ or $-1$. First, we would subtract the second row from the first via multiplication on the left by an elementary matrix: $$\left(\begin{array}{rr} 1& -1\\0&1\end{array}\right)\left(\begin{array}{ccc}1&1&0\\0&1&1\end{array}\right) = \left(\begin{array}{ccr}1 & 0 & -1\\0 & 1 & 1\end{array}\right).$$ Then we eliminate the nonzero entries in columns to the right of the pivots, via multiplication on the right: we want to add the first column to the third, and subtract the second column from the third. This is the same as: $$\left(\begin{array}{ccr}1 & 0 & -1\\0 & 1 & 1\end{array}\right)\left(\begin{array}{rrr}1 & 0 & 1\\0 & 1 & -1\\0 & 0 & 1\end{array}\right) = \left(\begin{array}{ccc}1 & 0 & 0\\0 & 1 & 0 \end{array}\right).$$ Putting it all together, you have: $$\left(\begin{array}{ccc} 1 & 0 & 0\\ 0 & 1 & 0 \end{array}\right) = \left(\begin{array}{cr} 1&-1\\0 & 1\end{array}\right)\left(\begin{array}{ccc}1 & 1 &0\\0 & 1 & 1\end{array}\right)\left(\begin{array}{rrr}1 & 0 & 1\\0 & 1 & -1\\0 & 0 & 1\end{array}\right).$$ Now you want to interpret this as linear transformations and change-of-bases matrix. The matrix on the far right tells you to you take the basis of $\mathbb{Z}^3$ given by its columns, $(1,0,0)$, $(0, 1, 0)$, and $(1,-1,1)$; the matrix on the left end of the right hand side tells you to take the basis for $\mathbb{Z}^2$ given by the columns of its inverse $$\left(\begin{array}{cr}1& -1\\0 & 1\end{array}\right)^{-1} = \left(\begin{array}{cc}1 & 1\\0 & 1\end{array}\right),$$ that is, $(1,0)$, $(1,1)$. Then $A$ is the linear transformation $\mathbb{Z}^3\to\mathbb{Z}^2$ that sends $(1,0,0)$ to $(1,0)$; $(0,1,0)$ to $(1,1)$; and $(1,-1,1)$ to $(0,0)$. So the kernel is generated by $(1,-1,1)$.
Now look at the map $\mathbb{Z}^2\to(\mathbb{Z}/2\mathbb{Z})^2$ given by reduction of coordinates. The kernel is $2\mathbb{Z}^2$, so it has basis given by $2(1,0) = (2,0)$ and $2(1,1)=(2,2)$. Pulling these back to $\mathbb{Z}^3$ along $A$ gives $2(1,0,0) = (2,0,0)$ (preimage of $(2,0)$ in the basis), $2(0,1,0)= (0,2,0)$ (preimage of $(2,2)$ in the basis), plus the kernel. So we get that the kernel of the composite map has basis $(2,0,0)$, $(0,2,0)$, and $(1,-1,1)$.
So another basis for the kernel is $(2,0,0)$, $(0,2,0)$, and $(1,-1,1)$.