# [Numpy-discussion] permutation symbol

David Goldsmith d_l_goldsmith@yahoo....
Tue Jun 30 13:28:34 CDT 2009

Hi!  I can't help but wonder if - out there somewhere - there's an optimized algorithm for implementing the general N-D Permutation Symbol:

"The symbol can be generalized to an arbitrary number of elements, in which case the permutation symbol is (-1)^(i(p)), where i(p) is the number of transpositions of pairs of elements (i.e., permutation inversions) that must be composed to build up the permutation p (Skiena 1990)."

(perhaps in the referenced paper - anyone have "free" access to such reprints online) which we could add to NumPy, including it's specializations to the 3-D and 2-D cases as convenience functions.  (I'd write it given the algorithm, but combinatorics was never my strong suit, i.e., I'm sure someone else on this list could figure out at least a brute force algorithm more efficiently than yours truly.)  Alternatively, isn't this "just" a tensor product with one factor a constant tensor, and thus we could implement it that way using an existing resource?

DG
--- On Tue, 6/30/09, Charles R Harris <charlesr.harris@gmail.com> wrote:

> From: Charles R Harris <charlesr.harris@gmail.com>
> Subject: Re: [Numpy-discussion] permutation symbol
> To: "Discussion of Numerical Python" <numpy-discussion@scipy.org>
> Date: Tuesday, June 30, 2009, 10:10 AM
>
>
> On Tue, Jun 30, 2009 at 10:56 AM,
> Charles R Harris <charlesr.harris@gmail.com>
> wrote:
>
>
>
> On
> Tue, Jun 30, 2009 at 10:40 AM, Nils Wagner <nwagner@iam.uni-stuttgart.de>
> wrote:
>
>
> On Tue, 30 Jun 2009 10:27:05 -0600
>
>   Charles R Harris <charlesr.harris@gmail.com>
> wrote:
>
> > On Tue, Jun 30, 2009 at 5:11 AM, Nils Wagner
>
> > <nwagner@iam.uni-stuttgart.de>wrote:
>
> >
>
> >> On Tue, 30 Jun 2009 11:22:34 +0200
>
> >>  "Nils Wagner" <nwagner@iam.uni-stuttgart.de>
> wrote:
>
> >>
>
> >>>  Hi all,
>
> >>>
>
> >>> How can I build the following product with
> numpy
>
> >>>
>
> >>> q_i = \varepsilon_{ijk} q_{kj}
>
> >>>
>
> >>> where  \varepsilon_{ijk} denotes the
> permutation symbol.
>
> >>>
>
> >>> Nils
>
> >>>
>
> >>  Sorry for replying to myself.
>
> >> The permutation symbol is also known as the
> Levi-Civita
>
> >>symbol.
>
> >> I found an explicit expression at
>
> >> http://en.wikipedia.org/wiki/Levi-Civita_symbol
>
> >>
>
> >> How do I build the product of the Levi-Civita
> symbol
>
> >>\varepsilon_{ijk} and
>
> >> the two dimensional array
>
> >> q_{kj}, i,j,k = 1,2,3 ?
>
> >>
>
> >
>
> > Write it out explicitly. It essentially
> antisymmetrizes
>
> >q and the three off
>
> > diagonal elements can then be treated as a vector.
>
> >Depending on how q is
>
> > formed and the resulting vector is used there may be
>
> >other things you can do
>
> > when you use it in a more general expression. If this
> is
>
> >part of a general
>
> > calculation there might be other ways of expressing
> it.
>
> >
>
> > Chuck
>
>
>
> Hi Chuck,
>
>
>
> Thank you for your response.
>
> The problem at hand is described in a paper by Angeles
>
> namely equation (17c) in
>
> "Automatic computation of the screw parameters of
>
> rigid-body motions.
>
> Part I: Finitely-separated positions"
>
> Journal of Dynamic systems, Measurement and Control, Vol.
>
> 108 (1986) pp. 32-38
>
>
> You can solve this problem using quaternions also, in which
> case it reduces to an eigenvalue problem. You will note that
> such things as PCA are used in the papers that reference the
> cited work so you can't really get around that bit of
> inefficiency.
>
>
>
> Here's a reference to the quaternion approach: http://people.csail.mit.edu/bkph/papers/Absolute_Orientation.pdf.
> You can get the translation part from the motion of the
> centroid.
>
>
> If you are into abstractions you will note that the problem
> reduces to minimising a quadratic form in the quaternion
> components. The rest is just algebra ;)
>
> Chuck
>
>
>
> -----Inline Attachment Follows-----
>
> _______________________________________________
> Numpy-discussion mailing list
> Numpy-discussion@scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>