# Solving a linear system up to scaling

Problem

Let $$v_i \in \mathbb{R}^n$$ and $$u_i \in \mathbb{R}^m$$, where $$n \ge m$$. We have $$m+1$$ pairs $$(v_i, u_i), i=1,...,m+1$$, where only $$m$$ many $$v_i$$ are lineary independent (i.e., $$\mathrm{dim}\,\mathrm{span}\{v_1, ..., v_{m+1}\} = m$$), and likewise for $$u_i$$. We wish to find a linear mapping $$A$$ which sends $$v_i$$ to $$u_i$$ up to scaling. That is, $$Av_i = \lambda_i u_i, \quad i=1,...,m+1$$ for some $$\lambda_i \in \mathbb{R}^*$$.

An equivalent formulation

Let $$n \ge m$$, and let $$V \in \mathbb{R}^{n\times(m+1)}$$ and $$U \in \mathbb{R}^{m\times(m+1)}$$ be rank $$m$$ matrices. Let $$A \in \mathbb{R}^{m\times n}$$ and let $$D \in \mathbb{R}^{(m+1)\times(m+1)}$$ be a nonsingular diagonal matrix such that $$AV = UD.$$ Given $$U$$ and $$V$$, how can one find $$A$$ (and hence $$D$$) to satisfy the above?

Solutions are not unique. I am interested in a method that yields any solution.

A method for a special case

A simple method presents itself when $$U$$ is in reduced row echelon form, so that $$AV = UD$$ looks like: $$A \underbrace{\begin{bmatrix} \vec{v}_1 \cdots \vec{v}_{m+1} \end{bmatrix} }_V = \underbrace{ \begin{bmatrix} \hat{\mathbf{e}}_1 & \cdots & \hat{\mathbf{e}}_m & \vec{c} \end{bmatrix} }_U D = \underbrace{ \begin{bmatrix} 1 & 0 & \cdots & 0 & c_1 \\ 0 & 1 & & 0 & c_2 \\ \vdots & & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & c_m \\ \end{bmatrix} }_U \underbrace{ \begin{bmatrix} \lambda_1 & & \\ & \ddots & \\ & & \lambda_{m+1} \end{bmatrix} }_D$$

Let $$B := \begin{bmatrix} \vec{v}_1 \cdots \vec{v}_{m} \end{bmatrix}^{-1}_L$$ be the left inverse, so that $$B\begin{bmatrix} \vec{v}_1 \cdots \vec{v}_{m} \end{bmatrix} = I$$.

Now, $$Bv_i = \hat{\mathbf{e}}_i$$ for $$i=1,...,m$$. Define $$d_i$$ by $$Bv_{m+1} =: \begin{bmatrix} d_1 \\ \vdots \\ d_m \end{bmatrix}$$ and now define $$A = \begin{bmatrix} c_1/d_1 & & \\ & \ddots & \\ & & c_m/d_m \end{bmatrix}B .$$

It's easy to verify that $$Av_i = \lambda_i \hat{\mathbf{e}}_i$$ with $$\lambda_i = c_i/d_i$$ for $$i=1,...,m$$ and $$Av_{m+1} = \lambda_{m+1}\vec{c}$$ with $$\lambda_{m+1} = 1$$ as required.

However, I am not sure how to generalise this method to the case where $$U$$ is not in reduced form. Is there a way of transforming $$U$$ into $$\mathrm{rref}(U)$$ without changing the system?

• "I am interested in a method that yields any solution." In that case, you can take $A$ and $D$ to be zero matrices. – Gerry Myerson Apr 23 at 2:48