2
$\begingroup$

Given two sets of dimension $n$ vectors

$\lbrace v_1 , v_2 , \ldots , v_m \rbrace$, $\lbrace u_1, u_2, \ldots , u_m \rbrace$,

where $m > n$, is there a computational method (in particular, using a program such as Mathematica, Maple, etc) to find an $n \times n$ matrix $A$ that gives a bijection between the two sets, so $A v_i = u_j$ for some $i,j$. In particular, the $n \times n$ matrix must have determinant $\pm 1$. The span of each set is the full $n$-dimensional space.

I have two sets of vectors that I think are the same up to a change in basis that preserves volume and permutes the vectors, but I can't think of an algorithmic way to approach the question.

Thanks!

  • 0
    In *Mathematica*, look up `FindGeometricTransform[]`.2012-08-03
  • 3
    If $m>n$, isn't it likely that there's no such transformation?2012-08-03
  • 0
    As an example, I have the set $\lbrace (1,0,0),(0,1,0),(0,0,1),(0,-1,1),(0,-1,0),(0,0,-1),(0,1,-1),(-1,1,0) \rbrace$ and $\lbrace (1,0,0),(1,0,1),(0,0,1),(-1,0,0),(-1,0,-1),(0,0,-1),(0,1,0),(1,-1,0) \rbrace$. I know that there is definitely a 3x3 unimodular matrix that gives a bijection between the sets (after permuting the vectors) but my understanding of FindGeometricTransform is that the vectors have to be given in an ordered list, so that we know which vector is mapped to which - am I wrong about this?2012-08-03
  • 0
    Letting each sets be the indicator functions $e_i+e_j$ of the edges $ij$ of some graph, this seems to be at least as hard as testing whether two graphs are isomorphic.2012-08-03
  • 0
    The question and its context are not at all clear. Could you have just _any_ pair of $m$-tuples of vectors (for instance one that contains the zero vector and the other does not; mentioning "computational method" suggest this interpretation, but it is clearly hopeless) or is there a particular pair you have in mind but of which you kept the details to yourself? Is $\det A=\pm1$ an _additional_ constraint? Do you want $Av_i=u_j$ for more than one couple $(i,j)$?2013-08-18

2 Answers 2