Find minimal set of rows to retain all unique values in each column
Python3 + PuLP library

This is equivalent to a set covering problem (where the elements are column/value pairs) which can be transformed into an integer linear programming problem.

from pulp import *

def opt(mat):
    num_rows = len(mat)
    covering_rows = {}
    for row_nr, vals in enumerate(mat):
        for pair in enumerate(vals):
            covering_rows.setdefault(pair, []).append(row_nr)
    prob = LpProblem("Minimal Covering Set of Rows", LpMinimize)
    vars = LpVariable.dicts("R", range(num_rows), 0, 1, LpInteger)
    prob += lpSum([vars[i] for i in range(num_rows)])
    for rowlist in covering_rows.values():
        prob += lpSum([vars[r] for r in rowlist]) &gt;= 1
    prob.solve()
    assert prob.status==LpStatusOptimal, "Couldn't solve"
    return [r for r in range(num_rows) if value(vars[r])==1]


On debian, the relevant package is called python3-pulp.

The function handles matrices with 20 columns and 100 rows in about one minute on weak hardware. The best way to substantially improve the speed is probably to use a better solver, which the PuLP library allows by adding an argument to the solve method call.