TransWikia.com

Bijection between tensors and permutations (in linear $O(n)$ time)

Mathematics Asked by Nikos M. on November 26, 2021

The number of permutations of the set $S={1, dots, n}$
is $n!$, or in other words the permutation group $S_n$ has $n!$ elements

The number of tensor components of a tensor in $n$ dimensions $(d_1=1,d_2=2,dots,d_n=n)$ is similarly $n!$ or in other words the set of the tensor components has $n!$ elements.

update

A tensor in $n$ dimensions as above has components $T^{i_1 i_2 dots i_n}$, where each index $i_k$ ranges over $1 dots k$ so total number of components is $1 times 2 times dots times n=n!$

In other words, it is the tensor product of $n$ vector spaces, where the $k$-th vector space has dimension $k$.

How about finding a bijection (“isomorphism”) between these two objects?

Between a specific tensor component in $n$ dimensions as above sense and a specific permutation of $n$ elements.

update2

We are talking about finite objects in a combinatorial way. The original purpose is to find better/faster ways to generate (rank/unrank) permutations for $n$ elements from tensors (to both of which i have algorithms but searching for alternative schemes)

For example ranking and unranking tensors (tensor components) is very fast (linear time), but ranking/unranking permutations (in lexicographic order) requires log-linear time (with some latest algorithms). Something better using the bijection between these entities?

One Answer

To answer my own question, the bijection, implied by the equality of sizes, is the set of permutation inversions which is also of size $n!$.

There is a fast linear mapping (ie the identity mapping) between tensor components and permutation inversions.

However the mapping between an inversion and its associated permutation (in lexicographic order) is not linear according to latest algorithms (and not likely to be in the future)

Answered by Nikos M. on November 26, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP