I am studying the list of inverse images (preimage sets) of some function $f$ at a given inverse depth $j$ -- for each element $x_i$ of a finite domain $X$.
For example,
$P_j=\left[f^{-j}(x_1), f^{-j}(x_2), f^{-j}(x_3),\text{...},f^{-j}( x_n)\right]$
For each of these, we may populate the matrix
$P=\left(\begin{array}{cccc} f^{-1}(x_{1}) & f^{-2}(x_{1}) & \cdots & f^{-n}(x_{1})\\ f^{-1}(x_{2}) & \ddots\\ \vdots\\ f^{-1}(x_{n}) & & & f^{-n}(x_{n}) \end{array}\right)$
However, of particular interest to me is what happens when we look at the sizes of such matrix elements.
Yielding a matrix $\Sigma$ with entries
$\Sigma=\left(\begin{array}{cccc}
\mid f^{-1}(x_{1})\mid & \cdots & \mid f^{-n}(x_{1})\mid \\
&\ddots\\
\vdots\\
\mid f^{-1}(x_{n})\mid & & \mid f^{-n}(x_{n})\mid
\end{array}\right)$
For example, for $f=(a,b),(b,a),(c,a)$ by calculating the second matrix we get $\Sigma_f=\left(\begin{array}{ccc}
2 & 1 & 2\\
1 & 2 & 1\\
0 & 0 & 0
\end{array}\right)$
Now, each preimage size (Sigma) matrix has to it associated a set of functions which have the matrix as their Sigma matrix. This is the partition of functions $X^X$ by the matrix structure.
I Suspect: 1. In each class $[f]={g:\Sigma g=\Sigma f}$ there is only one single-component functional digraph. 2. There are no two functions with the same size cycle
For example, for $f=(a,b),(b,a),(c,a),(d,b)$ and $g=(a,a),(b,b),(c,a),(d,b)$ we have the same sigma matrix
$\Sigma_{f,g}=\left(\begin{array}{ccc}
2 & 2 & 2 & 2\\
2 & 2 & 2 & 2\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0
\end{array}\right)$
However there is only one connected (maximal) functional digraph $f$
If anyone has some references or a suggestion on how to proceed I'd be grateful... I suspect that holding everything else the same, increasing/decreasing the cycle size in a connected functional digraph changes the preimage structure. Thus, to get cycles of length 1 (in the example above) the graph had to be disconnected. Similarly to increase the cycle size to 3 would require a different preimage structure...
Any help appreciated.
Fournier, Bradford M., "Towards a Theory of Recursive Function Complexity: Sigma Matrices and Inverse Complexity Measures" (2015). University of New Orleans Theses and Dissertations. 2072.
