$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 &\Longleftrightarrow PAMP^{-1}=PMAP^{-1} \\ &\Longleftrightarrow PAP^{-1} PMP^{-1} = PMP^{-1} PAP^{-1}\\ &\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}\}. $$

HINT: A square matrix $A$ over a field $F$ commutes with every $F$-linear combination of non-negative powers of $A$.

That is, for every $a_0$, $\dots$ ,$a_n \in F$,

$$A(\sum_{k=0}^n a_kA^k) = \sum_{k=0}^n a_k A^{k+1} = (\sum_{k=0}^n a_k A^k) A.$$