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).<br>
<br>
Example: a(4) = 14, see below.<br>
<br>
Eigenvalues of Functional Graphs<br>
<br>
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).<br>
<br>
To start with the three endofunctions on 2 points, we consider their
functional graphs, their adjacency matrices, and the eigenvalues of
those adjacency matrices.<br>
<br>
Let's call this one A2<br>
<br>
(1,2) -> (1,2)<br>
<br>
<br>
(1 0)<br>
(0 1)<br>
<br>
This is the identity 2x2 matrix I2, whose eigenvalues are (1, 1).<br>
<br>
Next, let's call this one B2<br>
<br>
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:<br>
<br>
(1,2) -> (2,2)<br>
<br>
(0 1)<br>
(0 1)<br>
<br>
Eigenvalues = (0, 1).<br>
<br>
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<br>
<br>
O<==> O<br>
<br>
1             2<br>
<br>
This can be identified with the endofunction:<br>
<br>
(1,2) -> (2,1)<br>
<br>
(0 1)<br>
(1 0)<br>
<br>
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?<br>
<br>
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.<br>
<br>
Eigenvalues = (-1, 1).<br>
<br>
The direct sum C2 + C2 happens to also be the categorical product C2 X C2<br>
<br>
(0 1 0 0)<br>
(1 0 0 0)<br>
(0 0 0 1)<br>
(0 0 1 0)<br>
<br>
Which has eigenvalues (-1, -1, 1, 1) which is just the eigenvalues of C2 with twice the multiplicity.<br>
<br>
Note that we can partition the matrix into diagonal blocks:<br>
<br>
(0 1 | 0 0)<br>
(1 0 | 0 0)<br>
(0 0 | 0 1)<br>
(0 0 | 1 0)<br>
<br>
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:<br>
<br>
P^(-1) A(G) P for some permutation matrix P.<br>
<br>
Different functional graphs can have the same spectrum (eigenvalues of adjacency matrix). <br>
<br>
Let A be the endomorphism (1,2,3,4)->(2,3,2,3)<br>
<br>
Let B be the endomorphism (1,2,3,4)->(3,3,4,3)<br>
<br>
Let C be the endomorphism (1,2,3,4)->(2,3,4,3)<br>
<br>
to pick a specific labeling of each.<br>
<br>
<br>
The adjacency matrices are:<br>
<br>
A =<br>
(0 1 0 0)<br>
(0 0 1 0)<br>
(0 1 0 0)<br>
(0 0 1 0)<br>
<br>
B =<br>
(0 0 1 0)<br>
(0 0 1 0)<br>
(0 0 0 1)<br>
(0 0 1 0)<br>
<br>
and C =<br>
(0 1 0 0)<br>
(0 0 1 0)<br>
(0 0 0 1)<br>
(0 0 1 0)<br>
<br>
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).<br>
<br>
More important, the eigenvalues of A = the eigenvalues of B =<br>
<br>
the eigenvalues of C = (0, 0, -1, 1).<br>
<br>
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.<br>
<br>
Also remember [N. Biggs, Algebraic Graph Theory, 2nd edition, Cambridge Mathematical Library, Cambridge University Press, 1993]:<br>
<br>
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.<br>
<br>
See also "characteristic polynomial of a matrix", Perron-Frobenius Theorem, Wielandt's Theorem.<br>
<br>

Happy new year,<br>
<br>

Jonathan Vos Post<br><br>
<div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><br>
<br><br>
<br><br>

</blockquote></div><br>