[Date Index] [Thread Index] [Author Index]

Re: Finding the intersection of some subspaces, given bases.

• To: mathgroup at smc.vnet.net
• Subject: [mg46691] Re: [mg46677] Finding the intersection of some subspaces, given bases.
• From: John Browne <jbrowne at swin.edu.au>
• Date: Sun, 29 Feb 2004 03:16:37 -0500 (EST)
• References: <200402280032.TAA03405@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Scott,

Would Grassmann's "regressive product" be of use here? The regressive 
product of two multivectors A and B (exterior product of vectors) gives 
the multivector whose space is the intersection of the spaces of A and 
B. One advantage might be that the product does not assume a metric, 
hence does not need or use concepts like orthogonality.

A discussion of the regressive product can be found at
http://www.ses.swin.edu.au/homes/browne/grassmannalgebra/book/


On 28/02/2004, at 11:32 AM, Scott Morrison wrote:

> Suppose I have a collection of subspaces described by bases, for
> example
>
> V1 = {{1,1,0},{1,-1,0}};
> V2 = {{1,1,1},{1,1,-1}};
>
> and I'd like to find the intersection of these. I'd like a function
> along the lines of
>
> IntersectSubspaces[V1,V2] = {{1,1,0}}
>
> I also need this function to work with vectors over Q(q), rational
> functions in an indeterminate q.
>
> Here's one method that works:
>
> IntersectSubspaces[bases__] := Module[{n, perp},
>     If[Length[{bases}] == 1, Return[bases]];
>     If[MemberQ[{bases}, {}], Return[{}]];
>     perp = Simplify[Join @@ (NullSpace[#, Method ->
>       OneStepRowReduction] & /@ {bases})];
>     If[perp == {}, n = Length[{bases}[[1, 1]]]; IdentityMatrix[n],
>       Simplify[NullSpace[perp, Method -> OneStepRowReduction]]]
>     ]
>
> The first two conditions check for some simple cases; only one
> subspace, and a 0-dimensional subspace.
>
> The idea then is to find an orthogonal complement for each of the
> subspaces, using NullSpace, joining these together to span a spanning
> set (but not a basis) for the direct sum of the complements, then
> taking NullSpace of this again to obtain the desired intersection.
> (There's also an extra check in there for the case where each of the
> subspaces spans the whole space.)
>
> Now -- why use Simplify and Method -> OneStepRowReduction? Simplify is
> there because the components become quite complicated rational
> functions in q. (An aside -- is it possible to get NullSpace (and
> LinearSolve, etc) to perform simplifications at every step? Would this
> help in doing linear algebra over rational functions?) The Method ->
> OneStepRowReduction is there ... because otherwise all sorts of bad
> things seem to happen, and the code runs extremely slowly once we're
> up in dimension 10 to 20.
>
> Unfortunately, this code is still way too slow... Any ideas for a more
> efficient approach?
>
> Thanks,
> Scott Morrison
> scott at-sign math dot berkeley dot edu
>
>
____________________________
John Browne
School of Engineering and Science
Swinburne University of Technology