Revision history [back]
 | 1 | initial version |
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}$$
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]
| | 2 | No.2 Revision |
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}$$\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]
