Le mercredi 18 avril 2012 à 22:48 +0100, Tom Bachmann a écrit : > [Sherjil, I'm CC-ing you because in my head you are the "linear algebra > expert" :-)] > > One last update for today: I tried to implement code which finds a > "nice" solution. > > Problem statement: let Ax=0 be a homogeneous system with non-trivial > solutions. Find a non-trivial solution with maximal number of zeros in > it. I'd be very happy if someone could come up with and post a good > algorithm to do that. Or any sign that anyone is reading my musings at > all ^^.
So, given a matrix A = (a_ij), you want to find minimal subsets J in {0, ..., n-1} so that \sum_{j \in J} a_ij x_j = 0 has non-trivial solutions. Such a set corresponds to a linearly dependent family of columns of A. We know that any family of size (rank(A) + 1) is dependent, so maybe that's good enough? If so, it should be easy to come up with an algorithm that combines solving the system with finding the dependent family, and it should be faster than finding the general solution of the system. If you really want to find sets of minimal size, then this is the problem of finding circuits of minimal size in a vector matroid[1] and there's apparently no efficient algorithm for that[2]. [1]: https://en.wikipedia.org/wiki/Matroid [2]: http://mathoverflow.net/questions/42419/an-algorithm-to-find-non-trivial-linear-dependencies -- You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to sympy@googlegroups.com. To unsubscribe from this group, send email to sympy+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sympy?hl=en.