# Understanding representation of permutation matrix as vector

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]

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

This permutation vector can be transformed into a permutation matrix using this simple code. For example, let's say the vector is

$$p=[3 1 2]$$

$$n=3$$

Then you do

for i=1:n
S(i,p(i))=1
end


This will result in the permutation matrix:

$$\left[\begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}\right]$$

If you want to know how many permutations were performed, just notice that when $S(i,i)=1$ (meaning the element on the diagonal is 1), there has been no permutation, so all you need to know is how many times $S(i,i)=0$:

count=0
for i=1:n
if S(i,i)==0
count=count+1
end
end

• I don't think this addresses the Question (posted some nearly three years ago). The approach you take is converting a permutation given in a literal arrangement of entries to a corresponding (row) permutation matrix. But the Question points out that the format used by their software involves vectors with duplicated entries, inconsistent with the interpretation you took. – hardmath Jun 1 '18 at 4:21