How to find linearly independent rows from a matrix

Question

How to identify the linearly independent rows from a matrix? For instance,

The 4th rows is independent.

Answer 1

With sympy you can find the linear independant rows using: sympy.Matrix.rref:

>>> import sympy  >>> import numpy as np >>> mat = np.array([[0,1,0,0],[0,0,1,0],[0,1,1,0],[1,0,0,1]])  # your matrix >>> _, inds = sympy.Matrix(mat).T.rref()   # to check the rows you need to transpose! >>> inds [0, 1, 3] 

Which basically tells you the rows 0, 1 and 3 are linear independant while row 2 isn't (it's a linear combination of row 0 and 1).

Then you could remove these rows with slicing:

>>> mat[inds] array([[0, 1, 0, 0],        [0, 0, 1, 0],        [1, 0, 0, 1]]) 

This also works well for rectangular (not only for quadratic) matrices.

Answer 2

First, your 3rd row is linearly dependent with 1t and 2nd row. However, your 1st and 4th column are linearly dependent.

Two methods you could use:

Eigenvalue

If one eigenvalue of the matrix is zero, its corresponding eigenvector is linearly dependent. The documentation eig states the returned eigenvalues are repeated according to their multiplicity and not necessarily ordered. However, assuming the eigenvalues correspond to your row vectors, one method would be:

import numpy as np  matrix = np.array(     [         [0, 1 ,0 ,0],         [0, 0, 1, 0],         [0, 1, 1, 0],         [1, 0, 0, 1]     ])  lambdas, V =  np.linalg.eig(matrix.T) # The linearly dependent row vectors  print matrix[lambdas == 0,:] 

Cauchy-Schwarz inequality

To test linear dependence of vectors and figure out which ones, you could use the Cauchy-Schwarz inequality. Basically, if the inner product of the vectors is equal to the product of the norm of the vectors, the vectors are linearly dependent. Here is an example for the columns:

import numpy as np  matrix = np.array(     [         [0, 1 ,0 ,0],         [0, 0, 1, 0],         [0, 1, 1, 0],         [1, 0, 0, 1]     ])  print np.linalg.det(matrix)  for i in range(matrix.shape[0]):     for j in range(matrix.shape[0]):         if i != j:             inner_product = np.inner(                 matrix[:,i],                 matrix[:,j]             )             norm_i = np.linalg.norm(matrix[:,i])             norm_j = np.linalg.norm(matrix[:,j])              print 'I: ', matrix[:,i]             print 'J: ', matrix[:,j]             print 'Prod: ', inner_product             print 'Norm i: ', norm_i             print 'Norm j: ', norm_j             if np.abs(inner_product - norm_j * norm_i) < 1E-5:                 print 'Dependent'             else:                 print 'Independent' 

To test the rows is a similar approach.

Then you could extend this to test all combinations of vectors, but I imagine this solution scale badly with size.