There are two matrices $A$ and $B$ which can not be diagonalized simultaneously. Is it possible to block diagonalize them? What if the matrices have an special pattern? Physics of the problem is that, I have $2$ layers of atoms where $A$ is connectivity within the layer $1$ itself and $B$ is connectivity between layer $1$ and $2$.
By block diagoanl matrix I mean a matrix which its diagonals are some matrices with size $M \times M$ (where M is much smaller than the actual size of matrix but larger than 1) For example a $3 \times 3$ block diagonal matrix [ \begin{array}{ccc} [a] & [0] & [0] \\ [0] & [b] & [0]\\ [0] & [0] & [c] \end{array} ]
I have attached the figures of sparsity pattern of an example $A$ and $B$.
I will propose a method for finding the optimal simultaneous block-diagonalization of two matrices $A$ and $B$, assuming that $A$ is diagonalizable (and eigenvalues are not too degenerate). (Something similar may work with the Jordan normal form of $A$ as well.) By optimal I mean that none of the corresponding blocks are simultaneously block-diagonalizable. Note that using the trivial block-diagonalization $A=(A)$ and $B=(B)$ this can always be done.
Let me start by verifying Victor Liu's comment that the problem is equivalent to expressing your vector space as a direct sum of invariant spaces. I will write $C\oplus D=\begin{pmatrix}C&0\\0&D\end{pmatrix}$ and similarly for several matrices. I assume that the matrices operate in the vector space $V=\mathbb R^n$ (or $\mathbb C^n$, this is irrelevant). If the two matrices $A$ and $B$ can be block-diagonalized simultaneously, $A=A_1\oplus A_2$ and $B=B_1\oplus B_2$, then $V$ is a direct sum $V=V_1\oplus V_2$, where the spaces $V_i$ are invariant under $A$ and $B$. A subspace $U\subset V$ is said to be invariant under $A$ if $A(U)\subset U$. Similarly, if $V$ is a direct sum of subspaces invariant under both $A$ and $B$, then $A$ and $B$ can be simultaneously block-diagonalized.
Now what are the subspaces of $V$ that are invariant with respect to both $A$ and $B$? Suppose $U\neq\{0\}$ is such a subspace. Suppose furthermore that there is another subspace $U'\subset V$ so that $U$ and $U'$ only intersect at the origin but they span all of $V$: $V=U\oplus U'$. (In other words, $U$ is an invariant subspace complementable by an invariant subspace. The spaces in the decomposition need to be of this type.)
Now $U$ is invariant under $A$. Let us first diagonalize $A$. Let $\lambda_1,\dots,\lambda_m$ be the eigenvalues and $V_1,\dots,V_m$ the corresponding eigenspaces. We can thus write $V$ as a direct sum $V=V_1\oplus\dots\oplus V_m$. Since $U$, it is necessarily of the form $U=U_1\oplus\dots\oplus U_m$, where $U_i$ is a subspace of $V_i$ (can be zero or the whole thing).
Suppose one of the eigenvalues of $A$, $\lambda_1$, is simple (perhaps the ground state if you have a quantum mechanical system). Then $V_1=\langle v_1\rangle$ has to belong to $U$ or its complementing space; suppose it belongs to $U$. We also need to have $Bv_1\in U$. Now $Bv_1=x_1\oplus\dots\oplus x_m\in V_1\oplus\dots\oplus V_m$. By the direct sum form of $U$, we must have $x_i\in U$ for all $i$. Now we have a list of new vectors $x_1,\dots,x_m$ in $U$. For each of them we can run the same argument: $Bx_i=\dots\in V_1\oplus\dots\oplus V_m$ must be in $U$ and so must each of its components (w.r.t. the eigenspace decomposition).
Differently put, if $\pi_I:V\to V_i$ is the orthogonal projection to the eigenspace, the following is true: If $u\in U$, then $\pi_iBu\in U$ for all $i$. It can be enlightening to calculate the matrices $\pi_iBu$. (You could probably see something at glance, but I have not developed intuition for it.)
This is a (at least computationally feasible) method to find an invariant subspace $U$ containing $V_1$. It can well happen that $U=V$ and only the trivial simultaneous block-diagonalization exists. If not, after some amount of iteration you will notice that the above procedure no longer produces more linearly independent vectors and $U$ is a nontrivial invariant subspace.
It does not yet follow that $U$ would be complementable by an invariant subspace. Assuming there is another simple eigenvalue (whose eigenspace is not contained in $U$), you can start the same construction with that one and produce a new invariant subspace $U'$. You will automatically have $U\cap U'=\{0\}$. You can also start at any eigenvector of $B$ corresponding to a simple eigenvalue. If you somehow know that a particular vector needs to be in an invariant subspace, you can use it as well. (But be careful: an eigenvector corresponding to a degenerate eigenvalue need not be in an invariant subspace.) With this method you can generate some amount of invariant subspaces. If these subspaces span the whole space, the corresponding block-diagonalization is optimal. If they do not span all of $V$, at least the rest of the problem is easier. (Note that even if $A$ is symmetric, a complementing invariant subspace need not be orthogonal to $U$.)
This is not a complete answer to your question, but perhaps you can solve your problem with something along these lines. And do ask if you need clarification.
Further details on block diagonalization can be found in this follow-up question.