[Math] Understanding representation of permutation matrix as vector

matricespermutation-matricespermutations

I hope this question is relevant here:

I'm using some external software that does an LU decomposition of a square $(n\times n)$ matrix; the result is returned as three matrices L, U and P where P is a row permutation matrix.

P is represented as a one-dimensional vector to save space; however I don't understand the representation nor its explanation in the documentation. I need to know how many permutations (pivots) were performed.

Here are some examples of the permutation "matrix" (vector) when $n=6$:

$(1,5,4,3,4,5)$

$(1,5,4,5,5,5)$

$(1,5,2,3,4,5)$

One thing that puts me off is that integers are repeated. Also note that they go from 1 to 5; one less than $n$. Any ideas about this representation; is there a standard one?

Note: The software is Alglib for c++ and the documentation says this about P:

P = P0*P1*…*PK, K=N-1

Pi – permutation matrix for I and Pivots[I]

Best Answer

I think what you are looking at is a pivot vector in "Nag Form". There are algorithms to transform it into the standard form of a permutation matrix, but the algorithm isn't clear to me.

Here are some references to routines that refer to the format:

Maple - Create Permutation

Calling NAG Routines from Matlab

Related Question