Theorem: Let $ f \in \mathbb{F}[x] $ and $ A_f = c(f) $ be the companion matrix of $ f $.
Given $ g \in \mathbb{F}[x] $ show that $ \dim \ker g(A_f) \leq \deg g $. ( Hint: show that $ \deg f - \deg g $ first columns of $ g(A_f) $ are linearly independent. )
I have no Idea what to do. I wrote
$ g(x) = b_0 + b_1 \cdot x+...+ b_{m-1} \cdot x^{m-1} + b_m \cdot x^m $,
$ f(x) = a_0 + a_1 \cdot x +...+ a_{n-1} \cdot x^{n-1} + a_n \cdot x^n $.
$c(f)=\left(\begin{array}{cccccc}0 & 0 & 0 & 0 & \ldots & -a_{0} \\ 1 & 0 & 0 & 0 & \ldots & -a_{1} \\ 0 & 1 & 0 & 0 & \ldots & -a_{2} \\ & \vdots & & & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \ldots & -a_{n-1}\end{array}\right)$ .
$ g(A_f) = b_0 I_n + b_1 A_f + ... + b_{m-1} A_f^{m-1} + b_m A_f^m $.
I got stuck because I have no idea how the matrix $ g(A_f) $ should look like in general, so I couldn't proceed to find $ \dim \ker g(A_f) $.
Do you have any ideas?
Well, if you try to calculate the power of the matrix $A_f$, you will get it at once. First, let's do it for $A_f^2$, its first n-2 columns are exactly the 2~ n-1 columns of $A_f$ : $$\begin{pmatrix} 0 & & & &*&*\\ 0 &0& & &*&*\\ 1 &0&0&& *&*\\ \vdots&\vdots& \vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&* &* \end{pmatrix}$$ it is obvious that the first $n-2$ columns are linearly independent, and we can ignore how the last two columns looks like exactly. Similarly, for $A_f^3$, its first $n-3$ columns are the 3~n-1 columns of $A_f$, and so on.
Then, the matrix $g(A_f)$ looks like $$\begin{pmatrix} b_0& & & &*&*\\ b_1&\ddots& & &*&*\\ b_2 &\ddots&b_0&& *&*\\ \vdots&\ddots&b_1&\ddots&\vdots&\vdots\\ b_m&\vdots &b_2 & \cdots& *&*\\ \vdots&\ddots &\vdots& &\vdots&\vdots\\ 0&\cdots&b_m&\cdots&* &* \end{pmatrix}$$ Since $b_m\neq 0$, we derive what we want.