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.
