ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 04 Oct 2022 03:35:54 +0200Finding minimal linearly dependent vectorshttps://ask.sagemath.org/question/64265/finding-minimal-linearly-dependent-vectors/I have a matrix whose rows are linearly dependent. Showing that with sage is straightforward. Is there a reasonably fast algorithm to find a smallest set of rows that form such a linear dependence and would it be simple to implement in sage?Sat, 01 Oct 2022 09:58:32 +0200https://ask.sagemath.org/question/64265/finding-minimal-linearly-dependent-vectors/Comment by kevinfat for <p>I have a matrix whose rows are linearly dependent. Showing that with sage is straightforward. Is there a reasonably fast algorithm to find a smallest set of rows that form such a linear dependence and would it be simple to implement in sage?</p>
https://ask.sagemath.org/question/64265/finding-minimal-linearly-dependent-vectors/?comment=64267#post-id-64267These are vectors of real numbers.Sat, 01 Oct 2022 17:04:05 +0200https://ask.sagemath.org/question/64265/finding-minimal-linearly-dependent-vectors/?comment=64267#post-id-64267Comment by Max Alekseyev for <p>I have a matrix whose rows are linearly dependent. Showing that with sage is straightforward. Is there a reasonably fast algorithm to find a smallest set of rows that form such a linear dependence and would it be simple to implement in sage?</p>
https://ask.sagemath.org/question/64265/finding-minimal-linearly-dependent-vectors/?comment=64266#post-id-64266Over what field is the matrix?Sat, 01 Oct 2022 13:36:20 +0200https://ask.sagemath.org/question/64265/finding-minimal-linearly-dependent-vectors/?comment=64266#post-id-64266Answer by Max Alekseyev for <p>I have a matrix whose rows are linearly dependent. Showing that with sage is straightforward. Is there a reasonably fast algorithm to find a smallest set of rows that form such a linear dependence and would it be simple to implement in sage?</p>
https://ask.sagemath.org/question/64265/finding-minimal-linearly-dependent-vectors/?answer=64269#post-id-64269Let'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](https://www.csc.kth.se/~viggo/wwwcompendium/node207.html). 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]Sat, 01 Oct 2022 18:50:16 +0200https://ask.sagemath.org/question/64265/finding-minimal-linearly-dependent-vectors/?answer=64269#post-id-64269Comment by kevinfat for <p>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 <a href="https://www.csc.kth.se/~viggo/wwwcompendium/node207.html">known to be NP-complete</a>. So our best shot would be using Integer Linear Programming.</p>
<p>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:</p>
<p>$$\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.</p>
<p>Here is a sample code:</p>
<pre><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]])
</code></pre>
<p>and a typical output:</p>
<pre><code>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]
</code></pre>
https://ask.sagemath.org/question/64265/finding-minimal-linearly-dependent-vectors/?comment=64292#post-id-64292Yah I was worried this might fall into the NP-complete issue.Tue, 04 Oct 2022 03:35:54 +0200https://ask.sagemath.org/question/64265/finding-minimal-linearly-dependent-vectors/?comment=64292#post-id-64292