10
$\begingroup$

From Wikipedia.

In linear algebra, two n-by-n matrices A and B are called similar if $$ B = P^{-1} A P$$ for some invertible n-by-n matrix $P$.

If $P$ is a permutation matrix, $A$ and $B$ are permutation similar.

Two graphs $G,H$ are isomorphic iff their adjacency matrices $A_G,A_H$ are permutation similar.

If $A_G$ and $A_H$ are not similar then $G$ and $H$ are not isomorphic.

It is possible $A_G$ and $A_H$ to be similar and $G$ and $H$ are not isomorphic.

Experimentally this doesn't happen often.

Recognizing matrix similarity is polynomial, $O(n^3)$.

$A$ and $B$ are similar if and only if they have the same rational canonical form (AKA Frobenius form).

Is there characterization of the graphs for which $A_G \sim A_H \implies G \cong H$?

Consider the following algorithm for graph isomorphism.

Recursively delete vertex from $G$ and from $H$ and check the matrices for similarity. If we don't hit bad case we will find isomorphism in polynomial time.

The exponential case is if we hit bad cases very often.

Is there construction of non-isomorphic graphs for which the above algorithm is exponential?

Added

The sequence of non-similar matrices of graphs of order $n$ starts

1 , 2 , 4 , 11 , 33 , 151 , 988 , 11453 , 247357

This coincides with OEIS A082104 Number of distinct characteristic polynomials among all simple undirected graphs on n nodes

If true, this would imply that symmetric matrices with $0,1$ entries are similar iff their characteristic polynomials are equal (which is likely known).

Improve this question
$\endgroup$
3
  • $\begingroup$ It should be noted that most graph isomorphism testing heuristics are mp MUCH faster than cubic, usually, so this question is not of great practical significance... $\endgroup$
    – Igor Rivin
    Commented Mar 22, 2015 at 15:54
  • $\begingroup$ @IgorRivin the question is not of great quality. AFAICT the best deterministic GI algorithms are super polynomial, maybe something like $\exp\sqrt{n}$. $\endgroup$
    – joro
    Commented Mar 22, 2015 at 16:15
  • $\begingroup$ Yes, I am just saying that the algorithm of checking for similarity first will (in practice) greatly underperform standard heuristic. I certainly agree that the question is of theoretical interest (though is probably very hard). $\endgroup$
    – Igor Rivin
    Commented Mar 22, 2015 at 16:47

2 Answers 2

Reset to default
10
$\begingroup$

There is no characterization known of when a graph is determined by its spectrum. The probability that a tree on $n$ is determined by its characteristic polynomial goes to zero as $n$ tends to infinity. It is conjectured that for graphs the probability goes to one.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks. Is it true that the sequence is really the OEIS sequence? $\endgroup$
    – joro
    Commented Mar 22, 2015 at 14:05
  • $\begingroup$ @joro: which sequence? $\endgroup$
    – Chris Godsil
    Commented Mar 22, 2015 at 14:36
  • $\begingroup$ I mean is it true that two symmetric matrices with 0,1 entries are similar iff their characteristic polynomials are equal? (For the general case wikipedia gives frobenius). $\endgroup$
    – joro
    Commented Mar 22, 2015 at 14:40
  • 1
    $\begingroup$ @joro: It is certainly true that real symmetric matrices are similar if and onlyif their characteristic polynomials are equal. $\endgroup$
    – Chris Godsil
    Commented Mar 22, 2015 at 15:24
3
$\begingroup$

There is an old result by L.Babai and D.Grigoriev saying that graph isomorphism for graphs with bounded dimension of eigenspaces can be decided in polynomial time. So yes, a variation of this approach - matching eigenspaces of $A_H$ and $A_G$ - is well-known.

For the second question, IMHO, the Cai-Furer-Immerman graphs look like an example.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .