Linear Algebra Marathon & Questions (2 Viewers)

RenegadeMx · Nov 22, 2016

Re: First Year Linear Algebra Marathon

i swear some of the questions here arent even first year

Paradoxica · Nov 22, 2016

Re: First Year Linear Algebra Marathon

RenegadeMx said:
i swear some of the questions here arent even first year

amazing.

Drsoccerball · Nov 22, 2016

Re: First Year Linear Algebra Marathon

RenegadeMx said:
i swear none of the questions here are first year

ftfy.

seanieg89 · Nov 23, 2016

Re: First Year Linear Algebra Marathon

First year courses have different content at different universities, and lecturers who write exams for these courses are way less constrained by things like syllabi than the people who write HSC exams.

Think of this thread as a place to post questions accessible by a first year student (on the knowledge front), with any terminology that would not be standard in all first year courses clarified.

In this sense it is similar to the advanced mx2 marathon, just you are a little less handcuffed re: the methods you can use and a higher standard of rigour is expected. And as always for these threads, I think the ideal question is more demanding on the ingenuity/creativity/intuition front than on the knowledge front.

Paradoxica · Nov 23, 2016

Re: First Year Linear Algebra Marathon

seanieg89 said:
First year courses have different content at different universities, and lecturers who write exams for these courses are way less constrained by things like syllabi than the people who write HSC exams.

Think of this thread as a place to post questions accessible by a first year student (on the knowledge front), with any terminology that would not be standard in all first year courses clarified.

In this sense it is similar to the advanced mx2 marathon, just you are a little less handcuffed re: the methods you can use and a higher standard of rigour is expected. And as always for these threads, I think the ideal question is more demanding on the ingenuity/creativity/intuition front than on the knowledge front.

Amen

seanieg89 · Nov 30, 2016

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

He-Mann · Nov 30, 2016

Re: First Year Linear Algebra Marathon

InteGrand said:
$\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?

Paradoxica · Dec 3, 2016

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}$

leehuan · Dec 3, 2016

Re: First Year Linear Algebra Marathon

Paradoxica said:
$$\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.}$

InteGrand · Dec 3, 2016

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

leehuan · Dec 3, 2016

Re: First Year Linear Algebra Marathon

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

seanieg89 · Dec 4, 2016

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?

Linear Algebra Marathon & Questions (2 Viewers)

RenegadeMx

Kosovo is Serbian

Paradoxica

-insert title here-

Drsoccerball

Well-Known Member

seanieg89

Well-Known Member

Paradoxica

-insert title here-

seanieg89

Well-Known Member

He-Mann

Vexed?

Paradoxica

-insert title here-

leehuan

Well-Known Member

InteGrand

Well-Known Member

leehuan

Well-Known Member

seanieg89

Well-Known Member

Users Who Are Viewing This Thread (Users: 0, Guests: 2)