Find matrix $R$ such that $(R^TPR-P)x=y$ or that $PRx = y$

Question

Consider an invertible matrix $P\in\mathbb{R}^{n\times n}$ and two vectors $x,y\in\mathbb{R}^n$ ($P,x,y$ are given). Now consider the following two problem.

• Problem 1: Find a matrix $R\in\mathbb{R}^{n\times n}$ (if it exists) such that $(R^TPR-P)x=y$.
• Problem 2: Find a matrix $R\in\mathbb{R}^{n\times n}$ (if it exists) such that $PRx = y$

Lately I've been encountering problems of this type. I've been trying to use some vectorization tricks without any success. I wanted to see how would you solve these equations so I can make a general idea of what would be the general strategy if it exists.

Answer 1

I don't think there are any general strategies. As shown by the answer below, the methods for solving your two problems are quite different.

Problem 1. I suppose $n\ge2$. Rewrite the equation as $R^TPRx=z$ where $z=Px+y$. Clearly it is not solvable when $x=0\ne z$. On the other hand, when $z=0$, an obvious solution is given by $R=0$.

Now suppose $x$ and $z$ are both nonzero. By absorbing some constant into $P$, we may assume that $x$ and $z$ are unit vectors. From $R^TPRx=z$, we obtain $x^TR^T(P+P^T)Rx=2x^Tz$. Hence the equation is solvable only if one of the following conditions is satisfied:

1. $x^Tz=0$ and $P+P^T$ is indefinite or singular,
2. $x^Tz>0$ and $P+P^T$ has a positive eigenvalue,
3. $x^Tz<0$ and $P+P^T$ has a negative eigenvalue.

We will show that these conditions are also sufficient. Since the third case reduces to the second one when we negate both $P$ and $x$, we shall omit it.

1. If $P+P^T$ is indefinite or singular, $u^T(P+P^T)u=0$ for some unit vector $u$. Therefore there exists an orthogonal matrix $U$ such that $\left(U^TPU\right)_{11}=\frac12\left(U^T(P+P^T)U\right)_{11}=0$. Since $P$ is invertible, the first column of $U^TPU$ must contain a nonzero entry. Therefore, by composing $U$ with a permutation matrix, we may further assume that $$ U^TPUe_1=(0,c,\ast,\cdots,\ast)^T \text{ for some } c\ne0. $$ Since $x^Tz=0$, $\{x,z\}$ is an orthonormal set. Thus $Qx=e_1$ and $Qz=e_2$ for some orthogonal matrix $Q$. Now let $D=\operatorname{diag}\left(c^{-1},1,0,\ldots,0\right)$. Then $$ DU^TPUDQx=DU^TPUDe_1=c^{-1}DU^TPUe_1 =c^{-1}D\pmatrix{0\\ c\\ \ast\\ \vdots\\ \ast} =e_2=Qz. $$ Hence $Q^TDU^TPUDQx=z$ and $R=UDQ$ is a solution.
2. When $P+P^T$ has a positive eigenvalue, there exists an orthogonal matrix $U$ such that $\left(U^TPU\right)_{11}=\frac12\left(U^T(P+P^T)U\right)_{11}>0$. That is, $$ U^TPUe_1=(c,\ast,\cdots,\ast)^T \text{ for some } c>0. $$ Let $Q$ be an orthogonal matrix such that $Qz=e_1$. The first entry of $Qx$ is $x^Tz$ because $\langle Qx,e_1\rangle=\langle Qx,Qz\rangle=\langle z,x\rangle$. Let $D=\operatorname{diag}\left(\frac{1}{\sqrt{cx^Tz}},0,\ldots,0\right)$. Then $$ DU^TPUDQx=DU^TPUD\pmatrix{x^Tz\\ \ast\\ \vdots\\ \ast} =\sqrt{\frac{x^Tz}{c}}DU^TPUe_1 =\sqrt{\frac{x^Tz}{c}}D\pmatrix{c\\ \ast\\ \vdots\\ \ast} =e_1 =Qz. $$ Hence $Q^TDU^TPUDQx=z$ and $R=UDQ$ is a solution.

Problem 2. If $x=0$, every matrix $R$ is a solution when $y=0$ and the equation is insolvable otherwise. If $x\ne0$, just pick any matrix $R$ such that $Rx=P^{-1}y$. As noted by the other answer, one particularly simple solution is given by the rank-one matrix $R=P^{-1}y\frac{x^T}{x^Tx}$.

Answer 2

For Problem $1$

This is not a rigorous approach, but shows that $R$ exists under certain conditions, $$(R^TPR-P)x=y$$ Let the eigenvalue decomposition of $P = UDU^{-1}$ and that of $R = VSV^{-1}$. Choose the eigenvectors of $V$ to be that of $P$, i.e. $V= U$ we get $$(USU^{-1} UDU^{-1}USV^{-1}- UDU^{-1})x=y$$ or $$(USDSU^{-1}- UDU^{-1})x=y$$ or $$U(SDS- D)U^{-1}x=y$$ or $$(SDS- D)U^{-1}x=U^{-1}y$$ Since $S$ and $D$ are diagonal then we can exchange them as $$(S^2 D- D)U^{-1}x=U^{-1}y$$ which is $$(S^2 - I)DU^{-1}x=U^{-1}y$$ Let $a = DU^{-1}x$ and $b = U^{-1}y$ so $$(S^2 - I)a=b$$ If the $k^{th}$ diagonal of $S$ is denoted by $s_k$, also if the $k^{th}$ element of vector $a,b$ is denoted by $a_k,b_k$ then the $k^{th}$ row of the above equation is nothing other than $$(s_k^2 - 1)a_k = b_k$$ If $a_k \neq 0 $ and $\frac{b_k}{a_k} > -1$, then $s_k = \pm \sqrt{\frac{b_k}{a_k} + 1}$. So your matrix $R = U S U^{-1}$ where $s_k = \pm \sqrt{\frac{b_k}{a_k} + 1}$ where $a = DU^{-1}x$ and $b = U^{-1}y$ given that all entries of $a$ are non-zero and all $\frac{b_k}{a_k} > -1$.

---

For Problem $2$

If $P$ is invertible, then $Rx = P^{-1}y$, you can now choose $R$ as $R = \frac{1}{x^T x} P^{-1}yx^T$. Verification: $$PRx = P(\frac{1}{x^T x} P^{-1}yx^T)x = \frac{1}{x^T x}PP^{-1}yx^Tx = \frac{x^Tx }{x^T x}y= y$$