4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is $a$ a matrix ?? $\endgroup$ – Yves Daoust Mar 30 '19 at 16:24
  • $\begingroup$ @YvesDaoust No, it's a (n-1) vector. $\endgroup$ – Vim Mar 30 '19 at 16:24
  • $\begingroup$ It's much easier to compute $A^k$ if we have $$ \pmatrix{I&0\\a^T & \alpha} $$ for what that's worth $\endgroup$ – Omnomnomnom Mar 30 '19 at 16:26
  • $\begingroup$ 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). $\endgroup$ – Vim Mar 30 '19 at 16:28
  • 1
    $\begingroup$ Isn't $A$ a companion matrix? $\endgroup$ – Rodrigo de Azevedo Mar 30 '19 at 17:10
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Vim Mar 31 '19 at 6:42
  • $\begingroup$ 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. $\endgroup$ – Martin Argerami Mar 31 '19 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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