Question

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$

Answer 1

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$.

Answer 2

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

Answer 3

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.