# Distinguishing combinatorial maps by their linearizations

Every (not-necessarily invertible) map $f$ from $[n]:=\{1,2,,,,.n\}$ to itself determines a linear map $L_f$ from ${\bf R}^n$ to itself that sends the basis vector $e_k$ to $e_{f(k)}$ for $1 \leq k \leq n$.

If $f$ and $g$ are two self-maps of $[n]$ for which the associated linear maps $L_f$ and $L_g$ are conjugate in the sense that there exists $A$ in $GL(n)$ with $L_f \circ A = A \circ L_g$, must $f$ and $g$ be conjugate in the sense that there exists a permutation $\pi$ in $S(n)$ with $f \circ \pi = \pi \circ g$?

Note that if we restrict to the case where $f$ and $g$ are permutations, the answer is Yes.

In the unrestricted case, I'm fairly sure the answer is No; Jordan canonical form (IIRC) classifies linear maps up to conjugation by $GL(n)$, and the decomposition into Jordan blocks is too combinatorially simple to capture the kind of tree structure self-maps of sets can possess. On the other hand, I don't see how to turn this intuition into a counterexample.

In the event that the answer is No (as I expect), then I ask a follow-up question: Is there some more refined way to linearize $f$ so that the resulting map, considered up to linear-map conjugacy, captures all the combinatorics of $f$?

As Benjamin Steinberg comments, the problem reduces to the following: represent $f$ by the digraph with vertices $[n]$ and edges $i\to f(i)$. Delete all the cycles. What remains is an acyclic digraph $D$ that defines a nilpotent matrix $N$ whose rows and columns are indexed by the vertices of $D$. Namely, $N_{uv}=1$ if there is an edge $u\to v$, and $N_{uv}=0$ otherwise. We need to find the Jordan form of $N$.

Now more generally let $E$ be any finite acyclic digraph and for each edge $u\to v$ let $x_{uv}$ be an indeterminate. Define $N_{uv}=x_{uv}$ if $u\to v$, and $N_{uv}=0$ otherwise. The Jordan form of this "generic nilpotent matrix" was determined by M. Saks and E. R. Gansner (independently). For Gansner's paper see http://www2.research.att.com/~erg/pdf/JADM-Gansner81.pdf. Namely, the sum of the sizes of the largest $j$ Jordan blocks is equal to the largest number of vertices in a union of $j$ paths of $E$. If we replace $x_{uv}$ by 1, then the problem is no longer combinatorial. For instance, let $A$ be any $n\times n$ $(0,1)$-matrix, and place it in the upper-right corner of a $(2n)\times (2n)$ matrix $B$ whose other entries are 0. Then $A$ and $B$ have the same rank so the Jordan form of the nilpotent matrix $B$ depends on the rank of an arbitrary $(0,1)$-matrix $A$, for which there is not a purely combinatorial description. However, going back to $D$, because $N$ has at most one 1 in each row it is easy to see that the Gansner-Saks theorem will continue to hold for the matrix $N$. That is, the sum of the sizes of the largest $j$ Jordan blocks is equal to the largest number of vertices in a union of $j$ paths of $D$.

• I don't think finding the Jordan form of $N$ is enough. Say $f$ sends $1,2,3,4$ to $2,3,1,1$, respectively. Removing the cycles leaves only the $4 \to 1$ arc, which makes the matrix non-semisimple. But the original matrix is semisimple (it has the three third roots of unity, and also $0$, as eigenvalues). – darij grinberg Feb 22 '15 at 16:53
• @Darijgrinberg , I think Richard wants to remove vertices 1,2,3 and so you would have a digraph with 1 vertex and no edges. This gives the 1x1 zero matrix as you want for N. Basically you get a nilpotent partial map by removing the eventual range. The idempotent of the minimal ideal of the cyclic monoid splits in the algebra giving you the direct sum of a permutation matrix and this nilpotent partial map – Benjamin Steinberg Feb 22 '15 at 17:20
• Ah! Is it somehow clear that the Jordan blocks of the resulting nilpotent matrix are Jordan blocks of the original $L_f$ too? – darij grinberg Feb 22 '15 at 17:49
• Yes. The original matrix is similar to the direct sum of the permutation matrix and the matrix of the nilpotent partial map so the Jordan blocks don't change. – Benjamin Steinberg Feb 22 '15 at 18:08
• I don't understand how one can get away with ignoring the cycles completely. What if there are nothing but cycles? That is, what if the original combinatorial map is a permutation? Then we know that spectrum of the associated linear map is $GL(n)$-invariant, and the spectrum determines the cycle-structure. – James Propp Feb 24 '15 at 12:41

Here is a more complete answer to your question including the follow-up question. Define the rank of a mapping $f$ to be the size of its image.

Thm. TFAE.

1. $L_f$ and $L_g$ are conjugate.
2. The images of $f$ and $g$ are conjugate under any linear representation of the monoid of all mappings over any field.
3. The rank of $f^j$ is the same as the rank of $g^j$ for all $1\leq j\leq n$ and the number of cycles of $f$ of size $i$ equals the number of cycles of $g$ of size $i$ for all $1\leq i\leq n$.

The point for the equivalence of 1 and 3 is that the number of Jordan blocks of size $\geq j$ in the nilpotent block of the Fitting decomposition of $L_f$ is the rank of $f^j$ minus the rank of $f^{j+1}$ and the invertible part of the Fitting decomposition is the permutation matrix associated to its action on the elements in its cycles.

This extends to any representation by noting that if $f$ and $g$ are mappings of the same rank then $f=xgy$ and $h=ugv$ for some maps $x,y,u,v$ and so they map to matrices of the same rank under any representation over any field. Then the above argument essentially runs through for any representation.

Of course the rank condition can be expressed in digraph language in the form discussed by Richard Stanley but I found the above formulation useful when trying to answer a similar question for arbitrary finite semigroups.

Original answer. Here is a more egregious example which shows some maps go to linearly conjugate matrices under any representation but are not conjugate under the symmetric group.

Two idempotent mappings will give rise to linearly conjugate matrices under your representation if and only if they have the same rank (same cardinality images). But to be conjugate under $S_n$ the integer partition of n obtained from counting preimages of each element of the image would have to be the same.

Idempotent mappings of the same rank will in fact go to idempotent matrices of the same rank under any representation of the full transformation monoid because they generate the same two sided ideal in the monoid. Since idempotent matrices are conjugate if and only if they have the same rank this gives no to your second question.

So for example the idempotent which maps 1 to 1 and all other elements to 2 is not conjugate under $S_n$ to an idempotent that maps the even numbers to 2 and the odd ones to 1 (for $n>3$) but both are linearly conjugate under any representation.

• I don't quite see how to reconcile this with the criterion of Saks and Gansner described by Stanley (below). Taking $n=4$ and $j=2$, I find that for the idempotent that maps 1 to 1 and maps 2, 3, and 4 to 2, the largest number of vertices in a union of two paths is 3, while for the idempotent that maps 2 and 4 to 2 and maps 1 and 3 to 1, the largest number of vertices in a union of two paths is $4 \neq 3$. What am I missing? – James Propp Feb 23 '15 at 2:30
• @JamesPropp, I think you are misinterpreting Stanley in the same way Darij did. Idempotent matrices have no non-zero nilpotent Jordan blocks. Stanley meant to remove all cycles and the vertices they go through not just the edges. So for an idempotent map the cycles are the elements of the image. When you remove them you just have a bunch of vertices and no edges . So the nilpotent part is just a zero matrix. – Benjamin Steinberg Feb 23 '15 at 3:13
• Said differently Stanley is deleting the recurrent states of the mapping and then applying Saks and Gansner to the acyclic digraph that remains, which in this case just has vertices. – Benjamin Steinberg Feb 23 '15 at 3:24

The matrices $A = \left( \begin{matrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \end{matrix} \right)$ and $B = \left( \begin{matrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \end{matrix} \right)$ are similar (in fact, $A = XBX^{-1}$ for $X = \left( \begin{matrix} 0 & -1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} \right)$), but are of the form $L_f$ for two non-isomorphic $f$'s, right?

I am wondering how the Jordan normal form of $L_f$ can be derived combinatorially from the structure of $f$.

• The matrix of a mapping is similar to the direct sum of a Permutation Matrix coming from its action on its eventual range and a nilpotent matrix. So I guess two maps will be linearly conjugate if they have the same cycle structure on their eventual range and their nilpotent behavior is "the same" where I am not sure immediately how to describe this. – Benjamin Steinberg Feb 22 '15 at 3:06