Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Neither $(1,1,0)$ nor $(0,1,1)$ are in the kernel; the first is mapped to $(0+2\mathbb{Z},1+2\mathbb{Z})\neq\mathbf{0}$, and the second to $(1+2\mathbb{Z},0+2\mathbb{Z})\neq \mathbf{0}$. –  Arturo Magidin Apr 13 '11 at 17:03
    
@Arthuro, you are right, I messed up the example, sorry. (That shows how badly I need a systematic way to go.) –  Rasmus Apr 13 '11 at 20:05

2 Answers 2

up vote 6 down vote accepted

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)$.

share|improve this answer
    
Thank you for this great answer! –  Rasmus Apr 13 '11 at 20:07
    
I edited one detail which I think was incorrently phrased. Hope you view this as an act of appreciation of your answer. –  Rasmus Apr 13 '11 at 20:50
    
@Rasmus: Thank you for the correction; I thought I had gone back and fixed that. Just goes to show. –  Arturo Magidin Apr 13 '11 at 21:26
    
Arturo, above you multiply a $2\times 3$-matrix with a $3\times 3$-matrix, which should result in a $2\times 3$-matrix. The last row does not exist. –  Rasmus Apr 14 '11 at 9:33
    
@Rasmus: Yes; sometimes it happens when I'm TeXing... Thanks. –  Arturo Magidin Apr 14 '11 at 12:59

Try also the Smith normal form.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.