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$?



Distinguishing combinatorial maps by their linearizations
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$.


