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