1
$\begingroup$

To solve the equation $AXB=C$ for X, we can use the property of vec operator and kronecker product to transform to $(B^{T}\otimes A)\operatorname{vec}(X)=\operatorname{vec}(C)$, where $\operatorname{vec}(\cdot)$ is the vectorization operator.

Is there any risk to do like this, since $B^{T}\otimes A$ is a much larger matrix than A or B?

Thank you.

$\endgroup$
  • 1
    $\begingroup$ I think the OP intended to write AXB and vec $\endgroup$ – Eckhard Jun 21 '13 at 19:37
  • $\begingroup$ yes. thanks Eckhard and amWhy. $\endgroup$ – Jack2019 Jun 21 '13 at 19:39
3
$\begingroup$

We assume that the unknown $X\in M_{m,n}$. When $A\in M_{m,m},B\in M_{n,n}$ are full matrices, $B^T\otimes A$ is a full $mn\times mn$ matrix; then inversion of such a matrix has complexity $O(m^3n^3)$. As we will see, using this method (when $A,B$ are large matrices), is a very bad idea.

There are special methods to solve equations in the form $AXB+CXD=E$ where $A,C\in M_{m,m},B,D\in M_{n,n},E\in M_{m,n}$ are known and $X\in M_{m,n}$ is unknown. cf.

i) http://www.maths.lth.se/na/courses/NUM115/NUM115-09/sylvester.pdf

uses an algorithm that is an extension of the Bartels–Stewart method and the Hessenberg-Schur method. Originally the Bartels –Stewart algorithm was used to solve the Sylvester equation.

ii) http://www.dm.unibo.it/~simoncin/matrixeq.pdf

That is important, is that the previous algorithms have complexity $O(n^3+m^3)$ that is much smaller than the complexity of the Kronecker product method. For example, solving a Lyapounov equation ($AX+XA^T=B$ with $n\times n$ matrices) -with Bartels–Stewart- has the same complexity ($\approx 40 n^3$) as finding eigenvalues and eigenvectors of a $n\times n$ matrix.

$\endgroup$
0
$\begingroup$

No, I don't think there is any risk algebraically (although there are obvious computational issues)- in fact, it's one of the benifits of the $\text{vec}$ operator. But you need to be aware that when you are done, you will have $\vec{X}$ not $X$

Check out the bottom of page 6: https://tminka.github.io/papers/matrix/minka-matrix.pdf

In that document (which is a great introduction to matrix calculus), they give the example of using the vec operator to solve the Lyapunov Equation $AX + XB = C$ for $X$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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