0
$\begingroup$

Find $n$ for given square matrix $M$ and vectors $v,w$ in $$w=M^nv$$


Trial (updated)

(as vujazzman suggested)

Jordan normal form: $$ w = (A J^n A^{-1})v$$ $$ A^{-1}w = J^n A^{-1}v$$

After this solve $J_{i,i}^n$ for diagonal elements ($\lambda^n$) not zero or unity.

Problem: In trials with known $n$ no row was equal at left an right side for this equation. (edit: I missed a factor before result)


with numbers:

$$M=\begin{pmatrix} -6 & 0 & 1 & 1 \\ 0 & 5 & 1 & 1 \\ 1 & 0 & 4 & 0 \\ 1 & 1 & 2 & 3\end{pmatrix} $$ $$v= \begin{pmatrix}1 \\ 3 \\ 4 \\ 7 \end{pmatrix}$$ $$\text{just for testing } n=5$$

$$\rightarrow w=M^5 v = \begin{pmatrix}3069 \\ 39932 \\ 5908 \\ 23189 \end{pmatrix}$$

$$M=AJA^{-1}$$ $$A=\begin{pmatrix} -11.1983 & 0.1078 & 0.3311 & 0.0927 \\ -0.1876 & -0.3812 & -3.9066 & 2.2532 \\ 1.0992 & -0.0757 & 2.3579 & 0.0630 \\ 1 & 1 & 1 & 1\end{pmatrix}$$

$$J=\begin{pmatrix} -6.1875 & 0 & 0 & 0 \\ 0 & 2.5753 & 0 & 0 \\ 0 & 0 & 4.1404 & 0 \\ 0 & 0 & 0 & 5.4718\end{pmatrix}$$

$$A^{-1}=\begin{pmatrix} -0.0878 & -0.0009 & 0.0068 & 0.0096 \\ -0.0099 & -0.3327 & -0.8920 & 0.8068 \\ 0.039 & -0.0197 & 0.3788 & 0.0169 \\ 0.0587 & 0.3533 & 0.5064 & 0.1667\end{pmatrix}$$

$$\text{insert in } A^{-1}w = J^n A^{-1}v$$ $$\begin{pmatrix}-39.875883 \\ 121.33529 \\ 1963.52008 \\ 21144.0205 \end{pmatrix}=\begin{pmatrix} -6.1875 & 0 & 0 & 0 \\ 0 & 2.5753 & 0 & 0 \\ 0 & 0 & 4.1404 & 0 \\ 0 & 0 & 0 & 5.4718\end{pmatrix}^{n=5}\begin{pmatrix}0.0044 \\ 1.0712 \\ 1.6136 \\ 4.3108 \end{pmatrix}$$ now (just for testing) computed with $n=5$ $$\begin{pmatrix}-39.875883 \\ 121.33529 \\ 1963.52008 \\ 21144.0205 \end{pmatrix}=\begin{pmatrix}-39.875883 \\ 121.33529 \\ 1963.52008 \\ 21144.0205 \end{pmatrix} \text{ q.e.d.}$$

Now its working...


To be complete: computing of $n$ if not known $$21144.0205/4.3108=5.4718^n$$ $$\log_{5.4718}(4904.894799)=\log(4904.894799)/\log(5.4718)=n$$ $$\rightarrow n=5$$

$\endgroup$
  • $\begingroup$ @vujazzman and is there a correct version? It is only a post about what did not work. $\endgroup$ – J. Doe Oct 16 at 7:20
  • $\begingroup$ Can you give a specific example? It's unlcear what the problem is $\endgroup$ – vujazzman Oct 16 at 20:03
1
$\begingroup$

Lets first make a weak assumption on $M$, lets suppose it has an eigenvalue $\lambda$ which is not zero or a root of unity. In this case, $n$ can be determined (or determined not to exist), by taking the Jordan normal form of $M = AJA^{-1}$ and considering the resulting equation $A^{-1}w = J^n (A^{-1}v)$. There is a row of $J^n$ consisting of $\lambda^n$ in one entry and the rest zeros. Due to the conditions on $\lambda$, there will be at most one solution for $n$. If there is a solution, check it in the original equation. In this case $n$ is the unique solution. Otherwise, there is no solution.

If $M$ doesn't satisfy the condition, the situation is more complicated, but in any case you still want to first reduce the problem by taking the Jordan decomposition. Enumerating all what can happen is probably still possible, you essentially need to answer the original problem for $M$ a Jordan block with root of unity or zero eigenvalue.

$\endgroup$
  • $\begingroup$ Did some test case. For known $n$ the equation $J^n(A^{-1}v)-A^{-1}w =0$ vector with size of $M$. In test case that was not the case for any row. $M$ had positive eigenvalues (and some negative). $\endgroup$ – J. Doe Oct 16 at 11:15
  • $\begingroup$ The row is the last row of the jordan block for that eigenvalue. If you are taking a random example, for instance, then $M$ is diagonalizable. So you diagonalize and solve the equation for $n$ corresponding to any of the rows. $\endgroup$ – vujazzman Oct 16 at 19:22
  • $\begingroup$ After copy all that numbers from example I noticed they are equal. Before I computed the difference from left and right side. I missed the $1e-10$ factor before the result... Thank yo for the answer, sorry for the inconveniences $\endgroup$ – J. Doe Oct 16 at 20: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.