% PERMUTATION : Helpful notes on permutation matrices and vectors.

%

%

% There are two ways to represent permutations in Matlab.  

% 

% A *permutation matrix* is a square matrix P that is zero except for exactly

% one 1 in each row and each column.  A *permutation vector* is a 1 by n

% or n by 1 vector p that contains each of the integers 1:n exactly once.

% 

% 

% Let A be any n by n matrix, P be an n by n permutation matrix, and p be

% a permutation vector of length n.  Then:

% 

%   P*A is a permutation of the rows of A.

%   A*P' is the same permutation of the columns of A.  Remember the transpose!

% 

%   A(p,:) is a permutation of the rows of A.

%   A(:,p) is the same permutation of the columns of A.

% 

% 

% Matrix P and column vector p represent the same permutation if and only if

% any of the following three equivalent conditions holds:

% 

%   p = P*(1:n)'     or     P = sparse(1:n,p,1,n,n)     or     P = I(p,:),

% 

% where I = speye(n,n) is the identity matrix of the right size.

% 

% 

% The inverse of a permutation matrix is its transpose:

% 

%   Pinv = inv(P) = P'

% 

% The inverse of a permutation vector can be computed by a one-liner:

% 

%   pinv(p) = 1:n;

% 

% (This works only if pinv doesn't already exist, or exists with the correct 

% dimensions.  To be safe, say:  pinv=zeros(1,n); pinv(p)=1:n; )

% 

% 

% Products of permutations go one way for matrices and the other way for

% vectors.  If P1, P2, and P3 are permutation matrices and p1, p2, and p3

% are the corresponding permutation vectors, then

% 

%   P1 = P2 * P3     if and only if     p1 = p3(p2).

% 

% 

% Permutation vectors are a little more compact to store and efficient 

% to apply than sparse permutation matrices (and much better than full

% permutation matrices).  A sparse permutation matrix takes about twice

% the memory of a permutation vector.  The Matlab function LU returns

% a permutation matrix (sparse if the input was sparse); most other 

% built-in Matlab functions return permutation vectors, including 

% SYMRCM, SYMMMD, COLAMD, DMPERM, and ETREE.

% John Gilbert, 6 April 1995

% Copyright (c) 1995 by Xerox Corporation.  All rights reserved.

help permutation