Solving a nonlinear matrix equation

Question

I'm trying to find the solution for $X$ of the following nonlinear matrix equation:

$F=PX^{−1}AX+wL$

where $w>0$ is a scalar, $F$, $P$, and $L$ are all a $1\times n$ row vector and $A$ is a $n\times n$ matrix of $a_{ij}$ and $X=diag(x_1,...,x_n)$ is a diagonal matrix. All the matrices and vectors are strictly positive.

$X$ is the unknown while the rest are all taken as given.

Edit: As shown in Robert Israel's Answer below, the system doesn't seem to have a nice symbolic solution in a general case. Then a new question: How can we formally prove this?

Thanks!

Answer 1

Let B = F-wL and consider the following reformulation/generalization of your problem:
Given A, B and P find diagonal X such that PX^-1AX = B
(it is a generalization in the sense that I have not required entry-wise positivity on the variables)

Let Y = X^-1, then we have PYAY^-1 = B or equivalently PYA = BY where Y has no zero entries

PYA is a row vector with each entry linear in the entries of Y, similarly for BY
Thus PYA = yV for some matrix V and BY = yW for some matrix W where y is the row vector of entries of Y So we get the equation yV = yW or equivalently Ky^T = 0 where K = (V-W)^T

So we need to find the matrix K which can easily be found from A, B and P, and then find the null space of K. Once we have the null space we need a vector in the null space without any zero entries. If you also require that X only have positive entries (I'm not sure if you meant X to be included when you say "All the matrices and vectors are strictly positive") then you instead want to find a point in the null space where all entries are positive.

Side note:
I'm a bit unclear on what needs to be positive. Consider the matrix X, it is diagonal and thus contains zero entries however all entries of matrices must be strictly positive, so this can't be. If you could clarify here that would be helpful.

In any case, I do suspect this problem can be reduced to intersecting a subspace (in this case the null space of a specific matrix) with the set of vectors with non zero entries, or in the second case intersecting a subspace with the set of vectors with all positive entries. The second case is a linear program (see here: https://en.wikipedia.org/wiki/Linear_programming). The first case however is more complex.

Answer 2

Letting $B = F - w L$, your equation is $P X^{-1} A X = B$. I don't think there is a nice symbolic solution. Your matrix equation translates to $n$ nonlinear rational equations in the variables $x_1, \ldots, x_n$ which can be solved e.g. by Groebner basis methods. But in general there may be no solutions.

For example, in the $2 \times 2$ case the equations are $$ \eqalign{\frac{p_2 a_{21} x_1 + (p_1 a_{11}-b_1) x_2}{x_2} &= 0\cr \frac{(p_2 a_{22} - b_2) x_1 + p_1 a_{12} x_2}{x_1} &= 0\cr}$$ so taking numerators of the left sides we get a linear homogeneous system (but $x_1$ and $x_2$ are not allowed to be $0$). This system has no solution unless the determinant $p_2 p_1 a_{12} a_{21} - (p_1 a_11 - b_1)(p_2 a_{22} - b_2) = 0$.

EDIT: In the $n \times n$ case you will get a linear homogeneous system in terms of the products of $n-1$ distinct $x_i$: thus in the $3 \times 3$ case the equations are

$$ \eqalign{\frac{p_3 a_{31} x_1 x_2 + p_2 a_{21} x_1 x_3 + (p_1 a_{11} - b_1) x_2 x_3}{x_2 x_3} &= 0\cr \frac{p_3 a_{32} x_1 x_2 + (p_2 a_22 - b_2) x_1 x_3 + p_1 a_{12} x_2 x_3}{x_1 x_3} &= 0\cr \frac{(p_3 a_{33} - b_3) x_1 x_2 + p_2 a_{23} x_1 x_3 + p_1 a_{13} x_2 x_3}{x_1 x_2} &= 0\cr}$$ and the numerators of the left sides are a linear system in $x_1 x_2$, $x_1 x_3$, $x_2 x_3$. In order to have a solution you need the determinant of the coefficient matrix to be $0$: for the $3 \times 3$ case that says

$$a_{{1,1}}a_{{2,2}}a_{{3,3}}p_{{1}}p_{{2}}p_{{3}}-a_{{1,1}}a_{{2,3}}a_{ {3,2}}p_{{1}}p_{{2}}p_{{3}}-a_{{1,2}}a_{{2,1}}a_{{3,3}}p_{{1}}p_{{2}}p _{{3}}+a_{{1,2}}a_{{2,3}}a_{{3,1}}p_{{1}}p_{{2}}p_{{3}}+a_{{1,3}}a_{{2 ,1}}a_{{3,2}}p_{{1}}p_{{2}}p_{{3}}-a_{{1,3}}a_{{2,2}}a_{{3,1}}p_{{1}}p _{{2}}p_{{3}}-a_{{1,1}}a_{{2,2}}b_{{3}}p_{{1}}p_{{2}}-a_{{1,1}}a_{{3,3 }}b_{{2}}p_{{1}}p_{{3}}+a_{{1,2}}a_{{2,1}}b_{{3}}p_{{1}}p_{{2}}+a_{{1, 3}}a_{{3,1}}b_{{2}}p_{{1}}p_{{3}}-a_{{2,2}}a_{{3,3}}b_{{1}}p_{{2}}p_{{ 3}}+a_{{2,3}}a_{{3,2}}b_{{1}}p_{{2}}p_{{3}}+a_{{1,1}}b_{{2}}b_{{3}}p_{ {1}}+a_{{2,2}}b_{{1}}b_{{3}}p_{{2}}+a_{{3,3}}b_{{1}}b_{{2}}p_{{3}}-b_{ {1}}b_{{2}}b_{{3}}=0 $$

Answer 3

According to the Fred's post, the problem reduces to the equation in the unknown $Y$ (a positive diagonal matrix) $(*)$ $pYA=bY$ where the vectors $p,b$ and the matrix $A$ are known and positive.

$(*)$ is equivalent to $(p\otimes A^T-b\otimes I_n)Y=0$ (if we stack row by row the matrix into a vector) cf. https://en.wikipedia.org/wiki/Kronecker_product

In fact, $(*)$ is the following linear homogeneous system of $n$ equations in $n$ unknowns $(y_i)$ that are non-zero

$(U-diag(b))[y_1,\cdots,y_n]^T=0$ where $U=[u_{i,j}]$ is the $n\times n$ matrix defined by $u_{i,j}=p_ja_{j,i}$.

As noted by Robert Israel, there is a necessary condition of existence; it can be written

$\det(U-diag(b))=0$.

In a second step, we search vectors (if they exist) in $\ker(U-diag(b))$ s.t. $y_1=1$ and, for every $i>1,y_i>0$. Standard softwares do easily the job (with explicit $b,p,A$).