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.


  • $\begingroup$ Unless I misunderstand, your list for the first inverse will often contain several copies of the empty set, and (as j grows larger than 1) will eventually devolve into a (probably rotating) list of partition pieces depending on j. Is there something more that isn't determined by the sequence of iterated f^j? Gerhard "Selfmap Monoid Says A Lot" Paseman, 2019.04.27. $\endgroup$ – Gerhard Paseman Apr 27 '19 at 20:28
  • $\begingroup$ I am not quite sure what you want. However, if you start with bijections and analyze that, you can then grow it to arbitrary injections and show how the general case derived from the case of bijections. In addition to unary algebras (universal algebra with one binary operation, cf Algebras,Lattices, Varieties Vol. I, chapter 3), look-up transformation monoids. Gerhard "Takes A General Algebraic Viewpoint" Paseman, 2019.04.27. $\endgroup$ – Gerhard Paseman Apr 27 '19 at 21:27
  • $\begingroup$ @GerhardPaseman The first inverse list will contain the fewest empty set elements. Suppose n is the domain size. Then if p is the longest sequence f, ff, fff(x) etc such that there are no repeats, then the number of empty set elements reaches its maximum in at most p steps. $\endgroup$ – Bradford Apr 28 '19 at 4:03
  • $\begingroup$ @GerhardPaseman For my own sanity I'll refer to the square n x n matrix of columns of increasing inverse depth as the "preimage matrix" --please forgive the parity with my thesis. $\endgroup$ – Bradford Apr 28 '19 at 5:01
  • 1
    $\begingroup$ This is a nice question. Please incorporate your comments above into the question itself to make it easier to understand what you are looking for. $\endgroup$ – kodlu Apr 28 '19 at 21:43

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.

  • $\begingroup$ Indeed, the matrix can also be derived very quickly from the (forward) "image" matrix with just iterated function elements for entries -- without ever needing to know any element (preimage set) of the preimage matrix. $\endgroup$ – Bradford May 1 '19 at 0:25
  • $\begingroup$ A cute algorithm is to 1.Get the forward n x n image matrix F. 2. Make an empty nxn matrix S, 3. Count the a's in each column of F and populate the first row of S with these, do this for b, populating the second row of S, etc. This is the Sigma matrix we want. $\endgroup$ – Bradford May 1 '19 at 16:18
  • $\begingroup$ Yes. While the perspective seems new to me, it feels to me to represent already studied information. I am sorry I can't give you any references (beyond a half-memory of work of Schweigert and possibly Frobenius). If for example you could readily recover period/tail information (say, Tr of an expression involving your matrix), or develop more ties between your perspective and the literature, someone may recognize literature you haven't found yet based on these ties. Gerhard "Just Keep Going At It" Paseman, 2019.05.01. $\endgroup$ – Gerhard Paseman May 1 '19 at 16:45
  • $\begingroup$ Frobenius, Reischer, Simovici. These are the names I get from Schweigert's 1993 monograph on hyperidentities, in the section on iterated and transformation monoids. Maybe this will help. Gerhard "At Least I Remembered Something" Paseman, 2019.05.01. $\endgroup$ – Gerhard Paseman May 1 '19 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.