Find vector $\mathbf v$ such that each element of $\mathbf{vA}$ is approximately equal

Question

Given a matrix $\color{red}{\mathbf A} \in \mathbb{Z}_{\ge 0}^{m \times n}$, find the row vector $\color{red}{\mathbf v} \in \mathbb{R}_{>0}^{1 \times m}$ such that the elements of $\color{red}{\mathbf{vA}}$ are equal to one another (or as close as possible).

Usually, $m > n$, but in rare scenarios, $m < n$.

---

Motivation

The vector $\color{red}{\mathbf v}$ is used to give weights to a set of equations which are minimized in a machine learning context. Each equation contains a varying number of predictors, which are represented in the matrix $\color{red}{\mathbf A}$; the columns are the different predictors and the rows are the minimized equations. To ensure that each predictor has approximately the same weight in the minimization routine, the equations are multiplied by the vector $\color{red}{\mathbf v}$.

$\color{red}{\mathbf v} > 0$ since each equation should be included in the minimization.

The solution needs to be programmable given the large size of $\color{red}{\mathbf A}$ (e.g., $m > 100$ and $n > 10$).

---

Example

$$\color{red}{\mathbf A}=\begin{bmatrix}0&4&2\\1&0&1\\2&2&0\\1&1&1 \end{bmatrix}$$

By inspection, $\color{red}{\mathbf v}=\begin{bmatrix}1&4&1&1\end{bmatrix}$ so that $\color{red}{\mathbf{vA}} = \begin{bmatrix}7&7&7\end{bmatrix}$.

Another solution is $\color{red}{\mathbf v}=\begin{bmatrix}0.5&2&1&1\end{bmatrix}$ so that $\color{red}{\mathbf{vA}}= \begin{bmatrix}5&5&5\end{bmatrix}$.

Any solution is acceptable as long as $\color{red}{\mathbf v} > 0$. (The elements of $\color{red}{\mathbf{vA}}$ do not have to be an integer).

---

Solution attempt

I am not super familiar with linear algebra, so the only solution I can think of is to iteratively search for $\color{red}{\mathbf v}$ using optimization.

The mean squared error between every element pair of $\color{red}{\mathbf{vA}}$ is the objective function. In our example:

$$MSE=\frac {(\mathbf{vA}_1 - \mathbf{vA}_2)^2 + (\mathbf{vA}_1 - \mathbf{vA}_3)^2 + (\mathbf{vA}_2 - \mathbf{vA}_3)^2}{3}$$

Find the vector $\color{red}{\mathbf v}$ that minimizes the $MSE$ (and whose elements $> 0$).

However, the solution needs to be as fast as possible, so I hope that an analytical solution exists, or at least a very fast iterative solution.

Answer 1

We want $Av \approx k[1,1,...,1]^T$. This is a typical least squares problem and the solution $v$ which minimizes $||Av - k[1,1,1,\dots,1]^T||_2$ is $v = k(A^TA)^{-1}A^T[1,1,\dots,1]^T$.

Answer 2

Augmented Matrix Solution
$\mathbf{v}A$ will produce something of the form: $$\mathbf{v}A = \begin{bmatrix}\mathbf{v}_{1} \cdot A_{11} + \mathbf{v}_{2} \cdot A_{21} + ... & \mathbf{v}_{1} \cdot A_{12} + \mathbf{v}_{2} \cdot A_{22} + ... & \mathbf{v}_{1} \cdot A_{13} + \mathbf{v}_{2} \cdot A_{23} + ...\end{bmatrix}$$ You can then produce an augmented matrix which follows the transpose of $A$: $$\left[\begin{array}{ccc|c} A_{11} & A_{21} & \dots & x \\ A_{12} & A_{22} & \dots & x \\ \vdots & \vdots & \ddots & \vdots \end{array}\right]$$ The augmented matrix is a convenient way of representing a set of simultaneous equations. Each column represents the coefficient of an element in $\mathbf{v}$. The first column corresponds to $\mathbf{v}_{1}$, the second to $\mathbf{v}_{2}$, etc.

You can then add or subtract rows from each other, provided that you also preserve whatever action you take on the right hand side. Or, you can multiply a whole row by some number, as long as you treat the right hand side the same.

Taking the example matrix $A$: $$A = \left[\begin{array}{ccc} 0 & 4 & 2 \\ 1 & 0 & 1 \\ 2 & 2 & 0 \\ \end{array}\right]$$

First transpose and augment: $$\left[\begin{array}{ccc|c} 0 & 1 & 2 & x \\ 4 & 0 & 2 & x \\ 2 & 1 & 0 & x \\ \end{array}\right]$$

Let the $i^{th}$ row be represented as $R_i$, then subtract $R_1$ from $R_3$: $$\left[\begin{array}{ccc|c} 0 & 1 & 2 & x \\ 4 & 0 & 2 & x \\ 2 & 0 & -2 & 0 \\ \end{array}\right]$$

Add $R_3$ to $R_2$: $$\left[\begin{array}{ccc|c} 0 & 1 & 2 & x \\ 6 & 0 & 0 & x \\ 2 & 0 & -2 & 0 \\ \end{array}\right]$$

Take $\frac{R_2}{3}$ from $R_3$: $$\left[\begin{array}{ccc|c} 0 & 1 & 2 & x \\ 6 & 0 & 0 & x \\ 0 & 0 & -2 & -\frac{x}{3} \\ \end{array}\right]$$

Add $R_3$ to $R_1$: $$\left[\begin{array}{ccc|c} 0 & 1 & 0 & \frac{2x}{3} \\ 6 & 0 & 0 & x \\ 0 & 0 & -2 & -\frac{x}{3} \\ \end{array}\right]$$

Now you have a solution for any $x$: $$\left.\begin{array}{ccc} \mathbf{v}_1 = \frac{x}{6} & \mathbf{v}_2 = \frac{2x}{3} & \mathbf{v}_3 = \frac{x}{6} \end{array}\right.$$

It should be mentioned that a matrix with dimensions $m \times n$ where $n > m$ may have many solutions, since this is effectively asking for more elements in $\mathbf{v}$ than are required. In those cases, you can make $n-m$ of $\mathbf{v}$'s elements equal to zero and reduce the problem to a $m \times m$ square matrix.
This may not produce every solution. For instance it does not produce the $\mathbf{v} = \begin{bmatrix}0.5 & 2 & 1 & 1\end{bmatrix}$ result, as you can see in the above working.

In Coding Applications
If you are programming, you can perform this iteratively without as much regard for using numbers that play well with mental arithmetic. It would follow some process like:

• Use some multiple of the first row to make one of the elements of the second row become zero
• Use some combination of the first and second rows to make two of the elements of the third row become zero
• Continue until you have a row with only one non-zero element
• Use that row to make all of the other elements in the same column become zero
• Now you should have a new row with only one non-zero element
• Continue until you have only one non-zero element in each column

I'm afraid I can't offer a fastest algorithm, but this is at least a starting point.

Answer 3

Taking the transpose of $v A$ produces the vector $y$, where

$ y = A^T v^T $

Let $B = A^T, x = v^T $

We want $y$ to be along $ u = [1, 1, \dots, 1]^T $

That is $ y = k [1, 1, \dots, 1]^T $

Thus, we now have to solve the equation

$ B x - k u = 0 $

Define the augmented matrix

$ C = [B | - u ] $ and $ z = [ x ; k ] $

And find the solution of

$ C z = 0 $

For example, using your matrix, we have

$ C = \begin{bmatrix} 0 && 1 && 2 && 1 && -1 \\ 4 && 0 && 2 && 1 && - 1 \\ 2 && 1 && 0 && 1 && -1 \end{bmatrix} $

The null space (the solution of $C z = 0 $ ) is

$ z = t \begin{bmatrix} -1 \\ -4 \\ -1 \\ 6 \\ 0 \end{bmatrix} + s \begin{bmatrix} 1 \\ 4 \\ 1 \\ 0 \\ 6 \end{bmatrix} $

The solution of $[1, 4, 1, 1]$ is obtained by setting $ s = \dfrac{7}{6}, t = \dfrac{1}{6} $. This is one solution corresponding to $k = 7$

By setting $ s = \dfrac{5}{6}, t = \dfrac{1}{3}$, we obtain the solution $[0.5, 2, 0.5, 2] $ as one of possible solution corresponding to $k = 5 $

Answer 4

If you are solving with computer, you can use for example QR decomposition:

QR Decomposition

A rectangular matrix $\mathbf{A}\in\mathbb{R}^{m\times n}$ with $m\geq n$ can be decomposed into product of orthonormal matrix $\mathbf{Q}$ and upper triangle matrix $\mathbf{R}$:

$$ \mathbf{A} = \begin{bmatrix} \mathbf{Q}_{1} & \mathbf{Q}_{2} \end{bmatrix} \begin{bmatrix} \mathbf{R} \\ \mathbf{0} \end{bmatrix} $$

Solving the Problem

$\mathbf{Q}$ is full rank so any arbitrary row vector $\mathbf{v}$ can be represented as: $\mathbf{v}=\mathbf{u}\mathbf{Q}^{T}$. We can then convert the initial problem as the following:

$$ \begin{aligned} \mathbf{v}\mathbf{A} &= \begin{bmatrix} \mathbf{u}_{1} & \mathbf{u}_{2} \end{bmatrix} \begin{bmatrix} \mathbf{Q}_{1}^{T} \\ \mathbf{Q}_{2}^{T} \end{bmatrix} \begin{bmatrix} \mathbf{Q}_{1} & \mathbf{Q}_{2} \end{bmatrix} \begin{bmatrix} \mathbf{R} \\ \mathbf{0} \end{bmatrix} \\ &= \begin{bmatrix} \mathbf{u}_{1} & \mathbf{u}_{2} \end{bmatrix} \begin{bmatrix} \mathbf{R} \\ \mathbf{0} \end{bmatrix} \\ &= \mathbf{u}_{1}\mathbf{R} \end{aligned} $$

To obtain $\mathbf{u}_{1}$:

$$ \mathbf{u}_{1} = \alpha\cdot \begin{bmatrix} 1,...,1 \end{bmatrix} \mathbf{R}^{-1} $$

Then your vector $\mathbf{v}$ is simply:

$$ \mathbf{v} = \begin{bmatrix} \mathbf{u}_{1} & \mathbf{u}_{2} \end{bmatrix} \begin{bmatrix} \mathbf{Q}_{1}^{T} \\ \mathbf{Q}_{2}^{T} \end{bmatrix} $$

with $\mathbf{v}_{2}$ arbitrary vector