Finding minimal linearly dependent vectors

savecancel

Let's consider the matrix over $\mathbb Q$ (a real matrix can be approximated by a rational one). By scaling it by an integer factor, the matrix can be assumed to be over $\mathbb Z$, where the corresponding problem is known to be NP-complete. So our best shot would be using Integer Linear Programming.

Let's introduce integer coefficients $c_i$ in the linear combination of the rows of a given matrix $M$ giving a zero vector. We want the smallest number but at least one of $c_i$ be nonzero. We will need indicator 01-variables $p_i$ and $n_i$ telling if $c_i$ is positive or negative, and assume that $c_i$ come from some range $(-C,C)$, where $C$ is a large constant of our choice. Then the problem can be formulated as the following MILP:

$$\begin{cases} \sum_i p_i + n_i \longrightarrow \min \\ \sum_i p_i + n_i \geq 1 \\ \forall i:\ p_i + n_i \leq 1 \\ \forall i:\ -(1-p_i) C + 1 \leq c_i \leq Cp_i \\ \forall i:\ -Cn_i \leq c_i \leq (1-n_i)C - 1 \\ \forall j:\ \sum_i c_i M_{i,j} = 0 \end{cases}$$ where $i,j$ range over indices of rows and columns of $M$, respectively.

Here is a sample code:

C = 10000

M = random_matrix(ZZ,10,5)
print(f'Matrix:\n{M}\n')

my_ilp = MixedIntegerLinearProgram(maximization=False)
c = my_ilp.new_variable(integer=True)
p = my_ilp.new_variable(binary=True)
n = my_ilp.new_variable(binary=True)

obj = sum(p[i]+n[i] for i in range(M.nrows()))
my_ilp.set_objective( obj )
my_ilp.add_constraint( obj >= 1 )

for j in range(M.ncols()):
    my_ilp.add_constraint( sum( c[i]*M[i,j] for i in range(M.nrows()) ) == 0 )

for i in range(M.nrows()):
    my_ilp.add_constraint( c[i] <= C*p[i]  )
    my_ilp.add_constraint( c[i] >= -(1-p[i])*C + 1  )
    my_ilp.add_constraint( c[i] >= -C*n[i]  )
    my_ilp.add_constraint( c[i] <= (1-n[i])*C - 1  )
    my_ilp.add_constraint( p[i]+n[i] <= 1 )

my_ilp.solve()
C = my_ilp.get_values(c)
e = vector( C[i] for i in range(M.nrows()) )
assert e * M == 0
print( 'Coefficients of minimal linear combination:', e)
print( 'Indices of linearly dependent rows of M:', [i for i in range(M.nrows()) if e[i]])

and a typical output:

Matrix:
[   5   -9   -1   -3  -10]
[   0   -5   -1    0   -3]
[   0    0   -2   -1   -1]
[   1   -1   -1   -1   -4]
[ -17   11    1    0    3]
[   4    0    0 -206    0]
[   1    4    6   11    3]
[   3    0   -1    2    2]
[   0   -8   -1    3   -2]
[  -4   -5   -1    1    1]

Coefficients of minimal linear combination: (1620.0, -9145.0, 0.0, 2435.0, 0.0, 0.0, -95.0, 0.0, 1910.0, 2610.0)
Indices of linearly dependent rows of M: [0, 1, 3, 6, 8, 9]