1
$\begingroup$

Suppose $X$ is an unknown $m \times m$ diagonal matrix. Given a scalar $0<c<1$, and a matrix $A$ of $m \times m$ size whose entries $0<A_{i,j}<1$. Are there some algorithms to find the diagonal matrix $X$ to the following equation:

$$diag(X+cAXA'+c^2A^2X(A')^2+\dots) = \vec1$$

where $\vec1$ is the $m \times 1$ vector of all 1s, $diag(Y)$ returns the vector consisting of all the diagonal entries of a matrix $Y$, and $A'$ denotes the transpose of matrix $A$.

$\endgroup$
2
  • $\begingroup$ What does $A'$ mean? $\endgroup$ Jul 24, 2014 at 12:05
  • $\begingroup$ $A'$ denotes the transpose of matrix $A$ $\endgroup$
    – John Smith
    Jul 24, 2014 at 12:12

2 Answers 2

2
$\begingroup$

First of all, I note that the scalar $c$ is redundant, we might as well replace $A$ by $\sqrt{c}A$. Now let $Y$ be the matrix such that $Y-AYA'=X$. This matrix is given in terms of $X$ by $m(m+1)/2$ equations for equally many unknowns (note that $Y$ is symmetric). By solving this linear system, you can express $Y$ in terms of $X$. What you want is that the diagonal elements of $Y$ are equal to one, which gives you a system of $m$ equations for the $m$ entries of $X$.

If $m$ is large, this method may not be practical. If $A$ is suitably small, you may consider the iteration $X_{n+1}=1-diag(AX_nA'+A^2X_n(A')^2...).$

$\endgroup$
1
  • $\begingroup$ thanks. What if $m$ is large? Any efficient methods? $\endgroup$
    – John Smith
    Jul 24, 2014 at 23:13
0
$\begingroup$

As Michael wrote, we may assume $c=1$.

Your equation can be written $diag(\phi(X))=[1]$ where $\phi$ is the linear function $\sum_{k=0}^{\infty}A^k\otimes A^k=\sum_{k=0}^{\infty}(A\otimes A)^k$ (Here we stack the matrices row by row). This series converge for every $X$ iff $\rho(A\otimes A)<1$, that is, iff $\rho(A)<1$; in the sequel, we assume that the previous condition is fulfilled. Note that your condition about the $(A_{i,j})$ is not sufficient, except perhaps if $c$ is small;

We obtain $diag((I_{m^2}-A\otimes A)^{-1}X)=[1]$. The general solution is $X=(I_{m^2}-A\otimes A)U$ where $U$ is an arbitrary $m\times m$ matrix with diagonal $1$. In particular, $X$ depend on $m^2-m$ free parameters ($X$ has $m^2-m$ degrees of freedom).

EDIT 1. I just see that $X=diag(x_i)$ is diagonal. Moreover, I obtain the same equation than Michael.

EDIT 2. It is better to reason as follows: let $B=[b_{i,j}]=(I_{m^2}-A\otimes A)^{-1}$. We obtain explicitly $X$ as a function of the $(b_{i,i})$: for every $i$, $x_i=1/b_{i,i}$.

In particular, a necessary condition is that, for every $i$, $b_{i,i}\not=0$ (and there is a sole solution in $X$), otherwise there are no solutions in $X$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.