Hi,
thanks for the input. I'm thinking about it.
Tom
On 19.04.2012 06:55, Ronan Lamy wrote:
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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sympy?hl=en.
