Challenge: Calculate the Largest Independent Subset

Program a Python algorithm to find the linearly independent subset of a collection of vectors.

Statement

Write a largestIndependentSubsetCalculator function that takes a collection of vectors S={v1,v2,⋯ ,vn}S = \{v_1, v_2, \cdots, v_n\}, where all vectors belong to the same vector space, and returns the largest linearly independent subset (this subset could be any subset and need not be unique).

Example

Consider an example of a collection of vectors:

{(1,4,7),(2,5,8),(3,6,9)}\{(1, 4, 7),(2, 5, 8),(3, 6, 9)\}

The largest possible independent subset of the collection is {(1,4,7),(2,5,8)}\{(1, 4, 7),(2, 5, 8)\}

Sample inputs and outputs

The following table describes the desired outputs of the corresponding inputs (including a few that are taken from the set of vectors above).

Input Output
S:[[1,4,7],[2,5,8],[3,6,9]]S:[[1, 4, 7],[2, 5, 8],[3, 6, 9]] [[1,4,7],[2,5,8]][[1, 4, 7],[2, 5, 8]]
S:[[7,52,58],[90,76,36],[67,90,13]]S:[[7, 52, 58],[90, 76, 36],[67, 90, 13]] [[7,52,58],[90,76,36],[67,90,13]][[7, 52, 58],[90, 76, 36],[67, 90, 13]]
S:[[5,3,2],[6,7,8],[5,3,2],[1,4,6]]S:[[5, 3, 2],[6, 7, 8],[5, 3, 2],[1, 4, 6]] [[5,3,2],[6,7,8]][[5, 3, 2],[6, 7, 8]]

Try it yourself

The signature of a function is given below. It accepts an array of vectors and returns an array of linearly independent vectors.

Get hands-on with 1200+ tech skills courses.