Sort matrix based on its diagonal entries

4
votes

First of all I would like to point out that my question is different than this one: Sort a numpy matrix based on its diagonal

The question is as follow: Suppose I have a numpy matrix 

A=

5 7 8

7 2 9

8 9 3

I would like to sort the matrix based on its diagonal and then re-arrange the matrix element based on it. Such that now

sorted_A:

2 9 7

9 3 8

7 8 5

Note that:

(1). The diagonal is sorted

(2). The other elements (non-diagonal) re-adjusted by it. How? because diag(A)= [5,2,3] & diag(sorted_A)=[2,3,5] so row/column indices A=[0,1,2] become [1,2,0] in sorted_A.

So far I use brute force where I extract the diagonal elements, get the indices O(N²) and then re-arrange the matrix (another O(N²)). I wonder if there is any efficient/elegant way to do this. I appreciate all the help I can get.

2
pythonsortingpython-3.xnumpymatrix
what code have you tried/come up with? - cctan
Python ofcourse, what I did: (1). get diag members of A = C (2). D = get index of sorted C (using argsort) (3). Loop all elements in the matrix to re-adjust based on D - Krisna Indrawan

2 Answers

2
votes

Sorting the rows based on the diagonal values is easy:

In [192]: A=np.array([[5,7,8],[7,2,9],[8,9,3]])
In [193]: A
Out[193]: 
array([[5, 7, 8],
       [7, 2, 9],
       [8, 9, 3]])
In [194]: np.diag(A)
Out[194]: array([5, 2, 3])
In [195]: idx=np.argsort(np.diag(A))
In [196]: idx
Out[196]: array([1, 2, 0], dtype=int32)
In [197]: A[idx,:]
Out[197]: 
array([[7, 2, 9],
       [8, 9, 3],
       [5, 7, 8]])

Rearranging the elements in each row to the original diagonals are back on the diagonal will take some experimenting - trial and error. We probably have to 'roll' each row based on some value related to the sorting idx. I don't recall if there is a function to roll each row separately or if we have to iterate over the rows to do that.

In [218]: A1=A[idx,:]
In [219]: [np.roll(a,-i) for a,i in zip(A1,[1,1,1])]
Out[219]: [array([2, 9, 7]), array([9, 3, 8]), array([7, 8, 5])]
In [220]: np.array([np.roll(a,-i) for a,i in zip(A1,[1,1,1])])
Out[220]: 
array([[2, 9, 7],
       [9, 3, 8],
       [7, 8, 5]])

So roll with [1,1,1] does the job. But off hand I don't see how that can be derived. I suspect we need to generate several more test cases, possibly larger ones, and look for a pattern.

That roll probably has something to do with how much the row has moved, the difference between the original position and the new one. Let's try:

np.arange(3)-idx

In [222]: np.array([np.roll(a,i) for a,i in zip(A1,np.arange(3)-idx)])
Out[222]: 
array([[2, 9, 7],
       [9, 3, 8],
       [7, 8, 5]])

Applying the sorting idx to both rows and columns seems to do the trick as well:

In [227]: A[idx,:][:,idx]
Out[227]: 
array([[2, 9, 7],
       [9, 3, 8],
       [7, 8, 5]])

In [229]: A[idx[:,None],idx]
Out[229]: 
array([[2, 9, 7],
       [9, 3, 8],
       [7, 8, 5]])
1
votes

Here I simplify a straightforward solution that has been stated before but is hard to get your heads around.

This is useful if you want to sort a table (e.g. confusion matrix by its diagonal magnitude and arrange rows and columns accordingly.

>>> A=np.array([[5,1,4],[7,2,9],[8,0,3]])
>>> A
array([[5, 1, 4],
   [7, 2, 9],
   [8, 0, 3]])
>>> diag = np.diag(A)
>>> diag
array([5, 2, 3])
>>> idx=np.argsort(diag) # get the order of items that are in diagon
>>> A[idx,:][:,idx]  # reorder rows and arrows based on the order of items on diagon
array([[2, 9, 7],
   [0, 3, 8],
   [1, 4, 5]])

if you want to sort in descending order just add idx = idx[::-1] # reverse order