Matrix transformation (sorting)

I have a sparse matrix containing either 0 or 1, for example :

A = [0; 1; 0];

I would like to find a transformation to sort this matrix, i.e. find another matrix such that:

T*A = [1 ; 0 ; 0]

All the 1 should come first.

In this example, T should be :

T = [0 1 0; 0 0 0; 0 0 0];

I can not use builtin functions such as "sort" because I need to apply this transformations to other matrices.

i.e. once I have calculated T corresponding to the A matrix, I need to apply the same transformation to other (not particularly sorted) matrices.

How can I write an algorithm for more complicated examples ? Is there a builtin function that does this already ?

Best regards,

Peter

Answer 1

[the cyclist]

i = find(sort(A,'descend'));
j = find(A);
s = numel(A);

T = zeros(s,s);
T(sub2ind([s s],i,j)) = 1;

I hope it's clear what is going on here.

Note that in this case, the pseudoinverse of T is equal to the transpose of T. The transpose is actually the easier way to understand what is happening. If there is a 1 in element (x,y) of T, then there has to be a 1 in element (y,x) of the inverse transformation. (You can think of T and pinv(T) as just "sending" 1's back and forth to the appropriate positions.)

[Peter T]

Thank you !

Answer 2

[the cyclist]

T = sort(A,'descend')/A

Note that I am only using sort here to define the result you need. The transformation matrix you get as a result doesn't rely on any actual sorting algorithm, and can be applied you your other matrices directly.

[Peter T]

Thank you for your answer.

There is something I forgot to say in my previous question, I would like this transformation to be reversible.

If I take a second example:

A = [0 ; 1 ; 0 ; 1];

Here a solution would be:

T = [0 1 0 0; 0 0 0 1; 0 0 0 0; 0 0 0 0];

Indeed I have :

B = T*A = [1 ; 1 ; 0 ; 0];

And I can come back to A from A2 using the inverse (here pseudo-inverse) of T:

pinv(T) * B = [0 ; 1 ; 0 ; 1] % initial A matrix

However, your solution does not allow this reversible action:

T2 = sort(A,'descend')/A;
B3 = T2 * A = [1 ; 1 ; 0 ; 0]

This gives the good solution to sort the matrix, but there is no possibility to inverse this transformation.

pinv(T2) * B2 = [0 ; 1 ; 0 ; 0] % this is not the initial A matrix