Finding the symbolic expression for a particular matrix raised to the $n^{\text{th}}$ power

Question

Consider the following matrix, with $a$ being a real number between $0$ and $1$. \begin{equation} \text{M}=\left[ \begin{array}{cc} 1-\frac{a^2}{3} & \frac{1}{3} \left(2 a-a^2\right) \\ \frac{2 a^2}{3} & 1-\frac{2}{3} \left(2 a-a^2\right) \\ \end{array} \right]. \end{equation}

For a general integer $n$, I am trying to compute the closed form expression for the entries of:

\begin{equation} \text{FinalVector}= \text{M}^{n} \left( \begin{array}{c} 1\\ 1 \\ \end{array} \right). \end{equation}

---

It is very easy to compute what $\text{FinalVector}$ is like for a few specific values of $n$, but is there a way to find a formula for a general $n$?

Here are the values for $\text{FinalVector}$ for the first few $n$ (from Mathematica.)

$n = 1$

$$\left( \begin{array}{c} -\frac{2 a^2}{3}+\frac{2 a}{3}+1 \\ \frac{4 a^2}{3}-\frac{4 a}{3}+1 \\ \end{array} \right)$$

$n = 2$

$$\left( \begin{array}{c} -\frac{2 a^4}{9}+\frac{10 a^3}{9}-\frac{20 a^2}{9}+\frac{4 a}{3}+1 \\ \frac{4 a^4}{9}-\frac{20 a^3}{9}+\frac{40 a^2}{9}-\frac{8 a}{3}+1 \\ \end{array} \right)$$

$n = 3$

$$\left( \begin{array}{c} -\frac{2 a^6}{27}+\frac{2 a^5}{3}-\frac{22 a^4}{9}+\frac{122 a^3}{27}-\frac{14 a^2}{3}+2 a+1 \\ \frac{4 a^6}{27}-\frac{4 a^5}{3}+\frac{44 a^4}{9}-\frac{244 a^3}{27}+\frac{28 a^2}{3}-4 a+1 \\ \end{array} \right)$$

$n = 4$

$$\left( \begin{array}{c} -\frac{2 a^8}{81}+\frac{26 a^7}{81}-\frac{16 a^6}{9}+\frac{440 a^5}{81}-\frac{812 a^4}{81}+\frac{308 a^3}{27}-8 a^2+\frac{8 a}{3}+1 \\ \frac{4 a^8}{81}-\frac{52 a^7}{81}+\frac{32 a^6}{9}-\frac{880 a^5}{81}+\frac{1624 a^4}{81}-\frac{616 a^3}{27}+16 a^2-\frac{16 a}{3}+1 \\ \end{array} \right)$$

---

Answer 1

There is no need to do any eigendecomposition. As observed by the others, $M$ is a rank-one update of the identity matrix: $$ M=\pmatrix{ 1-\frac{a^2}{3}&\frac{1}{3}(2a-a^2)\\ \frac{2a^2}{3}&1-\frac{2}{3}(2a-a^2)} =I+\pmatrix{1\\ -2} \pmatrix{-\frac{a^2}{3}&\frac{1}{3}(2a-a^2)} =I+uv^T. $$ Therefore, when $n\ge1$, \begin{aligned} M^n &=(I+uv^T)^n\\ &=\sum_{k=0}^n\binom{n}{k}(uv^T)^k\\ &=I+\sum_{k=1}^n\binom{n}{k}(uv^T)^k\\ &=I+\sum_{k=1}^n\binom{n}{k}(v^Tu)^{k-1}uv^T\\ &=\begin{cases} I+\frac{(1+v^Tu)^n-1}{v^Tu}uv^T&\text{if }v^Tu\ne0,\\ I+nuv^T&\text{if }v^Tu=0.\\ \end{cases} \end{aligned} It follows that $$ M^n\mathbf1 =\begin{cases} \mathbf1+\left[\frac{(1+v^Tu)^n-1}{v^Tu}(v^T\mathbf1)\right]u&\text{if }v^Tu\ne0,\\ \mathbf1+n(v^T\mathbf1)u&\text{if }v^Tu=0.\\ \end{cases}. $$

Answer 2

$ \def\a{\alpha}\def\b{\beta}\def\l{\lambda} \def\o{{\tt1}}\def\p{\partial} \def\L{\left}\def\R{\right}\def\LR#1{\L(#1\R)} \def\qiq{\quad\implies\quad} \def\grad#1#2{\frac{\p #1}{\p #2}} \def\m#1{\left[\begin{array}{c}#1\end{array}\right]} \def\fracLR#1#2{\LR{\frac{#1}{#2}}} $Given a rank-one matrix $A=uv^T$, multiply by $u$ and note that $$\eqalign{ Au &= u\LR{v^Tu} = \l u \qiq \l=u^Tv\quad\big({\rm eigenvalue}\big) }$$ Similarly, mulitply by any vector $q$ orthogonal to $v$ to find that it is also an eigenvector corresponding to an eigenvalue of $0$ $$\eqalign{ Aq &= u\LR{v^Tq} \;=\; 0 }$$ Multiplying the matrix by itself reveals an unusual property $$\eqalign{ A^2 &= \l A,\quad A^3 &= \l^2 A,\quad\ldots\quad A^k &= \l^{k-1}A \\ }$$ which allows any analytic function of the matrix to be reduced to a linear polynomial, i.e. $$ f(A) = \a A + \b I $$ Combining this with the fact that the eigenvalues of $f(A)$ are given by $f(\l_k)$ generates a system of scalar equations for our two eigenvalues which can be trivially solved for the unknown coefficients $$\eqalign{ \a 0 + \b &= f(0) &\qiq \b = f(0) \\ \a\l + \b &= f(\l) &\qiq \a = \frac{f(\l)-f(0)}{\l} \\ }$$ Now we can write an expression for the function of a rank-one matrix, including the limiting case when $\l\to 0\,$ (via l'Hopital's Rule) $$\eqalign{ f(A) &= f(0)\,I &+\; \fracLR{f(\l)-f(0)}{\l}A \\ \lim_{\l\to 0}\;f(A) &= f(0)\,I &+\; f'(0)\;A \\ }$$ and multiply it by the all-ones vector $$\eqalign{ f(A)\,\o &= f(0)\,\o &+\; \fracLR{f(\l)-f(0)}{\l}\LR{v^T\o}u \\ \lim_{\l\to 0}\;f(A)\,\o &= f(0)\,\o &+\; f'(0)\LR{v^T\o}u \\ \\ }$$

---

Substituting the parameters for this particular problem $$\eqalign{ u &= \m{+\o \\ -2}, \quad &v = \frac 13\m{-a^2 \\ 2a-a^2 }, \quad A = uv^T \\ \l &= \frac{a^2-4a}3,\quad &\LR{\o+\l} = \frac{\LR{a-1}\LR{a-3}}3 \\ f(\l) &= \LR{\o+\l}^n,\quad &f'(\l) = n\LR{\o+\l}^{n-1} \\ f(0) &= \o, &f'(0) = n \\ \\ }$$ $$\eqalign{ M^n &= f(A) \\ &= f(0)\,I \;+\; \fracLR{f(\l)-f(0)}{\l}A \\ &= I \;+\; \fracLR{\LR{\o+\l}^n-\o}{\l}A \qquad \qquad \qquad \qquad \quad \\ \\ \lim_{\l\to 0}\,M^n &= f(0)\,I \;+\; f'(0)\;A \\ &= I \;+\; nA \\ \\ }$$ Another interesting limit $($assuming $a\ne 0)\,$ is $\,n\to\infty$ $$\eqalign{ &0\lt a\le\o \qiq -\o\le\l\lt 0 \qiq 0\le\LR{\o+\l}\lt\o \\\\ &\lim_{n\to\infty} f(\l) = \lim_{n\to\infty}\LR{\o+\l}^n = 0 \\ &\lim_{n\to\infty} M^n = I - \fracLR{\o}{\l}A \\ }$$

Answer 3

$ M = I + B = I + \begin{bmatrix} 1 \\ -2 \end{bmatrix} \begin{bmatrix} \alpha && \beta \end{bmatrix} $

where $\alpha = -\frac{1}{3} a^2 $ and $\beta = \frac{1}{3} (2 a - a^2) $

Simple analysis shows the eigenvalues of $B$ are $0$ with corresponding eigenvector $[- \beta, \alpha]^T$, and $\alpha - 2 \beta $ with corresponding eigenvector $[1, -2]^T$

Now we want to express $[1,1]^T$ as a linear combination of these two eigenvectors.

$[1,1]^T = c_1 [-\beta, \alpha]^T + c_2 [1, -2]^T $

Solving yields,

$c_1 = \dfrac{3}{\alpha - 2 \beta} , \hspace{40pt} c_2 = \dfrac{\alpha+\beta}{\alpha - 2 \beta} $

Hence,

$M^n [1, 1]^T = c_1 (1)^n [-\beta, \alpha]^T + c_2 (\lambda_2)^n [1, -2]^T $

where $\lambda_2 = 1 + \alpha - 2 \beta \lt 1 $

Therefore,

$\displaystyle \lim_{n \to \infty} M^n [1, 1]^T = c_1 [-\beta, \alpha]^T = \dfrac{3}{\alpha-2\beta} \begin{bmatrix} -\beta \\ \alpha \end{bmatrix} $

And this simplifies to

$\displaystyle \lim_{n \to \infty} M^n [1, 1]^T = \dfrac{3}{\frac{a}{3}(a - 4) } \begin{bmatrix} - \frac{a}{3} (2 - a) \\ -\frac{1}{3} a^2 \end{bmatrix} $

And this simplifies further to,

$\displaystyle \lim_{n \to \infty} M^n [1, 1]^T = 3 \begin{bmatrix} \frac{2 -a}{4 - a} \\ \frac{a}{4 - a} \end{bmatrix} $