Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$

share|improve this question

3 Answers 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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer
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 '11 at 6:42
    
Is it easy to solve $AXA-X=C$ ? Could you give materials related to this formula? –  Peter Feb 18 '11 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 '11 at 11:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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