One partial answer, for which you don't need the knowledge that the spectra are complete sets of roots of unity.

First step : verify that the group $G$ generated by $A$ and $B$ is finite (it should be contained a permutation group of $n$ elements). For this, explore the free group in two letters $a$ and $b$ (together with $a^{-1}$ and $b^{-1}$). Consider the disk $D_k$ of words $w$ of length $\le k$, and let $N_k$ be the number of distinct elements $w(A,B)$ for $w\in D_k$. If $N_k$ comes to exceed $n!$, the basis does not exist. If not, you have reached a $k$ so that $N_{k+1}=N_k$ ; the group is finite and you still have a chance, provided this $N=N_k$ is $\le n!$.

Next step : In the latter case, you must verify that the trace of $w(A,B)$ is an integer, for every $w\in D_k$.

I suspect that the converse is true, and that it is a result about linear representations of finite groups. Does anyone have a clue ?

One partial answer, for which you don't need the knowledge that the spectra are complete sets of roots of unity.

First step : verify that the group $G$ generated by $A$ and $B$ is finite (it should be contained a permutation group of $n$ elements). For this, explore the free group in two letters $a$ and $b$ (together with $a^{-1}$ and $b^{-1}$). Consider the disk $D_k$ of words $w$ of length $\le k$, and let $N_k$ be the number of distinct elements $w(A,B)$ for $w\in D_k$. If $N_k$ comes to exceed $n!$, the basis does not exist. If not, you have reached a $k$ so that $N_{k+1}=N_k$ ; the group is finite and you still have a chance, provided this $N=N_k$ is $\le n!$.

Next step : In the latter case, you must verify that the trace of $w(A,B)$ is a non-negative integer, for every $w\in D_k$.

I suspect that the converse is true, and that it is a result about linear representations of finite groups. Does anyone have a clue ?