# Thread: Linear Algebra Marathon & Questions

1. ## Re: First Year Linear Algebra Marathon

Let p(n) be points in R^m defined recursively by p(n+1)=Ap(n), where A is a real mxm matrix.

1. Suppose that the eigenvalues of A all have modulus less than 1. What can you say about the limiting behaviour of the sequence p(n), for typical p(0)?

2. Suppose that at least one of the eigenvalues of A has modulus greater than 1. What can you say about the limiting behaviour of the sequence p(n), for typical p(0)?

2. ## Re: First Year Linear Algebra Marathon

Originally Posted by InteGrand
$\noindent Let d and n be positive integers and define f(0) = 2, f(d) = -1, and f(k) = 0 for k \neq 0,d. Let A be the n\times n matrix with ij entry f\left(|i-j|\right). Find in terms of d and n the solution \mathbf{x} = \begin{bmatrix}x_{1}\\x_{2}\\ \vdots \\x_{n}\end{bmatrix} to the linear system A\mathbf{x} = \mathbf{b}, where \mathbf{b} = \begin{bmatrix}f(1)\\ f(2) \\ \vdots \\ f(n)\end{bmatrix}.$
A is a real symmetric matrix with only 2's for the main diagonal and {-1, 0} for every other entry. I considered diagonalization but it leads me to finding the determinant of a monster.

Any hints or further guidance with or without Paradoxica's hint?

3. ## Re: First Year Linear Algebra Marathon

$\noindent Define a_0 = a, b_0 = b, c_0 = c, a_{n+1} = \frac{b_n+c_n}{2}, b_{n+1} = \frac{c_n+a_n}{2}, c_{n+1} = \frac{a_n+b_n}{2} \\ \text{Prove } \lim_{n \to \infty} a_n = \lim_{n \to \infty} b_n = \lim_{n \to \infty} c_n = \frac{a+b+c}{3}$

4. ## Re: First Year Linear Algebra Marathon

$\noindent Define a_0 = a, b_0 = b, c_0 = c, a_{n+1} = \frac{b_n+c_n}{2}, b_{n+1} = \frac{c_n+a_n}{2}, c_{n+1} = \frac{a_n+b_n}{2} \\ \text{Prove } \lim_{n \to \infty} a_n = \lim_{n \to \infty} b_n = \lim_{n \to \infty} c_n = \frac{a+b+c}{3}$
$\text{Let }\textbf{x}(k)=\begin{pmatrix}a_k\\b_k\\c_k \end{pmatrix}$

$\text{The system has been defined recursively with initial condition}\\ \textbf{x}(0)=\begin{pmatrix}a\\b\\c \end{pmatrix} \\ \text{RTP: } \lim_{k\to \infty}\textbf{x}(k)=\frac{a+b+c}{3} \begin{pmatrix}1\\1\\1\end{pmatrix}$

$\text{Due to the recursive definition, there exists some matrix }A\text{ such that}\\ \textbf{x}(k+1)=A\textbf{x}(k)\\ \text{Clearly, }A=\begin{pmatrix}0 & \frac12 & \frac12 \\ \frac12 & 0 & \frac12\\ \frac12 & \frac12 & 0\end{pmatrix}$

$\text{So due to the recursive definition, we have }\\ \lim_{k\to \infty} \textbf{x}(k) = \lim_{k\to \infty}A^k\textbf{x}(0)\\ \text{Hence, we need to compute }\lim_{k\to \infty}A^k$

$\text{It can be shown that the eigenvalues of }A\text{ are }-\frac12, -\frac12, 1\\ \text{with eigenvectors }\begin{pmatrix}-\frac{535}{748} \\ \frac{237}{14314} \\ \frac{1273}{1822}\end{pmatrix}, \begin{pmatrix}\frac{523}{1328} \\-\frac{7729}{9468}\\ \frac{935}{2213}\end{pmatrix}\text{ and }\begin{pmatrix}\frac{780}{1351} \\\frac{780}{1351}\\ \frac{780}{1351} \end{pmatrix}\text{ respectively.}$

$\text{Hence, }A\text{ can be expressed as }MDM^{-1}\\ \text{where } D=\begin{pmatrix}-\frac12 & 0 & 0\\ 0 & -\frac12 & 0\\ 0& 0& 1\end{pmatrix}\\ \text{and }M= \begin{pmatrix}-\frac{535}{748}&\frac{523}{1328} &\frac{780}{1351}\\ \frac{237}{14314} &-\frac{7729}{9468}&\frac{780}{1351}\\ \frac{1273}{1822}&\frac{935}{2213}&\frac{780}{1351}\end{pmatrix}$

$\text{Note that since }D\text{ is diagonal}\\ D^k=\begin{pmatrix}(-\frac12)^k&0&0\\0&(-\frac12)^k&0\\0&0&1^k\end{pmatrix} = \begin{pmatrix}(-\frac12)^k&0&0\\0&(-\frac12)^k&0\\0&0&1\end{pmatrix} \\ \text{Which implies }\lim_{k\to \infty}D^k=\begin{pmatrix}0&0&0\\0&0&0\\0&0&1 \end{pmatrix}$

$\text{So now using }A^k=\underbrace{(MDM^{-1})(MDM^{-1})\dots(MDM^{-1})}_{k\text{ terms}}=MD^kM^{-1}\\ \lim_{k\to \infty}A^k=\lim_{k\to \infty}MD^kM^{-1}\\ \text{which can be shown to equal }\begin{pmatrix}\frac13 & \frac13 & \frac13\\\frac13 & \frac13 & \frac13\\ \frac13 & \frac13 & \frac13 \end{pmatrix}$

$\text{Hence it can be verified that } \lim_{k\to \infty}\textbf{x}(k)=\lim_{k\to \infty}A^k\textbf{x}(0)=\frac{a+b+c}{3} \begin{pmatrix}1\\1\\1\end{pmatrix}\\ \text{and upon equating components, our result is achieved.}$

5. ## Re: First Year Linear Algebra Marathon

In fact, the matrix A is a doubly stochastic (in fact, symmetric) Markov matrix. By inspection it is the transition matrix of an irreducible Markov chain, and thus this chain (being irreducible and finite) has a unique stationary distribution. As it is doubly stochastic, this unique stationary distribution is the uniform distribution (1/3, 1/3, 1/3). It is also clear the period of the chain is 1, i.e. it is aperiodic (e.g. because state 1 can go to state 1 in two steps or three steps), so regardless of the initial distribution, we converge to the uniform distribution state vector. If the initial vector is (a, b, c), then since the state vector will have constant sum, we converge to ((a+b+c)/3, (a+b+c)/3, (a+b+c)/3) (this formula also clearly holding if the initial vector was the zero vector).

6. ## Re: First Year Linear Algebra Marathon

Oh true I didn't realise that this was a Markov matrix! Would've saved considerable MATLAB computations

7. ## Re: First Year Linear Algebra Marathon

Of course it is important that a student knows why some of these Markov chain facts are true, so here is a followup q:

Suppose you have a random sequence on a finite set A (your state space). The "randomness" is precisely that if the n-th term in this sequence is i, then the probability of the (n+1)-th term being j is given by f(i,j) where f: SxS -> [0,1] has to satisfy
$\sum_{j\in S} f(i,j)=1$
for the interpretation as a probability to make sense.

More generally, by $f_n(i,j)$, we denote the probability of the the n-th term in the sequence being j, given that the 0-th term is i.

1. If the nx1 column vector v denotes the respective probabilities of 0-th term in sequence being in each of the n possible states, find the corresponding vector for the first term in the sequence in terms of multiplication by a matrix. In this way we can associate a sequence of vectors to the random process governed by f.

2. Suppose that:

i) For each i and each j, we have $f_n(i,j)>0$ for some n.
ii) For each i, we have $f_n(i,i)>0$ for a collection of n with gcd 1.

Prove there is a unique vector w that the sequence of vectors introduced in (1.) converges to w for any choice of initial vector v.

3. Are conditions i) and ii) both required for this theorem to be true?

Page 2 of 2 First 12

There are currently 1 users browsing this thread. (0 members and 1 guests)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•