Question: Let $M_n$ be the set of all square $n \times n$ $(0,1)$-matrices. I write $$\mathbf{char}(M_n)=\{\chi(X)\text{ }|\text{ }\chi(X)\text{ is the characteristic polynomial for some matrix in } M_n. \}$$ How do I compute the order of $\mathbf{char}(M_n)$ ?
For example: $M_2$ has $16$ distinct matrices with $6$ distinct characteristic polynomials: $$\mathbf{char}(M_2)=\{X^2,X^2-X,X^2-2X+1,X^2-X-1,X^2-2X,X^2-1\}$$
I know that similar matrices have the same characteristic polynomial but the converse is false. I am not certain the question is equivalent to counting similar matrices ?
Edit: as pointed out in the comments, I had misunderstood the question
For any monic polynomial $p$ of degree $n$ over a field $K$, one can construct its companion matrix which is an $n \times n$ matrix over $K$ with characteristic polynomial $p$. Therefore counting the number of possible characteristic polynomials of $n \times n$ matrices over $K$ is the same as counting the number of possible monic polynomials of degree $n$ over $K$, i.e. $|K|^n$.