## is there any efficient way to compute the follow matrix equations easily

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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$

-

## 3 Answers

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.

-

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-

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

-

1
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. – alex Feb 18 2011 at 6:42
Is it easy to solve $AXA-X=C$ ? Could you give materials related to this formula? – Peter Feb 18 2011 at 9:11
@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. – Gerry Myerson Feb 18 2011 at 11:25
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 50, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9550514817237854, "perplexity_flag": "head"}