Permutation Matrix on a Vector

How can I compute the permutation matrix without using loop?

Let

V = Original n-vector

Vstar = Permuted n-vector

P = (n x n) Permutation Matrix

such that

P * V = Vstar.

Given V and Vstar, how can I determine P without using loop?

Answer 1

[Matt Fig]

If I understand your question correctly, there is no unique solution. You can understand this by looking at a 2-by-2 system.

P = [a b;c d]
V = [e;f]
Vs = [g;h]

Now from P*V = Vs, we know that:

a*e + b*f = g
c*e + d*f = h

Thus if V and Vs are known, then e, f, g, and h are known. But we still have two equations and four unknowns ( a , b, c, and d ). So unless there are two more ways of limiting the choices for the four unknowns, we are stuck.

For a larger system, the problem only gets worse.

[Jan]

But in addition we have the term "permutation matrix". This means that a,b,c,d are 0 or 1 with only one 1 per row and column.

[Raymond's Group Lee]

Matt

You are right. I should be more careful when I define my permutation matrix. I would like my permutation matrix to have one 1 for every row and every column, with the remaining entries being 0.

Please refer to Wikipedia:

http://en.wikipedia.org/wiki/Permutation_matrix

Thanks.

Raymond

Answer 2

[Jan]

If the values of V are unique:

V = (1:5)';
Vstar = V(randperm(length(V)));
P = bsxfun(@eq, V', Vstar);
isequal(P * V, Vstar)

[Raymond's Group Lee]

Jan,

Thank you for your solution. That is the answer I want.

Raymond

[Matt Fig]

Thanks Jan, I wasn't ready to assume this is what Raymond meant. You were correct.

[Matt Fig]

Jan, is this faster (though less comprehensible) on a newer version? On my 2007a, it is about 40% faster for N = 5000;

[VI,VI] = sort(V); % If V is sorted already, then skip this.

[VsI,VsI] = sort(Vstar);

P2 = zeros(N);

P2(VsI+(VI-1)*N) = 1;

[Jan]

Surprising! Two SORT compared to a simple comparison? BSXFUN seems to be worth to be improved. A further acceleration: P2 = zeros(N, N, 'uint8');