# Recurrence relation in matrices

I have the following recursive sequence:

$$Z_k = Z_{k-1} - AA^TZ_{k-1}xx^T$$ where $$Z_k \in \mathbb R^{n \times d}, A \in \mathbb R^{n \times d}, d > n, rank(A) = n, x \in \mathbb R^{d \times 1}$$

$$A$$ is a constant matrix, $$x$$ is a constant vector. Theoretically, this sequence of matrices $$Z_k$$ is entirely determined by $$Z_0$$ the initial element of the sequence.

If I give you $$Z_0$$ you are able to find $$Z_k$$ for any $$k$$.

Suppose I want to find $$Z_{100}$$. Is it possible to find an expression for $$Z_k$$ as a function of $$Z_0$$ so that I don't actually have to find $$Z_1, Z_2, ..., Z_{99}$$?

• This is a linear recurrence relation, so in theory it is possible to work out the general formula for $Z_k$, provided that the matrices $A$ and $x$ are explicitly given. Not sure whether there is an optimization for this special kind of recurrence relation. Jan 15 at 0:51

Let $$B=AA^T$$ and $$X=xx^T$$. Note that $$X^k=\|x\|^{2k-1}X$$.
\begin{align*} Z_1& = Z_{0} - BZ_{0}X \\ % Z_2& = Z_{1} - BZ_{1}X % = Z_{0} - BZ_{0}X -B\big[Z_{0} - BZ_{0}X\big]X % = Z_{0} - 2BZ_{0}X + B^2Z_{0}X^2 \\ % Z_3& = Z_{2} - BZ_{2}X % = Z_{1} - BZ_{1}X -B\big[Z_{1} - BZ_{1}X\big]X % = Z_{1} - 2BZ_{1}X + B^2Z_{1}X^2 \\ % & = Z_{0} - 3BZ_{0}X + 3B^2Z_{0}X^2-B^3Z_{0}X^3 . \end{align*}
\begin{align*} % Z_n& =\sum_{k=0}^n-1^k\binom nk B^kZ_0X^k % = Z_0 + \sum_{k=1}^n-1^k\binom nk \|x\|^{2k-1}B^kZ_0X\\ % & = Z_0-\frac1{\|x\|^2}Z_0X + \frac1{\|x\|^2} % \bigg[\sum_{k=0}^n-1^k\binom nk \|x\|^{2k}B^k\bigg]Z_0X \\ % & =Z_0-\frac1{\|x\|^2}Z_0X + \frac1{\|x\|^2} % [I-\|x\|^2B]^nZ_0X \\ % & =Z_0-\frac1{\|x\|^2}Z_0xx^T + \frac1{\|x\|^2} % [I-\|x\|^2AA^T]^nZ_0xx^T % \end{align*}