30
$\begingroup$

Motivated by the apparent lack of possible classification of integer matrices up to conjugation (see here) and by a question about possible complete graph invariants (see here), let me ask the following:

Question: Is there an example of a pair of non-isomorphic simple finite graphs which have conjugate (over $\mathbb Z$) adjacency matrices?

It is well-known that there are many graphs which have the same spectrum. This implies that their adjacency matrices are conjugate over $\mathbb C$.

In Allen Schwenk, Almost all trees are cospectral. New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971), pp. 275–307. Academic Press, New York, 1973 it was shown that almost all trees have cospectral partners. Maybe $\mathbb Z$-conjugate graphs can be found among trees?

$\endgroup$
7
  • $\begingroup$ The formatting of the question should be fixed... $\endgroup$
    – Igor Rivin
    Jan 15, 2011 at 17:06
  • $\begingroup$ ... what is wrong with it? $\endgroup$ Jan 15, 2011 at 17:11
  • 2
    $\begingroup$ In case you allow multiple (directed) edges and loops then such examples are easily found, for example $\begin{pmatrix} 0 & 3 \\ 0 & 2 \end{pmatrix} = C \begin{pmatrix} 1 & 1 \\\ 1 & 1 \end{pmatrix} C^{-1}$ for $C = \begin{pmatrix} 2 & 1 \\\ 1 & 1 \end{pmatrix}$. But that's probably not what you have in mind. $\endgroup$ Jan 15, 2011 at 17:22
  • 1
    $\begingroup$ Qiaochu, I just wanted to say that for graphs with multiple edges things are much easier; like with $\begin{pmatrix} 2 & 0 \\ 0 & 0 \end{pmatrix}$ and $\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$. $\endgroup$ Jan 15, 2011 at 22:02
  • 1
    $\begingroup$ For any particular pair of non-isomorphic but co-spectral adjacency matrices $A$ and $B$, let $Q$ be an orthogonal matrix such that $QAQ^T = QAQ^{-1} = B$, and let $C_1, \ldots, C_d$ be a basis for the space of matrices that commute with $B$. Then $A$ and $B$ are conjugate over $\mathbb Z$ if and only if the lattice of integer points within the space spanned by $C_1Q, \ldots, C_dQ$ contains a matrix of determinant $\pm 1$. $\endgroup$
    – Tracy Hall
    Jan 16, 2011 at 20:07

4 Answers 4

41
$\begingroup$

Yes.

Consider the adjacency matrices $$ A = \left[\begin{array}{rrrrrrrrrrr} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right] $$ and $$ B = \left[ \begin{array}{rrrrrrrrrrr} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right]. $$ These are both the adjacency matrices of trees, and both have characteristic polynomial $$\lambda^{11}-10\lambda^9+34\lambda^7-47\lambda^5+25\lambda^3-4\lambda.$$ Each tree has exactly two vertices of degree 3, separated by a path of length 1 in the case of $A$ but length 2 in the case of $B$. In particular, the trees are not isomorphic.

Now consider the [EDIT: improved, much nicer] matrix $$ C = \left[\begin{array}{rrrrrrrrrrr} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & -1 \\\\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\\\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\\\ \end{array}\right] $$ with determinant $-1$.

Since $C^{-1}AC = B$, the two trees (on 11 vertices) are non-isomorphic but have adjacency matrices that are conjugate over $\mathbb Z$.

Now to explain the where the example comes from. The pair of graphs was constructed by a method, attributed to Schwenk, that I found in Doob's chapter of Topics in algebraic graph theory (edited by Beineke and Wilson). The first 9 rows and columns of $A$, in common with $B$, come from a particular tree on 9 vertices that has a pair of attachment points such that extending the tree in the same way from either point gives isomorphic spectra. Adding a single pendant vertex cannot work for this problem, as I found using Brouwer and van Eijl's trick, mentioned by Chris Godsil, of comparing the Smith normal forms of (very) small polynomials in $A$ and $B$, in this case $A+2I$ and $B+2I$. When a path of length two is added at either of the two special vertices, however, there doesn't seem to be any obstruction of this type.

I then set about trying to conjugate both $A$ and $B$, separately, to the companion matrix of their mutual characteristic polynomial, by looking for a random small integer vector $x$ for which the matrix $X_A = [ x\ Ax\ A^2x\ \ldots\ A^{10}x]$ has determinant $\pm 1$, and similarly $y$ giving $Y_B$. (The fact that I succeeded fairly easily may have something to do with the fact that $A+I$ is invertible over $\mathbb Z$.) The matrix $X_AY_B^{-1}$ then acts like the $C$ above.

[EDIT: The actual matrix $C$ I found at random and first posted was not nearly so pretty, with a Frobenius norm nearly ten times the current example. But taking powers 0 to 10 of $A$ times $C$ gave a $\mathbb Q$-basis for the full space of conjugators, whose Smith normal form (as 11 vectors in $\mathbb R^{121}$) was all 1's down the diagonal, so in fact it was a $\mathbb Z$-basis. Performing an LLL reduction on this lattice basis then gave a list of smaller-norm matrices, the third of which is the more illuminating $C$ given above, of determinant $-1$. The other determinants from the reduced basis were all $0$ and $\pm 8$.]

Taking rational $x$ and not restricting the determinant of $X_A$ gives a space of possible rational matrices $C$ of dimension 11, which are generically invertible; varying $y$ gives the same space [EDIT: as does multiplying on the left by powers (or in the more general case commutants) of $A$]. Since the spectrum of $A$ has no repeated roots, this is also the dimension of the commutant of $A$, and every matrix conjugating $A$ to $B$ lies in this space. Starting with a rational basis, it is not hard to find an exact basis for the integer sublattice, and taking the determinant of a general point in the integer lattice gives an integer polynomial in 11 variables which takes the value $1$ or $-1$ if and only if the matrices $A$ and $B$ are conjugate over $Z$. If there are repeated roots, you have to work a little harder; in general the full space has dimension the sum of the squares of the multiplicities, and is generated by multiplying on the left by a basis for the commutator space of $A$. A basis for the commutant can be produced (for a diagonalizable matrix) by first conjugating $A$ to a direct sum of companion matrices for the irreducible factors of the characteristic polynomial, and then one at a time, for each $k$-by-$k$ block corresponding to a $k$-times repeated factor of degree $m$, replacing each of the $k^2$ blocks with powers $0$ to $m-1$ of the companion matrix for that factor, with $0$ everywhere elsewhere.

$\endgroup$
2
  • $\begingroup$ Very impressing! $\endgroup$ Jan 19, 2011 at 6:38
  • $\begingroup$ This is lovely. I'm impressed too. $\endgroup$ Jan 19, 2011 at 17:13
9
$\begingroup$

This is an overlong comment to Aaron's reply. The Shrikande and grid graphs do not work. There is a paper by Brouwer and van Eijl in J. Alg. Combin. 1 which studies $p$-rank of adjacency matrices. If the adjacency matrices of the graphs mentioned are $A$ and $B$, then B&E note that the Smith normal forms of $A+2I$ and $B+2I$ are different. Hence there is no unimodular $L$ in $GL(n,\mathbb{Z})$ such that $L^{-1}AL=B$. The results in the B&E paper can be used to produce many pairs of srg's that are cospectral but not integrally equivalent.

I think trees might be the best bet. Using sage I've found cospectral trees on 12 vertices such that $A+mI$ and $B+mI$ have the same Smith normal form for many values of $m$, but I cannot see how to decide if they are integrally equivalent :-(

(There are pairs of cospectral trees on fewer than 12 vertices, and some of these pairs may serve just as well. I just wanted examples with determinant 1.)

$\endgroup$
1
  • $\begingroup$ It's an interesting question whether some form of B&E always captures the pairs that won't work. It appears that at least more general polynomials are necessary: for the 4-cube and its spectral partner, the SNF of $A+mI$ and $B+mI$ are the same for at least all $|m| \le 2^{18}$, but they differ for $A^2$ and $B^2$. I wonder what clues, if any, the characteristic polynomial gives about what integer polynomials of $A$ and $B$ to test. $\endgroup$
    – Tracy Hall
    Jan 29, 2011 at 21:12
1
$\begingroup$

Not an answer, but something here might help. Zivkovic classifies small order (0,1) matrices by Smith Normal Form. and other measures. You might count classes to see where to look for two distinct graphs with the same SNF. http://arxiv.org/abs/math/0511636 is the paper by Miodrag Zivkovic. (Disclosure: he kindly refers to work of mine, but introduces a typo in the retelling of the argument; still, I am rather partial to this paper.)

Gerhard "Ask Me About System Design" Paseman, 2011.01.15

$\endgroup$
1
  • $\begingroup$ Maybe I'm missing something. There are 8 SNF classes of 4x4 0-1 matrices and 11 graphs on 4 unlabeled points. Perhaps Z-equivalent is stronger (more discriminating) than Smith Normal Form? Anyway, there should be a small example that may be easily found with a computer search. Gerhard "Head Cold Slowing Me Down" Paseman, 2011.01.17 $\endgroup$ Jan 17, 2011 at 22:41
1
$\begingroup$

Purely a guess but I would check the Shrikhande Graph and the 4x4 grid (both regular of degree 6 with 16 points and 48 edges). I'm not sure how one would check. They are distance regular graphs with the same parameters but the first is not distance transitive while the second is.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.