0
$\begingroup$

How can I solve this matrix equation for $X$: $$ (A^T)X = B(X-Y)C, $$ where $A^T$ is the transpose of $A$.

Here, all matrices are small (e.g., $2\times2$). I am especially interested in the following two cases: (a) $Y$ is the matrix with all entries having the value 2, and (b) $Y=2I$, where $I$ is the identity matrix.

$\endgroup$

closed as unclear what you're asking by user147263, Shailesh, Leucippus, BLAZE, Antonios-Alexandros Robotis Mar 14 '16 at 4:43

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Solve the equation for what? $\endgroup$ – copper.hat Mar 14 '16 at 4:18
  • 2
    $\begingroup$ What does $X-2$ mean? Are the matrices invertible? $\endgroup$ – copper.hat Mar 14 '16 at 4:34
  • 4
    $\begingroup$ What does 'find $X A^T = A^T$ mean? (Extracting the meaning bit by bit is rather tiresome.) $\endgroup$ – copper.hat Mar 14 '16 at 4:38
  • 2
    $\begingroup$ @Arthur: What do you mean by 'Had you gone to the source'? What line break are you talking about? How am I playing dumb? I have to say, MSE interactions often leave me scratching my head. $\endgroup$ – copper.hat Mar 14 '16 at 4:42
  • 1
    $\begingroup$ @Arthur: Lighten up. I try to help out where when I get a chance, I don't spend time debugging MathJax. Your insinuation of my being lazy is unwarranted and not appreciated. $\endgroup$ – copper.hat Mar 14 '16 at 4:50
3
$\begingroup$

If $B$ is invertible, or if both $A$ and $C$ are invertible, then this can be easily converted to a Sylvester equation, and you can use standard direct methods for solving it. If not (or if your matrices are not amenable to direct factorizations and you want to use an iterative method instead), then read on; the problem becomes very interesting.

You can use the relationship between vectorization, $\text{vec}(\cdot)$, and the Kronecker product, $\otimes$, to set up a meta-matrix representing the linear system for the vectorization of $X$. In general, the following useful facts hold for any matrices $U,V,W$ of the appropriate size and invertibility so that the equations make sense, $$\text{vec}(UVW) = (W^T \otimes U) \text{vec}(V),$$ $$(U \otimes V)^{-1} = (U^{-1} \otimes V^{-1}),$$ $$(U \otimes V)^T = (U^T \otimes V^T)$$ $$(U \otimes V)(Z \otimes Q) = (UZ) \otimes (VQ)$$ We can use this in our situation as follows, \begin{align} A^T X &= B(X-Y)C \\ \text{vec}(A^T X) &= \text{vec}(B (X - Y)C), \\ (I \otimes A^T) \text{vec}(X) &= (C^T \otimes B) \text{vec}(X) - (C^T \otimes B)\text{vec}(Y), \\ (\underbrace{I \otimes A^T}_{M_1} - \underbrace{C^T \otimes B}_{M_2})\underbrace{\text{vec}(X)}_{x} &= - \underbrace{(C^T \otimes B)}_{M_2}\underbrace{\text{vec}(Y)}_{y} \end{align} which yields the following system of the general form $$(M_1 - M_2)x=-M_2 y.$$ In the case where these matrices $M_1$ and $M_2$ are square and $M_1+M_2$ is invertible, and the sizes are not too large, you can directly form the matrices and solve for the vector of entries in the desired matrix, $x = \text{vec}(X)$. E.g., see the following Matlab code,

A = randn(5,5); B = randn(5,5); C = randn(3,3); Y = randn(5,3);

M1 = kron(eye(3),A');
M2 = kron(C',B);
b = -reshape(B*Y*C, [],1); % = -M2*y
x = (M1-M2)\b;
X = reshape(x,5,3);
norm(A'*X - B*(X-Y)*C) % returns machine zero

But what if the matrices $M_1$ and $M_2$ are not square? If $A$ is a tall matrix, then $M_1-M_2$ is a wide matrix. Unless we are particularly unlucky, this matrix will have full column rank, so we can still find a solution (one of many) by solving the normal equations, $$(M_1 - M_2)^T(M_1 - M_2)x = -(M_1 - M_2)M_2 y,$$ or if you like, the slightly regularized version, $$\left((M_1 - M_2)^T(M_1 - M_2) + \epsilon I \right)x = -(M_1 - M_2)M_2 y.$$ For example,

A = randn(5,3); B = randn(3,5); C = randn(4,4); Y = randn(5,4);

M1 = kron(eye(4),A');
M2 = kron(C',B);
b = -reshape(B*Y*C, [],1); % = -M2*y
epsilon=1e-7;
x = ((M1-M2)'*(M1-M2) + epsilon*eye(numel(Y)))\((M1-M2)'*b);
X = reshape(x,size(Y));
norm(A'*X - B*(X-Y)*C) % returns error on the order of epsilon

If $A$ is a wide matrix, then there is generally no solution to the equations, unless we get particularly lucky.

In the special case (a) where $Y=2 \mathbb{1}\mathbb{1}^T$ is the matrix of all 2's, the right hand side takes the form, $$y = (C^T \otimes B)\text{vec}\left(2\mathbb{1}\mathbb{1}^T\right) = 2\text{vec}\left(B \mathbb{1}\mathbb{1}^T C\right) = 2\text{vec}\left((B \mathbb{1})(C^T \mathbb{1})^T\right),$$ where $\mathbb{1}$ is the vector of all ones.

In the special case (b) where $Y=2I$, the right hand side takes the form, $$y = (C^T \otimes B)\text{vec}\left(2I\right) = 2\text{vec}(BIC) = 2\text{vec}(BC)$$

If the problem is large enough that forming $M$ is prohibitive, you can still apply the action of $M_1$ and $M_2$ on a vector $u=\text{vec}(U)$ by doing some matrix multiplications, $$M_1u = \text{vec}(A^T U), \quad M_2u = \text{vec}(BUC),$$ which allows you to use iterative methods like GMRES. Furthermore, we can precondition it as follows: if one of the matrices $M_1$ or $M_2$ is dominant over the other, you can use that matrix as a preconditioner.

If both matrices are of roughly equal importance, then you use both together as preconditioners, either additively, or multiplicatively.

$\endgroup$
  • 1
    $\begingroup$ I'm sorry, but could you explain what $X-2$ means? $\endgroup$ – Joel Reyes Noche Mar 14 '16 at 4:58
  • $\begingroup$ @JoelReyesNoche In matrix equations, a number $r$ is often used as shorthand for $rI$, where $I$ is the identity matrix. This is a slight abuse of notation, but common enough. $\endgroup$ – Arthur Mar 14 '16 at 5:03
  • $\begingroup$ @Arthur, thanks. I was unfamiliar with that notation. $\endgroup$ – Joel Reyes Noche Mar 14 '16 at 5:04
  • $\begingroup$ Usually in the context of matrix equations, $X-2$ means subtracting the matrix of all 2's (not the identity). This is somewhat confusing but this is how I have seen it in this context. $\endgroup$ – Nick Alger Mar 14 '16 at 5:06
  • $\begingroup$ @NickAlger, thanks, I'm also unfamiliar with that practice. $\endgroup$ – Joel Reyes Noche Mar 14 '16 at 5:07

Not the answer you're looking for? Browse other questions tagged or ask your own question.