Is there a simple way to swap rows in a matrix to form identity matrix on left side

Question

Given a matrix, A, that can be square, but, is most likely rectangular; and given that an identity matrix can be formed on the Rank(A) left most columns, is there a nice way to row swap to achieve this identity matrix?

For example, starting with

import numpy as np
row1 = np.array([1, 0, 0, 2, 3])
row2 = np.array([0, 0, 1, 4, 5])
row3 = np.array([0, 1, 0, 6, 7])
A = np.array([row1, row2, row3])

I would like to have

row1 = np.array([1, 0, 0, 2, 3])
row2 = np.array([0, 1, 0, 6, 7])
row3 = np.array([0, 0, 1, 4, 5])
A = np.array([row1, row2, row3])

I would like for this to be general, more than 1 row may need to be swapped, and there is no limit to the size of the matrix. Nor is there any guarantee the swap will be neighboring rows. Time does not matter i.e., efficiency is not important. Columns will not need to be swapped. The columns making up the Rank(A) identity matrix will on the left side.

A harder "test case" is

row1 = np.array([0, 0, 0, 0, 1, 5, 6, 7])
row2 = np.array([0, 0, 1, 0, 0, 1, 4, 2])
row3 = np.array([0, 0, 0, 1, 0, 6, 8, 4])
row4 = np.array([0, 1, 0, 0, 0, 1, 1, 1])
row5 = np.array([1, 0, 0, 0, 0, 6, 8, 4])
A = np.array([row1, row2, row3, row4, row5])

Does this answer your question? [Swap two rows in a numpy array in python](https://stackoverflow.com/questions/54069863/swap-two-rows-in-a-numpy-array-in-python) — ssp, Dec 22 '20 at 05:30
Is the matrix guaranteed to have full rank, or do we have to deal with cases where, say, the input is a 4x5 matrix with rank 3? — user2357112, Dec 22 '20 at 05:40
I have pruned the matrix so that it has full rank, at this point — George K, Dec 22 '20 at 05:43

ssp · Accepted Answer · 2020-12-22T05:58:15.037

4

Note that the shuffled-identity part of A is a unitary matrix.

And because of properties of permutations of the identity matrix, that means you can simply multiply A by A[:rows, :rows].T (the identity perm part):

rows = 3 # the number of rows

A = A[:rows, :rows].T.dot(A)

Result; A = :

array([[1, 0, 0, 2, 3],
       [0, 1, 0, 6, 7],
       [0, 0, 1, 4, 5]])

Who's rows are switched to form the identity.

edited Dec 22 '20 at 05:58

answered Dec 22 '20 at 05:36

ssp

1,666
11
15

This doesn't work for the following case 'row1 = np.array([0, 0, 0, 0, 1, 5, 6, 7]) row2 = np.array([0, 0, 1, 0, 0, 1, 4, 2]) row3 = np.array([0, 0, 0, 1, 0, 6, 8, 4]) row4 = np.array([0, 1, 0, 0, 0, 1, 1, 1]) row5 = np.array([1, 0, 0, 0, 0, 6, 8, 4]) A = np.array([row1, row2, row3, row4, row5]) rows = 5 A = A[:rows, :rows].dot(A)' – George K Dec 22 '20 at 05:41
1

This has a worse time complexity than a more "direct" shuffle based on copying rows where they need to go, but the questioner *did* say they don't care about efficiency. I'd be a bit worried about rounding error with some matrix multiplication algorithms when the input is floating point, though. – user2357112 Dec 22 '20 at 05:42
I don't know how to make that nicer, but all I did was add 2 rows, and jumble them up a bit – George K Dec 22 '20 at 05:42
1

@GeorgeK try it now I forgot to transpose. – ssp Dec 22 '20 at 05:45
1

Yes, very nice. I should have been able to spot that as well. – George K Dec 22 '20 at 05:54

PeptideWitch · Answer 2 · 2020-12-22T06:27:56.437

I have a solution, but it might be (very) unoptimised. Keeping in mind that this solution is dependent on the number of rows corresponding to the length of the identity matrix:

def find_RankA(arr):
    identity_len = arr.shape[0]
    new_arr = np.empty_like(arr)
    for row in arr:
        replacement_index = row[:identity_len].tolist().index(1)
        new_arr[replacement_index] = row
    return new_arr

if __name__ == '__main__':
    row1 = np.array([0, 0, 0, 0, 1, 5, 6, 7])
    row2 = np.array([0, 0, 1, 0, 0, 1, 4, 2])
    row3 = np.array([0, 0, 0, 1, 0, 6, 8, 4])
    row4 = np.array([0, 1, 0, 0, 0, 1, 1, 1])
    row5 = np.array([1, 0, 0, 0, 0, 6, 8, 4])
    A = np.array([row1, row2, row3, row4, row5])
    print(find_RankA(A))

(Feedback welcome)

We can shorten the function to:

def find_RankA(arr):
    new_arr = np.empty_like(arr)
    for row in arr:
        new_arr[row[:arr.shape[0]].tolist().index(1)] = row
    return new_arr

score 1 · Answer 3 · answered Dec 22 '20 at 13:11

1

Obligatory sorting based method:

A[np.argsort(np.argmax(A[:,:len(A)], 1))]

answered Dec 22 '20 at 13:11

user7138814

1,991
9
11

Is there a simple way to swap rows in a matrix to form identity matrix on left side

3 Answers3