# Given two sets of vectors, how do I find a change of basis that will convert one set to another?

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!

-
In Mathematica, look up FindGeometricTransform[]. –  Ｊ. Ｍ. Aug 3 '12 at 9:46
If $m>n$, isn't it likely that there's no such transformation? –  Raskolnikov Aug 3 '12 at 9:58
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? –  Nathan Aug 3 '12 at 10:18
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. –  Colin McQuillan Aug 3 '12 at 14:49
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)$? –  Marc van Leeuwen Aug 18 at 9:43
Let $$\mathbf{u}_i=[u_{i1},\cdots, u_{in}]^T,$$ $$\mathbf{v}_i=[v_{i1},\cdots, v_{in}]^T, i=1,\cdots, m$$ and $$\mathbf{A}=[\mathbf{a}_1,\cdots,\mathbf{a}_n]^T$$ where $\mathbf{a}_j=[a_{j1},\cdots, a_{jn}]$ ($j=1,\cdots, n$), so we have $$\mathbf{u}_i= \mathbf{A}\mathbf{v}_i$$.
To determine $\mathbf{A}$, we can solve the following equation $$\begin{bmatrix} \mathbf{u}_1 \\ \vdots \\ \mathbf{u}_m \end{bmatrix} =\begin{bmatrix} \mathbf{V}_1 \\ \vdots \\ \mathbf{V}_m \end{bmatrix} \begin{bmatrix} \mathbf{a}_1^T \\ \vdots \\ \mathbf{a}_n^T \end{bmatrix}$$ where $$\mathbf{V}_i = \begin{bmatrix} \mathbf{v}_i^T & \mathbf{0} & \cdots & \mathbf{0}\\ \mathbf{0} & \mathbf{v}_i^T & \cdots & \mathbf{0}\\ \vdots & \vdots & \ddots & \vdots \\ \mathbf{0} & \mathbf{0}& \cdots &\mathbf{v}_i^T& \end{bmatrix}_{n \times n^2}$$
Although this does assume that I know that vector $\textbf{v}_i$ is mapped to vector $\textbf{u}_i$. In general, I do not know which $\textbf{v}_j$ is mapped to $\textbf{u}_i$. –  Nathan Aug 6 '12 at 9:28