Timeline for An algorithm to find non-trivial linear dependencies
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Mar 30, 2015 at 21:24 | answer | added | xivaxy | timeline score: 2 | |
| Jun 8, 2011 at 16:07 | comment | added | Andy B | The circuits of a matroid are the minimal dependent sets. What you are calling circuits are the dependent sets of the matroid. This is consistent with the motivation from graph theory, where a circuit is what you think it is. | |
| Feb 10, 2011 at 6:31 | comment | added | Greg Kuperberg | @Gerry It's a point that also confused me for a while in this case. The answer is that a problem can have more than one regime. The lattice problem is already hard when there are no linear dependencies and $v=n$; in fact that's the standard case. But this is a trivial regime for the present problem, even though I suspect that it is NP-hard in other regimes. | |
| Feb 9, 2011 at 23:51 | comment | added | Gerry Myerson | @Greg, of course you're right - but in the last paragraph of the question, the field is the rationals, and there's a rational dependence if and only if there's an integer dependence. I can't reconcile your saying that finding linear dependencies over a field is easy with your guess that it's NP-hard to determine whether there are any linear dependencies. What am I missing? | |
| Feb 9, 2011 at 12:55 | comment | added | Greg Kuperberg | @Gerry Actually both of these algorithms pertain to integer dependencies. If you use them for linear dependencies over a field, then without some new idea, they work very hard just to do something easy. | |
| Feb 8, 2011 at 22:49 | comment | added | Gerry Myerson | The PSLQ algorithm is used to find (probable) linear dependencies - the context is somewhat different, but if you're not familiar with the algorithm, it may be worth your while to have a look at it. Also, the LLL algorithm is used to find shortest vectors in a lattice, but if the input vectors are linearly dependent I suppose it finds the zero vector, so it might also be worth a shot. | |
| Feb 8, 2011 at 22:30 | answer | added | Max Horn | timeline score: 3 | |
| Oct 16, 2010 at 21:26 | history | asked | Greg Kuperberg | CC BY-SA 2.5 |