Existence of a matrix, characteristic polynomial and minimal polynomial Let $k$ be a field and let $p(x),q(x)$ be elements of $k[x]$. If $q(x)$ divides $p(x)$ and if every root of $p(x)$ is a root of $q(x)$ prove there exists a matrix $A$ having minimal polynomial equal $q(x)$ and characteristic polynomial equal $p(x)$.
So I tried first an example. Take $p(x)=(x-3)^{2}(x-5)$ and $q(x)=(x-3)(x-5)$.
Now set:
$C= \left( \begin{array}{ccc}
3 & 0 & 0\\
0 & 3 & 0\\
0 & 0 & 5\end{array} \right)$
Then $C$ is a diagonal matrix and its characteristic polynomial is equal $p(x)$ while its minimal polynomial is $q(x)$.
Now how to deal with the general case? I'm not sure the same argument would hold for any general $p(x)$, can you please help?
 A: First, I'll note that the statement given is incorrect, read literally. For one thing, you need $q(x)$ to be monic, since the minimal polynomial is always monic; also, depending on your definition of characteristic polynomial, you need either $p(x)$ to be monic, or you need the leading coefficient to be $(-1)^{\deg p}$. 
Even with those to issues, it is still incorrect as written:
Take $k=\mathbb{R}$, $p(x) = x^4-1$, and $q(x)=x^2-1$. Since $p(x)=(x^2-1)(x^2+1)$, then $q(x)$ divides $p(x)$. In addition, every root of $p(x)$ is a root of $q(x)$ (the only roots are $1$ and $-1$. However, there is no matrix that has $x^4-1$ as the characteristic polynomial and $x^2-1$ as the minimal polynomial (even over $\mathbb{C}$). Why? Because every irreducible factor of the characteristic polynomial of $A$ must divide the minimal polynomial of $A$. So if a matrix with real coefficients has characteristic polynomial $x^4-1$, then the minimal polynomial must be a multiple of $x^2+1$, which $q(x)$ is not.
To fix the statement, you should change 

... every root of $p(x)$ is a root of $q(x)$ ...

to

... every root of $p(x)$ in an algebraic closure of $k$ is a root of $q(x)$...

Once that change is made, the asserted result is true.
The simplest way to do this is to use the Rational Canonical Form. Let $\phi_1(x),\ldots,\phi_k(x)$ be the irreducible factors (over $k$) of $p(x)$:
$$p(x) = (-1)^{n}(\phi_1(x))^{n_1}\cdots (\phi_k(x))^{n_k}.$$
The conditions on $q(x)$ and $p(x)$ mean that $\phi_1,\ldots,\phi_k$ are also precisely the irreducible factors of $q(x)$, so we have
$$q(x) = (\phi_1(x))^{m_1}\cdots (\phi_k(x))^{m_k}$$
where $1\leq m_i\leq n_k$ for each $i$.
This tells you that in the rational canonical form for the matrix you are looking for, the companion matrices corresponding to $\phi_i(x)$ will have a block corresponding to the companion matrix of $\phi_i(x)^{m_i}$, but no companion matrix with larger power; and the exponents will add up appropriately to give the characteristic polynomial. So the simplest way to construct a matrix with $p(x)$ as the characteristic polynomial and $q(x)$ as the minimal polynomial is to take a block diagonal matrix in which each block is a companion matrix, with one block each for $\phi_1(x)^{m_1}$, $\phi_2(x)^{m_2},\ldots,\phi_k(x)^{m_k}$, and then "fill out" with $n_1-m_1$ companion blocks for $\phi_1(x)$, $n_2-m_2$ companion blocks for $\phi_2$, etc. This gives a matrix over $k$ that has $p(x)$ as the characteristic polynomial and $q(x)$ as the minimal polynomial
If $p(x)$ splits over $k$, you can instead use the Jordan canonical form. The multiplicities of the roots in $q(x)$ give you the largest Jordan block size that needs to be and can be present, while the multiplicities in $p(x)$ tell you how many $1\times 1$ blocks you should add to "fill out" the matrix.
A: Your example has a bottom-right 2×2 block with characteristic AND minimal polynomial g.  The top-left block is a matrix with characteristic polynomial p / g and minimal polynomial dividing g.
Next try $p(x)=(x-3)^3(x-5)$ and $g(x)=(x-3)^2(x-5)$.  Your g was a little too special.

Next you basically do that same thing inductively:
Make a block with minimal polynomial = characteristic polynomial g.  Then make a block with minimal polynomial = characteristic polynomial g2 = gcd( g, p / g ).  Continue making blocks with gn+1 = gcd( gn, p / ( g ⋅ g2 ⋅ ⋯ ⋅ gn ) ).
