What is the name for the type of matrices? Let $ K $ be a field.  We can recursively define  matrices as
$ M_{a} = (a)$ for any $ a\in K $  and
$$ M_{a_1, \cdots, a_{2^i}} = 
\begin{pmatrix}
  M_{a_1, \cdots, a_{2^{i-1}}} & M_{a_{2^{i-1} +1}, \cdots, a_{2^i}}\\
  M_{a_{2^{i-1} +1}, \cdots, a_{2^i}} &   M_{a_1, \cdots, a_{2^{i-1}}}\\
\end{pmatrix}
 $$
when $ i>0 $ and $a_j\in K$.
What is the name for the type of matrices?
Let $ a_1, a_2, \cdots, a_{2^n} $ and
$ b_1, b_2, \cdots, b_{2^n} $ be two list of elements in $ K $.
Is there a formula for the eigenvalues of 
$$  M_{a_1, a_2, \cdots, a_{2^n}} - \operatorname{diag} ( b_1, b_2, \cdots, b_{2^n})? $$
 A: 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.
A: $\let\eps\varepsilon$Making Johannes' answer more exact, one may see that all matrices $M_{a_1\dots a_{2^n}}$ have a common eigenbasis. Namely, for every $\eps_0,\dots,\eps_{n-1}\in\{0,1\}$ one may choose $\mathbf e_i=(e_{i1},\dots,e_{in})$ where $e_{ij}=(-1)^{\eps_0p_{j0}+\dots+\eps_{n-1}p_{j,n-1}}$ and $j-1=\overline{p_{j,n-1}\dots p_{j0}}$ is the binary expansion of $j-1$. The corresponding eigenvalue is $\sum_{j=1}^{2^n}a_j(-1)^{\eps_0p_{j0}+\dots+\eps_{n-1}p_{j,n-1}}$. (The transition matrix is a known Hadamard matrix of order $2^n$.)
