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, the j-th such preimage list on an $n$ element domain would be the list of j-th inverse sets  

$P\_j=\left[f^{-j}(x\_1), f^{-j}(x\_2), f^{-j}(x\_3),\text{...},f^{-j}( x\_n)\right]$
  

  

  
  



This sequence of lists may be put into a preimage matrix P. 


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


  
  



There are some interesting properties of the Sigma matrix: 


* All bijections share the same sigma matrix
* There is a natural ordering on the set of sigma matrices on n elements corresponding to a simple transformation from bijections to constants etc.
* Two seemingly very different functions (i.e where their graphs have different component number etc) may share the same matrix.
* The partitioning of the set of all functions on $X$ into equivlanece classes according to the sigma matrix is very rich.
* The number of equivalence classes for each n generates a very interesting sequence.
* etc


I have found plenty of information on set-partitions, on preimages and fibres, iterated inverses via an IFS. *However, I have yet to find any information on the induced partitioning of a domain by inverse depth etc.* 


Any suggestions as to structures, resources or just alternate terminology 
for conducting a search would be greatly appreciated.


Having only worked on this myself I can not find much related information. 


**EDIT/UPDATE:** *Please see new question re [polynomial representation of columns of sigma matrices](https://mathoverflow.net/q/339901/76735) for a follow up question regarding polynomial representation of columns of the sigma matrix.* 


  
  

  
  




> 
> 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.
> 
> 
> 


<https://scholarworks.uno.edu/td/2072>



Primage structures: induced domain partitioning by itterated inverse (reference request)
This is a slightly different perspective on transformation semigroups.


You have reviewed a lot of the literature. I only recall dimly some related work by Dietmar Schweigert who, in preparation for work on certain kinds of hyperidentities, presented some results (from Frobenius perhaps?) on periods of selfmaps of a finite set. I think much of the preimage matrix you ask is derivable from this work.


The information you ask for is similar to the number of paths of a certain length in a directed tree which may involve self loops. The matrix you ask for can be derived from the adjacency matrix of the directed tree that represents the map on the set. The preimages of the jth inverse iterate correspond to paths of length j ending at the desired point. (Because the set is finite, there is at least one cycle, including a cycle of length one for each fixed point of the map.)


I am not surprised that these matrices have strong properties. I think you will find your matrices will arise as powers of certain binary matrices, or as readily derived from such powers.


Gerhard "The Power Of The Abstraction" Paseman, 2019.04.29.


