# 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[]. – J. M. 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 '13 at 9:43

It is a consequence of basic theorems of linear algebra that this cannot be done in general.

Assume that the first $n$ vectors $\{v_1,\ldots,v_n\}$ and $\{u_1,\ldots,u_n\}$ each span $X:={\mathbb R}^n$. Then there is a unique linear map $A:\>X\to X$ such that $Av_j=u_j$ for $1\leq j\leq n$. You can neither describe the value of $\det(A)$ nor hope that this $A$ transforms the remaining $v_j$ $\>(n<j\leq m)$ in some desired way.

I assume that the $v_j$ and the $u_j$ are given as column vectors with respect to the standard basis $(e_1,\ldots,e_n)$ of $X$, and you want the matrix of the above $A$ with respect to this same basis. To this end let $V$, resp. $U$, be the $n\times n$-matrix with the first $n$ vectors $v_j$, resp. $u_j$, in its columns. Then we want that $${\rm col}_j(AV)=Av_j=u_j={\rm col}_j(U)\qquad(1\leq j\leq n)\ ,$$ which is tantamount to $AV=U$. It follows that the matrix $A$ we are looking for is given by $$A=U\>V^{-1}\ .$$

-

Basically this is equivalent to solve overdetermined equations:

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}$$

-
Thanks for your help, I will give it a go! – Nathan Aug 6 '12 at 9:01
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