Closed Form Solution to System of Equations

Question

Let $ \mathbf{b} \in \mathbb{R}_+^n$, $\mathbf{V} \in \mathbb{R}_+^{n \times m}$ with $\mathbf{V} \mathbf{1}_m = \mathbf{1}_n$ where $\mathbf{1}_n$ is the vector of ones of size $n$.

I have the following system of equations where I am trying to find a closed form solution for non-negative $\mathbf{p}$ (i.e., $\mathbf{p} \in \mathbb{R}_+^m$): \begin{align} \mathbf{1}_m = \mathbf{V}^T D^{-1}(\mathbf{V} \mathbf{p}) D(\mathbf{b}) \mathbf{1}_n \end{align}

where $D(\mathbf{x})$ is the diagonal matrix whose $(i, i)^{th}$ entry corresponds to $x_i$ and $D^{-1}(\mathbf{x})$ is the inverse of $D(\mathbf{x})$.

Is there anyway I can find a closed form solution for non-negative $\mathbf{p}$?

Answer 1

$\mathbf{1}_m = \mathbf{V}^T D^{-1}(\mathbf{V} \mathbf{p}) D(\mathbf{b}) \mathbf{1}_n \tag{1}$

$\mathbf{V} \mathbf{1}_m = \mathbf{1}_n \tag{2}$

Multiply $(1)$ by $\mathbf{V}$ on the left:

$\mathbf{V}\mathbf{1}_m = \mathbf{V}\mathbf{V}^T D^{-1}(\mathbf{V} \mathbf{p}) D(\mathbf{b}) \mathbf{1}_n \tag{3}$

From $(2)$

$\mathbf{1}_n = \mathbf{V}\mathbf{V}^T D^{-1}(\mathbf{V} \mathbf{p}) D(\mathbf{b}) \mathbf{1}_n \tag{4}$

$\mathbf{1}_n = M \mathbf{1}_n \tag{5}$

$M$ is not necessarily the identity matrix $I$. e.g. $\begin{bmatrix} \frac1{2} & \frac1{2} & 0\\ \frac1{2} & 0 & \frac1{2}\\ 0 & \frac1{2} & \frac1{2} \end{bmatrix} $

---

$\mathbf{V}\mathbf{V}^T D^{-1}(\mathbf{V} \mathbf{p}) D(\mathbf{b}) = M\tag{6}$

Multiply the left by $ D(\mathbf{V} \mathbf{p}) (\mathbf{V}\mathbf{V}^T)^{-1}$

$ D(\mathbf{V} \mathbf{p}) (\mathbf{V}\mathbf{V}^T)^{-1} M = D(\mathbf{b})\tag{7}$

$ D(\mathbf{V} \mathbf{p}) = D(\mathbf{b}) M ^{-1} \mathbf{V}\mathbf{V}^T \tag{8}$

---

Let $U(x)$ be the inverse operation of $D(x)$ i.e. $U(D(x)) = x$. i.e. It takes the diagonal elements and returns a vector of those elements.

$\mathbf{V} \mathbf{p} = U( D(\mathbf{b}) M ^{-1} \mathbf{V}\mathbf{V}^T ) \tag{9}$

Its now a linear equation.

Using the pseudo inverse of $\mathbf{V}$ on the left

$\mathbf{V}^T \mathbf{V} \mathbf{p} = \mathbf{V}^T U(D(\mathbf{b}) M ^{-1} \mathbf{V}\mathbf{V}^T ) \tag{10}$

$\mathbf{p} = (\mathbf{V}^T \mathbf{V})^{-1} \mathbf{V}^T U(D(b) M ^{-1} \mathbf{V}\mathbf{V}^T ) \tag{11}$

This assumes $\mathbf{V}^T\mathbf{V}$ is invertable and equation $(5)$ : $\mathbf{1}_n = M \mathbf{1}_n$ and $D(b) M ^{-1} \mathbf{V}\mathbf{V}^T$ is diagonal.

There could be more than one solution for $M$.

Given $\mathbf{b} \in \mathbb{R}_+^n$ and $\mathbf{V} \in \mathbb{R}_+^{n \times m}$ were are the negatives coming from. The signs of inverses will very likely have negatives.

octave:

m = rand(5,5)
(m'*m)^-1

m =

   0.586655   0.908566   0.862766   0.921140   0.969437
   0.563071   0.253276   0.866507   0.492751   0.365716
   0.949001   0.420665   0.200587   0.065765   0.695191
   0.702112   0.770204   0.242768   0.140887   0.210560
   0.460073   0.217312   0.536004   0.167217   0.643273

>> (m'*m)^-1
ans =

    8.2750   -6.9269   -6.8769   11.4899   -3.7231
   -6.9269    8.2753    6.4269  -11.2654    1.6545
   -6.8769    6.4269   10.7360  -14.1042    1.2046
   11.4899  -11.2654  -14.1042   23.3144   -4.6586
   -3.7231    1.6545    1.2046   -4.6586    4.5740
 

---

To find positive $\mathbf{p}$ will require finding $M$ to satisfy the conditions and produce positive $\mathbf{p}$ values. This depends on the signs produced by the inverses. This looks like a system of inequalities with $\mathbf{p} \geq 0$.

---

Closed form: a linear system with multiple solutions will have one or more free variables.

Positive solution: linear system solutions don't favour a sign. $(\mathbf{V}^T \mathbf{V})^{-1} \mathbf{V}^T$ is likely to contain many negative values.

Answer 2

For typing convenience, define the following vectors and matrices $$\eqalign{ w &= Vp \\ B &= {\rm Diag}(b),\quad &W = {\rm Diag}(w) \\ A &= W^{-1},\quad &a = {\rm diag}(A) = A{\tt1}_m \\ I_n &= AW,\quad &{\tt1}_n = a\odot w \\ }$$ where $\odot$ is the Hadamard product.

Write the equation using the above variables and solve for $p$. $$\eqalign{ {\tt1}_m &= V^TAB{\tt1}_n \\ &= V^TBA{\tt1}_n &({\rm diagonal\,matrices\,commute}) \\ &= V^TBa \\ a &= (V^TB)^{-1}{\tt1}_m \\ w &= {\tt1}_n \oslash a \quad&({\rm Hadamard\,division}) \\ p &= V^+w + (I_m-V^+V)\,y \quad&({\rm general\,solution}) \\ }$$ where $V^+$ is the pseudoinverse, $\,(I-V^+V)\,$ is the nullspace projector, and $y$ is a free vector which can be adjusted to satisfy the non-negativity constraint (if such a constrained solution exists).