Re: Intersection of 2 subspaces

*To*: mathgroup at smc.vnet.net*Subject*: [mg21703] Re: [mg21681] Intersection of 2 subspaces*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Sat, 22 Jan 2000 02:53:15 -0500 (EST)*References*: <200001210900.EAA06601@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

RENAULT Fabien wrote: > > Here is my problem : > In a vectorial space of dimension n, I have 2 different subspaces defined > by a set of vectors. I need to find the subspace intersection of those 2 > subspaces that is to say find the vectors directors that define the > subspace intersection. > > For example if n=4 > If my first subspace is defined by the vectors (0,0,0,1) and (0,0,1,0) > If my second subspace is defined by the vectors (1,0,0,0) and (0,0,1,1) > > Then the answer would be the subspace intersection defined by the vector > (0,0,1,1). > > If someone could tell me where to find such a function or how to build an > efficient algorithm that could handle much higher values of n (up to > 25-30) that would be a great help for me. > > Thanks Call the subsets V = {v1,...,vr} and W = {w1,...,ws}. Say you have a vector x in the intersection. Then there are scalars {a1,...,ar} and {b1,...,bs} such that x == a1*v1 +...+ ar*vr + b1*w1 +...+bs*ws. So we need a way to describe an independent spanning set of the intersection, using an independnet generating set of all such {b1,...,bs}. It can be done fairly simply. Take a matrix with rows the vectors {v1,...,vr,w1,...,ws}. Augment with new columns on the right by an (r+s)x(r+s) identity matrix. Row-reduce this augmented matrix. Now look at those rows at the bottom for which all entries in the left part (before the augmented part) are zero. For each such, read off the aj's and (negatives of the) bk's from the augmented columns. If there is at least one nonzero aj and bk then we have a nontrivial relation of the sort above. Moreover because we are in row echelon form, we get an independent generating set of such relations in this way. Even better, if we start with linearly independent (say, row-reduced) vectors in each set, then any row of zeroes in the un-augmented columns will have at least one nonzero aj and one nonzero bk. So we just use the bk's to get our subspace generator, no need to first check that we meet the nonzero conditions. I'll illustrate with your example. The pairs of vectors are each linearly independent so no need to pre-reduce them. The set-up: nn = 4; vV = {{0,0,0,1}, {0,0,1,0}}; wW = {{1,0,0,0}, {0,0,1,1}}; mat = Join[vV,wW]; len = Length[mat]; augmat = Transpose[Join[ Transpose[mat],IdentityMatrix[len]]]; redmat = RowReduce[augmat] At this point we obtain Out[58]= {{1, 0, 0, 0, 0, 0, 1, 0}, {0, 0, 1, 0, 0, 1, 0, 0}, {0, 0, 0, 1, 0, -1, 0, 1}, {0, 0, 0, 0, 1, 1, 0, -1}} and it is clear we get our lone intersection generator from the last row of the reduced augmented matrix. To continue: zerorow = Table[0,{nn}]; relations = Select[redmat, (Take[#,nn]==zerorow)&]; multipliers = Map[Take[#,-Length[wW]]&, relations] This give us the set of all multipliers for the wW basis. Out[83]= {{0, -1}} Finally, we construct our generators for the intersection. generators = multipliers . wW Out[87]= {{0, 0, -1, -1}} There are ways to tweak the efficiency but basically the bottleneck is the row reduction(s). In any case, vectors of modest size integer coefficients in 30 dimensional space should pose no problem. The code below runs in a few seconds on my machine, faster if you use approximate numbers. nn = 30; SeedRandom[1111]; vV = Table[Random[Integer,10], {20}, {nn}]; wW = Table[Random[Integer,10], {20}, {nn}]; ... I did not first check that the two bases are independent sets but given the random construction it was a safe enough bet. And as expected the intersection is generated by 20+20-30 == 10 vectors. Daniel Lichtblau Wolfram Research

**Follow-Ups**:**DSolve problems with system of ODEs. Out in pure notation?***From:*"J.Guillermo Sanchez" <guillerm@gugu.usal.es>

**References**:**Intersection of 2 subspaces***From:*RENAULT Fabien <renaulf1@cti.ecp.fr>