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>
- DSolve problems with system of ODEs. Out in pure notation?
- References:
- Intersection of 2 subspaces
- From: RENAULT Fabien <renaulf1@cti.ecp.fr>
- Intersection of 2 subspaces