$C(M)=\{A\in M_n(\mathbb{C}) \mid AM=MA\}$ is a subspace of dimension at least $n$. Let $M_n(\mathbb{C})$ denote the vector space over $\mathbb{C}$ of all $n\times n$ complex matrices. Prove that if $M$ is a complex $n\times n$ matrix then $C(M)=\{A\in M_n(\mathbb{C}) \mid AM=MA\}$ is a subspace of dimension at least $n$.


My Try:

I proved that $C(M)$ is a subspace. But how can I show that it is of dimension at least $n$. No idea how to do it. I found similar questions posted in MSE but could not find a clear answer. So, please do not mark this as duplicate.

Can somebody please help me how to find this? 

EDIT: Non of the given answers were clear to me. I would appreciate if somebody check my try below:

If $J$ is a Jordan Canonical form of $A$, then they are similar. Similar matrices have same rank. $J$ has dimension at least $n$. So does $A$. Am I correct?
Your approach is correct. Let $PMP^{-1}=J$ with invertible $P$ and Jordan form $J$. Then 
$$
\begin{align}
AM=MA &amp;\Longleftrightarrow PAMP^{-1}=PMAP^{-1} \\
&amp;\Longleftrightarrow PAP^{-1} PMP^{-1} = PMP^{-1} PAP^{-1}\\
&amp;\Longleftrightarrow PAP^{-1} J=   J PAP^{-1}.
\end{align}
$$
Thus, we have 
$$
\phi_P : C(M) \rightarrow C(J)
$$
given by $\phi_P(A) = PAP^{-1}$, is an invertible linear transformation with $\phi_P^{-1}(B)= P^{-1}BP$. So, $C(M)$ and $C(J)$ are isomorphic via the isomorphism $\phi_P$. Therefore, $C(M)$ and $C(J)$ have the same dimensions over $\mathbb{C}$. 

Then if you prove that $C(J)$ has dimension at least $n$, then the same is true for $C(M)$ too. 

Alternatively, as I commented last year, you can also use the general formula given in Centralizer of a Matrix. This gives the following info:

Let $\mathbb{F}$ be a field and $M\in M_n(\mathbb{F})$. Denote by $C(M)=\{A\in M_n(\mathbb{F}) | AM=MA\}$ the centralizer of $M$. The dimension of 
$C(M)$ over   $\mathbb{F}$ is given by
$$
\mathrm{dim}_{\mathbb{F}} C(M) = \sum_p (\mathrm{deg}(p))\sum_{i,j} \min (\lambda_{p,i}, \lambda_{p,j}),
$$
where $p$ is any irreducible polynomial that divides the characteristic polynomial of $M$, and $\lambda_p= \sum \lambda_{p,i}$ is the exact power of $p$ in the characteristic polynomial of $M$. Here, $\lambda_{p,i}$ are the powers of $p$ in the primary decomposition of the $\mathbb{F}[x]$-module $\mathbb{F}^n$ in which $x$ acts by $M$-multiplication on the left. 

By taking $i=j$ only in the double sum, we obtain that
$$
\mathrm{dim}_{\mathbb{F}}C(M) \geq \sum_p (\mathrm{deg}(p)) \sum_i \lambda_{p,i} = n.
$$

The equality occurs if and only if the minimal polynomial and the characteristic polynomial of $M$ coincide. Moreover, we have in this case, 
$$
C(M)=\{f(M) | f\in \mathbb{F}[x]\} = \mathrm{span}_{\mathbb{F}} \{ I, A, \ldots , A^{n-1}\}.
$$
In the case that $M$ has $n$ unique eigenvalues and eigenvectors, there is a fairly straightforward argument. For the eigenvalue $\lambda$, there are vectors $v_L$ and $v_R$ which are the left and right eigenvectors. Construct the $n\times n$ matrix $C_\lambda = v_L v_R^T$: $C_v$ is such that all its rows are scalar multiples of $v_R$ and all its columns are scalar multiples of $v_L$.

Therefore $M C_\lambda = C_\lambda M = \lambda C_\lambda$.

I'd expect to be able to make good headway working with generalised eigenvectors.