2
$\begingroup$

I am now struggling to solve the matrix $X \in R^{n \times n}$ in the following equation:

$X=c \cdot AXA' - diag(c \cdot AXA')+ I$,

where

(1) $A \in R^{n \times n}$ is a given matrix whose element $0\le A_{i,j} \le 1$,

(2) $c$ is a constant value $0<c<1$,

(3) $I \in R^{n \times n}$ is an identity matrix,

(4) The operator $diag(X)$ returns a diagonal matrix with the same size of matrix $X$, whose main diagonal entries are the diagonal entries of $X$.

=========

I know that if the $diag(\cdot)$ terms in the above equation is omitted, then I can solve $X$ in the equation $X=c \cdot AXA' + I$ easily, because $X=I+cAA'+c^2A^2 A'^2 + ...$ is a unique solution. However, currently there is an additional diagonal term in the equation to ensure $X$'s diagonal entries are corrected to all 1s. So I appreciate if you can give me some hints on solving that equation. Thanks in advance.

Improve this question
$\endgroup$
8
  • $\begingroup$ Actually your assumptions are not sufficient for the convergence of the series $X=I+cAA'+c^2A^2 A'^2 + \dots$. For instance, if $A_{ij}=1$ for all $i,j$ then $A^k=A'^k=n^{k-1}A$ so you need $|c|<1/n^2$. $\endgroup$
    – Pietro Majer
    Commented Aug 14, 2014 at 14:42
  • $\begingroup$ And the same condition together with(1) is also sufficient for the convergence of the Neumann series $X:=I+\mathcal{L}I+ \mathcal{L}^2I\dots$ for the solutions of both problems, written as $X=I+\mathcal{L}X$. $\endgroup$
    – Pietro Majer
    Commented Aug 14, 2014 at 15:24
  • $\begingroup$ @PietroMajer, Thanks for pointing out the right convergence condition. Currently, what I am baffling with user35593's answer is that how to find out $D$ effectively. It seems to me that calculating $D$ is still very hard. $\endgroup$
    – John Smith
    Commented Aug 14, 2014 at 17:25
  • $\begingroup$ If $c$ small is OK to you, can't you just solve your problem by means of the Newman series (check my previous comment)? Precisely, with $\mathcal{L}M:=cAMA'-c\mathrm{diag}(AMA')$. $\endgroup$
    – Pietro Majer
    Commented Aug 14, 2014 at 17:42
  • 1
    $\begingroup$ I don't think so, because the infinite product needs $\mathcal{L}^{2^k}$, not $\mathcal{L}^{2^k}I$. But the series $X=\sum_{k\ge0}M_k$ with $M_0:=I$, $M_{k+1}=\mathcal{L}M_k$ is not that bad. Note that $\mathcal{L}M$ is even simpler than $cAMA'$ to compute (the entries coincide outside the diagonal, and diagonal entries in $\mathcal{L}M$ are zero). $\endgroup$
    – Pietro Majer
    Commented Aug 14, 2014 at 20:50

2 Answers 2

Reset to default
2
$\begingroup$

Let $D$ be the (unknown) diagonal matrix defined by $$D:=I-diag(cAXA').$$ Then $X=cAXA'+D$ and as in your comment we have (assuming that $c\|A\|\|A'\|<1$) that $$X=D+cADA'+c^2A^2D(A')^2+\dots$$ is a solution. Now the problem is to choose $D$ in such a way that $X$ is 1 on the diagonal. For this consider the linear map $f$ defined by $$D \mapsto diag(D+cADA'+c^2A^2D(A')^2+\dots)$$ and find $D:=f^{-1}(I)$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Is there an explicit expression for $D$ ? $\endgroup$
    – John Smith
    Commented Jul 15, 2014 at 14:29
0
$\begingroup$

We study an affine equation $\phi(X)=X$ but there is no closed form for "the" solution.

Here $\phi:X\rightarrow cAXA^T-diag(cAXA^T)+I$ ; let $E_i$ be the matrix with all entries $=0$ except the $(i,i)^{th}$ that is $1$. If we stack the square matrices row by row, then $\sum_i E_i\bigotimes E_i:X\rightarrow diag(X)$ (cf. http://en.wikipedia.org/wiki/Kronecker_product). Thus $\phi=cA\bigotimes A-c(\sum_i E_i\bigotimes E_i)(A\bigotimes A)+1=cA\bigotimes A-c\sum_i(E_iA)\bigotimes(E_iA)+1=cA\bigotimes A-c\sum_i A_i\bigotimes A_i+1$ where $1:X\rightarrow I$ and $A_i$ is the matrix with all rows $=0$ except the $i^{th}$ that is the $i^{th}$ row of $A$. There exist numerical methods that solve this type of equation.

EDIT: for $l^2$ norm, $||\sum_i E_i\bigotimes E_i)||=1$ and $||A\bigotimes A||\leq ||A||^2$. Therefore $||D\phi||\leq 2c||A||^2$ ; if $2c||A||^2\leq k<1$, then we can use the Banach fixed point theorem.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .