Endofunctions by indegree

[Jonathan Post]

Possible integer sequence: a(n) = number of nonisomorphic functional graphs
on n points which are isopectral (have the same eigenvalues as another
functional graph on n points).

Example: a(4) = 14, see below.

Eigenvalues of Functional Graphs

It has been said: "An nxn matrix cries out for you to find its eignevalues."
The eigenvalue of an endomorphism is an eigenvalue of the adjacency matrix
of its directed graph (functional graph).

To start with the three endofunctions on 2 points, we consider their
functional graphs, their adjacency matrices, and the eigenvalues of those
adjacency matrices.

Let's call this one A2

(1,2) -> (1,2)


(1 0)
(0 1)

This is the identity 2x2 matrix I2, whose eigenvalues are (1, 1).

Next, let's call this one B2

The two vertices are labeled "1" and "2" and there is an arrow from "1" to
"2" with the latter point looping to itself. The above is a drawing of the
endofunction on 2 point:

(1,2) -> (2,2)

(0 1)
(0 1)

Eigenvalues = (0, 1).

This is not isomorphic to the unique functional graph on two vertices which
has a cycle of length 2, and which we’ll call C2

O<==> O

1             2

This can be identified with the endofunction:

(1,2) -> (2,1)

(0 1)
(1 0)

What can we say about the eignevalues of of A + B and of A X B for two
functional graphs A and B whose eigenvalues we know?

In the case of A + B, it is simple, actually a directed sum. This is usually
written with a directed sum symbol which is a "+" sign inside a circle. The
adjacency matrix of a direct sum is the direct sum of the adjacency
matrices.

Eigenvalues = (-1, 1).

The direct sum C2 + C2 happens to also be the categorical product C2 X C2

(0 1 0 0)
(1 0 0 0)
(0 0 0 1)
(0 0 1 0)

Which has eigenvalues (-1, -1, 1, 1) which is just the eigenvalues of C2
with twice the multiplicity.

Note that we can partition the matrix into diagonal blocks:

(0 1 | 0 0)
(1 0 | 0 0)
(0 0 | 0 1)
(0 0 | 1 0)

This is always true, for the right labeling of the vertices. Reordering the
labelings of the vertices is a basis transformation: the adjacency matrix of
reorderings of the labelings of the vertices of A(G) where A(G) is an
adjacency matrix of the graph G:

P^(-1) A(G) P for some permutation matrix P.

Different functional graphs can have the same spectrum (eigenvalues of
adjacency matrix).

Let A be the endomorphism (1,2,3,4)->(2,3,2,3)

Let B be the endomorphism (1,2,3,4)->(3,3,4,3)

Let C be the endomorphism (1,2,3,4)->(2,3,4,3)

to pick a specific labeling of each.


The adjacency matrices are:

A =
(0 1 0 0)
(0 0 1 0)
(0 1 0 0)
(0 0 1 0)

B =
(0 0 1 0)
(0 0 1 0)
(0 0 0 1)
(0 0 1 0)

and C =
(0 1 0 0)
(0 0 1 0)
(0 0 0 1)
(0 0 1 0)

Then we can verify that B is a prime endofunction, while A = a product of 2
prime endofunctions on 2 points. It is the categorical product of
(1,2)->(2,2) with (1,2)->(2,2).

More important, the eigenvalues of A = the eigenvalues of B =

the eigenvalues of C = (0, 0, -1, 1).

Among the 19 endofunctions on 4 points, 4 of them prime, there are 2
cospectral pair, 2 cospectral triplets, and one cospectral quadruplet. So,
rather than the exception, of the 19 there are 14 which are isospectral to
at least one other endofunction.

Also remember [N. Biggs, Algebraic Graph Theory, 2nd edition, Cambridge
Mathematical Library, Cambridge University Press, 1993]:

Let A be the adjacency matrix of a directed graph G. Then Ak(i,j) = the
number of directed walks of length k from vertex i to vertex j.

See also "characteristic polynomial of a matrix", Perron-Frobenius Theorem,
Wielandt's Theorem.

Happy new year,

Jonathan Vos Post


>
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061231/3193ee6c/attachment-0003.htm>