7

This came up in a practical problem involving a state change in a digital filter system.

Find $X$ given $A$ and $K$, where $A,X,K$ are all $n$ x $n$ square matrices:

$$ X - A X A = K $$ I couldn't find a direct way to do this, eventually I realized that it's just $n^2$ linear equations in $n^2$ unknowns, and it can be solved as follows:

  • Restate so $X$ and $K$ are column vectors $\vec x$ and $\vec k$, each with $n^2$ elements
  • The term $A X A$ becomes $A_L A_R \vec x$, where $A_L, A_R$ are $n^2$ x $n^2$ matrices which perform the equivalent of multiplying by $A$ on the left and right in the original form
  • Find $\vec x = \left(I-A_L A_R \right)^{-1} \vec k$ and reorder to get $X$

For $n=3$, for instance, if $$ A = \begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix} $$ then $$ A_L = \begin{bmatrix} a & 0 & 0 & b & 0 & 0 & c & 0 & 0 \\ 0 & a & 0 & 0 & b & 0 & 0 & c & 0 \\ 0 & 0 & a & 0 & 0 & b & 0 & 0 & c \\ d & 0 & 0 & e & 0 & 0 & f & 0 & 0 \\ 0 & d & 0 & 0 & e & 0 & 0 & f & 0 \\ 0 & 0 & d & 0 & 0 & e & 0 & 0 & f \\ g & 0 & 0 & h & 0 & 0 & i & 0 & 0 \\ 0 & g & 0 & 0 & h & 0 & 0 & i & 0 \\ 0 & 0 & g & 0 & 0 & h & 0 & 0 & i \end{bmatrix} $$ and (in block form): $$ A_R = \begin{bmatrix} A^T & 0 & 0 \\ 0 & A^T & 0 \\ 0 & 0 & A^T \end{bmatrix} $$

Question is: is there any easier way to solve this? I'm now thinking that the relationship between the $n^2$ variables is such that you can't solve it without this kind of rewriting, but I'd be happy to be proven wrong. Is there a name for the procedure of restating the problem as above? Or a name for the type of the original equation? Perhaps it would be more natural with tensor notation - I'm not that familiar with that area.

One other note: the original equation can be be rewritten as the following two forms:

$$ X = A X A + K $$ and (assuming $A$ is not singular) $$ X = A^{-1} \left( X - K \right) A^{-1} $$ ... and it seems to me that one of these (depending on the properties of $A$) may be usable as a iterator that will converge to the correct value of $X$. In some applications this may easier to work with than the full solution.

greggo
  • 338

1 Answers1

7

You are basically correct, and yes there is a systematic way in solving these kind of equations. It is more like a systematic way of writing it down, than a different approach since it is really just solving a linear equation system (as you already noticed). The key things are

The key formula is (which is easily proved, and similar to what you found)

$\text{vec}(ABC) = (C^T \otimes A) \text{vec}(B)$.

This gives an elegant solution of your (and related) problems:

$X - AXA = K$

gives

$\text{vec}(X) - (A^T \otimes A) \text{vec}(X) = \text{vec}(K)$.

Which is easily solved for the elements of $X$ (represented by $\text{vec}(X)$)

$\text{vec}(X) = (I - A^T \otimes A)^{-1} \text{vec}(K)$.

This also tells you that a unique solution exists, if and only if $I - A^T \otimes A$ is invertible. In the wikipedia references, you may find interesting properties of the vectorization operator and the Kronecker product, which may or may not be helpful for you. For example, the eigenvalues and eigenvectors of it are very easily obtained.

EDIT: If one prefers row-wise vectorization, one can also do that. The key is to recognize that row-wise vectorization is just $\text{vec}(X^T)$. We can write your problem as

$X^T - A^TX^TA^T = K^T$

which after vectorization gives

$\text{vec}(X^T) - (A \otimes A^T) \text{vec}(X^T) = \text{vec}(K^T)$

or

$\text{vec}(X^T) = (I - A \otimes A^T)^{-1} \text{vec}(K^T)$.

You see, that with row-wise vectorization a very similar formula is obtained. Actually just the order of the arguments in the Kronecker product are exchanged.

Andreas H.
  • 1,525