# The first element of a matrix power

Let $$A \in \Bbb R^{n \times n}$$ be the following block matrix:

$$A:= \begin{bmatrix} a^T & \alpha\\ I_{n-1} & 0_{n-1} \end{bmatrix}$$

where $$a, 0_{n-1} \in \Bbb R^{n-1}$$ are vectors and $$\alpha$$ is a scalar. Then, is there a closed form for

$$e_1^T A^k e_1,\quad k\in\Bbb N$$

i.e., the top left element of $$A^k$$?

By closed form, I mean something like the combination of sums ($$\sum$$) or products ($$\prod$$) or anything else that would make solving for $$k$$ the equation $$e_1^T A^k e_1= 1/2$$ easier. Such a $$k$$ is called the half life of an AR(p) process whose coefficients are the first row of $$A$$.

Explanation for the tag: This problem arises from computing the impulse response function, and therefore the half life, of a general AR process.

Edit: $$A$$ is diagonalisable, non singular, and has spectral radius < 1 for what it's worth. So one numerical way to solve the equation $$e_1^T A^k e_1= 1/2$$ I can think about is to first diagonalise it as $$A=QDQ^{-1}$$, then we can define for any real number $$k$$ the matrix power $$A^k$$ as $$A^k=QD^kQ^{-1}$$ And once we obtain $$Q$$, $$D$$ numerically, we can expect to get a polynomial in $$\lambda_{1,\cdots, n}^k$$ where $$\lambda$$ are eigenvalues of $$A$$, and thus is solvable by software.

• Is $a$ a matrix ?? – Yves Daoust Mar 30 '19 at 16:24
• @YvesDaoust No, it's a (n-1) vector. – Vim Mar 30 '19 at 16:24
• It's much easier to compute $A^k$ if we have $$\pmatrix{I&0\\a^T & \alpha}$$ for what that's worth – Omnomnomnom Mar 30 '19 at 16:26
• Yes that would be triangular. But i dont think it's possible to have such a nice form for the AR(p) structure (tried and failed). – Vim Mar 30 '19 at 16:28
• Isn't $A$ a companion matrix? – Rodrigo de Azevedo Mar 30 '19 at 17:10

If you are looking to implement a solution in software, you can do the following. You want $$e_1^TA^ke_1$$, which is the first entry of $$A^ke_1$$. If you write $$A=\begin{bmatrix} a_1&a_2&\cdots&a_n&\alpha \\ 1&0&0&\cdots&0\\ 0&1&0&\cdots&0\\ \vdots&\vdots&\ddots&\ddots&0\\ 0&0&\cdots&1&0 \end{bmatrix},$$ then $$Ax=\begin{bmatrix} \sum_{j=1}^na_jx_j+\alpha x_{n+1}\\ x_1\\ \vdots\\ x_n \end{bmatrix}.$$ So if we write $$z_k$$ for the first entry of $$A^ke_1$$ (and $$z_j=0$$ when $$j<0$$) we have the recursion $$z_{m}=\sum_{j=1}^{n} x_{j}z_{m-j}+\alpha z_{m-n-1}.$$ This recursion is very easy to implement in software. One could also attempt to solve the recursion explicitly, by looking at the characteristic polynomial (of the recursion).
• Thanks! Actually my main challenge isn't how to compute this value, but rather how to solve the equation $|e_1^T A^k e_1|=1/2$ for k. One nasty thing is that $k$ is continuous here ($k\in\Bbb R_+$), which is why I mentioned diagonalising $A$ first to make the potentially fractional power $A^k$ well defined. – Vim Mar 31 '19 at 6:42
• The "real power" thing will only work naturally if the eigenvalues of $A$ are positive. Do you have any condition that guarantees that? From the couple of simple examples I tried, non-positive and non-real eigenvalues pop up easily. – Martin Argerami Mar 31 '19 at 18:49