Diagonalizable matrices in $M_{2\times 2}(\mathbb{F}_2)$ List all diagonalizable $2\times 2$ matrices over the a field $F$ consisting of two elements $0$ and $1$.
I want to try and do this using C++, but perhaps this isn't the place to ask. I have an idea as to how I'd do it.
 A: If $M$ is diagonalizable, we have $M=PDP^{-1}$ with $D$ diagonal. Since $D^2=D$, we get $M^2=M$. Conversely, if $M^2=M$, $M$ is annihilated by $X^2-X=X(X-1)$ which has simple roots and splits over $\mathbb{F}_2$. So $M$ is diagonalizable.
Hence the diagonalizable matrices are exactly the idempotents, i.e. $M$ such that $M^2=M$. This gives three possibilities for the minimal polynomial of $M$: $X$, $X-1$, and $X^2-X$. In the latter case, it must be equal to the characteristic polynomial as well. 
We get the null and the identity matrix with the first two cases, and the matrices whose characteristic polynomial is $X^2-X$ in the last case. The latter correspond to the matrices $M$ with $\mbox{trace} \;M=1$ and $\det M=0$:
$$
M=\pmatrix{a&b\\ c&d}\qquad a+d=1\qquad ad-bc=0.
$$
This leaves a few cases to consider and this gives in the end eight diagonalizable matrices:
$$
\pmatrix{0& 0\\0&0}\;\pmatrix{1& 0\\0&1}\;\pmatrix{1& 0\\0&0}\;\pmatrix{1& 1\\0&0}\; \pmatrix{1& 0\\1&0}\;\pmatrix{0& 0\\0&1}\;\pmatrix{0& 0\\1&1}\;\pmatrix{0& 1\\0&1}.
$$
Conclusion: $50\%$ of the matrices are diagonalizable in $M_2(\mathbb{F}_2)$.
A: there are only finitely many (and a small number too) of matrices to consider so, of course, you can just write some code that will attempt to diagonlize a $2\times 2$ matrix, and just run over all the relevant matrices. 
But in this case it's a lot easier (and more instructive) to figure it out using a bit of linear algebra. For instance, if the characteristic polynomial of a matrix factorizes as the product of distinct linear factors, then the matrix is diagonalizable. Any $2\times 2$ matrix will have characteristic polynomial of degree $2$, and over the field with two elements there are very few such polynomials. Just check them all to see which ones do not factorize as the product of distinct linear factors to find those matrices that might not be diagonalizable. There will not be too many of those, and you can then check them individually.
It will probably take you less time going about this problem mathematically than it would to write and debug your program.  
A: Consider similarity classes(equivalence class consisting of similar matrices)
There are only three classes having representatives: 
$$
\pmatrix{0& 0\\0&0}\;\pmatrix{1& 0\\0&1}\;\pmatrix{1& 0\\0&0},$$
respectively. 
Then consider conjugation with invertible matrices in $M_{2\times 2}(\mathbb{F}_2)$. 
There are only 6 of them. (i.e. $|GL_2(\mathbb{F}_2)|=6$)
Edit:  If we allow finite extension of $\mathbb{F}_2$, then the following one is also a diagonalizable matrix. 
$$
\pmatrix{1&1\\1&0}$$
which has eigenvalues $\lambda=\lambda_1$, $\lambda_2$ satisfying 
$$\lambda^2+\lambda+1=0.$$
So if we consider diagonalizable matrices in $M_{2\times 2}(\mathbb{F}_2)$ over $\overline{\mathbb{F}_2}$ are not necessarily projection. 
A: I'll answer this for $n\times n$ matrices, which gives only slightly more of a challenge. A diagonalisable matrix $A$ is completely determined by its eigenspaces, which form a direct sum giving the whole space, and of cuorse $A$ determines those subspaces as well. Over $\Bbb F_2$ only two eigenspaces are possible, for eigenvalues $0$ and $1$. The matrix $A$ will be the projection onto its $1$-eigenspace parallel to its $0$-eigenspace; it will be idempotent ($A^2=A$) and conversely all idempotent matrices are diagonalisable.
The number of such matrices equals the number of ways to decompose the space $\Bbb F_2^n$ as an ordered direct sum of two subspaces (the eigenspaces of $0$ respectively for $1$; "ordered" just means that swapping the two summands is considered to give a different decomposition, as $A$ will differ). The set of such decompositions into subspaces of dimension $k$ and $n-k$ is the $GL(n,\Bbb F_2)$-orbit of the standard decompostion $\Bbb F_2^n=\Bbb F_2^k\oplus\Bbb F_2^{n-k}$, so by the orbit-stabiliser theorem the number of such decompositions is
$$
  \frac{\#GL(n,\Bbb F_2)}{\#GL(k,\Bbb F_2)\times\#GL(n-k,\Bbb F_2)}
 =2^{k(n-k)}\binom nk_2
$$
(the final factor is the Gaussian binomial coefficient $\binom nk_q$ evaluated at $q=2$), and so the total number of diagonalisable matrices $A$ is
$$
  \sum_{k=0}^n2^{k(n-k)}\binom nk_2
$$
which does not seem to simplify. The values for $n=0,1,2,3,4$ are respectively $1,2,8,58,802$, and having said that I can of course not fail to mention that this is OEIS A132186.
