  We axiomatize and study the matrices of type $H\in M_N(A)$, having unitary
entries, $H_{ij}\in U(A)$, and whose rows and columns are subject to
orthogonality type conditions. Here $A$ can be any $C^*$-algebra, for instance
$A=\mathbb C$, where we obtain the usual complex Hadamard matrices, or
$A=C(X)$, where we obtain the continuous families of complex Hadamard matrices.
Our formalism allows the construction of a quantum permutation group $G\subset
S_N^+$, whose structure and computation is discussed here.
