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