As for the eigenvalues there is neat trick I learned once: A matrix of the form $\left(\begin{smallmatrix} A & B \\ B & A\end{smallmatrix}\right)$ is conjugate (by $\left(\begin{smallmatrix} I & I \\ I & -I \end{smallmatrix}\right)$) to $\left(\begin{smallmatrix} A+B & \\ & A-B\end{smallmatrix}\right)$. Therefore there is a recursion for the (multi)set of eigenvalues of your matrix.

As for the eigenvalues there is neat trick I learned once: A matrix of the form $\left(\begin{smallmatrix} A & B \\ B & A\end{smallmatrix}\right)$ is conjugate (by $\left(\begin{smallmatrix} I & I \\ I & -I \end{smallmatrix}\right)$) to $\left(\begin{smallmatrix} A+B & \\ & A-B\end{smallmatrix}\right)$. Therefore there is a recursion for the (multi)set of eigenvalues of your matrix.

EDIT: I just realized that the diagonal matrix you're subtracting messes up this special form of the $M_a$ so that what I described leads only to a solution for the special case of a scalar matrix $b_1=...=b_{2^n}$. Maybe you still can use it anyway.