Finding commuting matrices Is there a procedure for finding all matrices which commute with two given square and complex matrices?
For example, given two elements $A,B \in$ $\mathfrak{su}(4)$ is it possible to find all elements which commute with both $A$ and $B$ individually.
 A: Generically (e.g., if one of the matrices has distinct eigenvalues, or more generally, is non-derogatory; for two commuting matrices, the conditions are even weaker), the centralizer of a single matrix just consists of the polynomials in that matrix. So if you pick a pair of commuting matrices at random, the polynomials in them will almost always suffice. 
But if you select a random pair of matrices (not commuting), generically they will generate the entire matrix algebra, and so the centralizer will consist of the scalar matrices. 
Of course, if you're being picky, you have to look at common invariant subspaces, a nuisance.
A: I am answering the two questions (A) and (B) in the OP's comment. The answer is really already contained in @RyanBudney's comment: this is a linear system ($AH = HA, BH = HB,$) so you are asking if a linear system has a solution, and if yes, describe all the solutions. The short answer to both questions is "row reduction".
Addendum A slightly fancier way of putting the above: you are looking for the intersection of kernels of $A\otimes I - I \otimes A$ and $B\otimes I - I \otimes B.$
A: EDIT.  Prop.: If there is a not scalar matrix $H$ s.t. $AH=HA,BH=HB$ then $A,B$ have a non-trivial common invariant subspace.
Proof.  Let $\mathcal{A}$ be the algebra generated by $A,B$; since $H$ commute with the elements of $\mathcal{A}$, $\mathcal{A}$ is not whole $M_n(\mathbb{C})$. According to the Burnside's theorem, $A,B$ have a non trivial common invariant subspace.
As Clement writes below, the converse is false. Moreover, it is easier to solve the system $\{AH=HA,BH=HB\}$ rather than finding the common invariant spaces of $A,B$ of dimension $k\in (o,n)$. For those who are interested in this problem, one reference is
Tsatsomeros, "A criterion for the existence of common invariant subspaces of matrices". http://www.sci.wsu.edu/math/faculty/tsat/files/t3.pdf
If $k=1$, then it is easy; use the Shemesh criterion (Theorem 3.1).
If $k>1$, then we may assume that $A,B$ are invertible and use Corollary 2.3. Unfortunately, using the previous method can be challenging; in particular, when $k$ increases, the numerical complexity exponentially grows.
A: You might ask whether there is an idempotent matrix $E$ which commutes with both $A$ and $B$. If there is ( with $0 \neq E \neq I$), then you can reduce the question to lower dimension ( the underlying space is the direct sum of the $1$-eigenspace of $E$ and the $0$-eigenspace of $E$, and these are both invariant under $A$ and $B$). If there is no such idempotent matirx $E$, then the matrices which commute with both $A$ and $B$ form a local ring, and, in particular, since you are working with complex matrices, any matrix which commutes with both $A$ and $B$ has just one eigenvalue.
