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