Solving matrix equation involving sum of trace

Question

Define a symmetic matrix $\Theta_j\in \mathbb R^{n\times n}, \forall j \in \{1,2,\cdots,M\}$, symmetic matrices $A,S\in \mathbb R^{n\times n}$, scalar $\rho\in \mathbb R_+$, and scalar $c_{i,j} \in \mathbb R, \forall i \in \{1,2,\cdots,N\}, \forall j \in \{1,2,\cdots,M\}$. We have

$$ A + {\rho} \sum\limits_{i=1}^N \sum\limits_{j=1}^{M} \left({\Theta_j}\left(\operatorname{Tr}\left({\Theta_j} X \right) + {c_{i,j}} \right) \right) + 2\left(X^\top - S\right) = 0. $$

Note that the matrices $\Theta_j$ are not positive definite. I wonder how to calculate $X\in \mathbb R^{n\times n}$.

Answer 1

Let's rearrange terms and separate knowns from unknowns: $$ 2 X^\top + \rho \sum_{i=1}^N \sum_{j=1}^M \Theta_j \operatorname{Tr}(\Theta_j X) = 2 S - A - \rho \sum_{j=1}^M \Theta_j \sum_{i=1}^N c_{i,j} $$ It is clear now that summation by $i$ is not necessary. Let $d_j = \sum_{i=1}^N c_{i,j}$. $$ 2X^\top + \rho N \sum_{j=1}^M \Theta_j \operatorname{Tr}(\Theta_j X) = 2S - A - \rho \sum_{j=1}^M d_j \Theta_j $$ The right hand side is known, so let's denote is as $R \equiv 2S - A - \rho \sum_{j=1}^M d_j \Theta_j$.

Let's simplify further by replacing $\operatorname{Tr}(\Theta_j X)$ by $\operatorname{Tr}(X^\top\Theta_j^\top)$. Since $\Theta_j$ are symmetric, $\operatorname{Tr}(X^\top\Theta_j^\top) = \operatorname{Tr}(X^\top\Theta_j)$. After that only $X^\top$ remains in the equation $$ 2X^\top + \rho N \sum_{j=1}^M \Theta_j \operatorname{Tr}(X^\top \Theta_j) = R. $$ Now let's apply the vectorization to the both sides: $$ 2 \operatorname{vec}(X^\top) + \rho N \sum_{j=1}^M \operatorname{vec} (\Theta_j) \operatorname{Tr}(X^\top \Theta_j) = \operatorname{vec}(R). $$ Using the property $\operatorname{Tr}(AB) = \operatorname{vec}(A)^\top \operatorname{vec}(B) = \operatorname{vec}(B)^\top \operatorname{vec}(A)$ we obtain $$ 2 \operatorname{vec}(X^\top) + \rho N \sum_{j=1}^M \operatorname{vec} (\Theta_j) \operatorname{vec}(\Theta_j)^\top \operatorname{vec}(X^\top) = \operatorname{vec}(R). $$ Finally the equation can be written as a system of linear equations: $$ \left[ 2 I + \rho N \sum_{j=1}^M \operatorname{vec} (\Theta_j) \operatorname{vec}(\Theta_j)^\top \right] \operatorname{vec}(X^\top) = \operatorname{vec}(R). $$ The matrix of the system is symmetric and positive definite.

Here is a small python implemetation of the method.

Answer 2

$\def\bb{\mathbb}$ Start by taking the transpose of the equation $$\eqalign{ (2S^T - A^T) &= 2X + \rho\sum_{i=1}^N \sum_{j=1}^M\Theta_j{\rm Tr}({\Theta_j} X) + \Theta_j\,{C_{ij}} \tag{1} \\ }$$ Define the vectors $\,b_j={\rm vec}(\Theta_j)$ and collect them into the columns of a matrix $$\eqalign{ B &= \big[b_1\;b_2\;\ldots\;b_M\big] \in {\bb R}^{n^2\times M} \\ b_j &= Be_j \\ }$$ where $\{e_j\}$ denote the standard basis vectors for $\bb R^M$ and, for future reference,
let ${\tt1}\in\bb R^N$ denote the all-ones vector.

Vectorizing Equation $(1)$ yields $$\eqalign{ (2Ks - Ka) &= 2x + N\rho\sum_j b_jb_j^Tx + \rho\sum_i\sum_j {\tt1}_iC_{ij}b_j \\ (2Ks - Ka) &= 2x + N\rho BB^Tx + \rho BC^T{\tt1} \\ \big(2I+N\rho BB^T\big)x &= \big(2Ks-Ka-\rho BC^T{\tt1}\big) \\ x &= \big(2I+N\rho BB^T\big)^{-1}\big(2Ks-Ka-\rho BC^T{\tt1}\big) \\ }$$ where $K$ is the Commutation Matrix used to vectorize the transpose of a matrix and $$a={\rm vec}(A),\quad s={\rm vec}(S),\quad x={\rm vec}(X)$$

The remaining step is to reshape the solution vector $(x)$ into a matrix $(X)$.