$F^n$ as a direct sum of cyclic submodules Let $A$ be an $n\times n$ matrix over a field $F$. Denote by the same letter $A$ the linear operator $F^n\to F^n$ given by $X\mapsto AX$. Endow $F^n$ with the structure of an $F[t]$-module by defining scalar multiplication as follows: if $f(t)\in F[t]$ and $X\in F^n$, then $f(t)X=[f(A)]X$. By the structure theorem for modules over PIDs, $F^n$ is a direct sum of cyclic modules each of which is of the form $F[t]/(g(t))$ where $g(t)$ is a power of a monic irreducible polynomial.
The question is how to find this decomposition in practice? I believe one should reduce some matrix to the Smith normal form and then draw conclusions. But I can't seem to adapt the usual alorithm for groups for this case. I guess it would be best if someone could give some (nontrivial) example (say with $n=3$, $F=\mathbb R$, and $A$ a matrix of your choice).

The key result is that we have an isomorphism of $F[X]$-modules $F^n\simeq F[X]^n/\ker(XI_n-A)$. 
I don't have much time now, so I leave you to find some references for now on the web or in the standard books. If I have time tonight (French time) , I will edit my answer and provide a full proof.
Now, you just apply the standard procedure . Find the Smith normal form of $XI_n-A$: $$\begin{pmatrix} I_{n-r}  & & & \cr & P_1 & & \cr & & \ddots & \cr & & & P_r\end{pmatrix},$$
where $P_1,\ldots, P_r\in F[X]$ are monic of degree $\geq 1$  and $P_1\mid P_2\mid\cdots\mid P_r.$
Then $F^n\simeq F[X]/(P_1)\times\cdots \times F[X]/(P_r)$.
