Widely linear systems of equations

I would strongly assume that this must exist already somewhere but I couldn’t find the solution so I thought it would be interesting to post it here. The closest to this I could find is widely linear estimation (e.g., Picinbono, TSP, 1995), but it’s not quite the same.

Consider the following widely linear system of equations:

$$\ma{A} \cdot \ma{x} + \ma{B} \cdot \ma{x}^* = \ma{c},$$

where $\ma{A},\ma{B} \in \compl^{N \times N}$ are square invertible matrices and $\ma{x}, \ma{c} \in \compl^{N \times 1}$ vectors of corresponding dimension. We would like to find the vector $\ma{x}$ which satisfies this equation given $\ma{A}$, $\ma{B}$, and $\ma{c}$, if it exists.

This is a system of equations but it is not linear in $\ma{x}$. It is widely linear though and this implies that it is linear in  ${\rm Re}\{\ma{x}\}$ and in ${\rm Im}\{\ma{x}\}$. Therefore, it can easily be rewritten as a set of linear equations by introducing the real and imaginary parts of all quantities, i.e., $\ma{A} = \ma{A}_{\rm R} + \jmath \ma{A}_{\rm I}$, $\ma{B} = \ma{B}_{\rm R} + \jmath \ma{B}_{\rm I}$, $\ma{c} = \ma{c}_{\rm R} + \jmath \ma{c}_{\rm I}$, and $\ma{x} = \ma{x}_{\rm R} + \jmath \ma{x}_{\rm I}$. Inserting this into the widely linear system of equations and separating real and imaginary parts we obtain

$$\left( \left[ \ma{A}_{\rm R} + \ma{B}_{\rm R} \right] \cdot \ma{x}_{\rm R} + \left[ -\ma{A}_{\rm I} + \ma{B}_{\rm I} \right] \cdot \ma{x}_{\rm I}\right) + \jmath \cdot \left( \left[ \ma{A}_{\rm I} + \ma{B}_{\rm I} \right] \cdot \ma{x}_{\rm R} + \left[ \ma{A}_{\rm R} – \ma{B}_{\rm R} \right] \cdot \ma{x}_{\rm I}\right) = \ma{c}_{\rm R} + \jmath \ma{c}_{\rm I}.$$

As both sides of the equations are complex numbers, they are equal only if the real parts are equal and the imaginary parts are equal. Hence we have two real-valued systems of equation, which we can write in one larger system:

$$\begin{bmatrix} \ma{A}_{\rm R} + \ma{B}_{\rm R} & -\ma{A}_{\rm I} + \ma{B}_{\rm I}  \\ \ma{A}_{\rm I} + \ma{B}_{\rm I} & \ma{A}_{\rm R} – \ma{B}_{\rm R} \end{bmatrix} \cdot \begin{bmatrix} \ma{x}_{\rm R} \\ \ma{x}_{\rm I} \end{bmatrix} = \begin{bmatrix} \ma{c}_{\rm R} \\ \ma{c}_{\rm I} \end{bmatrix}.$$
$$\ma{\tilde{C}} \cdot \begin{bmatrix} \ma{x}_{\rm R} \\ \ma{x}_{\rm I} \end{bmatrix} = \begin{bmatrix} \ma{c}_{\rm R} \\ \ma{c}_{\rm I} \end{bmatrix}.$$

Consequently we have exactly one solution in $\ma{x}$ if and only if the block matrix $\ma{\tilde{C}}$ is non-singular, which implies additional conditions on $\ma{A}$ and $\ma{B}$. For instance, a sufficient (but not necessary) condition is that $\ma{A}_{\rm R} + \ma{B}_{\rm R}$ and its Schur complement $\ma{A}_{\rm R} – \ma{B}_{\rm R} – (\ma{A}_{\rm I} + \ma{B}_{\rm I}) \cdot (\ma{A}_{\rm R} + \ma{B}_{\rm R})^{-1} \cdot (-\ma{A}_{\rm I} + \ma{B}_{\rm I})$ are both invertible.

*Update* We found a simpler, solution, please read the follow-up blog post on the closed-form solution that avoids real-valued stacking.