So the characteristic pol. of A is and its minimal pol. MUST be the same, otherwise, as the char. pol. and the min. pol. have the same irreducible factors, the min. pol would be , but then A would be diagonalizable as its min. pol. would be the product of different linear factors...
Now, check that the following matrix does the trick:
This matrix is known as the companion matrix of the pol. and it's used to prove that for any given monic polynomial there exists a square matrix whose char. pol. is that given monic pol.