How to prove that the 2 graph matrices describe the same graph?

Question

To simplify the question, we suppose that:

1. All verticles of $G$ are $v_1, v_2,...,v_n$
   
2. There is no edge which connect it with itself.
   
3. $G$ is non-directed.
   
4. There are at most one edge between 2 different verticles
   

Now, we focus on an $n\times n$ matrix $A=a_{ij}$. If $v_i$ and $v_j$ are connected, then $a_{ij}=a_{ji}=1$. If not, $a_{ij}=a_{ji}=0$. It is obvious to konw that for the same graph G, the order of verticles are arbitrary, so if 2 graphs' matrix $A,B$ are given, how to know whether they are the same graph(isomorphic graph)?
Maybe it has some connection with $A=PAP^{-1}$ or something else?
------------------------------------------------------------------
Your comments are really helpful, thanks.
2 year ago, when I first learned graph theory, the problem occured to me, since there are almost $\frac{n!}{2}$ possible situations to check if the 2 matrices are the "same", I guess it might be an NP problem.
And later, we learned something about abstract algebra. Graph isomorphism possibly has some connection with equivalent relationship, and by using it, we can classify the $n\times n$ matrices. So, maybe we can solve it by using algebra methods?

Answer 1

The Graph isomorphism problem is in NP (obviously), but is not known to be NP-complete. The best known result is that it is in the quasi-polynomial time (Babai).