0
$\begingroup$

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?

$\endgroup$
15
  • $\begingroup$ Why does the number of tensor components equal $n!$? Perhaps you could elaborate, or provide a reference to the book you're reading. I'm not sure what you mean. $\endgroup$
    – Eric Auld
    Sep 9, 2015 at 1:39
  • $\begingroup$ @EricAuld, 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 n=n!$ $\endgroup$
    – Nikos M.
    Sep 9, 2015 at 1:40
  • $\begingroup$ It does? Why? I know tensors, but perhaps we are talking about different things or this is an area of ignorance for me. "A tensor in $n$ dimensions" seems ambiguous unless you provide some more information. In particular, are you referring to the vector space being $n$ dimensional, or to the $n$-fold tensor product of the vector space? Or both? $\endgroup$
    – Eric Auld
    Sep 9, 2015 at 1:42
  • $\begingroup$ This is not analytic, but algebraic/combinatoric, one can assume each $k$-th vector space (used in the tensor product) to have dimension $k$. But this is not the problem $\endgroup$
    – Nikos M.
    Sep 9, 2015 at 1:44
  • $\begingroup$ @EricAuld, tensor product of $n$ vector spaces, where the $k$-th vector space has dimension $k$ $\endgroup$
    – Nikos M.
    Sep 9, 2015 at 1:46

1 Answer 1

0
$\begingroup$

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)

$\endgroup$
2
  • $\begingroup$ Wait, so what is the bijection? Also what do you mean by "linear" in the last sentence? $\endgroup$
    – anon
    Apr 11, 2022 at 19:44
  • $\begingroup$ @runway44, For example take a 3x2x1 tensor it has 6! components which when expanded as indices (eg, [0,0,0], [2,1,0], ..) correspond to the set of inversions of the prmutations of 6 items. This is the bijection. Linear is meant in the sense of computational complexity that is O(n) $\endgroup$
    – Nikos M.
    Apr 12, 2022 at 8:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .