2
$\begingroup$

Let $A$ and $D$ are $n\times n$ diagnal matrices, and $B$ is an $n\times n$ orthogonal matrix. Is there any efficient way to compute the follow matrix equations easily?

$\sum_{i=0}^{k} A^i \cdot B^T \cdot D \cdot B \cdot A^i$

$\endgroup$

3 Answers 3

2
$\begingroup$

OK here's my take on this calculation: first of all, observe that if $E$ is any $n \times n$ square matrix, and $\Lambda$ is the diagonal matrix $diag(\lambda_{1}, \lambda_{2}, . . ., \lambda_{n})$, then $E \Lambda$ simply multiplies the $j$-th column of $E$ by $\lambda_{j}$ for each $j$, $1 \le j \le n$. Likewise, $\Lambda E$ multiplies the $l$-th row of $E$ by $\lambda_{l}$. Taking $A = diag(a_{1}, a_{2}, . . ., a_{n})$, we have $A^{k} = diag(a_{s}^{k})$, where I have made the (hopefully) obvious abbreviation of notation. So $A^{m}EA^{m}$ multiplies the $lj$ entry of $E$, call it $e_{lj}$ (so that $E = [e_{lj}]$), by $a_{l}^{m}a_{j}^{m} = (a_{l}a_{j})^m$: $A^{m}EA^{m} = [e_{lj}(a_{l}a_{j})^{m}]$, so $\sum_{i=0}^{i=k}A^{k}EA^{k} = [e_{lj}\sum_{i=0}^{i=k}(a_{l}a_{j})^i]$. A further simplification may be obtained by observing that $\sum_{i=0}^{i=k}(a_{l}a_{j})^{i} = ((a_{l}a_{j})^{k+1} -1)/(a_{l}a_{j} - 1)$ if $a_{l}a_{j} \ne 1$ and $\sum_{i=0}^{i=k}(a_{l}a_{j})^{i} =k + 1$ if $a_{l}a_{j} = 1$ Now consider $B^{T}DB$; since $D$ is diagonal, we can group it with either $B^{T}$ or $B$ and use the same trick applied above to $\Lambda E$, $E \Lambda$ to simplify one of the matrix multiplications. But it seems like our luck ends there, you'll just have to do plain old-fashioned matrix multiplication on either $(B^{T}D)B$ or $B^{T}(DB)$ (your choice). Then take $E = B^{T}DB$ and proceed as described in previous to get the sum.

Not sure about the complexity of this method, there's at least one full matrix multiply involved in calculating $B^{T}DB$, which is $O(n^{3})$; the rest of it looks like it might be $O(kn^{2})$, since we have eliminated the for complete matrix multiplication in favor of multiplying each element by one value. Just guessing here, but it's pushing 3AM and I've had to wrestle with MathJax tonight, so this took longer to type than anticipated. Too sleepy to think much more . . . but, complexity issues aside, there's another way to look at it.

BTW, it seems that Gerry Myerson's idea can be patched up by setting $C = A^{k+1}B^{T}DBA^{k+1} -B^{T}DB$, i.e., subtracting off the $i = 0$ term.

@Peter: $AXA - X = C$ is a linear system in the entries of $X$; the solution is standard. The technique I described avoids some of the problems which might arise in linear system solution, i.e. ill-conditioning of the coefficient matrices. There's a ton of literature on this; I suggest googling around a bit.

$\endgroup$
1
$\begingroup$

Let S(j) denote the sum of the first j terms of your sum. Then S(2j-1) = S(j-1) + A^j S(j-1) A^j. So you can arrange the work so that it requires O(log k) multiplications.

Gerhard "Ask Me About System Design" Paseman, 2011.02.18

$\endgroup$
0
$\begingroup$

I'm going to assume that the problem is that $k$ might be large (and that "effective" was supposed to be "efficient", and "digonal" was supposed to be "diagonal"). Let's call the sum $X$. Then $AXA-X=A^{k+1}B^TDBA^{k+1}=C$, say, is easy to calculate. Furthermore, it's easy to relate the entries of $AXA$ to those of $X$, so it's easy to solve $AXA-X=C$ for $X$.

$\endgroup$
3
  • 1
    $\begingroup$ I think you forgot to account for the $i=0$ term. To see this, note that the equation you write down has no solution when $A$ is the identity matrix. $\endgroup$
    – alex
    Feb 18, 2011 at 6:42
  • $\begingroup$ Is it easy to solve $AXA-X=C$ ? Could you give materials related to this formula? $\endgroup$
    – Peter
    Feb 18, 2011 at 9:11
  • $\begingroup$ @alex, absolutely right, I should have written $A^{k+1}B^TDBA^{k+1}-B^TDB$. @Peter, this site caters for mathematicians doing research. I expect any research mathematician to be able to work out how $AXA$ relates to $X$ when $A$ is diagonal and go from there. If you can't, you've come to the wrong site. Have a look at the faq, and the alternative websites mentioned therein. $\endgroup$ Feb 18, 2011 at 11:25

Your Answer

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

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