4 Epsilon needs to be sufficiently small

Over the complex numbers the answer is yes. It was proved by Gerstenhaber that the variety of pairs of commuting matrices is irreducible. This variety has an open subset the set of pairs $(A,B)$ such that $A$ and $B$ are commuting diagonalizable matrices.

Edit: I'm fairly sure M. Gerstenhaber was the first to prove that the irreducibility result. His paper is: On dominance and varieties of commuting matrices, Annals Math. 73 (1961), 324-348. However the result asked for in the question was already known from Theorem 5 in T. S. Motzkin, Olga Taussky, Pairs of matrices with property L II, Trans. Amer. Math. Soc. 80 (1955), 387-401. There is a short account of this work after Remark 3.4 in the paper by Meara and Vinsonhaler mentioned in SJ's answer.

Further edit for real case: It is sufficient to prove that if $A$ and $B$ are commuting real matrices then there exist matrices $E$ and $F$ such that for all sufficiently small non-zero $\epsilon > 0$, \epsilon$, the matrices$A + \epsilon E$and$B + \epsilon F$commute and are diagonalizable. This can be done using some details from the proof by Motzkin and Taussky. Outline: Since$A$and$B$commute they preserve each others primary decompositions. This reduces to the case where$A$and$B$are primary matrices. I'll deal here with the case where neither$A$nor$B$have real eigenvalues. By adding a multiple of the identity matrix to$A$and$B$we can assume that$A$has characteristic polynomial$(x^2 + \theta^2)^m$and$B$has characteristic polynomial$(x^2 + \phi^2)^m$. There is a decomposition $$V = \left< u_1, v_1 \right> \oplus \cdots \oplus \left< u_m, v_m \right>$$ and matrices$S$,$T$,$M$and$N$such that •$S$,$T$,$M$,$N$commute, •$A = S(I+M)$and$B = T(I+N)$, •$S$and$T$preserve each$2$-dimensional summand$\langle u_i,v_i \rangle$, acting as the matrices $$\left( \begin{matrix} \cos \theta & \sin \theta \newline -\sin \theta & \cos \theta \end{matrix} \right) \quad\text{and}\quad \left( \begin{matrix} \cos \phi & \sin \phi \newline -\sin \phi & \cos \phi \end{matrix} \right)$$ respectively. •$M$and$N$are nilpotent and$u_i M \in \langle u_{i+1}, v_{i+1}, \ldots, u_m , v_m \rangle$and similarly for$v_i M$. (The action of$N$could be more complicated.) If$A$is cyclic then there exists$f \in \mathbf{R}[x]$such that$B = f(A)$. If$E$is such that$A + \epsilon E$is diagonalizable for all sufficiently small non-zero$\epsilon > 0$\epsilon$ then we can define the required perturbation $F$ by $B + \epsilon F = f(A+ \epsilon E)$.

If $A$ is not cyclic then there exists $r > 1$ such that the projection $E_r$ with image $\langle u_r, v_r, \ldots, u_m, v_m \rangle$ and kernel $\langle u_1, v_1, \ldots, u_{r-1}, v_{r-1} \rangle$ commutes with $A$. Then $T(I + N + \epsilon E_r)$ commutes with $A$. Moreover, $E_r$ commutes with $T$, and since $N$ and $M$ commute, the eigenvalues of $N + \epsilon E_r$ are either $0$ or $\epsilon$. The characteristic polynomial of $T(I+N + \epsilon E_r)$ splits into a product of powers of the distinct irreducibles $x^2 + \phi^2$ and $x^2 + \phi^2 - \epsilon$. So we get a further decomposition of $\mathbf{R}^{2m}$, still preserved by $A$, and the result follows by induction on the dimension.

3 Added an outline of the real case; added 17 characters in body

Further edit for real case: It is sufficient to prove that if $A$ and $B$ are commuting real matrices then there exist matrices $E$ and $F$ such that for all $\epsilon > 0$, the matrices $A + \epsilon E$ and $B + \epsilon F$ commute and are diagonalizable. This can be done using some details from the proof by Motzkin and Taussky.

Outline: Since $A$ and $B$ commute they preserve each others primary decompositions. This reduces to the case where $A$ and $B$ are primary matrices. I'll deal here with the case where neither $A$ nor $B$ have real eigenvalues. By adding a multiple of the identity matrix to $A$ and $B$ we can assume that $A$ has characteristic polynomial $(x^2 + \theta^2)^m$ and $B$ has characteristic polynomial $(x^2 + \phi^2)^m$. There is a decomposition

$$V = \left< u_1, v_1 \right> \oplus \cdots \oplus \left< u_m, v_m \right>$$

and matrices $S$, $T$, $M$ and $N$ such that

• $S$, $T$, $M$, $N$ commute,
• $A = S(I+M)$ and $B = T(I+N)$,
• $S$ and $T$ preserve each $2$-dimensional summand $\langle u_i,v_i \rangle$, acting as the matrices$$\left( \begin{matrix} \cos \theta & \sin \theta \newline -\sin \theta & \cos \theta \end{matrix} \right) \quad\text{and}\quad\left( \begin{matrix} \cos \phi & \sin \phi \newline -\sin \phi & \cos \phi \end{matrix} \right)$$respectively.
• $M$ and $N$ are nilpotent and $u_i M \in \langle u_{i+1}, v_{i+1}, \ldots, u_m , v_m \rangle$ and similarly for $v_i M$. (The action of $N$ could be more complicated.)

If $A$ is cyclic then there exists $f \in \mathbf{R}[x]$ such that $B = f(A)$. If $E$ is such that $A + \epsilon E$ is diagonalizable for all $\epsilon > 0$ then we can define the required perturbation $F$ by $B + \epsilon F = f(A+ \epsilon E)$.

If $A$ is not cyclic then there exists $r > 1$ such that the projection $E_r$ with image $\langle u_r, v_r, \ldots, u_m, v_m \rangle$ and kernel $\langle u_1, v_1, \ldots, u_{r-1}, v_{r-1} \rangle$ commutes with $A$. Then $T(I + N + \epsilon E_r)$ commutes with $A$. Moreover, $E_r$ commutes with $T$, and since $N$ and $M$ commute, the eigenvalues of $N + \epsilon E_r$ are either $0$ or $\epsilon$. The characteristic polynomial of $T(I+N + \epsilon E_r)$ splits into a product of powers of the distinct irreducibles $x^2 + \phi^2$ and $x^2 + \phi^2 - \epsilon$. So we get a further decomposition of $\mathbf{R}^{2m}$, still preserved by $A$, and the result follows by induction on the dimension.

Over the complex numbers the answer is yes. It was proved by Gerstenhaber that the variety of pairs of commuting matrices is irreducible. This variety has an open subset the set of pairs $(A,B)$ such that $A$ and $B$ are commuting diagonalizable matrices.

Edit: I'm fairly sure M. Gerstenhaber was the first to prove that the irreducibility result. His paper is: On dominance and varieties of commuting matrices, Annals Math. 73 (1961), 324-348. However the result asked for in the question was already known from Theorem 5 in T. S. Motzkin, Olga Taussky, Pairs of matrices with property L II, Trans. Amer. Math. Soc. 80 (1955), 387-401. There is a short account of this work after Remark 3.4 in the paper by Meara and Vinsonhaler mentioned in SJ's answer.

1