1
$\begingroup$

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]

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – hardmath Jun 1 '18 at 4:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.