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

1

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

0

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{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} \end{equation} where \begin{equation} \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} \end{equation}

  • 0
    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$.2012-08-06