7
$\begingroup$

Is there a simple way without having to manually compute the matrices and do LinearSolve to do the following? Assume I'm given two lists $l_1$, $l_2$ of vectors of the same dimension. I want a list of vectors that that represents a basis of the intersection of the spans of $l_1$ and $l_2$. I'm interested in this over the rationals, reals and the complex numbers.

This should be a fairly basic operation, so I don't want to implement it if I don't have to...

Improve this question
$\endgroup$
3
  • $\begingroup$ To give a useful answer, it would help to know what have you tried and what you mean by "manually" computing matrices (i.e., does a sequence of Mathematica commands count as "manual"?). $\endgroup$
    – Jens
    Sep 21, 2014 at 20:05
  • $\begingroup$ If I have to do v[[i]] many times, then I consider that manual and slow. If I can do it with a sequence of built in "big" commands that work on the whole lists and maybe finish of with a RowReduce and pick a list of rows to get the basis, then I consider that efficient. $\endgroup$
    – user19939
    Sep 21, 2014 at 20:12
  • $\begingroup$ In other words, how can I do this in a way that will run fast. I will need this for vector spaces of dimension in the thousands. $\endgroup$
    – user19939
    Sep 21, 2014 at 20:13

2 Answers 2

Reset to default
10
$\begingroup$

Ok, I'll go ahead and answer my own question. After some thinking I came up with this:

getIntersection[l1_, l2_] :=
  Module[{n, ker, coeffs},
    ker = NullSpace[Transpose[Join[l1,l2]]];
    n = Length[l1];
    coeffs = Map[Function[v, v[[1 ;; n]]], ker];
    Return [Map[Function[v, v.l1], coeffs]];
];

Can this be made any faster?

Improve this answer
$\endgroup$
5
  • $\begingroup$ Probably not. Could have something like coeffs=ker[[All,1;;n]]; ker.coeffs for the last two lines. Shorter code but not a speed difference that would be notable. $\endgroup$
    – Daniel Lichtblau
    Sep 21, 2014 at 22:49
  • $\begingroup$ OK. To make it more general, I think one could compute the lengths of l1 and l2 and then use the shorter one for the last two lines. However, in my usage case l1 is always shorter. $\endgroup$
    – user19939
    Sep 21, 2014 at 22:55
  • $\begingroup$ @Daniel: I'm surprised, however, that this very basic operation on vector spaces is not supported directly. Maybe, you should add it, as I see you work for Wolfram. :) $\endgroup$
    – user19939
    Sep 21, 2014 at 22:56
  • 3
    $\begingroup$ That's not exactly the recommended way to thank someone for upvoting your response (not that you necessarily knew I was an upvoter). $\endgroup$
    – Daniel Lichtblau
    Sep 22, 2014 at 16:53
  • $\begingroup$ It's returning some zero vectors among the answer $\endgroup$
    – André Gomes
    Aug 16, 2017 at 0:26
2
$\begingroup$

I post here another way of doing this. Since the algorithm below builds a block matrix I suspect it is slower for large matrices than the previous answer (this was also indicated on my machine, when I tried it on some examples). My coding skills are however very limited, so the reason it is slower might be my fault. 

getIntersectionbasis[l1_, l2_] := Module[{n, c1, c2, c3},
  n = Dimensions[l1][[2]];
  c1 = ArrayFlatten[{{l1, l1}, {l2, 0*l2}}];
  c2 = RowReduce[c1];
  c3 = Select[Take[#, n] == Table[0, {j, 1, n}] &][c2];
  Map[Take[#, -n] &, c3]
]

The algorithm works like this: Build matrices $A$ and $B$ out of the row vectors in $\ell_1$ and $\ell_2$, and put them into a block matrix $$C_1=\begin{pmatrix} A & A\\ B & 0\\ \end{pmatrix}.$$ Next, use row reduction on $C_1$ to obtain $C_2$. When that is done, construct $C_3$ from the rows in $C_2$ containing only zeros in their first $n$ entries (i.e. in the block where $B$ was). Finally, omitting the first $n$ zeros of each row in $C_3$ will leave you with a basis of the intersection of $\ell_1$ and $\ell_2$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.