Matrix inversion help If $g(n)$ is an integer functions periodic in $a$
And $\phi(a)$ is eulers totient function
And $[r_1,r_2,r_3,...r_{\phi(a)}]$ are the postive integers less then $a$ coprime to $a$
With $[r_1^{-1},r_2^{-1},r_3^{-1},...r_{\phi(a)}^{-1}]$, being there modular multiplicative inverses  ( ie ,  $r_jr_j^{-1}\equiv 1 \text{ mod a}$ )
Then what is inverse of
$$\begin{pmatrix} g(r_1r_1^{-1}) & g(r_1r_2^{-1}) & g(r_1r_3^{-1}) & .... & g(r_1r_{\phi(a)}^{-1})\\ g(r_2r_1^{-1}) & g(r_2r_2^{-1}) & g(r_2r_3^{-1}) & .... & g(r_2r_{\phi(a)}^{-1}) \\ g(r_3r_1^{-1}) & g(r_3r_2^{-1}) & g(r_3r_3^{-1}) & .... & g(r_3r_{\phi(a)}^{-1}) \\ g(r_4r_1^{-1}) & g(r_4r_2^{-1}) & g(r_4r_3^{-1}) & .... & g(r_4r_{\phi(a)}^{-1})\\ : & :& : & : & :\\ : & :& : & : & :\\ g(r_{\phi(a)}r_1^{-1}) & g(r_{\phi(a)}r_2^{-1}) & g(r_{\phi(a)}r_3^{-1}) & .... & g(r_{\phi(a)}r_{\phi(a)}^{-1})\end{pmatrix}$$
Where if, $M_{\phi(a)\times\phi(a)}$, is the above coefficient matrix, we have $m_{i,j}=g(r_ir_j^{-1})$,
And some additional properties include,
$$\sum_{i=1}^{\phi(a)}m_{i,j}=\sum_{j=1}^{\phi(a)}m_{i,j}=\sum_{k=1}^{\phi(a)}g(r_k)$$
ie, the sum of the entries in any row or column are always the same
In addition, the trace of $M$ is given by $\text{tr}(M)=\phi(a)g(1)$
So given this, how do I find the inverse of matrix $M$?
 A: This is a slight generalization of circulant matrices, and since the representation theory of $\mathbb Z_a^*$ is not much more complicated than the cyclic case, the same Fourier decomposition trick should work.
Let $\chi(n)$ be a character mod $a$, and $\mathbf v_\chi$ be the vector $[\chi(r_i)]_{i=1}^{\phi(a)}$.  Then $(M\mathbf v_\chi)_i = \sum_{j=1}^{\phi(a)} g(r_i r_j^{-1}) \chi(r_j)$, which by a change of variables is $\sum_{j=1}^{\phi(a)} g(r_j) \chi(r_i r_j^{-1}) = \left( \sum_{j=1}^{\phi(a)} g(r_j)\chi(r_j)^{-1} \right) \chi(r_i)$.
Thus $\mathbf v_\chi$ is an eigenvector of $M$ with eigenvalue $\sum_{j=1}^{\phi(a)} g(r_j)\chi(r_j)^{-1}$.  Collecting this over all $\phi(a)$ characters mod $a$ gives an orthogonal set of eigenvectors of $M$, so $M$ is unitarily diagonalizable as $XDX^{-1}$.  From this it is easy to read off the determinant of $M$.  If no eigenvalues vanish, then the inverse $XD^{-1}X^{-1}$ should have the same group-table structure as $M$.  Each entry could be explicitly written as a double sum by expanding out the diagonalization.
