When is a Complex Matrix a Character Table? A Reduction to Vertex Independence

In [3] R. Brauer asked the question: When is an \(n \times n\) complex matrix \(X\) the ordinary character table of some finite group? It is shown that the problem can be reduced in polynomial time to that of VERTEX INDEPENDENCE. We also pose and solve some (much) simpler problems of a related combinatorial nature.